Search:
Optimal,
Branch and
Bound, A*
Михайлишин А.В.
Содержание
1) Эвристические методы решения
2) Алгоритм проверки ответа (the Oracle checking
algorithm)
3) Метод ветвей и границ (branch and bound)
4) + список пройденных вершин (+ extended list)
5) + допустимая эвристика (+ admissible
heuristic)
6) Алгоритм A* и его применимость
Эвристические алгоритмы
Эвристический алгоритм (эвристика) — подход к
решению задачи не являющийся гарантированно
точным или оптимальным, но достаточным в рамках
данной задачи
В задаче поиска путей в графе-карте в качестве
расстояния между вершинами можно взять
расстояние между ними по прямой (as the crow flies,
airline distance).
The Oracle checking algorithm
If you want to solve a problem,
the easiest way is, usually, ask
somebody who knows the
answer.
Алгоритм проверки некоторого
пути заключается в переборе
всех путей с отбросом тех,
чья длина больше.
0
3
7
11
B
C
S
5
A
6
11
B
D
G
9
12
A
D
9
15
C
A
Branch and bound
✔
Инициализация очереди
Проверка первого пути
из очереди
Получен
ответ
×
Добавление в очередь
всех путей, полученных
из первого добавлением
одной вершины и
сортировка очереди
Список пройденных вершин
Keep track of the things that have been extended and not
extend them again.
В методе ветвей и границ для поиска пути в графе не
надо расширять пути, которые оканчиваются в
вершине для которой уже известно кратчайшее
расстояние.
Admissible heuristic
Тот же метод ветвей и
границ, но в качестве
длины пути следует
рассматривать уже
пройденный путь +
эвристическая оценка
для пути, который еще
осталось пройти.
0
3 + 7+ = 10+
7 + 6 = 13
S
5 + 6 = 11
A
B
B
D
9 + 7+
= 16+
A
6+5
= 11
C
9 + 7+
= 16+
G
11 + 0 = 11
A*
✔
Инициализация очереди
Проверка кратчайшего
пути из очереди
Получен
ответ
×
Расширение кратчайшего
пути, если никакой другой
путь, оканчивающийся в
этой вершине не был
расширен, и их
добавление в очередь
1) Очередь с приоритетом
2) Критерий для сортировки: длина пути + оценка длины оставшегося
пути
Применимость методов
1) Admissible heuristic: H(x, G) ≤ D(x, G) (admissible)
2) A*: | H(x, G) - H(y, G) | ≤ D(x, y) (consistency)
Сравнение методов
Количество добавленных в очередь путей
Случай 1
Случай 2
Branch and bound
835
57
Branch and bound +
extended list
38
35
Branch and bound +
admissible heuristic
70
6
A*
27
6
It almost always depends on the problem itself. If you change the problem, you may
get a different result.
Спасибо за внимание!