Разгоняем А*
Модераторы: Sanja, Максим Кич
Разгоняем А*
Можно ли ускорить поиск с помощью алгоритма A* ?
Можно если применить более качественную эвристическую функцию.
Рассмотрим поиск пути в лабиринте, где любой узел S задается координатами (x, y) и перемещение разрешено только по горизонтали или вертикали.
Обозначим:
s0 - начальный узел,
g - целевой узел,
h - эвристическая функция.
Определим эвристическую функцию h для произвольного узла s как:
h(s) = |s.x - g.x| + |s.y - g.y|, где g - целевой узел.
Данная эвристическая функция позволяет алгоритму A* находить оптимальное решение. Но h(s) недооценивает стоимость пути, если приходиться обходить препятствия. Как следствие при поиске открывается большее количество узлов.
Попробуем определить лучшую эвристическую функцию. Для этого случайным образом выберем в лабиринте несколько узлов (назовем их ориентирами). Для каждого ориентира выполним расчет длины кратчайшего пути до каждого узла лабиринта и сохраним полученное значение в узле. После обработки всех ориентиров, для каждого узла лабиринта будет известно кратчайшее расстояние до каждого ориентира.
Обозначим:
m - ориентирный узел,
d(s, m) - кратчайшее расстояние от узла s до ориентирного узла m.
Определим функцию dg для произвольного узла s как:
dg(s, m) = |d(s, m) - d(g, m)|, где m - ориентирный узел, g - целевой узел.
Определим новую эвристическую функцию h-new для произвольного узла s как:
h-new(s) = max{h(s), dg(s, m1), ... , dg(s, mN)}, где m1, ... , mN - ориентирные узлы.
Качество эвристической функции h-new(s) зависит от выбора ориентирных узлов. Имеет смысл располагать ориентирные узлы по периметру лабиринта.
Посмотрим как это работает на практике:
..............
.2xxxxxx....3.
.01....x.G....
..xxxxxx......
..............
x - непроходимый пункт
0 - начальный пункт
G - целевой пункт
3 - ориентирный пункт
Необходимо определить какой пункт предпочтительнее 1 или 2. Стандартная эвристическая функция даст нам оценку: h(1) = 7, h(2) = 9. Из чего следует что выбрать надо пункт 1.
Рассчитаем h-new(1) и h-new(2):
dg(1, 3) = |d(1, 3) - d(G, 3)| = |15 - 4| = 11
dg(2, 3) = |d(2, 3) - d(G, 3)| = |13 - 4| = 9
h-new(1) = max{h(1), dg(1, 3)} = max{7, 11} = 11
h-new(2) = max{h(2), dg(2, 3)} = max{9, 9} = 9
Видно, что эвристическая функция h-new(s) дает лучшую оценку, чем h(s).
Более подробно вопрос рассмотрен здесь:
http://research.microsoft.com/research/ ... ort&id=986
Можно если применить более качественную эвристическую функцию.
Рассмотрим поиск пути в лабиринте, где любой узел S задается координатами (x, y) и перемещение разрешено только по горизонтали или вертикали.
Обозначим:
s0 - начальный узел,
g - целевой узел,
h - эвристическая функция.
Определим эвристическую функцию h для произвольного узла s как:
h(s) = |s.x - g.x| + |s.y - g.y|, где g - целевой узел.
Данная эвристическая функция позволяет алгоритму A* находить оптимальное решение. Но h(s) недооценивает стоимость пути, если приходиться обходить препятствия. Как следствие при поиске открывается большее количество узлов.
Попробуем определить лучшую эвристическую функцию. Для этого случайным образом выберем в лабиринте несколько узлов (назовем их ориентирами). Для каждого ориентира выполним расчет длины кратчайшего пути до каждого узла лабиринта и сохраним полученное значение в узле. После обработки всех ориентиров, для каждого узла лабиринта будет известно кратчайшее расстояние до каждого ориентира.
Обозначим:
m - ориентирный узел,
d(s, m) - кратчайшее расстояние от узла s до ориентирного узла m.
Определим функцию dg для произвольного узла s как:
dg(s, m) = |d(s, m) - d(g, m)|, где m - ориентирный узел, g - целевой узел.
Определим новую эвристическую функцию h-new для произвольного узла s как:
h-new(s) = max{h(s), dg(s, m1), ... , dg(s, mN)}, где m1, ... , mN - ориентирные узлы.
Качество эвристической функции h-new(s) зависит от выбора ориентирных узлов. Имеет смысл располагать ориентирные узлы по периметру лабиринта.
Посмотрим как это работает на практике:
..............
.2xxxxxx....3.
.01....x.G....
..xxxxxx......
..............
x - непроходимый пункт
0 - начальный пункт
G - целевой пункт
3 - ориентирный пункт
Необходимо определить какой пункт предпочтительнее 1 или 2. Стандартная эвристическая функция даст нам оценку: h(1) = 7, h(2) = 9. Из чего следует что выбрать надо пункт 1.
Рассчитаем h-new(1) и h-new(2):
dg(1, 3) = |d(1, 3) - d(G, 3)| = |15 - 4| = 11
dg(2, 3) = |d(2, 3) - d(G, 3)| = |13 - 4| = 9
h-new(1) = max{h(1), dg(1, 3)} = max{7, 11} = 11
h-new(2) = max{h(2), dg(2, 3)} = max{9, 9} = 9
Видно, что эвристическая функция h-new(s) дает лучшую оценку, чем h(s).
Более подробно вопрос рассмотрен здесь:
http://research.microsoft.com/research/ ... ort&id=986
-
- Сообщения: 59
- Зарегистрирован: 11 мар 2007, 13:21
- Откуда: Беларусь, Минск
- Контактная информация:
Епт, многа букав, ниасилил.
А вообще есть очень хороший совет: оптимизируйте то, что работает медленнее всего и ДЕЙСТВИТЕЛЬНО замедляет программу. Поэтому меня и прикалывают попытки зафигачить какой-нибудь новомодный оптимизированный алгоритм в рогалик. Хотя потом можно лихо понтануццо где-нибудь. Типа "я представил лабиринт в виде графа и сча юзаю Дейкстру для поиска пути и все это счастье работает за NlogN". Вопрос: нахера? Или вам надо, чтобы оно летало на первом Pentium'e?
А вообще есть очень хороший совет: оптимизируйте то, что работает медленнее всего и ДЕЙСТВИТЕЛЬНО замедляет программу. Поэтому меня и прикалывают попытки зафигачить какой-нибудь новомодный оптимизированный алгоритм в рогалик. Хотя потом можно лихо понтануццо где-нибудь. Типа "я представил лабиринт в виде графа и сча юзаю Дейкстру для поиска пути и все это счастье работает за NlogN". Вопрос: нахера? Или вам надо, чтобы оно летало на первом Pentium'e?
- Максим Кич
- Администратор
- Сообщения: 1642
- Зарегистрирован: 03 дек 2006, 20:17
- Откуда: Витебск, Беларусь
- Контактная информация:
Оптимизация действительно имеет смысл только тогда, когда в ней появляется необходимость. К примеру лось, скачущий по Брезенхему, вполне нормально пашет, когда он один. А пересчитай полсотни таких лосей на кадр хотя бы при 50 fps и уже как-то кажется, что не такое это резвое животное. И надо как-то чистить алгоритм, чтобы не делать лишних итераций.v0l0sat1y писал(а):Епт, многа букав, ниасилил.
А вообще есть очень хороший совет: оптимизируйте то, что работает медленнее всего и ДЕЙСТВИТЕЛЬНО замедляет программу. Поэтому меня и прикалывают попытки зафигачить какой-нибудь новомодный оптимизированный алгоритм в рогалик. Хотя потом можно лихо понтануццо где-нибудь. Типа "я представил лабиринт в виде графа и сча юзаю Дейкстру для поиска пути и все это счастье работает за NlogN". Вопрос: нахера? Или вам надо, чтобы оно летало на первом Pentium'e?
Скорость нахождения пути в рогаликах вообще особенно не должна смущать. Тут интереснее будет найти какие-нибудь весовые коэффициенты, чтобы монстры могли более адекватно оценивать ситуацию и бежать не туда, где ближе, а туда где больше шансов сделать своё грязное дело.
С другой стороны, нерациональные решения имеют кумулятивный эффект и в момент икс, когда вдруг окажется, что всё это тормозит на двухъядерном монстре, будет весьма проблематично распутывать клубок из собственных недочётов, чтобы выдрать необходимую скорость.
А уровень в виде графа в принципе полезно представлять. Но не все могут себе это позволить
Dump the screen? [y/n]
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 37 гостей