\documentclass{article} \usepackage{graphicx} % Required for inserting images \usepackage[chinese]{babel} \usepackage[UTF8]{ctex} \usepackage{float} \usepackage[letterpaper,top=2cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry} \usepackage{listings} \usepackage{authblk} % Useful packages \usepackage{amsmath} \usepackage{subfigure} \usepackage{graphicx} \usepackage[colorlinks=true, allcolors=blue]{hyperref}
\title{2023算法设计大作业} \author[]{21009201106-潘笃驿} \author[]{21009201203-曹宇思} \author[]{21009201084代淑婷} \author[]{21009200904李泽荟} \author[]{21009201005 毛美文} \author[]{21009200999余菲月}
\affil[*]{算法第六组}
\renewcommand\Authands{ and }
\date{October 2023}
\begin{document}
\maketitle
\section{迷宫设计}
\subsection{迷宫初始化} 我们使用随机化的Prim算法来创建迷宫。
Prim算法是一种图论中的算法，用于找到加权连通图的最小生成树。在这个迷宫生成器中，Prim算法被用于创建迷宫的通路，而迷宫的墙则是最小生成树之外的部分。
我们可以把迷宫看做这个样子，左边是用类似数组表示的迷宫，把墙简化后比较容易看
\begin{figure}[H] \centering \includegraphics[width=0.5\linewidth]{image01.png} \caption{01} \label{fig:galaxy} \end{figure}
这是迷宫初始化的样子，所有墙壁都是封死的，路径格处于独立状态。如果把迷宫看作带权图G，则点集V即4为简化图中显示的9个路径格，边集E则是任意相邻两路径格间连线的集合，可以看作所有路径权值都相等。
设迷宫入口为左上角的路径格，出口为右下角的路径格，则生成一个迷宫的实质就是找G的一个最小生成树T，T包含所有路径格，不成环，且其中任意两个路径格连通。（事实上当不必连通所有格，只要连通了起点和终点，也可以算迷宫生成完毕，只是这样的迷宫不完整）
把起点加入空集A，则森林Ga中包含9棵根节点状态的树，接下来要不断在E中找安全边，使Ga中的根节点状态的树元素都加入到集合A中，直到Ga中只剩A一个元素（或者Ga中某树包含起点和终点）为止。
在具体实现中我们可以按照下面的步骤来做 \begin{enumerate} \item[1).] 让迷宫全是墙 \item[2).] 选一个单元格作为迷宫的通路，然后把它的邻墙放入列表 \item[3).] 当列表里还有墙时从列表里随机选一个墙，如果这面墙分隔的两个单元格只有一个单元格被访问过，那就从列表里移除这面墙，即把墙打通，让未访问的单元格成为迷宫的通路，再把这个格子的墙加入列表 \item[4).] 如果墙两面的单元格都已经被访问过，那就从列表里移除这面墙 \item[5).] 列表里已经没有墙了，结束 \end{enumerate}
实现代码如下： \begin{lstlisting}[language=python] from random import randint, choice from enum import Enum
迷宫通路、墙、起点和终点
class MAP_ENTRY_TYPE (Enum): MAP_EMPTY = 0, MAP_BLOCK = 1, MAP_START = 2, MAP_END = 3,
class WALL_DIRECTION(Enum): WALL_LEFT = 0, WALL_UP = 1, WALL_RIGHT = 2, WALL_DOWN = 3,
class Map(): def init(self, width, height): self.width = width self.height = height self.map = [[0 for x in range(self.width)] for y in range(self.height)]
def resetMap(self, value):
for y in range(self.height):
for x in range(self.width):
self.setMap(x, y, value)
# 地图的设置
def setMap(self, x, y, value):
if value == MAP_ENTRY_TYPE.MAP_EMPTY:
self.map[y][x] = 0
elif value == MAP_ENTRY_TYPE.MAP_BLOCK:
self.map[y][x] = 1
elif value == MAP_ENTRY_TYPE.MAP_START:
self.map[y][x] = 2
elif value == MAP_ENTRY_TYPE.MAP_END:
self.map[y][x] = 3
# 判断是否已经访问过（访问过则代表不设定为墙
def isVisited(self, x, y):
return self.map[y][x] != 1
# 将生成的地图写入data.txt文件
def showMap(self):
# coding=UTF-8
filename = 'data.txt'
# 初始化data文件，删除原有内容成为空白文件
with open(filename, 'w') as file_object:
file_object.write("")
for row in self.map:
s = " '"
with open(filename, 'a') as file_object:
file_object.write(" '")
for entry in row:
# 通路
if entry == 0:
s += '.'
with open(filename, 'a') as file_object:
file_object.write(".")
# 墙
elif entry == 1:
s += '#'
with open(filename, 'a') as file_object:
file_object.write("#")
# 起点
elif entry == 2:
s += 'S'
with open(filename, 'a') as file_object:
file_object.write("S")
# 终点
else:
s += 'E'
with open(filename, 'a') as file_object:
file_object.write("E")
s += "',"
with open(filename, 'a') as file_object:
file_object.write("',\n")
print(s)
找出与当前位置相邻的墙（四个方向
然后将其中一个方向的墙随机添加到checklist中，并将其标记为已访问
def checkAdjacentPos(map, x, y, width, height, checklist): directions = [] # 如果当前位置处在边界（即最多只有三个相邻墙位置 if x > 0: if not map.isVisited(2 * (x - 1) + 1, 2 * y + 1): directions.append(WALL_DIRECTION.WALL_LEFT)
if y > 0:
if not map.isVisited(2 * x + 1, 2 * (y - 1) + 1):
directions.append(WALL_DIRECTION.WALL_UP)
if x < width - 1:
if not map.isVisited(2 * (x + 1) + 1, 2 * y + 1):
directions.append(WALL_DIRECTION.WALL_RIGHT)
if y < height - 1:
if not map.isVisited(2 * x + 1, 2 * (y + 1) + 1):
directions.append(WALL_DIRECTION.WALL_DOWN)
# 如果当前位置四周的相邻结点有墙
if len(directions):
# 随机选择一个方向的墙
direction = choice(directions)
if direction == WALL_DIRECTION.WALL_LEFT:
map.setMap(2 * (x - 1) + 1, 2 * y + 1, MAP_ENTRY_TYPE.MAP_EMPTY)
map.setMap(2 * x, 2 * y + 1, MAP_ENTRY_TYPE.MAP_EMPTY)
checklist.append((x - 1, y))
elif direction == WALL_DIRECTION.WALL_UP:
map.setMap(2 * x + 1, 2 * (y - 1) + 1, MAP_ENTRY_TYPE.MAP_EMPTY)
map.setMap(2 * x + 1, 2 * y, MAP_ENTRY_TYPE.MAP_EMPTY)
checklist.append((x, y - 1))
elif direction == WALL_DIRECTION.WALL_RIGHT:
map.setMap(2 * (x + 1) + 1, 2 * y + 1, MAP_ENTRY_TYPE.MAP_EMPTY)
map.setMap(2 * x + 2, 2 * y + 1, MAP_ENTRY_TYPE.MAP_EMPTY)
checklist.append((x + 1, y))
elif direction == WALL_DIRECTION.WALL_DOWN:
map.setMap(2 * x + 1, 2 * (y + 1) + 1, MAP_ENTRY_TYPE.MAP_EMPTY)
map.setMap(2 * x + 1, 2 * y + 2, MAP_ENTRY_TYPE.MAP_EMPTY)
checklist.append((x, y + 1))
return True
else:
# 找不到四周有未经访问的墙（即周边的墙都已经访问过
return False
随机prim算法
def randomPrim(map, width, height): # 起始点的设置 startX, startY = (0, 0) map.setMap(2startX+0, 2startY+1, MAP_ENTRY_TYPE.MAP_START) # 终点的设置 endX, endY = (width, height) map.setMap(2endX-0, 2endY-1, MAP_ENTRY_TYPE.MAP_END)
checklist = []
checklist.append((startX, startY))
while len(checklist):
# 从checklist中选择一个随机方向的墙
entry = choice(checklist)
if not checkAdjacentPos(map, entry[0], entry[1], width, height, checklist):
# 如果四周的墙都已访问过，则把该结点位置从checklist中删除
checklist.remove(entry)
def doRandomPrim(map): # 将地图的所有结点位置都设置为墙 map.resetMap(MAP_ENTRY_TYPE.MAP_BLOCK) randomPrim(map, (map.width - 1) // 2, (map.height - 1) // 2)
def run(): WIDTH = 41 HEIGHT = 31 map = Map(WIDTH, HEIGHT) doRandomPrim(map) map.showMap()
if name == “main”: run() \end{lstlisting}
\subsection{迷宫交互设计} 完成迷宫设计后，我们利用python中的Turtle库来绘制迷宫，使用turtle库来创建游戏窗口，设置窗口大小和背景色，注册迷宫中使用到的图片资源（墙、玩家角色、迷宫入口）。
我们设计了两个类
画笔类（Pen）：
Pen类继承自t.Turtle，用于绘制迷宫。
| 在 \verb | make_maze | 方法中，根据迷宫地图绘制迷宫的墙。 |
玩家类（Player）：
Player类也继承自t.Turtle，用于控制玩家角色。
| 提供了四个方向的移动方法：\verb | go_right | , \verb | go_left | , \verb | go_up | , \verb | go_down | 。 |
在移动方法中，玩家角色会改变形状以显示移动状态，并且只有在没有撞到墙的情况下才会移动。
具体代码如下：
\begin{lstlisting}[language=python] #1.创建游戏背景 import turtle as t
import random
创建窗口
mz = t.Screen()
设置长宽
mz.setup(520,400)
设置背景色
mz.bgcolor(‘#EBEBEB’)
设置标题
mz.title(‘MoveMaze’)
使用照片前先将照片注册
mz.register_shape(‘images/wall.gif’) mz.register_shape(‘images/pr.gif’) mz.register_shape(‘images/la.gif’)
不用一步一步显示画面，最后一起显示，和mz.update()配合用
mz.tracer(0)
r_map = []
P：player;
map = [ ‘#########################################’, ‘S………….#.#…#……………….#’, ‘#.#.#####.#.###.#.###.###########.#.###.#’, ‘#.#…..#.#…..#…..#…#…..#.#…#.#’, ‘###.#####.#######.#####.###.###.#######.#’, ‘#…….#……………..#…#.#…#.#.#’, ‘###.#######################.#####.###.#.#’, ‘#………#.#…………………..#.#.#’, ‘#.#####.#.#.#.#############.#####.###.###’, ‘#.#…..#…#………….#…..#…….#’, ‘#.#####.#####.#######.###.#.#.###.#.#.#.#’, ‘#.#……………#…..#.#.#…#.#.#.#.#’, ‘#.#####.#.#.#.#############.###########.#’, ‘#.#…..#.#.#………….#………#.#.#’, ‘#.###.#.#########.#.#######.#####.###.###’, ‘#…#.#………#.#…….#…..#.#…..#’, ‘###.#.#.#.#.#.###.#.#####.#########.#.###’, ‘#…#.#.#.#.#…#.#…..#………..#.#.#’, ‘#.#.#.###.###.###.#########.#.#.#.#####.#’, ‘#.#.#.#…..#…#…..#…#.#.#.#…….#’, ‘#.#.#.#.#####.#.#.#.#.#.#######.#.#.#####’, ‘#.#.#.#…..#.#.#.#.#………#.#.#…..#’, ‘#.#.###.#####.###.#.#.#.#####.#.#.###.###’, ‘#.#…#.#…….#.#.#.#…..#.#.#…#…#’, ‘#.#.#.#.#####.###.#.#.###.#####.#.#.###.#’, ‘#.#.#.#…..#…#.#.#.#.#…#…#.#…#.#’, ‘###.#.#########.#.#.#.#.###########.#.#.#’, ‘#…#………#.#.#.#………….#.#.#.#’, ‘#.#.#.###.#####.###.#.#.###.#.###.#.#####’, ‘#.#.#…#…#…..#.#.#…#.#…#.#…..E’, ‘#########################################’, ]
r_map.append(map)
class Pen(t.Turtle): # ———–画笔————- def init(self): # 继承父类的属性 super().init() # 先隐藏起来，隐秘进行运动 self.ht() self.shape(‘images/wall.gif’) self.speed(0) self.penup()
# -----------迷宫--------------
def make_maze(self):
level = r_map[current - 1]
for i in range(len(level)):
# 取出某一行
row = level[i]
# 获取到某一元素的坐标
for j in range(len(row)):
screen_x = -244 + 12 * j
screen_y = 185 - 12 * i
char = row[j]
#如果元素为X，则画出迷宫
if char == '#':
self.goto(screen_x,screen_y)
self.stamp()
walls.append((screen_x,screen_y))#元组
elif char == 'S':
player.goto(screen_x,screen_y)
player.st()
class Player(t.Turtle): #当前位置的移动 def init(self): super().init() # 先隐藏起来，隐秘进行运动 self.ht() self.shape(‘images/pr.gif’) self.speed(0) self.penup()
# 右移
def go_right(self):
# print('going right')
self.shape('images/la.gif')
self.stamp()
go_x = self.xcor() + 12
go_y = self.ycor()
self.shape('images/pr.gif')
self.move(go_x, go_y)
# 左移
def go_left(self):
# print('going left')
self.shape('images/la.gif')
self.stamp()
go_x = self.xcor() - 12
go_y = self.ycor()
self.shape('images/pr.gif')
self.move(go_x,go_y)
# 上移
def go_up(self):
# print('going up')
self.shape('images/la.gif')
self.stamp()
go_x = self.xcor()
go_y = self.ycor() + 12
self.shape('images/pr.gif')
self.move(go_x, go_y)
# 下移
def go_down(self):
# print('going down')
self.shape('images/la.gif')
self.stamp()
go_x = self.xcor()
go_y = self.ycor() - 12
self.shape('images/pr.gif')
self.move(go_x, go_y)
# 运动时的共同行为
def move(self, go_x, go_y):
if (go_x, go_y) not in walls:
self.goto(go_x, go_y)
else:
print('撞墙了')
current = 1
调用画笔类
pen = Pen()
调用玩家
player = Player()
walls数组来存储墙的坐标
walls = []
根据不同的关卡绘制迷宫
pen.make_maze()
根据键盘移动
mz.listen() mz.onkey(player.go_right, ‘Right’) mz.onkey(player.go_left, ‘Left’) mz.onkey(player.go_up, ‘Up’) mz.onkey(player.go_down, ‘Down’)
while True: mz.update()
mz.mainloop()
\end{lstlisting}
\section{A*算法求解迷宫}
\subsection{A*算法介绍与实现}
A*算法最初发表于1968年，由Stanford研究院的Peter Hart, Nils Nilsson以及Bertram Raphael发表。它可以被认为是Dijkstra算法的扩展。
由于借助启发函数的引导，A算法通常拥有更好的性能。A吸取了Dijkstra 算法中的优点，为每个边长设置权值，不停的计算每个顶点到起始顶点的距离（G），以获得最短路线，同时也汲取贪婪最佳优先搜索算法中不断向目标前进优势，并持续计算每个顶点到目标顶点的距离（Heuristic distance），以引导搜索队列不断想目标逼近，从而搜索更少的顶点，保持寻路的高效
启发函数会影响A*算法的行为。在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。
如果h(n)始终小于等于节点n到终点的代价，则A*算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
如果h(n)完全等于节点n到终点的代价，则A算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。 如果h(n)的值比节点n到终点的代价要大，则A算法不能保证找到最短路径，不过此时会很快。 在另外一个极端情况下，如果h()n相较于g(n)大很多，则此时只有h(n)产生效果，这也就变成了最佳优先搜索。
由上面这些信息我们可以知道，通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可。这也是A*算法比较灵活的地方。
对于网格形式的图，有以下这些启发函数可以使用：
如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离（Manhattan distance）。 如果图形中允许朝八个方向移动，则可以使用对角距离。 如果图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）。
在实验中我们选择曼哈顿距离作为启发函数
具体实现如下：
\begin{lstlisting}[language=python]
-- coding: utf-8 --
import math import tkinter from tkinter import *
DrawMap生成的地图导入
tm = [ ‘#########################################’, ‘S………..#.#…..#………..#.#.#.#.#’, ‘#.#.#########.#.#####.#######.###.#.#.#.#’, ‘#…………………..#…#…..#…..#’, ‘###.#.###.#####.#########.###.#######.###’, ‘#.#.#…#…..#………….#………..#’, ‘#.#.#.###################.#.#######.#.#.#’, ‘#…#……………….#.#…….#.#.#.#’, ‘#.#.#.#####.#.#.#####.###.###.#########.#’, ‘#.#.#…..#.#.#…..#…#…#…..#.#…#’, ‘#####.#.#.###.###########.#######.#.###.#’, ‘#…..#.#…#………..#…….#…..#.#’, ‘###.#######.#.#.#####.#.#######.#########’, ‘#………#.#.#…..#.#…….#………#’, ‘#.###.#######.#########.###.#.###########’, ‘#…#…….#…#…..#…#.#………..#’, ‘#.#.#.#.#.###.#.#.###.#.#.###.#.###.#####’, ‘#.#.#.#.#…#.#…..#.#.#.#.#.#…#…#.#’, ‘#.###.#.#####.#.###.#####.#.#.#.#.#.###.#’, ‘#.#…#.#…..#…#.#…#…#.#.#.#…..#’, ‘#.#.#.#.#####.#.#####.#############.###.#’, ‘#.#.#.#…..#.#……………….#…#.#’, ‘#.#.###.#.###.#.#####.#.#######.#######.#’, ‘#.#.#…#.#…#…..#.#…….#…….#.#’, ‘#.#.#.#.#.#.#.###.#.#.###.#.#.#.#.#####.#’, ‘#.#.#.#.#.#.#.#…#.#…#.#.#.#.#…..#.#’, ‘#.#.#.#.#.#.#####.###.###.#############.#’, ‘#.#.#.#.#.#.#…#.#…#………….#.#.#’, ‘#.#######.#.#.#####.#.###.#.#########.#.#’, ‘#…#…..#…….#.#…#.#………..#.E’, ‘#########################################’, ]
存储搜索时的地图
test_map = []
开放列表和关闭列表的元素类型，parent用来在成功的时候回溯路径
class Node_Elem:
def __init__(self, parent, x, y, dist):
self.parent = parent # 回溯父节点
self.x = x # x坐标
self.y = y # y坐标
self.dist = dist # 从起点到此位置的实际距离
A*算法
class A_Star:
def __init__(self, root, s_x, s_y, e_x, e_y, w=41, h=31):
self.s_x = s_x # 起点x
self.s_y = s_y # 起点y
self.e_x = e_x # 终点x
self.e_y = e_y # 终点y
self.open = [] # open表
self.close = [] # close表
self.path = [] # path表
# 创建画布
self.root = root # 画布根节点
self.width = w # 地图w，默认41
self.height = h # 地图h，默认31
self.__r = 5 # 半径
# Tkinter.Canvas
self.canvas = tkinter.Canvas(
root,
width=self.width * 10 + 100,
height=self.height * 10 + 100,
bg="#EBEBEB", # 背景白色
xscrollincrement=1,
yscrollincrement=1
)
self.canvas.pack(expand=tkinter.YES, fill=tkinter.BOTH)
self.title("A*Maze")
self.__bindEvents()
self.new()
# 按键响应程序
def __bindEvents(self):
self.root.bind("<Return>", self.quite) # 退出程序
# 退出程序
def quite(self, evt):
self.root.destroy()
# 更改标题
def title(self, s):
self.root.title(s)
# 初始化
def new(self):
# 提示墙的颜色为黑色
node = self.canvas.create_rectangle(100 - self.__r,
20 - self.__r, 100 + self.__r, 20 + self.__r,
fill="#000000",
outline="#ffffff",
tags="node",
)
self.canvas.create_text(130, 20,
text=u'Wall',
fill='black'
)
# 提示通路的颜色为绿色
node = self.canvas.create_rectangle(200 - self.__r,
20 - self.__r, 200 + self.__r, 20 + self.__r,
fill="#00ff00",
outline="#ffffff",
tags="node",
)
self.canvas.create_text(230, 20,
text=u'Path',
fill='black'
)
# 提示按下enter键可以寻路
self.canvas.create_text(350, 20,
text=u'Enter：find way',
fill='black'
)
for i in range(self.width):
for j in range(self.height):
# 生成墙壁
if test_map[j][i] == '#':
node = self.canvas.create_rectangle(i * 10 + 50 - self.__r,
j * 10 + 50 - self.__r, i * 10 + 50 + self.__r,
j * 10 + 50 + self.__r,
fill="#000000", # 填充黑色
outline="#ffffff", # 轮廓白色
tags="node",
)
# 显示起点
if test_map[j][i] == 'S':
node = self.canvas.create_rectangle(i * 10 + 50 - self.__r,
j * 10 + 50 - self.__r, i * 10 + 50 + self.__r,
j * 10 + 50 + self.__r,
fill="#00ff00", # 填充绿色
outline="#ffffff", # 轮廓白色
tags="node",
)
self.canvas.create_text(i * 10 + 50, j * 10 + 50 - 20, # 使用create_text方法在坐标处绘制文字
text=u'Start', # 所绘制文字的内容
fill='black' # 所绘制文字的颜色为灰色
)
# 显示终点
if test_map[j][i] == 'E':
node = self.canvas.create_rectangle(i * 10 + 50 - self.__r,
j * 10 + 50 - self.__r, i * 10 + 50 + self.__r,
j * 10 + 50 + self.__r,
fill="#00ff00", # 填充绿色
outline="#ffffff", # 轮廓白色
tags="node",
)
self.canvas.create_text(i * 10 + 50, j * 10 + 50 + 20, # 使用create_text方法在坐标处绘制文字
text=u'End', # 所绘制文字的内容
fill='black' # 所绘制文字的颜色为灰色
)
# 生成通路
if test_map[j][i] == '*':
node = self.canvas.create_rectangle(i * 10 + 50 - self.__r,
j * 10 + 50 - self.__r, i * 10 + 50 + self.__r,
j * 10 + 50 + self.__r,
fill="#00ff00", # 填充绿色
outline="#ffffff", # 轮廓白色
tags="node",
)
# 查找路径的入口函数
def find_path(self):
# 构建开始节点
p = Node_Elem(None, self.s_x, self.s_y, 0.0)
while True:
# 扩展节点
self.extend_round(p)
# 如果open表为空，则不存在路径，返回
if not self.open:
return
# 取F值最小的节点
idx, p = self.get_best()
# 到达终点，生成路径，返回
if self.is_target(p):
self.make_path(p)
return
# 把此节点加入close表，并从open表里删除
self.close.append(p)
del self.open[idx]
# 生成路径
def make_path(self, p):
# 从结束点回溯到开始点，开始点的parent == None
while p:
self.path.append((p.x, p.y))
p = p.parent
# 判断是否为终点
def is_target(self, i):
return i.x == self.e_x and i.y == self.e_y
# 取F值最小的节点
def get_best(self):
best = None
bv = 10000000 # MAX值
bi = -1
for idx, i in enumerate(self.open):
value = self.get_dist(i)
if value < bv:
best = i
bv = value
bi = idx
return bi, best
# 求距离
def get_dist(self, i):
# F = G + H
# G 为当前路径长度，H为估计终点长度
return i.dist + math.sqrt((self.e_x - i.x) * (self.e_x - i.x)) + math.sqrt((self.e_y - i.y) * (self.e_y - i.y))
# 扩展节点
def extend_round(self, p):
# 上下左右四个方向移动
xs = (0, -1, 1, 0)
ys = (-1, 0, 0, 1)
for x, y in zip(xs, ys):
new_x, new_y = x + p.x, y + p.y
# 检查位置是否合法
if not self.is_valid_coord(new_x, new_y):
continue
# 构造新的节点，计算距离
node = Node_Elem(p, new_x, new_y, p.dist + self.get_cost(
p.x, p.y, new_x, new_y))
# 新节点在关闭列表，则忽略
if self.node_in_close(node):
continue
i = self.node_in_open(node)
# 新节点在open表
if i != -1:
# 当前路径距离更短
if self.open[i].dist > node.dist:
# 更新距离
self.open[i].parent = p
self.open[i].dist = node.dist
continue
# 否则加入open表
self.open.append(node)
# 移动距离，直走1.0，斜走1.4
def get_cost(self, x1, y1, x2, y2):
if x1 == x2 or y1 == y2:
return 1.0
return 1.4
# 检查节点是否在close表
def node_in_close(self, node):
for i in self.close:
if node.x == i.x and node.y == i.y:
return True
return False
# 检查节点是否在open表，返回序号
def node_in_open(self, node):
for i, n in enumerate(self.open):
if node.x == n.x and node.y == n.y:
return i
return -1
# 判断位置是否合法，超出边界或者为阻碍
def is_valid_coord(self, x, y):
if x < 0 or x >= self.width or y < 0 or y >= self.height:
return False
return test_map[y][x] != '#'
获取起点坐标
def get_start_XY(): return get_symbol_XY(‘S’)
获取终点坐标
def get_end_XY(): return get_symbol_XY(‘E’)
查找特定元素
def get_symbol_XY(s): for y, line in enumerate(test_map): try: x = line.index(s) except: continue else: break return x, y
标记路径位置
def mark_path(l): mark_symbol(l, ‘*’)
标记函数
def mark_symbol(l, s): for x, y in l: test_map[y][x] = s
标记起点和终点
def mark_start_end(s_x, s_y, e_x, e_y): test_map[s_y][s_x] = ‘S’ test_map[e_y][e_x] = ‘E’
将地图字符串转化为表
def tm_to_test_map(): for line in tm: test_map.append(list(line))
寻找路径
def find_path(): s_x, s_y = get_start_XY() e_x, e_y = get_end_XY() # A*算法 a_star = A_Star(tkinter.Tk(), s_x, s_y, e_x, e_y) a_star.root.mainloop() a_star.find_path() path = a_star.path # 标记路径位置 mark_path(path) # 标记起点和终点 mark_start_end(s_x, s_y, e_x, e_y) print(u”路径长度:%d” % (len(path))) a_star = A_Star(tkinter.Tk(), s_x, s_y, e_x, e_y) a_star.root.mainloop()
程序的入口处
if name == ‘main’: # 载入地图 tm_to_test_map() # 寻找路径 find_path() \end{lstlisting}
\subsection{复杂度分析}
时间复杂度： 在最坏情况下，如果启发式函数h(n)始终返回0（即没有提供任何有用的信息），A算法将退化为Dijkstra算法。在这种情况下，时间复杂度取决于搜索空间的规模。对于网格中的搜索，如果每个节点平均有b个邻居，并且搜索空间中有N个节点，那么最坏情况下的时间复杂度可能是$O(b^N)$。然而，这在实际应用中几乎不会发生，因为启发式函数通常会提供有用的信息来指导搜索。 在平均情况下或启发式函数提供良好估计的情况下，A算法的时间复杂度可能会显著降低。实际的时间复杂度取决于启发式函数的质量以及图的结构。
空间复杂度：
A*算法需要维护一个开放列表（open list）和一个关闭列表（closed list）。开放列表包含待探索的节点，而关闭列表包含已探索的节点。在最坏情况下，如果所有节点都需要被探索，空间复杂度可能会达到O(N)，其中N是图中节点的数量。
在实践中，通过使用有效的数据结构（如优先队列）来管理开放列表，并适时地从列表中移除不必要的节点，可以进一步优化空间复杂度。
启发式函数的影响：
如果启发式函数h(n)是可采纳的（即它从不高估从当前节点到目标的实际代价），并且是一致的（即对于任意节点n和通过任何一步到达的邻居节点$n’$，有$h(n) ≤ d(n, n’) + h(n’)$，其中$d(n, n’)$是从n到n’的实际代价），那么A*算法将保证找到最短路径。曼哈顿距离通常用作网格上的启发式函数，因为它满足这些条件。
启发式函数的质量会影响A*算法的搜索效率。一个好的启发式函数能够更准确地估计从当前节点到目标的代价，从而减少搜索所需探索的节点数量。
\end{document}