Переполнение стека с помощью A *, чтобы решить 8-головоломку - PullRequest
Новая
       29

Переполнение стека с помощью A *, чтобы решить 8-головоломку

0 голосов
/ 30 апреля 2018

Цель этого кода - решить N-головоломку (см. Здесь: https://en.wikipedia.org/wiki/15_puzzle)

Функция предназначена для получения зашифрованного списка целых чисел от 0 до (N ** 2-1) и возврата списка ходов, чтобы достичь решенного состояния, где ход - это список координат x и y. (Например, [2, 2] означает перемещение нижней правой части в головоломке 3х3). Я знаю, что только некоторые платы разрешимы, и доска, на которой я тестирую свой код, определенно разрешима.

Я пытался реализовать поиск A *, но, похоже, что-то не так с ним, так как для многих плат я получаю переполнение стека. Доска, которую я использую в приведенном ниже коде, приводит к переполнению стека, но эта доска вернет правильную последовательность ходов примерно через 20 секунд (что кажется слишком длинным): [7, 2, 8, 1, 5, 6, 0, 3, 4]

Основная идея состоит в том, чтобы начать со списка путей ходов, а затем найти путь с наименьшей стоимостью, который не был расширен (стоимость = текущая длина пути + оставшееся расстояние в Манхэттене), и расширить этот путь и продолжать движение пока решение не найдено.

Я понимаю, что для 8-головоломок брутфорс может быть таким же, как если бы не более жизнеспособным, чем А *, но я бы хотел, чтобы мой код мог функционировать и для 15-головоломок.

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

Я действительно новичок в программировании, так есть ли в моем коде простая ошибка, или у меня есть фундаментальное неправильное понимание алгоритма? Я довольно уверен, что мои вспомогательные функции работают так, как задумано, и что проблема заключается в функции решения. Любой совет будет оценен 

import math
import copy

#Making move on board
def makeMove(board, move):
    L = int(math.sqrt(len(board)))
    copyBoard = copy.copy(board)
    zI = copyBoard.index(L**2-1)
    #Calculating move index in 1D list based off of x/y coords
    moveI = move[0] + L*move[1]
    copyBoard[zI], copyBoard[moveI] = copyBoard[moveI], copyBoard[zI]
    return copyBoard

#Function to find the board based off of the given path
def makeMoves(board, path):
    newBoard = copy.deepcopy(board)
    for move in path:
        newBoard = makeMove(newBoard, move)
    return newBoard

def mDist(board): #Calculating manhattan distance of board
    totalDist = 0
    L = int(math.sqrt(len(board)))
    for i in range(int(L**2)):
        #Finding sum of differences between x and y coordinates
        cX, cY = i % L, i // L
        fX, fY = board[i] % L, board[i] // L
        dX, dY = abs(cX-fX), abs(cY - fY)
        totalDist += (dX+dY)
    return totalDist

def nDisp(board):
    score = 0
    for i in range(len(board)):
        if i != board[i]:
            score += 1
    return score

def getLegalMoves(board):
    finalMoves = []
    L = int(math.sqrt(len(board)))
    #Finding the coordinates of the blank
    zI = board.index(L**2-1)
    zX, zY = zI % L, zI // L
    #Finding possible moves from that blank
    testMoves = [[zX+1, zY], [zX-1, zY], [zX, zY+1], [zX, zY-1]]
    for move in testMoves:
        if isLegalMove(move, L):
            finalMoves.append(move)
    return finalMoves

def isLegalMove(move, L):
    #Move is legal if on board
    for i in move:
        if i < 0 or i >= L:
            return False
    return True

def solve(board):
    queue = [] #List of paths, where a path is a sequence of moves
    for move in getLegalMoves(board): #Getting initial paths
        queue.append([move])
    def search(queue, board):
        bestScore = math.inf
        bestPath = None
        for path in queue:
            #Score based off of A* = estimated distance to finish + current distance
            dist = mDist(makeMoves(board, path))
            score = dist + len(path)
            #Checking if solved
            if dist == 0:
                return path
            #Finding best path that has not already been expanded
            if score < bestScore:
                bestScore = score
                bestPath = path
        #Removing the path since it is going to be expanded
        queue.remove(bestPath)
        bestPathBoard = makeMoves(board, bestPath)
        #Expanding the path
        for move in getLegalMoves(bestPathBoard):
            newPath = bestPath + [move]
            queue.append(newPath)
        #Recursing
        return search(queue, board)
    return search(queue, board)

print(solve([8, 0, 1, 6, 7, 3, 2, 5, 4]))
...