У нас есть школьный проект, где у нас есть игровая доска 8х8 с кусочками. Цель состоит в том, чтобы получить любой кусок в любой квадрат противоположного заднего ряда. Части могут двигаться только вперед, но в любом направлении вперед (вперед-влево, вперед или вперед-вправо).
Мы смогли представить доску в виде ориентированного ациклического графа, и с помощью различных правил игры мы также смогли установить вес на каждом ребре. Короче говоря, мы находим путь, с каждой частью как возможное начало, к любому из квадратов заднего ряда, чтобы найти путь наименьшего сопротивления от любой части до конца. Кроме того, большинство сопротивления будут встречены около финиша.
Однако наша программа тратит много времени именно на это. Мы полагаем, что это связано с тем, что многие пути очень похожи по весу, особенно если учесть, что любой возможный шаг приведет к победе (поскольку двигаться можно только вперед, а все квадраты заднего ряда являются пунктами назначения). На этой доске нет никаких препятствий, только края, которые весят тяжелее, поэтому у нас остается много открытых узлов, которые все «хорошо выглядят».
Наша эвристическая функция очень проста:
movement_cost = # movement cost here #
def heuristic(node):
return node.cost + node.distanceToFinish * movement_cost
Где node.cost - сумма весов пройденных ребер, плюс movement_cost умноженное на число пройденных ребер.
Существует ли алгоритм, который будет более эффективным, чем A *, для обработки случаев, когда у вас есть несколько источников и несколько пунктов назначения? Плата никогда не будет больше, чем 8x8, поэтому, возможно, приветствуются и космические алгоритмы.
РЕДАКТИРОВАТЬ Мы думали о поиске пути от финиша до фрагментов, но это добавляет много сложностей эвристической функции, поскольку теперь мы должны отслеживать каждый фрагмент, а не просто отслеживать, как далеко мы из последней строки.