Реализация алгоритма A*

Эта статья является продолжением моего введения в алгоритм A*. В ней я показал, как реализуются поиск в ширину, алгоритм Дейкстры, жадный поиск по наилучшему первому совпадению и A*. Я стремился как можно больше упростить объяснение.

Поиск по графам — это семейство схожих алгоритмов. Существует множество вариаций алгоритов и их реализаций. Относитесь к коду этой статьи как к отправной точке, а не окончательной версии алгоритма, подходящей ко всем ситуациям.
 

1. Реализация на Python

Ниже я объясню бо́льшую часть кода. Файл implementation.py несколько шире. В коде используется Python 3, поэтому если вы используете Python 2, то нужно будет поменять вызов super() и функцию print на аналоги из Python 2.