Какие улучшения можно внести в алгоритм AnyTime Weighted A *?

Question

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

Взвешенный A* аналогичен A * с одним различием в функции f:

(где g - стоимость пути до узла, а h - эвристика до конца пути до достижения цели)

Original = f(node) = g(node) + h(node)

Weighted = f(node) = (1-w)g(node) +h(node)

Мой алгоритм в любое время запускает Weighted A * с уменьшением веса от 1 до 0,5, пока не достигнет ограничения по времени.

Моя проблема в том, что большую часть времени занимает много времени, пока он не достигнетрешение, и если ему дается что-то вроде 10 секунд, оно обычно не находит решения, в то время как другие алгоритмы, такие как пучок в любое время, находят его за 0,0001 секунды.

Есть идеи, что делать?

Answer 1

На вашем месте я бы выбросил неограниченную эвристику.Допустимая эвристика намного лучше, поскольку при заданном значении веса для решения, которое вы нашли, вы можете сказать, что оно не более 1 / веса, умноженного на длину оптимального решения.

Большая проблема при реализации A* Производные это структуры данных.Когда я реализовал двунаправленный поиск, просто переключившись со списков массивов на комбинацию очередей с увеличенным хешем и списков массивов по требованию, сократил стоимость времени выполнения на три порядка - буквально.

Основная проблема заключается в том, что большинство статей дают только псевдокод для алгоритма, использующего логику множеств - вы сами должны выяснить, как представлять множества в вашем коде.Не бойтесь использовать несколько ADT для одного списка, т.е. вашего открытого списка.Я не уверен на 100% в Anytime Weighted A *, я сделал другие производные, такие как Anytime Dynamic A * и Anytime Repairing A *, но не AWA *.

Другая проблема заключается в том, что когда вы устанавливаете слишком низкое значение g, иногда может потребоваться гораздо больше времени, чтобы найти какое-либо решение, чем если бы оно было более высоким.Распространенной ловушкой является забывание проверять закрытый список на наличие дублирующих состояний, что приводит к циклу (бесконечному, если ваше значение g уменьшается до 0).Я бы попробовал начать с чего-то значительно выше 0, если вы получаете быстрые результаты с помощью поиска луча.

Некоторый псевдокод, вероятно, поможет здесь!В любом случае, это всего лишь мои мысли по этому поводу, вы, возможно, уже решили это - если это так хорошо для вас:)

Answer 2

Поиск луча не завершен, так как он сокращает неблагоприятные состояния, тогда как поиск A * завершен.В зависимости от того, какую проблему вы решаете, если неполнота не мешает вам найти решение (как правило, существует много правильных путей от источника до места назначения), тогда перейдите к поиску Beam, в противном случае оставайтесь с AWA *.Тем не менее, вы всегда можете запустить оба параллельно, если есть достаточно аппаратных ресурсов.