Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло.

алгоритмах

Поиск с возвращением. Общая схема (алгоритм).
Задача о ферзях.
Оценка сложности. Метод

Монте-Карло.
Другие способы программирования.

Метод ветвей и границ. Общая схема. Задача коммивояжера (ЗК).
Метод ветвей

и границ. ЗК (продолжение). Приближенные решения.
Динамическое программирование. Идея и общая схема. Оптимальное умножение матриц.
Динамическое программирование. Оптимальные БДП. Хорошие БДП. Аналогии.

10.02.2014

Поиск с возвращением

Алгоритм ЯПД.
Непересекающиеся подмножества.
Обходы графа. Алгоритм Борувки для МОД.
МОД как приближение

в ЗК. Двусвязные компоненты (применение обхода в глубину).
ПВГ в орграфах. Топологическая сортировка. Сильно связные компоненты.
Кратчайшие пути в графе (1).
Кратчайшие пути в графе (2).

10.02.2014

Поиск с возвращением

хеширования.
Задание 2.
Перебор с возвращением (Backtracking).
Задание 3.
Метод ветвей

и границ
Задание 4.
Динамическое программирование.
 
Курсовая работа (КР): Алгоритмы на графах.

10.02.2014

Поиск с возвращением

и псевдокоде.
10.02.2014
Поиск с возвращением

с возвратом =
= Backtracking

Пример.
Поиск пути в лабиринте

(x, y, Направление)
(3,1,с)
(3,2,с)
(4,2,в)
(4,3,с)
(4,2,ю)
(4,1,ю)
(5,1,в)
(4,1,з)
(3,2,з)
(2,2,з)
(1,2,з)
…
1 2

3 4 5 x

y
5
4
3
2
1

(x,y) – целевая клетка,
Направление – в ц.к.

– конечно, но, вообще говоря, заранее не известно
ai∈ Ai ;

Ai – конечное линейно упорядоченное множество
Исчерпываем все элементы множества A1×A2×A3×…×Ai
i = 0 → ()
i = 1; S1 ⊂ A1; a1 ∈ S1; () → (a1)
i = 2; S2 ⊂ A2; a2 ∈ S2; (a1) → (a1, a2)
…
i = k; Sk ⊂ Ak; ak ∈ Sk; (a1,…, ak-1) → (a1,…, ak-1,ak)
При Sk = ∅ backtrack и новый выбор ak-1 ∈ Sk-1;

a3
Выбор a4
Выбор a5
Выбор a6

0;
while (k>0) { //пока не все решения найдены
while

(Sk != ∅) {
// продвижение вперед
ak = элемент из Sk; //выбор очередного элемента из Sk
Sk = Sk − {ak};
count ++;
if ((a1,…, ak-1,ak) – решение) { /*фиксировать решение*/}
else {
// переход к следующему уровню
k ++;
вычислить Sk;
}
} // end while продвижения вперед
k --; // backtrack
} //все решения найдены; count – число обследованных узлов

максимальное число не атакующих друг друга ферзей.
n = 4

a2, a3, a4)
ai – номер горизонтали на i-ой

вертикали

атакуют друг друга:
i = k - ферзи на одной вертикали
ai

= ak - ферзи на одной горизонтали
⏐ai - ak⏐ = ⏐i - k⏐ - ферзи на одной диагонали

Наращивание (продолжение) решения
(a1, a2, …, ak-1)∙ak = (a1, a2, …, ak-1, ak )

вертикалей.
Множество Sk явно не формируется,
но, выбирая очередного кандидата αk

∈ Ak, проверяем α k ∈ Sk

Используется sk - нижняя граница в Ak,
т.о. кандидаты в Sk выбираются из множества
(sk, sk+1, …, n) , т.е. Sk ⊂ (sk, sk+1, …, n).

Обсудить альтернативу.

1)

// ферзь не может быть поставлен в строку s столбца

k
{ bool Flag = true;
uns i = 1;
while ((i // Flag='ферзи [1..i) не атакуют поле '
// атакует ли ферзь из i-го столбца поле ?}
Flag = !( (a[i]==s) || (abs(a[i]-s)== k-i) );
i++;
} //end - while
return (!Flag);
} // end noQueen

s[k],
начиная с текущего s[k];
если такового

нет, то s[k]=n+1
*/
while ((s[k]<=n) && noQueen (s[k],k)) s[k]++;

элемент множества Sk неопробованных (допустимых) значений
*/
uns count = 0; //

счетчик обследованных // узлов дерева поиска
uns countS = 0; // счетчик найденых решений
a[1] = 1; s[1] = 1;
uns k = 1;

s[k]++;
// найти следующее наименьшее значение s[k]
while ((s[k]

s[k]++;
count++;
if (k==n) {countS++; …} //решение найдено - фиксировать !
else {// переход к следующей вертикали
k++;
s[k]= 1;
//найти следующее наименьшее значение s[k],
while ((s[k]<=n) && noQueen (s[k],k)) s[k]++;
}
}
k--; // backtrack
}

3 5








3 5 2 4 1

3 5








4 2 5 3 1

3 5








5 3 1 4 2

Отсечение и склеивание ветвей

элемент множества Sk //неопробованных (допустимых) значений
uns count = 1; //

счетчик обследованных узлов
uns countS = 0; // счетчик найденых решений
uns n_div_2 = n/2;
a[1] = 2; s[1] = 3;
uns k = 2; s[2] = 4;
while (k>0){
while ( ((k>1) && (s[k]<=n)) || ((k==1) && (s[1]<=(n_div_2))) )
{ a[k]= s[k];
…
}

каждом столбце один nn ≈ 1,7*107
+ В каждой строке

один n! ≈ 4,0*104
На каждой диагонали не более одного 2056

Усовершенствования (вращения и отражения) 801

и я :
1 :: 2 4 1 3
всего

вершин = 4
количество ферзей = 5
р е ш е н и я :
1 :: 2 4 1 3 5
2 :: 2 5 3 1 4
всего вершин = 11
количество ферзей = 6
р е ш е н и я :
1 :: 2 4 6 1 3 5
2 :: 3 6 2 5 1 4
всего вершин = 54

количество ферзей = 7
р е ш е н и я :
1 :: 2 4 1 7 5 3 6
2 :: 2 4 6 1 3 5 7
3 :: 2 5 1 4 7 3 6
4 :: 2 5 3 1 7 4 6
5 :: 2 5 7 4 1 3 6
6 :: 2 6 3 7 4 1 5
7 :: 2 7 5 3 1 6 4
8 :: 3 1 6 2 5 7 4
9 :: 3 1 6 4 2 7 5
10 :: 3 5 7 2 4 6 1
11 :: 3 6 2 5 1 4 7
12 :: 3 7 2 4 6 1 5
13 :: 3 7 4 1 5 2 6
всего вершин = 164

и я :
1 :: 2 4 6

8 3 1 7 5
2 :: 2 5 7 1 3 8 6 4
3 :: 2 5 7 4 1 8 6 3
4 :: 2 6 1 7 4 8 3 5
5 :: 2 6 8 3 1 4 7 5
6 :: 2 7 3 6 8 5 1 4
7 :: 2 7 5 8 1 4 6 3
8 :: 2 8 6 1 3 5 7 4
9 :: 3 1 7 5 8 2 4 6
10 :: 3 5 2 8 1 7 4 6
11 :: 3 5 2 8 6 4 7 1
12 :: 3 5 7 1 4 2 8 6
13 :: 3 5 8 4 1 7 2 6
14 :: 3 6 2 5 8 1 7 4
15 :: 3 6 2 7 1 4 8 5
16 :: 3 6 2 7 5 1 8 4
17 :: 3 6 4 1 8 5 7 2
18 :: 3 6 4 2 8 5 7 1
19 :: 3 6 8 1 4 7 5 2
20 :: 3 6 8 1 5 7 2 4
21 :: 3 6 8 2 4 1 7 5

22 :: 3 7 2 8 5 1 4 6
23 :: 3 7 2 8 6 4 1 5
24 :: 3 8 4 7 1 6 2 5
25 :: 4 1 5 8 2 7 3 6
26 :: 4 1 5 8 6 3 7 2
27 :: 4 2 5 8 6 1 3 7
28 :: 4 2 7 3 6 8 1 5
29 :: 4 2 7 3 6 8 5 1
30 :: 4 2 7 5 1 8 6 3
31 :: 4 2 8 5 7 1 3 6
32 :: 4 2 8 6 1 3 5 7
33 :: 4 6 1 5 2 8 3 7
34 :: 4 6 8 2 7 1 3 5
35 :: 4 6 8 3 1 7 5 2
36 :: 4 7 1 8 5 2 6 3
37 :: 4 7 3 8 2 5 1 6
38 :: 4 7 5 2 6 1 3 8
39 :: 4 7 5 3 1 6 8 2
40 :: 4 8 1 3 6 2 7 5
41 :: 4 8 1 5 7 2 6 3
42 :: 4 8 5 3 1 7 2 6
всего вершин = 801

и я :
1 :: 2 4 1 7

9 6 3 5 8
2 :: 2 4 7 1 3 9 6 8 5
3 :: 2 4 8 3 9 6 1 5 7
4 :: 2 4 9 7 3 1 6 8 5
5 :: 2 4 9 7 5 3 1 6 8
6 :: 2 5 7 1 3 8 6 4 9
7 :: 2 5 7 4 1 3 9 6 8
8 :: 2 5 7 9 3 6 4 1 8
9 :: 2 5 7 9 4 8 1 3 6
10 :: 2 5 8 1 3 6 9 7 4
11 :: 2 5 8 1 9 6 3 7 4
12 :: 2 5 8 6 9 3 1 4 7
13 :: 2 5 8 6 9 3 1 7 4
14 :: 2 5 9 4 1 8 6 3 7
15 :: 2 6 1 3 7 9 4 8 5
16 :: 2 6 1 7 4 8 3 5 9
17 :: 2 6 1 7 5 3 9 4 8
18 :: 2 6 1 9 5 8 4 7 3
19 :: 2 6 3 1 8 4 9 7 5
20 :: 2 6 9 3 5 8 4 1 7
21 :: 2 7 5 1 9 4 6 8 3
22 :: 2 7 5 8 1 4 6 3 9
23 :: 2 7 9 6 3 1 4 8 5
24 :: 2 8 1 4 7 9 6 3 5
25 :: 2 8 5 3 9 6 4 1 7
26 :: 2 8 6 9 3 1 4 7 5
27 :: 2 9 5 3 8 4 7 1 6
28 :: 2 9 6 3 5 8 1 4 7
29 :: 2 9 6 3 7 4 1 8 5
30 :: 2 9 6 4 7 1 3 5 8
31 :: 3 1 4 7 9 2 5 8 6
32 :: 3 1 6 8 5 2 4 9 7
33 :: 3 1 7 2 8 6 4 9 5

34 :: 3 1 7 5 8 2 4 6 9
35 :: 3 1 8 4 9 7 5 2 6
36 :: 3 1 9 7 5 2 8 6 4
37 :: 3 5 2 8 1 4 7 9 6
38 :: 3 5 2 8 1 7 4 6 9
39 :: 3 5 7 1 4 2 8 6 9
40 :: 3 5 8 2 9 6 1 7 4
41 :: 3 5 8 2 9 7 1 4 6
42 :: 3 5 9 2 4 7 1 8 6
43 :: 3 5 9 4 1 7 2 6 8
44 :: 3 6 2 7 1 4 8 5 9
45 :: 3 6 2 9 5 1 8 4 7
46 :: 3 6 8 1 4 7 5 2 9
47 :: 3 6 8 1 5 9 2 4 7
48 :: 3 6 8 2 4 9 7 5 1
49 :: 3 6 8 5 1 9 7 2 4
50 :: 3 6 8 5 2 9 7 4 1
51 :: 3 6 9 1 8 4 2 7 5
52 :: 3 6 9 2 5 7 4 1 8
53 :: 3 6 9 2 8 1 4 7 5
54 :: 3 6 9 5 8 1 4 2 7
55 :: 3 6 9 7 1 4 2 5 8
56 :: 3 6 9 7 2 4 8 1 5
57 :: 3 6 9 7 4 1 8 2 5
58 :: 3 7 2 4 8 1 5 9 6
59 :: 3 7 2 8 5 9 1 6 4
60 :: 3 7 2 8 6 4 1 5 9
61 :: 3 7 4 2 9 5 1 8 6
62 :: 3 7 4 2 9 6 1 5 8
63 :: 3 7 4 8 5 9 1 6 2
64 :: 3 7 9 1 5 2 8 6 4
65 :: 3 7 9 4 2 5 8 6 1
66 :: 3 8 2 4 9 7 5 1 6
67 :: 3 8 4 7 9 2 5 1 6
…………

…
90 :: 4 2 9 5 1 8 6 3 7
91 :: 4 6 1 5 2 8 3 7 9
92 :: 4 6 1 9 5 8 2 7 3
93 :: 4 6 1 9 7 3 8 2 5
94 :: 4 6 3 9 2 5 8 1 7
95 :: 4 6 3 9 2 8 5 7 1
96 :: 4 6 3 9 7 1 8 2 5
97 :: 4 6 8 2 5 1 9 7 3
98 :: 4 6 8 2 5 7 9 1 3
99 :: 4 6 8 2 7 1 3 5 9
100 :: 4 6 8 3 1 7 5 2 9
101 :: 4 6 9 3 1 8 2 5 7
102 :: 4 7 1 3 9 6 8 5 2
103 :: 4 7 1 6 9 2 8 5 3
104 :: 4 7 1 8 5 2 9 3 6
105 :: 4 7 3 6 9 1 8 5 2
106 :: 4 7 3 8 2 5 9 6 1
107 :: 4 7 3 8 6 1 9 2 5
108 :: 4 7 3 8 6 2 9 5 1
109 :: 4 7 5 2 9 1 3 8 6
110 :: 4 7 5 2 9 1 6 8 3
111 :: 4 7 5 2 9 6 8 3 1
112 :: 4 7 9 2 5 8 1 3 6
113 :: 4 7 9 2 6 1 3 5 8
114 :: 4 7 9 6 3 1 8 5 2
115 :: 4 8 1 5 7 2 6 3 9
116 :: 4 8 5 3 1 6 2 9 7
117 :: 4 8 5 3 1 7 2 6 9
118 :: 4 9 3 6 2 7 5 1 8
119 :: 4 9 5 3 1 6 8 2 7
120 :: 4 9 5 3 1 7 2 8 6
121 :: 4 9 5 8 1 3 6 2 7
всего вершин = 2857

мощность множества Ai
В лучшем случае

≈ Const
и тогда число узлов дерева ≈ Сn

точек

(количество веток)





2+2*3+2*3*4=32
2+2*2+2*2*2=14
2+2*2+2*2*3=18
2+2*3+2*3*2=20
2+2*3+2*3*1=14

(32+14+18)/3 = 64/3=21.3≈21
(32+14+18+20+14)/5 = 98/5=19.6 ≈ 20

Sk случайный с вероятностью 1/mk.
При mk = 0 испытание заканчивается.

























Выбор

a1: m1=⏐S1⏐

Выбор a2 : m2=⏐S2⏐

Выбор a3 : m3=⏐S3⏐

Выбор a4 : m4=⏐S4⏐

Выбор a5 : m5=⏐S5⏐

Выбор a6 : m6=⏐S6⏐

Конец !

m1m2m3 + … + m1m2…mL
Математическое ожидание
E(V) = число узлов

в дереве (отличных от корня)
Напоминание: для случайной величины x с исходами x1, x2,…, xk и вероятностями p1, p2,…, pk
математическое ожидание есть

дереве
1) функция на дереве T (не случайная)
где ν

- число братьев x, включая самого x
(т.е. число сыновей узла отец(x) )
Пусть путь от корня к узлу x есть v1, v2, …, vj , тогда
μ(x) = μ(vj) = νj× μ(vj-1) = νj × νj-1 × μ(vj-2) = … =
= νj × νj-1 × … × ν1 × μ(v1) = νj × νj-1 × … × ν1

μ(d) = μ(e) = μ(f) = 2*3=6,
μ(g)= μ(h)= 4, μ(i)=

μ(j)= 12, μ(k)= μ(l)= μ(m)= μ(n)= 24,
μ(o)= 6, μ(p)= μ(q)= 8, μ(r) = μ(s) = μ(t) = 12

пройден при испытании
I(x) =
0, если узел x не пройден при

испытании
Случайное событие = «узел x пройден»,
а I(x) − случайная величина ∈{0,1}

Вероятность дойти до узла x = vj есть
(1/m1) × (1/m2) × … × (1/mj)

в дереве

число испытаний
for (i = 1; i

S1 = А1; m1 = ⏐S1⏐;
Sum = 0; Prod = 1;
while (mk ≠ 0) {
{ //продвижение вперед
Prod* = mk;
Sum+ = Prod;
ak = случайный выбор очередного элемента из Sk;
k ++;
вычислить Sk и mk;
}
SV := SV + Sum;
} // end - for
V = SV/ M;

div 2; all := 0;
for iExp:=1 to nExp

do
begin { очередное испытание }
m_k := n_div_2 - 1; num := Random ( m_k ) + 1;
a[1] := 1+num; k := 2; prod := m_k; sum := prod;
FormSk ( k, m_k, S_k );
while m_k<>0 do
begin
prod := prod*m_k; sum := sum + prod;
num := Random ( m_k ) + 1; a[k] := S_k[num];
k := k + 1; FormSk ( k, m_k, S_k );
end {while};
all := all + sum
end {for};
v := all/nExp
end { MonteCarlo };

Nat0; var S_k: pos );
{ формирует "множество" (вектор) S_k

возможных ходов и
его мощность m_k; если S_k пусто, то m_k=0 }
var s: Nat;
begin
m_k := 0;
for s:=1 to n do
if not NoQueen( k, s) then
begin { можно ставить }
m_k := m_k + 1;
S_k[m_k] := s
end;
end {FormSk};

backtrack (sequence a, int k);
// a = (a1, a2, …,ak-1)

– частичное решение

(a1, a2, …,ak-1) – частичное решение
{
if (a – решение)

{фиксировать a;}
else {
вычислить Sk;
for (∀b ∈ Sk ) backtrack ( postfix (a, b), k+1 );
}
} // end - backtrack

/*Старт:*/ k = 1; a = Create; backtrack (a, k);

вычислить Sk;
Lk: if Sk = ∅ then goto Lk-1;

ak = очередной элемент из Sk;
Sk := Sk − {ak};

k++) CODEk;
CODE1;
CODE2;
…
…
CODEk;
…
CODEn;
фиксировать решение (a1,

a2, …,an);
goto Ln;
L0: // конец – все решения найдены

1965 году Джон Флетчер [1].
Существует ровно 2339 различных укладок

пентамино в прямоугольник 6×10, не считая поворотов и отражений целого прямоугольника, но считая повороты и отражения его частей

(иногда внутри прямоугольника образуется симметричная комбинация фигур, поворачивая которую, можно получить дополнительные решения; для прямоугольника 3×20, приведённого на рисунке, второе решение можно получить поворотом блока из 7 фигур, или, иначе говоря, если поменять местами четыре фигуры, крайние слева, и одну крайнюю справа, см.предыдущий слайд).

368 решений,
3×20 — всего 2 решения.

John G. Fletcher (1965).

"A program to solve the pentomino problem by the recursive use of macros". Communications of the ACM 8, 621–623.

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ