Астар против IDAstar производительность

Question

Кажется, я не могу понять причину, по которой A * превосходит IDA* в большинстве случаев. Мой профессор сказал, что причина не в том, что ранние (ближе к корню) узлы повторно исследуются как возвратные пути IDA* после достижения f-предела, а скорее потому, что A * поддерживает открытый и закрытый список, так что данное состояние не исследуется несколько раз по дереву, тогда как в IDA*, если в дереве есть несколько путей к данному узлу, оно будет исследовать эти узлы снова и снова. У меня такой же вопрос с IDA* т.е. Возможно ли реализовать IDA* с открытым и закрытым списком, и если нет, то почему?

Answer 1

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

Если вы измените IDA * для использования открытого и закрытого списка, вы, вероятно, вернетесь к BFS-подобному процессу, поэтому по сути вернетесь к A *.