Что неправильно в алгоритме пятнашек ?

Question

[Skver0]

import pprint
pp = pprint.PrettyPrinter(indent=4)

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] + 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 moves(mat):
    """
    Returns a list of all possible moves
    """
    output = []
    m = eval(mat)
    i = 0
    while 0 not in m[i]: i += 1
    j = m[i].index(0)  #blank space (zero)

    if i > 0:
        m[i][j], m[i - 1][j] = m[i - 1][j], m[i][j]  #move up
        output.append(str(m))
        m[i][j], m[i - 1][j] = m[i - 1][j], m[i][j]

    if i < 3:
        m[i][j], m[i + 1][j] = m[i + 1][j], m[i][j]  #move down
        output.append(str(m))
        m[i][j], m[i + 1][j] = m[i + 1][j], m[i][j]

    if j > 0:
        m[i][j], m[i][j - 1] = m[i][j - 1], m[i][j]  #move left
        output.append(str(m))
        m[i][j], m[i][j - 1] = m[i][j - 1], m[i][j]

    if j < 3:
        m[i][j], m[i][j + 1] = m[i][j + 1], m[i][j]  #move right
        output.append(str(m))
        m[i][j], m[i][j + 1] = m[i][j + 1], m[i][j]

    return output


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: continue
            distance += abs((i - m[i][j] / 4)) + abs((j - m[i][j] % 4))
    return distance


if __name__ == '__main__':

    puzzle = str([[1, 2, 6, 3], [4, 9, 5, 7], [8, 13, 11, 15], [12, 14, 0, 10]])
    end = str([[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]])

    puzz_astar(puzzle, end)

с этими значениями работает без проблем

puzzle = str([[1, 2, 6, 3], [4, 9, 5, 7], [8, 13, 11, 15], [12, 14, 0, 10]])
end = str([[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]])

но я хочу чтоб выдача выглядела так

end = str([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 0]])

то есть чтобы 0 стоял в конце.

для простых входных данных алгоритм работает. решение в 7 ходов.

[[0, 1, 3, 4], [5, 2, 7, 8], [9, 6, 11, 12], [13, 10, 14, 15]]

а вот если дать сгенерированную но решаемую матрицу он висит...
например такую

[[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 11, 12], [13, 10, 14, 15]]

Answer 1

[Skver0]

уточню. сейчас алгоритм убирает пустую фишку влево вверх. а я хочу убрать ее вправо вниз.

все решение найдено. у меня для такой конфигурации пятнашек была полностью неправильно написана эвристика. возможно кому то пригодится...

def manhattan_distance(puzz, end):
    """
    Manhettan distance heuristic
    """
    m = eval(puzz)
    a = eval(end)
    lst = []
    result = 0

    for x in range(4):
        for y in range(4):
            if a[x][y] == 0:
                continue
            lst.append([[x, y], a[x][y]])

    for i in range(4):
        for j in range(4):
            if m[i][j] == 0:
                continue
            for s in lst:
                if s[1] == m[i][j]:
                    x = s[0][0]
                    y = s[0][1]

            result += abs(i - x) + abs(j - y)
    return result

Answer 2

[throughtheether]

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)

это очень плохо. Может быть, это сгодится для "олимпиадок", но не рекомендую вам привыкать так делать.

Comments

[Skver0]

да спасибо исправил. но все равно это не решило моего вопроса.
алгоритм ставит пустую фишку всегда в позицию [0, 0] а если поставить ее в другое место он "висит"

[Skver0]

спасибо за развернутый комментарий. эвристику я уже переписал заново, как я думаю, более правильно. остальные моменты я учту при доработке.

[throughtheether]

рад был помочь