我正在尝试对 k 谜题实施迭代深化搜索。我设法找到了目标节点。但是，我无法从目标节点回溯到开始节点以找到最佳移动。我认为这与 IDS 中的重复状态有关。目前，我正在跟踪 IDS 算法中的所有访问状态。
这是我算法的当前实现。在下面的代码中，moves_dict存储每个节点的先前状态并移动到当前状态。
import os
import sys
from itertools import chain
from collections import deque
# Iterative Deepening Search (IDS)
class Node:
def __init__(self, state, empty_pos = None, depth = 0):
self.state = state
self.depth = depth
self.actions = ["UP", "DOWN", "LEFT", "RIGHT"]
if empty_pos is None:
self.empty_pos = self.find_empty_pos(self.state)
else:
self.empty_pos = empty_pos
def find_empty_pos(self, state):
for x in range(n):
for y in range(n):
if state[x][y] == 0:
return (x, y)
def find_empty_pos(self, state):
for x in range(n):
for y in range(n):
if state[x][y] == 0:
return (x, y)
def do_move(self, move):
if move == "UP":
return self.up()
if move == "DOWN":
return self.down()
if move == "LEFT":
return self.left()
if move == "RIGHT":
return self.right()
def swap(self, state, (x1, y1), (x2, y2)):
temp = state[x1][y1]
state[x1][y1] = state[x2][y2]
state[x2][y2] = temp
def down(self):
empty = self.empty_pos
if (empty[0] != 0):
t = [row[:] for row in self.state]
pos = (empty[0] - 1, empty[1])
self.swap(t, pos, empty)
return t, pos
else:
return self.state, empty
def up(self):
empty = self.empty_pos
if (empty[0] != n - 1):
t = [row[:] for row in self.state]
pos = (empty[0] + 1 , empty[1])
self.swap(t, pos, empty)
return t, pos
else:
return self.state, empty
def right(self):
empty = self.empty_pos
if (empty[1] != 0):
t = [row[:] for row in self.state]
pos = (empty[0] , empty[1] - 1)
self.swap(t, pos, empty)
return t, pos
else:
return self.state, empty
def left(self):
empty = self.empty_pos
if (empty[1] != n - 1):
t = [row[:] for row in self.state]
pos = (empty[0] , empty[1] + 1)
self.swap(t, pos, empty)
return t, pos
else:
return self.state, empty
class Puzzle(object):
def __init__(self, init_state, goal_state):
self.init_state = init_state
self.state = init_state
self.goal_state = goal_state
self.total_nodes = 1
self.total_visited = 0
self.max_frontier = 0
self.depth = 0
self.visited = {}
self.frontier_node = []
self.move_dict = {}
def is_goal_state(self, node):
return node.state == self.goal_state
def is_solvable(self):
flat_list = list(chain.from_iterable(self.init_state))
num_inversions = 0
for i in range(max_num):
current = flat_list[i]
for j in range(i + 1, max_num + 1):
next = flat_list[j]
if current > next and next != 0:
num_inversions += 1
if n % 2 != 0 and num_inversions % 2 == 0:
return True
elif n % 2 == 0:
row_with_blank = n - flat_list.index(0) // n
return (row_with_blank % 2 == 0) == (num_inversions % 2 != 0)
else:
return False
def succ(self, node, frontier):
succs = deque()
node_str = str(node.state)
self.visited[node_str] = node.depth
self.total_visited += 1
frontier -= 1
for m in node.actions:
transition, t_empty = node.do_move(m)
transition_str = str(transition)
transition_depth = node.depth + 1
if transition_str not in self.visited or transition_depth < self.visited[transition_str]:
self.total_nodes += 1
transition_depth = node.depth + 1
transition_str = str(transition)
self.move_dict[transition_str] = (node_str, m)
succs.append(Node(transition, t_empty, transition_depth))
frontier += 1
return succs , frontier
def depth_limited(self, node, depth, frontier):
if self.is_goal_state(node):
return node
if node.depth >= depth:
return None
succs, frontier = self.succ(node, frontier)
self.max_frontier = max(self.max_frontier, frontier)
while succs:
result = self.depth_limited(succs.popleft(), depth, frontier)
if result is not None:
return result
return None
def solve(self):
if not self.is_solvable():
return ["UNSOLVABLE"]
goal_node = None
while goal_node is None:
goal_node = self.depth_limited(Node(self.init_state), self.depth, 1)
if goal_node is not None:
break
# reset statistics
self.visited = {}
self.total_nodes = 1
self.move_dict = {}
self.depth += 1
print self.depth
print "out"
print goal_node.state
solution = deque()
init_str = str(self.init_state)
current_str = str(goal_node.state)
while current_str != init_str:
current_str, move = self.move_dict[current_str]
solution.appendleft(move)
print "Total number of nodes generated: " + str(self.total_nodes)
print "Total number of nodes explored: " + str(self.total_visited)
print "Maximum number of nodes in frontier: " + str(self.max_frontier)
print "Solution depth: " + str(self.depth)
return solution
我已经有一段时间了。我使用一个 hashMap 将状态字符串映射到它的深度，并且当相同的状态出现在较浅的深度时添加节点
编辑
此测试用例的最佳解决方案深度为 22。初始状态：[[1,8,3],[5,2,4],[0,7,6]]
目标状态：[[1,2,3],[4,5,6],[7,8,0]]