distance += abs((i - m[i][j] / 4)) + abs((i - m[i][j] % 4))
Если вы вычисляете "манхэттенское" расстояние между текущим и идеальным положениями плитки, то почему под знаками модуля в каждом случае используется один лишь индекс
i? Я полагаю, корректнее будет исправить:
distance += abs((i - m[i][j] / 4)) + abs((j - m[i][j] % 4))
UPD.
алгоритм ставит пустую фишку всегда в позицию [0, 0] а если поставить ее в другое место он "висит"
Предполагаю, это из-за вашего подсчета расстояния. Вы нулевое значение (т.е. положение пустой кдетки) игнорируете по какой-то причине.
Если исправить текст так, то указанный вами пример ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 11, 12], [13, 10, 14, 15]]) нормально обсчитывается
исправления
def puzz_astar(start, end):
"""
A* algorithm
"""
front = [[heuristic_2(start), start]]
print(front)
expanded = []
expanded_nodes = 0
while front:
i = 0
for j in range(1, len(front)):
if front[i][0] > front[j][0]:
i = j
path = front[i]
front = front[:i] + front[i + 1:]
endnode = path[-1]
if endnode == end:
break
if endnode in expanded: continue
for k in moves(endnode):
if k in expanded: continue
newpath = [path[0] + abs(heuristic_2(k) - heuristic_2(endnode))] + path[1:] + [k]
front.append(newpath)
expanded.append(endnode)
expanded_nodes += 1
print "Expanded nodes:", expanded_nodes
print "Solution:"
pp.pprint(path)
def heuristic_2(puzz):
"""
Manhattan distance
"""
distance = 0
m = eval(puzz)
for i in range(4):
for j in range(4):
if m[i][j] == 0: distance+=3-i+3-j
distance += abs((i - m[i][j] / 4)) + abs((j - m[i][j] % 4))
return distance
Пара комментариев - во-первых, это ad-hoc решение (для случая, когда в конечном положении пустая клетка расположена в конце). Во-вторых, по-хорошему, расстояние надо измерять от одной ноды до другой (то есть, передавать в функцию heuristic_2 текущую ноду и конечную и суммировать, какая плитка на сколько позиций сдвинута). В-третьих,
m = eval(puzz)
это очень плохо. Может быть, это сгодится для "олимпиадок", но не рекомендую вам привыкать так делать.
