我正在使用 bfs 和 iddfs 来找到 8 个瓷砖拼图的最佳解决方案，但是，我的 IDDFS 缺少解决方案，我不知道为什么。我检查过，似乎每个节点都访问它的所有儿子，至少在第一次迭代中，所以我不确定问题的根源可能是什么。将图块排列为 [1,4,5,0,8,2,3,6,7] 我的 iddfs 似乎没有在适当的深度找到正确的解决方案，后来偶然发现了另一个解决方案： BFS 解决路径： [1,4,5,2,8,5,4,1,3,6,7,8,5,4,1]
iddfs 解决路径： [8, 2, 5, 4, 1, 8, 2, 1, 8, 2, 1, 8, 4, 5, 8, 4, 2, 1, 3, 6, 7, 8, 5, 2, 1 ]
请注意，我的 iddfs k（深度）以 1 为间隔增加，因此我应该在我的 bfs 相同的深度找到最佳解决方案，这意味着尽可能早的深度。 我正在添加 iddfs 代码以及运行它所需的其余代码：
# helper method for the iddfs, solves a dfs to a limited depth k
def dfs_solve_k(self, node, depth):
if depth < 0:
return False
self.total_count += 1
board_tuple = tuple(tuple(row) for row in node.board_array)
self.explored.add(board_tuple)
if node.check_end_state():
return True
# Iterate over possible swap positions in a specific order
for swappable_pos in node.possible_swap_positions:
tracker = node.board_array[swappable_pos.i][swappable_pos.j]
# Perform swap to reach a new board
new_board = node.swap(swappable_pos)
new_board_tuple = tuple(tuple(row) for row in new_board)
# Check if the new board state has not been explored before
if new_board_tuple not in self.explored:
new_node = StateNode(new_board, swappable_pos)
is_solved = self.dfs_solve_k(new_node, depth - 1)
if is_solved:
self.path.append(tracker)
return True
return False
# iterative deepening dfs
def iddfs(self, node, max_depth):
search_depth = 1
while search_depth <= max_depth:
self.explored.clear()
self.path = []
is_solved = self.dfs_solve_k(node, search_depth)
if is_solved:
self.path = self.path[::-1]
return True
else:
search_depth += 1
return False
用于测试的附加代码：
rows = 3
columns = 3
goal_state = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
class Position:
def __init__(self, i, j):
self.i = i
self.j = j
class Directions(Enum):
LEFT = Position(0, -1)
RIGHT = Position(0, 1)
UP = Position(-1, 0)
DOWN = Position(1, 0)
def get_inv_count(board):
inv_count = 0
empty_value = 0
n = len(board)
for i in range(n * n):
for j in range(i + 1, n * n):
row_i, col_i = divmod(i, n)
row_j, col_j = divmod(j, n)
val_i = board[row_i][col_i]
val_j = board[row_j][col_j]
if val_i != empty_value and val_j != empty_value and val_i > val_j:
inv_count += 1
return inv_count
# This function returns true if the given puzzle is solvable.
def is_solvable(puzzle):
# Count inversions in the given puzzle
inv_count = get_inv_count(puzzle)
# Return true if the inversion count is even.
return inv_count % 2 == 0
def find_position(value, board):
for i in range(3):
for j in range(3):
if board[i][j] == value:
return Position(i, j)
def calculate_distance(position1, position2):
x1, y1 = position1
x2 = position2.i
y2 = position2.j
distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
return distance
def heuristic(board_state):
distance_score = 0
for i in range(3):
for j in range(3):
cell_value = board_state[i][j]
if cell_value != 0: # Skip the empty tile (represented by 0)
target_position = find_position(cell_value, goal_state)
current_position = (i, j)
distance = calculate_distance(current_position, target_position)
distance_score += distance
return distance_score
class StateNode:
def __init__(self, board, zero_pos, score=0, parent=None):
self.board_array = board
self.zero_pos = zero_pos
self.score = score
self.possible_swap_positions = []
self.parent_node = parent
for direction in Directions:
new_zero_pos = Position(self.zero_pos.i + direction.value.i,
self.zero_pos.j + direction.value.j)
if (
0 <= new_zero_pos.i < len(self.board_array) and
0 <= new_zero_pos.j < len(self.board_array)
):
self.possible_swap_positions.append(new_zero_pos)
def get_value(self, position):
return self.board_array[position.i][position.j]
def swap(self, swappable_pos):
# deep copy our array
new_board = deepcopy(self.board_array)
temp_value = self.board_array[swappable_pos.i][swappable_pos.j]
# change current zero to value in new position
new_board[self.zero_pos.i][self.zero_pos.j] = temp_value
# change swapped position to zero
new_board[swappable_pos.i][swappable_pos.j] = 0
return new_board
def check_end_state(self):
for board_row, end_state_row in zip(self.board_array, goal_state):
if board_row != end_state_row:
return False
return True
class GameBoard:
def __init__(self, values_array):
self.total_count = 0
self.rows = rows
self.columns = columns
self.path = []
self.explored = set()
expected_size = rows * columns
self.game_board = [[0] * columns for _ in range(rows)]
# Check if the dimensions of values_array match the dimensions of the game_board
try:
values_array = [int(value) for value in values_array]
except ValueError:
raise ValueError("All elements in values_array must be convertible to integers.")
if len(values_array) == expected_size:
self.game_board = [values_array[i:i + self.columns] for i in range(0, expected_size, self.columns)]
else:
raise ValueError(
"The dimensions of the provided values_array do not match the dimensions of the game board.")
要小心如何定义某个状态是否已被探索。 可能有一条较长的路径具有不同的起点，在最终达到解决方案状态之前达到与解决方案路径共享的中间状态。 当以解决方案的最大深度（此处为 15）运行 DFS 时，您可能会首先遵循这条较长的路径，并访问中间状态，但无法到达最终状态，因为替代路径的长度超过 15。 然后，当遵循所需解决方案路径的第一步时，您将到达中间已访问过的状态，并决定不扩展您的搜索。
总之，如果存在的话，你的 IDDFS 会找到一个解决方案，但不一定是最短的。