标签：补全 state self 迷宫 solution 算法 table def row
补全下列关于走迷宫的程序：
class Node():
#TODO: 完成结点类的定义，结点中要包含状态、父结点、算符等必要成员。根据算法需求，还可能包含该结点的路径代价、启发函数值、估计代价等信息
def __init__(self, state, parent, action, stepCost, hCost):
self.state = state #结点状态
self.parent = parent #父节点
self.action = action #父结点至当前结点算符
if parent != None:
self.cost = parent.cost + stepCost
else:
self.cost = 0
self.hCost = hCost
self.estCost = self.cost + hCost
class Open():
#构造函数
def __init__(self):
self.table = []
#增加新结点
def add(self, node):
self.table.append(node)
self.table.sort(key=lambda x:x.estCost, reverse=True)
#表中是否已有该状态结点
def contains_state(self, state):
for node in self.table:
if node.state == state:
return True
return False
#判断Open表是否空
def empty(self):
return len(self.table) == 0
#从Open表中移出结点
def remove(self):
if self.empty():
raise Exception("无解") #无解异常
else:
if self.empty():
raise Exception("无解")
else:
node = self.table[-1]
self.table = self.table[:-1]
return node
class ClosedTable():
#构造函数
def __init__(self):
self.table = []
#添加结点
def add(self, node):
self.table.append(node)
#表中是否已有该状态结点
def contains_state(self, state):
for node in self.table:
if node.state == state:
return True
return False
class Maze():
#构造函数
def __init__(self, filename):
# 读取迷宫文件，并设置迷宫范围
with open(filename) as f:
contents = f.read()
# 确定迷宫有效性
if contents.count("A") != 1:
raise Exception("迷宫需要有唯一的起点")
if contents.count("B") != 1:
raise Exception("迷宫需要有唯一终点")
# 确定迷宫长宽范围
contents = contents.splitlines()
self.height = len(contents)
self.width = max(len(line) for line in contents)
# 找出迷宫墙壁
self.walls = []
for i in range(self.height):
row = []
for j in range(self.width):
try:
if contents[i][j] == "A":
self.start = (i, j)
row.append(False)
elif contents[i][j] == "B":
self.goal = (i, j)
row.append(False)
elif contents[i][j] == " ":
row.append(False)
else:
row.append(True)
except IndexError:
row.append(False)
self.walls.append(row)
self.solution = None
#打印输出迷宫
def print(self):
solution = self.solution[1] if self.solution is not None else None
print()
for i, row in enumerate(self.walls):
for j, col in enumerate(row):
if col:
print("█", end="")
elif (i, j) == self.start:
print("A", end="")
elif (i, j) == self.goal:
print("B", end="")
elif solution is not None and (i, j) in solution:
print("*", end="")
else:
print(" ", end="")
print()
print()
def output_image(self, filename, show_solution=True, show_explored=False):
from PIL import Image, ImageDraw
cell_size = 50
cell_border = 2
# 创建画布
img = Image.new(
"RGBA",
(self.width * cell_size, self.height * cell_size),
"black"
)
draw = ImageDraw.Draw(img)
solution = self.solution[1] if self.solution is not None else None
for i, row in enumerate(self.walls):
for j, col in enumerate(row):
# 墙
if col:
fill = (40, 40, 40)
# 起点
elif (i, j) == self.start:
fill = (255, 0, 0)
# 终点
elif (i, j) == self.goal:
fill = (0, 171, 28)
# 解法
elif solution is not None and show_solution and (i, j) in solution:
fill = (220, 235, 113)
# 已探索点
elif solution is not None and show_explored and closed_table.contains_state((i, j)):
fill = (212, 97, 85)
# 空格子
else:
fill = (237, 240, 252)
# 绘制格子
draw.rectangle(
([(j * cell_size + cell_border, i * cell_size + cell_border),
((j + 1) * cell_size - cell_border, (i + 1) * cell_size - cell_border)]),
fill=fill
)
img.save(filename)
infer_img = '/home/aistudio/'+filename
print(infer_img)
img = Image.open(infer_img)
display(img)
def actions(self, state):
row, col = state
candidates = [
("上", (row - 1, col)),
("下", (row + 1, col)),
("左", (row, col - 1)),
("右", (row, col + 1))
]
result = []
for action, (r, c) in candidates:
if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
result.append((action, (r, c)))
return result
def heuristic(self, state):
(i, j) = self.goal
(x, y) = state
#TODO： 设计启发函数计算h值，替换下面语句
h = 0
for y in range(len(state)):
for x in range(len(state[y])):
if state[y][x] != self.goalState[y][x]:
for i in range(len(state)):
for j in range(len(state[y])):
if state[y][x] == self.goalState[i][j]:
if state[y][x] != 0:
h += abs(y-i) + abs(x-j)
return h
class Solver(Maze):
#结点扩展
def expand(self, node):
actions = self.actions(node.state)
result = []
for action, (r, c) in actions:
childState = (r, c)
childHCost = self.heuristic(childState)
child = Node(state=childState, parent=node, action=action, stepCost=1, hCost=childHCost) #TODO：依照结点类定义，补全（）中代码，生成扩展结点
result.append(child)
return result
def solve(self):
#初始设定
startHCost = self.heuristic(self.start)
start = Node() #TODO：依照结点类定义，补全（）中代码，生成初始状态结点
open_table = Open() #实例化Open表
open_table.add(start) #将初始状态结点填至Open表
closed_table = ClosedTable()
# 循环求解
while True:
#Open表为空，则所有结点均探索完，还没找到目标状态结点，无解异常
if open_table.empty():
raise Exception("无解")
#从Open表中取出结点
node = open_table.remove()
#目标验证
if node.state == self.goal:
actions = [] #求解路径
cells = []
while node.parent is not None: #由目标状态结点逆推至初始状态结点
actions.append(node.action) #将逆推路径结点添加至求解路径
cells.append(node.state)
node = node.parent
actions.reverse() #将逆推求解路径翻转至正序
cells.reverse()
self.solution = (actions, cells)
num = len(closed_table.table)+len(open_table.table)
return num, closed_table
#TODO：完成代码，将从Open表中取出待扩展结点添加至Closed表（已探索结点）
#扩展结点，获得后继结点
children = self.expand(node)
#如果扩展的后继结点既不在Open表中，也不在Closed表中，则添加至Open表
for child in children:
if not open_table.contains_state(child.state) and not closed_table.contains_state(child.state):
open_table.add(child)
# 程序运行
filename = '/home/aistudio/maze2.txt' #载入迷宫文件
m = Solver(filename) #求解问题
print("迷宫:")
m.print()
print("求解中...")
num, closed_table = m.solve()
print("共探索:", num, "个点")
print("解法:")
m.print()
m.output_image("maze.png", show_explored=True) #输出图形
标签：补全,
state,
self,
迷宫,
solution,
算法,
table,
def,
row
From： https://blog.csdn.net/bhxlm/article/details/136739680