В чем смысл алгоритма IDA * vs A *

Question

Я не понимаю, как IDA* экономит пространство памяти. Как я понимаю IDA* is A* с итерационным углублением.

В чем разница между объемом памяти A* использует vs IDA*.

Не было бы последней итерации IDA* вести себя точно так же, как A* и использовать тот же объем памяти. Когда я отслеживаю IDA*, я понимаю, что он также должен помнить приоритетную очередь узлов, которые ниже порога f(n).

Я понимаю, что первый поиск ID-Глубина помогает глубине первого поиска, позволяя ему делать ширину сначала, как поиск, а не запоминать каждый узел. Но я думал, что A* уже ведет себя как глубина, так как в ней игнорируются некоторые поддеревья на этом пути. Как итеративно углубление делает использование меньше памяти?

Еще один вопрос: поиск по глубине с итерационным углублением позволяет найти кратчайший путь, заставляя его вести себя сначала по ширине. Но A* уже возвращает оптимальный кратчайший путь (учитывая, что эвристика допустима). Как итеративное углубление помогает. Я чувствую, что последняя итерация IDA * идентична A*.

Answer 1

В IDA*, в отличие от A*, вам не нужно сохранять набор ориентировочных узлов, которые вы намерены посетить, поэтому потребление памяти предназначено только для локальных переменных рекурсивной функции.

Хотя этот алгоритм ниже на потребление памяти, у него есть свои недостатки:

В отличие от *, IDA * не использует динамическое программирование и поэтому часто заканчивается изучение тех же узлов, много раз. (IDA* In Wiki)

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

Вот демо памяти, необходимой в каждом алгоритме:

В алгоритме A* все узлы и окружающие их узлы должны быть включены в «необходимость посещают ", а в IDA* вы получаете следующие узлы« лениво », когда вы достигаете своего узла предварительного просмотра, поэтому вам не нужно включать его в дополнительный набор.

Как уже упоминалось в комментариях, IDA* is basically just IDDFS with heuristics: