Алгоритм A*

Является эристическим (информированным)  алгоритмом поиск в пространстве вариантов . На каждом шагу алгоритм учитывает и пройденный путь и эвристическую функцию (оценку до цели).

На эвристическую функцию накладывается два ограничения:

1. Она не должна переоценивать стоимость пути

2. Она должна быть монотонной

Хорошее наглядное описание работы алгоритма можно найти здесь:

https://www.redblobgames.com/pathfinding/a-star/introduction.html

Алгоритм IDA* 

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