Optimal,
Branch and
Bound, A*:
Contributors’
Slides
Содержание
2
Основные пункты
Метод ветвей и границ для поиска
оптимального пути
Улучшения метода ветвей и границ
Метод A*
Сравнение методов на разных задачах
Струянский О
3
Термины и
основные понятия
4
TERMS
Branch and bound – метод ветвей и границ
Dead end – тупик
Queue – очередь
Heuristic estimates – эвристические оценки
Depth first search – поиск в глубину
Admissible heuristic – допустимая
эвристическая оценка
Savostin Peter
5
Terms
Branch and bound – метод ветвей и границ
Strategy for finding the shortest path – стратегия
нахождения кратчайшего пути
Heuristic search algorithm – эвристический алгоритм
поиска
Accumulated path length – накопленная длина пути
Lengths are all non-negative – все длины –
неотрицательны
Put all extensions back on the queue – добавить все
расширения в очередь
Булгакова
6
Glossary
Admissible heuristic – допустимая эвристическая
оценка
Accumulated path length – суммарная длина пути
Estimated distance – предполагаемое расстояние
Мартиросян
7
Pathfidiig algorithms
Branch and bound
discard branches longer than current shortest path
Extended list
extend the shortest path unextended before
Admissible heuristic
extend the shortest actual + estimated distance
A* algorithm
combination of Admissible heuristic and A*
Елонов
8
Алгоритм с
оракулом
9
Oracle-based
algorithm
6
C
4
5
3
2.
3.
B
A
G
4
S
1.
E
5
3
D
We have some initial answer for the
shortest path
The answer must be checked to be
accepted
An obvious way is to check that all the
other paths are for sure longer
It is convenient to do this with a tree-like
diagram
S
Build the iiitial path to the
goal
3 A
Oi each step exteid the
D6
shortest path that cai be
exteided
G1
Stop, whei there are io more
1
paths that cai be exteided
aid keep smaller distaice
OK
thai the iiitial oie
Check the initial
answer
Кузьмин
NOT OK
S
3 A
D6
B
G 11
S
5
3 A 6
7 B D
1
1
C
G
1
1
5
B 9
9
A C
D E
1
2
15
10
Алгоритм с оракулом
Задан путь в графе, требуется определить, является ли он
кратчайшим.
S
S
A
B 5
3 A
D
11 G
Шрамов
7
11
B
D
A
C
G
D
11
9
12
C
E
9
13
11
Алгоритм ветвей и
границ
12
Braich aid Bouid
Flow
chart:
Iiitialize
queue
Цзян Лэй
Test frst
path
Exteid
frst
path
thei
sort
them
Метод ветвей и границ
Задание
очереди
Проверка
первого пути
Продолжение
первого пути
Сортировка
очереди
Рой
14
Метод ветвей и границ
1- Инициализировать очередь всех путей
Пока не найден путь, достигающий цели:
Проверить самый короткий путь в очереди,
достигает ли он цели
Продолжить самый короткий путь на 1 шаг
Струянский О
15
Метод ветвей и границ
0
1
3
3
7
B
8
11 D
Рой
A
S
2
5
4
6 D
7
11 G
B
A
9
9
5
6
9
C
10
D
12
15 E
16
Braich aid Bouid
Processiig fow:
S
3
7
B
11
C
Цзян Лэй
A
B
6
1
1
5
D
A
9
C
9
G
D
12
E
15
Braich aid Bouid
Queue of paths uider coisideratioi:
(S,0)
(S,A,3)(S,B,5)
(S,A,B,7)(S,A,D,6)(S,B,5)
(S,B,A,9)(S,B,C,9)(S,A,B,7)(S,A,D,6)
(S,A,D,G,11)(S,B,A,9)(S,B,C,9)(S,A,B,7)
Fiid result
(S,A,B,C,11)(S,A,D,G,11)(S,B,A,9)(S,B,C,9)
(S,B,A,D,12)(S,A,B,C,11)(S,A,D,G,11)(S,B,C,9)
(S,B,C,E,15)(S,B,A,D,12)(S,A,B,C,11)(S,A,D,G,11)
Цзян Лэй
Coifrm the
miiimum
Метод ветвей и границ
Инициализировать
очередь
Очередь
пуста?
C
4
да
Конец
нет
S
Изъять путь из очереди
Путь ведет
к цели?
нет
Продлить путь;
Отсортировать очередь
Асирян
5
3
B
да
SAB:7
SBA:9
SBC:9
SABC:11
SADG:11
SBAD:12
SB:5
SAD:6
SBA:9
SBC:9
SABC:11
SADG:11
SBAD:12
SBCE:15
SAB:7
SBC:9
SADG:11
SBAD:12
SBCE:15
G
4
A
Очередь
SAD:6
SAB:7
SBA:9
SBC:9
SABC:11
SADG:11
S:0
SA:3
SB:5
E
6
3
5
D
0 S
3 A
5 B
7 B
6 D 9 A
9 C
11 C
11 G 12 D
15 E
19
Braich & bouid
wasted momeits
0
S
Would it make
seise to exteid
path with already
3
used letter
aid
bigger
distance?
Popov V
5
A
6
7
B
9
9
B
D
A
C
C
G
D
E
11
11
12
15
20
Алгоритм ветвей и
границ + список
пройденных вершин
21
Braich & bouid
+ exteided list
It is ai improvement of previous algorithm by
dead horse priiciple:
As sooi as we fgure out that a path goes to
a particular place cai’t possibly be the
wiiiiig path, we get rid of it, aid doi’t
bother exteidiig it.
It makes this algorithm more efcieit:
38 exteitiois iistead of 835 ii a case of big
tree!
Popov V
22
Exteisioi List
Extension list (список расширений) – способ
сокращения числа расширений путей.
Идея: запоминать вершины, пути через
которых были расширены. Если в будущем мы
встретим путь, оканчивающийся на вершину из
этого списка, мы не будем его расширять.
Сальников
23
Метод ветвей и границ
со списком раскрытых
вершин
Задание
очереди
Проверка
первого пути
Продолжение первого пути,
если его конечная вершина
уже не в списке раскрытых
Сортировка
очереди
Рой
24
Метод ветвей и границ
со списком раскрытых
вершин
0
S
1
3
3
7
B
A
6 D
11 G
B
5
4
7
Рой
2
A
9
5
6
9
C
8
15 E
25
Braich & bouid
+ exteided list
0
Exteidiig the
shortest path aid
rememberiig
already exteided
letters
S
3
B
(a lot of work if tree is
big)
Popov V
A
6
7
We save work!
5
exteide
d with 5
<7
B
9
9
D
A
C
G
exteide
d
with 3 <
9
E
11
15
26
Braich & bouid +
exteided list
1
S
1
3 A
7 B
Exteided List
1. S
2. S, A
3. S, A, B
4. S, A, B, D
5. S, A, B, D, C
Попов К.
5
2
3
2
6 D
4
A 9
6
11 G
Shortest
B
3
5
C 9
7
E 15
1.
2.
3.
4.
5.
6.
7.
SA = 3, SB = 5, mii = SA
SAB = 7, SAD = 6, mii = SB
SBA = 9, SBC = 9, mii =SAD
SADG = 11, mii = SAB
B ii exteided, mii = SBA
A ii exteided, mii = SBC
SBCE = 15, stop
27
МВГ + список
пройденных вершин
Инициализировать
очередь
Очередь
пуста?
C
4
да
Конец
нет
S
Изъять путь из очереди
Путь ведет
к цели?
нет
Продлить путь, если
еще не был продлен;
Отсортировать очередь
Асирян
5
3
B
да
SB:5
SAD:6
SAB:7
SBA:9
SBC:9
SADG:11
SBCE:15
SAB:7
SBA:9
SBC:9
SADG:11
SBC:9
SADG:11
G
4
A
Очередь
S:0
SA:3
SB:5
SAD:6
SAB:7
SBA:9
SBC:9
SADG:11
E
6
3
5
D
0 S
3 A
7 B
5 B
6 D 9 A
11 G
9 C
15 E
28
Алгоритм ветвей и
границ + допустимая
эвристика
29
Admissible Heuristic
Admissible heuristic (допустимая эвристика) –
способ сокращения числа расширений путей.
Идея: основывать выбор того, из какой точки
продолжать путь, не только на расстоянии от
начала пути до этой точки, но и на нижней
грани оценки длины пути от этой точки к
целевой.
Сальников
30
Airliie Distaice
- the distance that the crow would fly to get from one
place to another
6
C
4
5
B
4
S
3
A
E
In general, it is the best to be in
place that is airline-close to the goal
G
But it can get us into trouble
(example: E and G)
Anyway, it’s an important heuristic
that is efficiently used in queue
algorithms
5
3
Кузьмин
D
31
МВГ + допустимая
эвристика
Инициализировать
очередь
Очередь
пуста?
C
4
да
S
Изъять путь из очереди
нет
Продлить путь;
Отсортировать очередь
Асирян
5
Конец
нет
Путь ведет
к цели?
6
3
да
SAD:11
S:0
SA:10+
SB:11
SADG:11
SB:11
SAD:11
SAB:13
SAB:13
SBA:16+
SBC:16+
7+
6
B
G
7+
4
A
Очередь
E
3
D
5
0 S
10+ A
13 B
11 B
11 D 16+ A 16+ C
11 G
32
Алгоритм A*
33
A* search algorithm
A* search algorithm – is an algorithm for finding the
shortest path in a graph.
The idea is to combine admissible heuristic and
extended list in branch and bound method.
At each iteration A* selects the path that minimizes:
F(n) = G(n) + H(n), where:
G(n) is the cost of the path from the start node to n.
H(n) is a heuristic that estimates the cost of the
cheapest path from n to the goal.
Savostin Peter
34
Алгоритм поиска А*
A* = метод ветвей и границ (branch and bound)
+ список раскрытых вершин (extended list)
+ допустимая оценка (admissible heuristic)
Вместо сортировки вершин – поиск вершины
с минимальной суммой накопленного
расстояния (accumulated distance) и оценкой
расстояния до цели.
Галкина
Algorithm A*
Branch &
Bound
+
Initialize
queue
Extended
List
+
Admissible
Heuristic
Test
shortest
path
=
A*
Extend frst
path if not
already
extended
Sort by
accumulated
distance +
admissible
heuristic
Булгакова
36
Проблема
алгоритма A*
37
Ограничения алгоритма A*
Нужно осторожно выбирать оценку.
В случае евклидовых расстояний (например, поиск пути на
карте) достаточно допустимой оценки:
H(x, G) <= D(x, G)
Но в других ситуациях могу понадобиться более жесткие
ограничения:
|H(x, G) – H(y, G)| <= D(x, y) - согласованная оценка
H(x, y) – предполагаемое расстояние
D(x, y) – реальное расстояние
G – целевая вершина
Шрамов
38
Допустимая vs.
согласованная
эвристическая оценка
H – эвристическая оценка расстояния, D –
реальное расстояние между вершинами, х, у –
любые вершины, G – целевая вершина.
H называется допустимой (admissible), если:
H называется согласованной (consistent), если:
Галкина
А* работает не всегда
Вершина С будет раскрыта только в правой ветви,
поэтому кратчайший путь не будет найден.
Галкина
Admissible heuristic problem
S
100
1
A
1
S
C
1
B
10
0
100
G
1+10 A
0=10
1
B 1+1=
2+0=
C
2
C 11+0
1
=11
0
G 111+
0=11
1
Из-за extended list мы не будем искать дальше в ветке S, A, C, так как уже
искали продолжение C в ветке S, B, C, G = > получаем неверный ответ
Мартиросян
41
1.
2.
3.
4.
5.
Problem with admissible
heuristic (A* algorithm)
100
1
A
S
C
1
B
0
1+100=101
1
1
10
0
100
G
S
1+0=1
1
A
2+0=2
B
4
11+0=11
C
C
SA = 101, SB = 1, mii = SB, ext = [S]
5
SBC = 11, mii = SBC, ext = [S, B]
SBCG = 111, mii = SA, ext = [S, B, C] Decisioi SAC = 2, mii = SAC, ext = [S, B, C, A] Coisisteit heuristic:
C ii exteided, stop
• Admissible:
Попов К.
2
3
111+0=111
G
Not shortest
H(x,g)<=D(x,g)
• Coisisteit:
|H(x,g)-H(y,g)|<=D(x,y)
42
Сравнение алгоритмов
43
Algorithms’ Comparisoi
Algorithm
Case 1
Case 2
(#extende (#extende
d)
d)
Braich & Bouid
835
57
B&B + exteided list
38
35
B&B + admissible
heuristic
70
6
A*
27
6
So it all depeids oi the iature of the space that you're tryiig to explore.
Попов К.
44
Вопросы
45
Q&A
In which cases does the admissible heuristic
algorithm work ?
What is consistency condition?
Мартиросян
46
Questiois
What is consistency?
What algorithm is computationally better:
extended list or admissible heuristic?
Елонов
47
QUESTIONS
Do we need sorting in A*?
Is extended list is better than admissible heuristic in any
case?
Can we use any heuristic estimates in pathfinding
problems?
Savostin Peter
48
QUESTIONS
Do we need sorting in A*?
No, we don’t need to sort accumulated distance plus
admissible heuristic, we can keep tracking what’s the
minimum.
Is extended list is better than admissible heuristic in any
case?
No, in some graphs this statement is false.
Can we use any heuristic estimates in pathfinding problems?
No, in some cases we need stronger condition, as for
example, consistency.
Savostin Peter
49
ВСЕМ БОЛЬШОЕ
СПАСИБО!
50
