带重复节点的8拼图求解器 - Python

Question

我正在尝试用一些方法来解决8块拼图，比如广度优先搜索（BFS）、深度优先搜索（DFS）、贪心算法和A*算法，使用曼哈顿距离作为我的启发式解决方案。

问题是，虽然我能解决很多拼图，但有些拼图在扩展父节点时，得到的子节点可能已经出现在之前的节点中。

我不知道我是否解释得清楚，但我主要的问题是，我尝试检查我创建的新节点是否已经在旧节点中。

遇到这个问题时，我通常只能到达深度9，然后我的程序就不再继续或者给出解决方案了。

我有一个想法是使用以下代码：

if node in prev:
    continue
prev.append(node)

但我觉得我可能走错了方向。

我是在用Python编写这个程序，这里是我的代码，看看有没有人能帮我。

#!/usr/bin/python

import sys
import copy


class Board:
    def __init__(self, matrix, whitepos=None):
        self.matrix = matrix
        self.whitepos = whitepos
        if not whitepos:
            for y in xrange(3):
                for x in xrange(3):
                    if board[y][x] == 0:
                        self.whitepos = (x, y)


def is_final_state(board):
    final = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
    for y in xrange(3):
        for x in xrange(3):
            if board.matrix[y][x] != final[y][x]:
                return False
    return True


def get_whitepos(board):
    return board.whitepos


def move(board, x, y, dx, dy):
    b = copy.deepcopy(board.matrix)
    b[y][x] = b[y + dy][x + dx]
    b[y + dy][x + dx] = 0
    return Board(b, (x + dx, y + dy))


def manhattan_heur(board):
    finalpos = [(1, 1), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2),
                (0, 1)]
    cost = 0
    for y in xrange(3):
        for x in xrange(3):
            t = board.matrix[y][x]
            xf, yf = finalpos[t]
            cost += abs(xf - x) + abs(yf - y)
    return cost


def wrongplace_heur(board):
    finalpos = [(1, 1), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2),
                (0, 1)]
    cost = 0
    for y in xrange(3):
        for x in xrange(3):
            t = board.matrix[y][x]
            if finalpos[t] != (x, y):
                cost += 1
    return cost


def heuristic(board):
    return manhattan_heur(board)


class Node:
    def __init__(self, board, parent):
        self.state = board
        self.parent = parent
        if not parent:
            self.g = 0
        else:
            self.g = parent.g + 1
        self.h = heuristic(board)

    def test_goal(self):
        return is_final_state(self.state)

    def expand(self):
        children = []
        b = self.state
        x, y = get_whitepos(b)
        if x > 0:
            children.append(Node(move(b, x, y, -1, 0), self))
        if x < 2:
            children.append(Node(move(b, x, y, +1, 0), self))
        if y > 0:
            children.append(Node(move(b, x, y, 0, -1), self))
        if y < 2:
            children.append(Node(move(b, x, y, 0, +1), self))
        return children


class Solution:
    def __init__(self, node, mem_needed, steps):
        self.node = node
        self.mem_needed = mem_needed
        self.iterations = steps

    def inc(self, other):
        self.node = other.node
        self.mem_needed = max(self.mem_needed, other.mem_needed)
        self.iterations += other.iterations


def search(board, queue_fn, queue_arg=None):
    max_nodes = 1
    steps = 0
    nodes = [Node(Board(board), None)]
    prev = []
    depth = 0
    while nodes:
        node = nodes.pop(0)

        if node.g > depth:
            depth = node.g
            print depth

        if node in prev:
            continue
        prev.append(node)

        if node.test_goal():
            return Solution(node, max_nodes, steps)
        new_nodes = node.expand()
        nodes = queue_fn(nodes, new_nodes, queue_arg)

        max_nodes = max(max_nodes, len(nodes))
        steps += 1
    return Solution(None, max_nodes, steps)


def fifo_queue(nodes, new_nodes, _):
    nodes.extend(new_nodes)
    return nodes


def bl_search(board):
    return search(board, fifo_queue)


def lifo_queue(nodes, new_nodes, _):
    new_nodes.extend(nodes)
    return new_nodes


def dfs_search(board):
    return search(board, lifo_queue)


def bpl_queue(nodes, new_nodes, max_depth):
    def f(n):
        return n.g <= max_depth

    new_nodes = filter(f, new_nodes)
    new_nodes.extend(nodes)
    return new_nodes


def bpi_search(board):
    solution = Solution(None, 0, 0)
    for max_depth in xrange(0, sys.maxint):
        sol = search(board, bpl_queue, max_depth)
        solution.inc(sol)
        if solution.node:
            return solution


def sort_queue(nodes, new_nodes, cmp):
    nodes.extend(new_nodes)
    nodes.sort(cmp)
    return nodes


def guloso2_search(board):
    def cmp(n1, n2):
        return n1.h - n2.h

    return search(board, sort_queue, cmp)


def astar_search(board):
    def cmp(n1, n2):
        return (n1.g + n1.h) - (n2.g + n2.h)

    return search(board, sort_queue, cmp)


def print_solution(search, sol):
    print
    print "*", search
    node = sol.node
    if node:
        print "moves:", node.g
        while node:
            print "\t", node.state.matrix
            node = node.parent
    else:
        print "no solution found"
    print "nodes needed:", sol.mem_needed
    print "iterations:  ", sol.iterations


board = [[6, 5, 7], [2, 0, 1], [8, 4, 3]]

print_solution("bl", bl_search(board))
print_solution("dfs", dfs_search(board))
print_solution("bpi", bpi_search(board))
print_solution("guloso2", guloso2_search(board))
print_solution("astar", astar_search(board))

A*算法深度优先搜索广度优先搜索贪心算法曼哈顿距离重复节点 8拼图启发式搜索

带重复节点的8拼图求解器 - Python

1 个回答

撰写回答