human after all
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 = []
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