我必须在 python 中使用 bfs、dfs 和 A* 算法做一个 8 谜题解析器，但我有一些问题。我无法通过所有测试。任何人都可以帮助我吗？
编辑：我编辑了使用一维数组的代码。它适用于：
python driver_3.py bfs 3,1,2,0,4,5,6,7,8
python driver_3.py bfs 1,2,5,3,4,0,6,7,8
但python driver_3.py bfs 6,1,8,4,0,2,7,3,5似乎没有找到解决方案。它运行了几分钟而没有找到解决方案。
这是我的代码：
driver_3.py
import sys
from EightPuzzle import EightPuzzle as g
if __name__ == "__main__":
method = sys.argv[1]
board = list(map(int,sys.argv[2].split(',')))
print("Start: ", board)
game = g(board)
if (method == 'bfs') | (method == 'dfs') | (method == 'ast') :
game.resolve(alg=method)
else:
print('Method not allowed.')
八拼图.py
from Graph import Graph as Graph
from Node import Node
import time
class EightPuzzle(object):
def __init__(self, initialState):
self.graph = Graph(Node(initialState))
self.actions = ['Up','Down', 'Left', 'Right']
self.goal = [0,1,2,3,4,5,6,7,8]
self.start_time = time.time()
self.end_time = 0
self.diff_time = 0
self.ram = 0
def get_graph(self):
return self.graph
def set_graph(self, other):
self.graph = other
def get_actions(self):
return self.actions
def set_actions(self, other):
self.actions = other
def get_goal(self):
return self.goal
def set_goal(self, other):
self.goal = other
def get_start_time(self):
return self.start_time
def set_start_time(self, other):
self.ram = other
def get_end_time(self):
return self.end_time
def set_end_time(self, other):
self.end_time = other
def set_diff_time(self):
self.diff_time = self.end_time - self.start_time
return None
def get_diff_time(self):
return self.diff_time
def set_ram_usage(self):
import sys
if sys.platform == "win32":
import psutil
self.ram = psutil.Process().memory_info().rss
else:
# import resource
# self.ram = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
return False
def get_ram(self):
return self.ram
def set_ram(self, other):
self.ram = other
def find_zero(self, node_state):
return node_state.index(0)
def move_up(self, node_state, zero):
up = node_state[:]
val = up[zero-3]
up[zero-3] = 0
up[zero] = val
return up
def move_down(self, node_state, zero):
down = node_state[:]
val = down[zero+3]
down[zero+3] = 0
down[zero] = val
return down
def move_left(self, node_state, zero):
left = node_state[:]
val = left[zero-1]
left[zero-1] = 0
left[zero] = val
return left
def move_right(self, node_state, zero):
right = node_state[:]
val = right[zero+1]
right[zero+1] = 0
right[zero] = val
return right
def find_neighbors(self, node):
node_state = node.get_state()
print("Node: ", node_state)
zero = self.find_zero(node_state)
neighbors = []
if zero > 2:
neighbors.append(Node(self.move_up(node_state, zero), parent=node, action="Up"))
if zero < 6:
neighbors.append(Node(self.move_down(node_state,zero), parent=node, action="Down"))
if (zero != 0) & (zero != 3) & (zero != 6):
neighbors.append(Node(self.move_left(node_state,zero), parent=node, action="Left"))
if (zero != 2) & (zero != 5) & (zero != 8):
neighbors.append(Node(self.move_right(node_state,zero), parent=node, action="Right"))
return neighbors
def success(self):
self.end_time = time.time()
self.set_diff_time()
self.set_ram_usage()
#self.output()
return "Success"
def bfs(self, goal):
print("bfs")
graph = self.get_graph()
while len(graph.get_frontiers()) != 0:
current_node = graph.frontiers.shift()
graph.explored.append(current_node)
if (current_node == goal):
print("Explored ", str(len(graph.get_explored())-1))
print("Solution found!: ", current_node)
return "Done"
neighbors = self.find_neighbors(current_node)
current_node.set_neighbors(neighbors)
for neighbor in neighbors:
if (neighbor not in graph.get_frontiers()) & (neighbor not in graph.get_explored()):
graph.frontiers.append(neighbor)
print("Solution Not Found")
def dfs(self, goal):
print("dfs")
graph = self.get_graph()
while len(graph.get_frontiers()) != 0:
current_node = graph.frontiers.pop()
graph.explored.append(current_node)
if (current_node == goal):
print("Explored ", str(len(graph.get_explored())-1))
print("Solution found!: ", current_node)
return "Done"
neighbors = self.find_neighbors(current_node)
current_node.set_neighbors(neighbors)
for neighbor in neighbors:
if (neighbor not in graph.get_frontiers()) & (neighbor not in graph.get_explored()):
graph.frontiers.prepend(neighbor)
print("Solution Not Found")
def ast(self, goal):
print("ast")
# TO DO
print("Solution Not Found")
# def output(self):
# with open("output.txt", "w") as f:
# f.write("path_to_goal: ", str(self.path))
# f.write("cost_of_path: ", str(len(self.cost_of_path)))
# f.write("node_expanded: ", str(len(self.explored)))
# f.write("max_search_depth: ", str(self.max_depth))
# f.write("running_time: ", str(self.diff_time))
# f.write("max_ram_usage: ", str(self.ram))
# f.closed
# return "Output Done"
def resolve(self, alg):
if alg == 'bfs':
self.bfs(self.goal)
elif alg == 'dfs':
self.dfs(self.goal)
elif alg == 'ast':
self.ast(self.goal)
return None
节点.py
class Node(object):
def __init__(self, state, parent=None, action="Root", path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
self.depth = 0
self.neighbors = []
if parent:
self.depth = parent.depth + 1
self.path_cost = parent.path_cost + 1
def __eq__(self,other):
return self.state == other
def __str__(self):
return str(self.state)
def __repr__(self):
return str(self.state)
def get_state(self):
return self.state
def set_state(self, new_state):
self.state = new_state
def get_parent(self):
return self.parent
def set_parent(self, new_parent):
self.parent = new_parent
def get_action(self):
return self.action
def set_action(self, other_action):
self.action = other_action
def get_path_cost(self):
return self.path_cost
def set_path_cost(self, other_path):
self.path_cost = other_path
def get_depth(self):
return self.depth
def set_depth(self, other_depth):
self.depth = other_depth
def get_neighbors(self):
return self.neighbors
def set_neighbors(self, other_neighbors):
self.neighbors = other_neighbors
图.py
from Frontiers import Frontiers
class Graph:
def __init__(self, initialState):
self.frontiers = Frontiers(initialState)
self.explored = []
self.path = []
self.max_depth = 0
self.cost_of_path = 0
def get_frontiers(self):
return self.frontiers
def set_frontiers(self, other):
self.frontiers = other
def get_explored(self):
return self.explored
def set_explored(self, other):
self.explored = other
def get_path(self):
return self.path
def set_path(self, other):
self.path = other
def get_max_depth(self):
return self.max_depth
def set_max_depth(self, other):
self.max_depth = other
def get_cost_of_path(self):
return self.cost_of_path
def set_cost_of_path(self, other):
self.cost_of_path = other
前沿.py
class Frontiers(list):
def __init__(self, initialState):
self.state = [initialState]
def __len__(self):
return len(self.state)
def __contains__(self,other):
return True if other in self.state else False
def __str__(self):
return str(self.state)
def __repr__(self):
return str(self.state)
def set_state(self,new_state):
self.state = new_state
def get_state(self):
return self.state
def append(self, other):
#append element at the end of the frontiers
self.set_state(self.get_state() + [other])
def prepend(self, other):
#append element at the beginning of the frontiers
self.set_state([other] + self.get_state())
def shift(self):
#return first element of frontier state
first = self.get_state()[0]
if(len(self.get_state()) > 1):
self.set_state(self.get_state()[1:])
else:
self.set_state([])
return first
def pop(self):
#return last element of frontier state
last = self.get_state()[-1]
if(len(self.get_state()) > 1):
self.set_state(self.get_state()[:-1])
else:
self.set_state([])
return last