A * алгоритм открытый список выбор

Question

Я понимаю, что в алгоритме A * при выполнении следующего шага шаг с следующей самой низкой прогнозируемой стоимостью следует выбирать из открытого списка или границы, но когда есть несколько наименьших шагов, все с одинаковыми прогнозируемая стоимость есть ли предпочтение, для которого нужно выбрать?

Я думаю, что последнее на первом этапе может работать лучше, но я не уверен, есть ли лучший способ выбрать следующий шаг, когда есть несколько сопоставимых затрат.

Answer 1

В соответствии с A * все этапы с равной оценочной стоимостью (стоимостью от начала плюс эвристические) в равной степени заслуживают изучения.

Дело в том, что без дальнейшей эвристики мне трудно сделать выбор; или, скорее, это зависит от того, что вы хотите.

В стандартном f(x) = g(x) + h(x) случае, если у вас нет другой эвристики или информации, есть 2 основные стратегии:

• вы выбираете самый последний шаг x, в надежде, что она соответствует хорошей трассе (и может помочь в проблемах с памятью): если это последнее, это означает, что он получил относительно небольшое обновление стоимости по отношению к остальным;
• вы выбираете шаг x с наименьшим h, то есть для которого относительный вклад стоимости знания является наивысшим по отношению к неизвестной стоимости (для чего нацелен взвешенный A *).

Для этой второй стратегии, кроме раздувания эвристики, вам просто нужно заказать шаги/узлы парой (f, h) вместо просто f. Это, однако, не гарантирует, что у вас нет связи:

* 
/\ 
| | 
\/
+ 

В конце концов, вам нужно выбрать один, например, самый последний (или только один, что ваша реализация доходностей очереди приоритетов) ,

Обратите внимание, что если вы выберете x с максимальным количеством h, вы приблизитесь к поведению широты, на которое ссылался Амит.

Answer 2

Я думаю, что вы ищете bounded relaxation (AKA A*-epsilon).

Идея создания f(v) = g(v) + (1+eps)h(v). При очень маленьком значении eps он не изменяет оптимальность алгоритма, а способствует «глубине» над «широтой» в поиске и часто увеличивает скорость поиска.

Аналогичным образом, вы можете использовать ширину, очень близкую к нулю, но отрицательное значение eps - но я не знаком с любым использованием предпочтительной ширины здесь.

Answer 3

Теоретически, ни один из них не лучший выбор, потому что ваша фитнес-функция должна моделировать, которая лучше, чем другая, используя всю доступную информацию.

Выберите, какой из них проще всего запрограммировать, самый последний или ваш любимый ith премьер в списке. Это не имеет значения.