Python:N Puzzle (8-Puzzle) Solver Heruistics:如何迭代？

Question

我编写了一系列函数来尝试解决 N 难题/8 难题。

我对自己处理拼图的能力感到非常满意，但在如何迭代和找到最佳路径方面苦苦挣扎。我的技能也不是 OOP，所以功能很简单。

这个想法显然是为了减少 heruistic 距离并将所有棋子放置在他们想要的位置。

我已经阅读了很多关于这个主题的其他问题，但它们通常更高级并且更专注于 OOP。

当我尝试遍历时，没有好的 Action 。我不确定如何执行 A* 算法。

from math import sqrt, fabs
import copy as cp

# Trial puzzle
puzzle1 = [
    [3,5,4],
    [2,1,0],
    [6,7,8]]

# This function is used minimise typing later
def starpiece(piece):
    '''Checks the input of a *arg and returns either tuple'''
    if piece == ():
        return 0
    elif isinstance(piece[0], (str, int)) == True:
        return piece[0]
    elif isinstance(piece[0], (tuple, list)) and len(piece[0]) == 2:
        return piece[0]

# This function creates the goal puzzle layout
def goal(puzzle):
    '''Input a nested list and output an goal list'''
    n = len(puzzle) * len(puzzle)
    goal = [x for x in range(1,n)]
    goal.append(0)
    nested_goal = [goal[i:i+len(puzzle)] for i in range(0, len(goal), len(puzzle))]
    return nested_goal

# This fuction gives either the coordinates (as a tuple) of a piece in the puzzle
# or the piece in the puzzle at give coordinates 
def search(puzzle, *piece):
    '''Input a puzzle and piece value and output a tuple of coordinates. 
    If no piece is selected 0 is chosen by default. If coordinates are 
    entered the piece value at those coordinates are outputed'''
    piece = starpiece(piece)
    if isinstance(piece, (tuple, list)) == True:
        return puzzle[piece[0]][piece[1]]
    for slice1, sublist in enumerate(puzzle):
        for slice2, item in enumerate(sublist):
            if puzzle[slice1][slice2] == piece:
                x, y = slice1, slice2
    return (x, y)  

# This function gives the neighbours of a piece at a given position as a list of coordinates
def neighbours(puzzle, *piece):
    '''Input a position (as a tuple) or piece and output a list 
    of adjacent neighbours. Default are the neighbours to 0'''
    length = len(puzzle) - 1
    return_list = []
    piece = starpiece(piece)
    if isinstance(piece, tuple) != True:
        piece = search(puzzle, piece)
    if (piece[0] - 1) >= 0:
        x_minus = (piece[0] - 1)
        return_list.append((x_minus, piece[1]))
    if (piece[0] + 1) <= length:
        x_plus = (piece[0] + 1)
        return_list.append((x_plus, piece[1]))
    if (piece[1] - 1) >= 0:
        y_minus = (piece[1] - 1)
        return_list.append((piece[0], y_minus))
    if (piece[1] + 1) <= length:
        y_plus = (piece[1] + 1)
        return_list.append((piece[0], y_plus))
    return return_list

# This function swaps piece values of adjacent cells 
def swap(puzzle, cell1, *cell2):
    '''Moves two cells, if adjacent a swap occurs. Default value for cell2 is 0.
    Input either a cell value or cell cooridinates''' 
    cell2 = starpiece(cell2)
    if isinstance(cell1, (str, int)) == True:
        cell1 = search(puzzle, cell1)    
    if isinstance(cell2, (str, int)) == True:
        cell2 = search(puzzle, cell2) 
    puzzleSwap = cp.deepcopy(puzzle)
    if cell1 == cell2:
        print('Warning: no swap occured as both cell values were {}'.format(search(puzzle,cell1)))
        return puzzleSwap
    elif cell1 in neighbours(puzzleSwap, cell2):
        puzzleSwap[cell1[0]][cell1[1]], puzzleSwap[cell2[0]][cell2[1]] = puzzleSwap[cell2[0]][cell2[1]], puzzleSwap[cell1[0]][cell1[1]]
        return puzzleSwap
    else:
        print('''Warning: no swap occured as cells aren't adjacent''')
        return puzzleSwap

# This function gives true if a piece is in it's correct position
def inplace(puzzle, p):
    '''Ouputs bool on whether a piece is in it's correct position'''
    if search(puzzle, p) == search(goal(puzzle), p):
        return True
    else:
        return False

# These functions give heruistic measurements 
def heruistic(puzzle):
    '''All returns heruistic (misplaced, total distance) as a tuple. Other 
    choices are: heruistic misplaced, heruistic distance or heruistic list'''
    heruistic_misplaced = 0
    heruistic_distance = 0
    heruistic_distance_total = 0
    heruistic_list = []
    for sublist in puzzle:
        for item in sublist:
            if inplace(puzzle, item) == False:
                heruistic_misplaced += 1          
    for sublist in puzzle:
        for item in sublist:
            a = search(puzzle, item)
            b = search(goal(puzzle), item)
            heruistic_distance = int(fabs(a[0] - b[0]) + fabs(a[1] - b[1]))
            heruistic_distance_total += heruistic_distance
            heruistic_list.append(heruistic_distance)

    return (heruistic_misplaced, heruistic_distance_total, heruistic_list)

def hm(puzzle):
    '''Outputs heruistic misplaced'''
    return heruistic(puzzle)[0]

def hd(puzzle):
    '''Outputs total heruistic distance'''
    return heruistic(puzzle)[1]

def hl(puzzle):
    '''Outputs heruistic list'''
    return heruistic(puzzle)[2]

def hp(puzzle, p):
    '''Outputs heruistic distance at a given location'''
    x, y = search(puzzle, p)[0], search(puzzle, p)[1]
    return heruistic(puzzle)[2][(x * len(puzzle)) + y]

# This is supposted to iterate along a route according to heruistics but doesn't work
def iterMove(puzzle):
    state = cp.deepcopy(puzzle)
    while state != goal(puzzle):
        state_hd = hd(state)
        state_hm = hm(state)
        moves = neighbours(state)
        ok_moves = []
        good_moves = []
        for move in moves:
            maybe_state = swap(state, move)
            if hd(maybe_state) < state_hd and hm(maybe_state) < state_hm:
                good_moves.append(move)
            elif hd(maybe_state) < state_hd:
                ok_moves.append(move)
            elif hm(maybe_state) < state_hm:
                ok_moves.append(move)
        if good_moves != []:
            print(state)
            state = swap(state, good_moves[0])
        elif ok_moves != []:
            print(state)
            state = swap(state, ok_moves[0])


>> iterMove(puzzle1)
'no good moves'

Answer 1

要在 Python 中实现 A*，您可以使用 https://docs.python.org/3/library/heapq.html对于优先队列。您将可能的位置放入队列中，优先级为“到目前为止的成本 + 剩余成本的启发式”。当您将它们从队列中取出时，您会检查一组已经看到的位置。如果您已经看到位置，请跳过这个，否则将其添加到集合中然后处理。

关键代码段的未经测试版本:

queue = [(heuristic(starting_position), 0, starting_position, None)]
while 0 < len(queue):
    (est_moves, cur_moves, position, history) = heapq.heappop(queue)
    if position in seen:
        continue
    elif position = solved:
        return history
    else:
        seen.add(position)
        for move in possible_moves(position):
            next_position = position_after_move(position, move)
            est_moves = cur_moves + 1 + heuristic(next_position)
            heapq.heappush(queue,
                          (est_moves, cur_moves+1,
                           next_position, (move, history)))
return None