Comments 11
Рассказывать алгоритм на графах не через графы — довольно спорный подход. Даже если и удастся так что-то объяснить "через школьную арифметику", то обучающийся в лучшем случае научится просто самостоятельно писать А* для задач, полностью аналогичных примеру. Немного в сторону — и будут большие проблемы. В качестве примеров "отхода в сторону":
- появление направленных ребер (как в статье — с крыши на землю спрыгнуть можно, обратно — нет)
- появление ячеек с разной проходимостью (по песку идти медленнее, чем по асфальту)
- оптимизация по другому параметру (не длина пути, а время в дороге/количество топлива и т.д.)
- в конце концов, просто задача не связанная с перемещением в пространстве. Для многих игрушек АИ оппонента вполне можно написать через А*, где ребра графа — действия АИ, а узлы — состояния агента либо всей игры.
Эта статья дает намного более фундаментальное понимание, что такое поиск на графе вообще, что такое А* в частности, как он работает и с чем его едят. И если и не дает готовых решений проблем выше, то по крайней мере очень хорошо показывает направление, куда копать. А в случае объяснения на пальцах без графов "через школьную арифметики" у меня большие сомнения, что все будет так просто. Более того, есть ощущение, что как минимум часть из тех проблем покажутся вообще нерелевантными для А*.
Впрочем, буду рад если поделитесь все таки ссылкой. Может там и правда хорошее объяснение.
В первую очередь оказался полезным сам алгоритм построения алгоритма.
Я как-то интуитивно забраковывал простейшую версию алгоритма и никогда не думал в её сторону. Но если рассматривать решение каждой конеретной проблемы алгоритма отдельно, то они вполне решаются. Ну кроме части за пределами 3-х измерений. До этого я бы сам не додумался, как до части алгоритма поиска пути.
Алгоритм отрубает варианты, когда ты повторно выходишь в ту клетку, где уже был.
Следовательно можно перебрать все варианты, отбрасывая их когда стоимость начинает превышать стоимость уже найденного пути.
Правда это при условии, что цена прохода клетки не отрицательная.
А* учитывает не только эвристическое расстояние до цели, но и текущую длину пути. Так что как только пройденная часть "длинного обхода аппендикса" станет длиннее, чем путь "шаг в сторону и потом по прямой" — алгоритм переключится на рассмотрение и расширение последнего.
А* гарантированно найдет кратчайший путь. За исключением разве что ситуаций, когда выбранная эвристика оценки расстояния — какая-то неадекватная (скажем, работающая "наоборот" и возвращающая высокие значения для коротких расстояний и низкие для длинных). Но если следовать требованиям А* при выборе эвристики (а именно: эвристика может недооценивать длину пути, но не должна переоценивать), то алгоритм в самом худшем случае выродится в поиск в ширину. Но найденный путь по-прежнему будет кратчайшим.
Простое объяснение алгоритмов поиска пути и A*