使用 A-star 搜索算法的 N-puzzle 问题
N-puzzle problem using A-star search algorithm
我正在使用 Python 中的 A* 为我的人工智能 class 制作一个 n-puzzle 求解器。我的解决方案存在的问题是 solve_puzzle() 没有正常工作。在搜索节点时，它变得越来越深，但它永远不会结束，深度达到非常高的数字（例如，某些子节点的深度为 5k）。
我认为它陷入了某个循环，并且一直循环遍历相同的节点（这正是我的想法，我不确定）。我真的不知道，我尝试了 3 种不同的 A* 解决方案，但结果是一样的——搜索循环永远不会结束，也永远不会达到目标。
我可以解决非常原始的谜题，比如
开始 -> 0, 1, 2, 3, 4, 5, 6, 7, 8
目标 -> 1, 2, 0, 3, 4, 5, 6, 7, 8（只需两步剩下的）
但对于像
这样更复杂的拼图
开始 = 0、1、2、3、4、5、6、7、8
goal = 1, 2, 5, 0, 3, 4, 6, 7, 8 这是一个永无止境的搜索。
我移动的是带数字的方块，不是空白方块。
完整代码如下：
'''
class Node():
def __init__(self, n_size, m_size, current_state, goal_state, choosen_heuristic, parent):
self.n_size = n_size
self.m_size = m_size
self.dimension = self.n_size * self.m_size
self.current_state = current_state
self.goal_state = goal_state
self.choosen_heuristic = choosen_heuristic
self.parent = parent
self.child = [None, None, None, None]
self.last_operator = None
self.heuristic_cost = 0
self.depth = 0
self.priority = self.depth + self.heuristic_cost
def check_if_goal_is_reached(self):
if (self.heuristic_cost == 0):
print("GOAL IS REACHED!")
exit(1) #for now
#return
def get_blank_tile_position(self):
blank_position = 0
for i in range(self.dimension):
if (self.current_state[i] == 0):
blank_position = i
return blank_position
def misplaced_tiles_heuristic(self):
misplaced_sum = 0
for i in range(self.dimension):
if self.current_state[i] != self.goal_state[i]:
misplaced_sum += 1
#print("Count of misplaced tiless in this node is : ", misplaced_sum)
self.heuristic_cost = "misplaced"
self.heuristic_cost = misplaced_sum
self.check_if_goal_is_reached()
return misplaced_sum
def manhattan_distance(self):
distance_sum = 0
for i in range(self.dimension):
current_x = self.current_state[i] % self.n_size
goal_x = self.goal_state[i] % self.n_size
current_y = self.current_state[i] // self.m_size
goal_y = self.goal_state[i] // self.m_size
distance_sum += abs(current_x - goal_x) + abs(current_y - goal_y)
#print("Sum of Manhattan distance for this node is : ", distance_sum)
self.heuristic_cost = "manhattan"
#print("Hĺbka tohto uzla : ", self.depth)
self.check_if_goal_is_reached()
return distance_sum
def generate_children(self, choosen_heuristic):
possible_directions = []
current_node_blank_position = self.get_blank_tile_position()
# UP - I move a tile with number on it, not the blank tile
if current_node_blank_position < (self.dimension - self.n_size):
self.child[0] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[0] = copy.deepcopy(self)
self.child[0].parent = self.current_state
self.child[0].last_operator = "UP"
self.child[0].depth = self.depth + 1
new_blank_position = current_node_blank_position + self.m_size
temp = self.child[0].current_state[current_node_blank_position]
self.child[0].current_state[current_node_blank_position] = self.child[0].current_state[new_blank_position]
self.child[0].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[0].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[0].manhattan_distance()
possible_directions.append("UP")
print("Depth of this node is : : ", self.child[0].depth)
else:
self.child[0] = None
# DOWN - I move a tile with number on it, not the blank tile
if current_node_blank_position > (self.n_size - 1):
self.child[1] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[1] = copy.deepcopy(self)
self.child[1].parent = self.current_state
self.child[1].last_operator = "DOWN"
self.child[1].depth = self.depth + 1
new_blank_position = current_node_blank_position - self.m_size
temp = self.child[1].current_state[current_node_blank_position]
self.child[1].current_state[current_node_blank_position] = self.child[1].current_state[new_blank_position]
self.child[1].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[1].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[1].manhattan_distance()
possible_directions.append("DOWN")
#print("Depth of this node is : : ", self.child[1].depth)
else:
self.child[1] = None
# RIGHT - I move a tile with number on it, not the blank tile
if (current_node_blank_position + self.n_size) % self.m_size:
self.child[2] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[2] = copy.deepcopy(self)
self.child[2].parent = self.current_state
self.child[2].last_operator = "RIGHT"
self.child[2].depth = self.depth + 1
new_blank_position = current_node_blank_position - 1
temp = self.child[2].current_state[current_node_blank_position]
self.child[2].current_state[current_node_blank_position] = self.child[2].current_state[new_blank_position]
self.child[2].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[2].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[2].manhattan_distance()
possible_directions.append("RIGHT")
#print("Depth of this node is : : ", self.child[2].depth)
else:
self.child[2] = None
# LEFT - I move a tile with number on it, not the blank tile
if (current_node_blank_position + 1) % self.m_size:
self.child[3] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[3] = copy.deepcopy(self)
self.child[3].parent = self.current_state
self.child[3].last_operator = "LEFT"
self.child[3].depth = self.depth + 1
new_blank_position = current_node_blank_position + 1
temp = self.child[3].current_state[current_node_blank_position]
self.child[3].current_state[current_node_blank_position] = self.child[3].current_state[new_blank_position]
self.child[3].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[3].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[3].manhattan_distance()
possible_directions.append("LEFT")
#print("Depth of this node is : ", self.child[3].depth)
else:
self.child[3] = None
#print("From this node (the parent node) I can move to -> ", possible_directions)
def get_node_priority(node):
return node.priority
def solve_puzzle(n_size, m_size, current_state, goal_state, choosen_heuristic):
open_list = []
closed_list = []
init_node_parent = None
init_node = Node(n_size, m_size, current_state, goal_state, choosen_heuristic, init_node_parent)
open_list.append(init_node)
while len(open_list) != 0:
if (len(open_list) == 0):
print("Fail - solution not found !")
else:
node = open_list.pop(0)
if (node.parent != None):
node.check_if_goal_is_reached()
node.generate_children(choosen_heuristic)
closed_list.append(node)
temp_list = []
for i in range(4):
if node.child[i] != None:
temp_list.insert(0, node.child[i])
sorted_temp_list = sorted(temp_list, key=get_node_priority, reverse=True)
for x in range(len(sorted_temp_list)):
if sorted_temp_list[x] != None:
open_list.insert(0, sorted_temp_list[x])
def print_current_node(current_node):
puzzle = ""
if current_node is None:
puzzle = ""
print(puzzle)
else:
puzzle = ""
count_lines = 0
for i in range(current_node.dimension):
puzzle += (str(current_node.current_state[i]) + " ")
count_lines += 1
if (count_lines % current_node.m_size == 0):
puzzle += "\n"
print(puzzle)
def main():
###################
# Static Data #
###################
# static for now, later I will let user to choose
n_size = 3
m_size = 3
current_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]
goal_state = [8, 0, 6, 5, 4, 7, 2, 3, 1]
choosen_heuristic = "manhattan"
start_time = time.process_time()
solve_puzzle(n_size, m_size, current_state, goal_state, choosen_heuristic)
end_time = time.process_time()
search_time = end_time - start_time
print("Solved in : ", search_time, "seconds.")
main()
'''
确保使用 solvable 拼图进行测试。
以下是一些可解决的测试：
goal: {1,2,3,4,5,6,7,8,0}
6 steps: {1,3,5,4,0,2,7,8,6}
18 steps: {1,4,0,5,2,8,7,6,3}
26 steps: {2,1,7,5,0,8,3,4,6}
27 steps: {8,5,3,4,7,0,6,1,2}
28 steps: {0,6,7,3,8,5,4,2,1}
30 steps: {5,7,0,4,6,8,1,2,3}
31 steps: {8,6,7,2,5,4,3,0,1} (highest number of steps possible for 3x3 )
我正在使用 Python 中的 A* 为我的人工智能 class 制作一个 n-puzzle 求解器。我的解决方案存在的问题是 solve_puzzle() 没有正常工作。在搜索节点时，它变得越来越深，但它永远不会结束，深度达到非常高的数字（例如，某些子节点的深度为 5k）。
我认为它陷入了某个循环，并且一直循环遍历相同的节点（这正是我的想法，我不确定）。我真的不知道，我尝试了 3 种不同的 A* 解决方案，但结果是一样的——搜索循环永远不会结束，也永远不会达到目标。
我可以解决非常原始的谜题，比如
开始 -> 0, 1, 2, 3, 4, 5, 6, 7, 8
目标 -> 1, 2, 0, 3, 4, 5, 6, 7, 8（只需两步剩下的）
但对于像
这样更复杂的拼图
开始 = 0、1、2、3、4、5、6、7、8
goal = 1, 2, 5, 0, 3, 4, 6, 7, 8 这是一个永无止境的搜索。
我移动的是带数字的方块，不是空白方块。
完整代码如下：
'''
class Node():
def __init__(self, n_size, m_size, current_state, goal_state, choosen_heuristic, parent):
self.n_size = n_size
self.m_size = m_size
self.dimension = self.n_size * self.m_size
self.current_state = current_state
self.goal_state = goal_state
self.choosen_heuristic = choosen_heuristic
self.parent = parent
self.child = [None, None, None, None]
self.last_operator = None
self.heuristic_cost = 0
self.depth = 0
self.priority = self.depth + self.heuristic_cost
def check_if_goal_is_reached(self):
if (self.heuristic_cost == 0):
print("GOAL IS REACHED!")
exit(1) #for now
#return
def get_blank_tile_position(self):
blank_position = 0
for i in range(self.dimension):
if (self.current_state[i] == 0):
blank_position = i
return blank_position
def misplaced_tiles_heuristic(self):
misplaced_sum = 0
for i in range(self.dimension):
if self.current_state[i] != self.goal_state[i]:
misplaced_sum += 1
#print("Count of misplaced tiless in this node is : ", misplaced_sum)
self.heuristic_cost = "misplaced"
self.heuristic_cost = misplaced_sum
self.check_if_goal_is_reached()
return misplaced_sum
def manhattan_distance(self):
distance_sum = 0
for i in range(self.dimension):
current_x = self.current_state[i] % self.n_size
goal_x = self.goal_state[i] % self.n_size
current_y = self.current_state[i] // self.m_size
goal_y = self.goal_state[i] // self.m_size
distance_sum += abs(current_x - goal_x) + abs(current_y - goal_y)
#print("Sum of Manhattan distance for this node is : ", distance_sum)
self.heuristic_cost = "manhattan"
#print("Hĺbka tohto uzla : ", self.depth)
self.check_if_goal_is_reached()
return distance_sum
def generate_children(self, choosen_heuristic):
possible_directions = []
current_node_blank_position = self.get_blank_tile_position()
# UP - I move a tile with number on it, not the blank tile
if current_node_blank_position < (self.dimension - self.n_size):
self.child[0] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[0] = copy.deepcopy(self)
self.child[0].parent = self.current_state
self.child[0].last_operator = "UP"
self.child[0].depth = self.depth + 1
new_blank_position = current_node_blank_position + self.m_size
temp = self.child[0].current_state[current_node_blank_position]
self.child[0].current_state[current_node_blank_position] = self.child[0].current_state[new_blank_position]
self.child[0].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[0].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[0].manhattan_distance()
possible_directions.append("UP")
print("Depth of this node is : : ", self.child[0].depth)
else:
self.child[0] = None
# DOWN - I move a tile with number on it, not the blank tile
if current_node_blank_position > (self.n_size - 1):
self.child[1] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[1] = copy.deepcopy(self)
self.child[1].parent = self.current_state
self.child[1].last_operator = "DOWN"
self.child[1].depth = self.depth + 1
new_blank_position = current_node_blank_position - self.m_size
temp = self.child[1].current_state[current_node_blank_position]
self.child[1].current_state[current_node_blank_position] = self.child[1].current_state[new_blank_position]
self.child[1].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[1].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[1].manhattan_distance()
possible_directions.append("DOWN")
#print("Depth of this node is : : ", self.child[1].depth)
else:
self.child[1] = None
# RIGHT - I move a tile with number on it, not the blank tile
if (current_node_blank_position + self.n_size) % self.m_size:
self.child[2] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[2] = copy.deepcopy(self)
self.child[2].parent = self.current_state
self.child[2].last_operator = "RIGHT"
self.child[2].depth = self.depth + 1
new_blank_position = current_node_blank_position - 1
temp = self.child[2].current_state[current_node_blank_position]
self.child[2].current_state[current_node_blank_position] = self.child[2].current_state[new_blank_position]
self.child[2].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[2].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[2].manhattan_distance()
possible_directions.append("RIGHT")
#print("Depth of this node is : : ", self.child[2].depth)
else:
self.child[2] = None
# LEFT - I move a tile with number on it, not the blank tile
if (current_node_blank_position + 1) % self.m_size:
self.child[3] = Node(self.n_size, self.m_size, self.current_state, self.goal_state, self.choosen_heuristic, self.current_state)
self.child[3] = copy.deepcopy(self)
self.child[3].parent = self.current_state
self.child[3].last_operator = "LEFT"
self.child[3].depth = self.depth + 1
new_blank_position = current_node_blank_position + 1
temp = self.child[3].current_state[current_node_blank_position]
self.child[3].current_state[current_node_blank_position] = self.child[3].current_state[new_blank_position]
self.child[3].current_state[new_blank_position] = temp
if choosen_heuristic == "misplaced":
self.child[3].misplaced_tiles_heuristic()
if choosen_heuristic == "manhattan":
self.child[3].manhattan_distance()
possible_directions.append("LEFT")
#print("Depth of this node is : ", self.child[3].depth)
else:
self.child[3] = None
#print("From this node (the parent node) I can move to -> ", possible_directions)
def get_node_priority(node):
return node.priority
def solve_puzzle(n_size, m_size, current_state, goal_state, choosen_heuristic):
open_list = []
closed_list = []
init_node_parent = None
init_node = Node(n_size, m_size, current_state, goal_state, choosen_heuristic, init_node_parent)
open_list.append(init_node)
while len(open_list) != 0:
if (len(open_list) == 0):
print("Fail - solution not found !")
else:
node = open_list.pop(0)
if (node.parent != None):
node.check_if_goal_is_reached()
node.generate_children(choosen_heuristic)
closed_list.append(node)
temp_list = []
for i in range(4):
if node.child[i] != None:
temp_list.insert(0, node.child[i])
sorted_temp_list = sorted(temp_list, key=get_node_priority, reverse=True)
for x in range(len(sorted_temp_list)):
if sorted_temp_list[x] != None:
open_list.insert(0, sorted_temp_list[x])
def print_current_node(current_node):
puzzle = ""
if current_node is None:
puzzle = ""
print(puzzle)
else:
puzzle = ""
count_lines = 0
for i in range(current_node.dimension):
puzzle += (str(current_node.current_state[i]) + " ")
count_lines += 1
if (count_lines % current_node.m_size == 0):
puzzle += "\n"
print(puzzle)
def main():
###################
# Static Data #
###################
# static for now, later I will let user to choose
n_size = 3
m_size = 3
current_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]
goal_state = [8, 0, 6, 5, 4, 7, 2, 3, 1]
choosen_heuristic = "manhattan"
start_time = time.process_time()
solve_puzzle(n_size, m_size, current_state, goal_state, choosen_heuristic)
end_time = time.process_time()
search_time = end_time - start_time
print("Solved in : ", search_time, "seconds.")
main()
'''
确保使用 solvable 拼图进行测试。 以下是一些可解决的测试：
goal: {1,2,3,4,5,6,7,8,0} 6 steps: {1,3,5,4,0,2,7,8,6} 18 steps: {1,4,0,5,2,8,7,6,3} 26 steps: {2,1,7,5,0,8,3,4,6} 27 steps: {8,5,3,4,7,0,6,1,2} 28 steps: {0,6,7,3,8,5,4,2,1} 30 steps: {5,7,0,4,6,8,1,2,3} 31 steps: {8,6,7,2,5,4,3,0,1} (highest number of steps possible for 3x3 )