我正在尝试使用 BFS 搜索、DFS、贪婪和 A* 等技术来解决 8tile 难题，并使用曼哈顿距离作为我的启发式解决方案。
问题是，虽然我可以解决一些问题，但问题在于一些谜题，我扩展父节点时得到的子节点可能已经位于较旧的节点中。
我不知道我是否能够很好地解释自己，但我的主要问题是我试图查看我创建的新节点是否已经在旧节点上。
对于这个问题，我通常会到达深度 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))
最佳答案
看起来您的处理方式是正确的，但您需要在 Node 类中定义 __eq__ 和 __ne__ 方法；否则 node in prev 将始终返回 False，因为 Python 不知道如何将 node 与列表中的项目进行比较。查看Python data model documentation了解有关如何对用户定义类型进行比较的更多信息。
我捕获了你的代码并添加了几个(非常天真的)方法来进行相等性检查，并且它似乎不再挂起。还值得注意的是，您的类应该继承自基本对象(见下文)。这些是我所做的更改(在上下文中):
class Board(object):
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 __eq__(self, o):
# Note that comparing whitepos is not strictly necessary; but I left
# it in as a safety measure in case the board state gets corrupted.
# If speed becomes an issue, take it out.
return (self.matrix, self.whitepos) == (o.matrix, o.whitepos)
class Node(object):
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
def __eq__(self, o):
# Note that you don't have to compare parents, since your goal
# is to eliminate ANY nodes with the same position.
return self.state == o.state
class Solution(object):
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
#...
print_solution("bl", bl_search(board))
# I commented out all but the first search to avoid cluttering up the output.
通过这些更改，代码确实会产生一个解决方案(我将由您来验证它是否正确，但这是我的输出)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
* bl
moves: 20
[[1, 2, 3], [8, 0, 4], [7, 6, 5]]
[[1, 2, 3], [8, 6, 4], [7, 0, 5]]
[[1, 2, 3], [8, 6, 4], [0, 7, 5]]
[[1, 2, 3], [0, 6, 4], [8, 7, 5]]
[[1, 2, 3], [6, 0, 4], [8, 7, 5]]
[[1, 0, 3], [6, 2, 4], [8, 7, 5]]
[[0, 1, 3], [6, 2, 4], [8, 7, 5]]
[[6, 1, 3], [0, 2, 4], [8, 7, 5]]
[[6, 1, 3], [2, 0, 4], [8, 7, 5]]
[[6, 1, 3], [2, 7, 4], [8, 0, 5]]
[[6, 1, 3], [2, 7, 4], [8, 5, 0]]
[[6, 1, 3], [2, 7, 0], [8, 5, 4]]
[[6, 1, 0], [2, 7, 3], [8, 5, 4]]
[[6, 0, 1], [2, 7, 3], [8, 5, 4]]
[[6, 7, 1], [2, 0, 3], [8, 5, 4]]
[[6, 7, 1], [2, 5, 3], [8, 0, 4]]
[[6, 7, 1], [2, 5, 3], [8, 4, 0]]
[[6, 7, 1], [2, 5, 0], [8, 4, 3]]
[[6, 7, 0], [2, 5, 1], [8, 4, 3]]
[[6, 0, 7], [2, 5, 1], [8, 4, 3]]
[[6, 5, 7], [2, 0, 1], [8, 4, 3]]
nodes needed: 44282
iterations: 59930
希望这有帮助!
关于python - 具有重复节点的 8 个平铺求解器 - Python，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15253529/