2022年11月24日 17:22:48

搜索求解

  • 是AI的基本技术之一 , 在人工智能各应用领域中被广泛地使用
  • 早期的AI程序与搜索技术联系紧密：几乎所有的（智力难题、棋类游戏、简单数学定理证明）都是以搜索为基础的
  • 现在，搜索技术已渗透在各种AI系统中，可以说没有哪一种AI应用不用搜索方法，在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都在广泛使用
  • 搜索算法——问题求解智能体
  • 智力游戏：3传教士+3野人渡河、一条船、每次2人；如何规划摆渡方案？ 可有几种方案？所用步骤是否最少——如何找到？

什么是搜索？

•根据问题的实际情况不断寻找可利用的知识，构造出一条代价较少的推理路线，使问题得到圆满解决的过程。

包括两个方面：

•找到从初始事实到问题最终答案的一条推理路径

•找到的这条路径在时间和空间上复杂度最小

状态图搜索

由于搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹font>。
必须记住下一步还可以走哪些点： OPEN表（存放待扩展的节点表）
必须记住哪些点走过了： CLOSED表（存放已扩展的节点）
必须记住从目标返回的路径
每个表示状态的节点结构中必须有指向父节点的指针
所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点（后续节点）

图的一般搜索策略

图搜索分类

对OPEN表中节点排序方式产生了不同的搜索策略， 不同的搜索搜索策略效率不同。

排序是任意的，即盲目的——盲目搜索

排序用启发信息为依据——启发式搜索

盲目式搜索

概念

对特定问题不具有任何相关信息的条件下，按照固定的步骤（依次或者随机）进行搜索，搜索过程中获得的中间信息不用来改进控制策略。一般只适用于求解比较简单的问题

种类

宽度优先（Breadth-first search）
深度优先（Depth-first search）
等代价（代价优先）搜索（Uniform-cost search）

特点

搜索过程中不使用与问题有关的经验信息
搜索效率低
不适合大空间的实际问题求解

启发式搜索

为什么需要启发式搜索？

•盲目搜索的不足

•效率低，耗费过多的计算空间与时间

•可能带来组合爆炸

•分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法, 其主要的差别是 OPEN表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。

什么可以做为启发式信息？

•启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。

启发式就是要猜测：

从节点n开始，找到最优解的可能性有多大？

从起始节点开始，经过节点n，到达目标节点的最佳路径的费用是多少

启发式搜索是利用与问题有关的启发性信息，并以这些启发性信息指导的搜索的问题求解过程。

•需定义一个评价函数，对当前的搜索状态进行评估， 找出一个最有希望的节点来扩展。

•重排OPEN表， 选择最有希望的节点加以扩展。

广度优先

宽度/广度优先搜索基本思想：

•首先扩展根节点；

•接着扩展根节点的所有后继节点；

•然后再扩展后继节点的后继，依此类推；

•在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。

深度优先

深度优先搜索基本思想：

•总是扩展搜索树的当前扩展分支中最深的节点；

•搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点；

•然后搜索算法回退到下一个还有未扩展后继节点的上层节点继续扩展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
常见错误：在得到一条成功路径之后就结束
记录[]，路径[]
dfs(起始，末尾)：
if(当前=末尾){
进行结束操作
}
for(i=1;i<n;i++){
	if(符合要求){
	记录，记录路径
	dfs
	清空记录
	清空记录的路径
	}
}

A*算法

有序搜索，也称优先搜索/全局择优， 选择OPEN表上具有最小 f 值的节点作为下一个要扩展的节点。

维基解释：

迪杰斯特拉（Dijkstra）算法

一个很好的讲解博客

Dijkstra 算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法，时间复杂度 O(n2)

等代价搜索(Uniform-cost Search)

BFS的扩展版本：Expand node with lowest path cost
1959年由Dijkstra（迪科斯彻）提出——Dijkstra算法
基本思想：
是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。
状态图中每条连接弧线上的有关代价，表示时间、距离等开销。
节点代价的定义：
g (n)： 表示从初始节点 S。到节点n的代价；
c (n1, n2) : 表示从父节点 n1 到其子节点 n2 的代价；
g (n2) = g (n1) + c ( n1 ,n2)

《算法图解》

1
2
3
4
5
狄克斯特拉算法包含4个步骤。
(1) 找出最便宜的节点，即可在最短时间内前往的节点。
(2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。

实验要求

本实验要求用广度优先算法、深度优先算法和A*算法求解“罗马尼亚度假问题”，即找到从初始地点 Arad到目的地点 Bucharest 的一条最佳路径

1.给出各种搜索算法得到的具体路径、相应的代价、经过的节点数、open表和close表

2.这几种方法效果做对比，例如时间维度

加分项：交互性界面，可自选出发地和目标地

图为罗马尼亚的地图，上面也显示了各个城市之间的代价值

原理

广度优先搜索

从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点，找到目标节点或完全遍历结束。

深度优先搜索

从图中一个未访问的顶点 V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到找到目标节点或所有的顶点都遍历完成。

A* 算法

通过下面这个函数来计算每个节点的优先级：

​ f(n) = g(n) + h(n)

其中：

•f(n)是节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。

•g(n) 是节点n距离起点的代价。

h(n)是节点n距离终点的预计代价，这也就是A*算法的启发函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
while(OPEN!=NULL)
{
    从OPEN表中取f(n)最小的节点n;
    if(n节点==目标节点)
        break;
    for(当前节点n的每个子节点X)
    {
        计算f(X);
        if(XinOPEN)
            if(新的f(X)<OPEN中的f(X))
            {
                把n设置为X的父亲;
                更新OPEN表中的f(n);
            }
        if(XinCLOSE)
            continue;
        if(Xnotinboth)
        {
            把n设置为X的父亲;
            求f(X);
            并将X插入OPEN表中;//还没有排序
        }
    }//endfor
    将n节点插入CLOSE表中;
    按照f(n)将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}//endwhile(OPEN!=NULL)

实验代码&结果

文件：

citymap.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Arad Zerind 75 Timisoara 118 Sibiu 140
Bucharest Urziceni 85 Giurgiu 90 Pitesti 101 Fagaras 211
Craiova Drobeta 120 Pitesti 138 Rimnicu 146
Drobeta Mehadia 75 Craiova 120
Eforie Hirsova 86
Fagaras Sibiu 99 Bucharest 211
Giurgiu Bucharest 90
Hirsova Eforie 86 Urziceni 98
Iasi Neamt 87 Vaslui 92
Lugoj Mehadia 70 Timisoara 111
Mehadia Lugoj 70 Drobeta 75
Neamt Iasi 87
Oradea Zerind 71 Sibiu 151
Pitesti Rimnicu 97 Bucharest 101 Craiova 138
Rimnicu Sibiu 80 Pitesti 97 Craiova 146
Sibiu Rimnicu 80 Fagaras 99 Arad 140 Oradea 151
Timisoara Lugoj 111 Arad 118
Urziceni Bucharest 85 Hirsova 98 Vaslui 142
Vaslui Iasi 92 Urziceni 142
Zerind Oradea 71 Arad 75

cityname.txt

1
2
Arad, Bucharest, Craiova,Drobeta, Eforie, Fagaras,Giurgiu, Hirsova, Iasi,Lugoj, Mehadia, 
Neamt,Oradea, Pitesti, Rimnicu,Sibiu, Timisoara, Urziceni,Vaslui, Zerind

dis_info.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Arad=(91, 492)
Bucharest=(400, 327)
Craiova=(253, 288)
Drobeta=(165, 299)
Eforie=(562, 293)
Fagaras=(305, 449)
Giurgiu=(375, 270)
Hirsova=(534, 350)
Iasi=(473, 506)
Lugoj=(165, 379)
Mehadia=(168, 339)
Neamt=(406, 537)
Oradea=(131, 571)
Pitesti=(320, 368)
Rimnicu=(233, 410)
Sibiu=(207, 457)
Timisoara=(94, 410)
Urziceni=(456, 350)
Vaslui=(509, 444)
Zerind=(108, 531)

导入库

1
2
3
4
5
6
import functools
import time
import math
import numpy as np
import matplotlib.pyplot as plt
from queue import PriorityQueue #优先队列

导入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class city(object):  # 每一个城市的信息
    def __init__(self, name, coordination):
        self.name = name  # 城市名
        self.coordination=coordination
        #self.nextnum=0
        self.nextcity=[]

class neighbour(object):#邻居
    def __init__(self,name,dist,point=()):
        self.name=name
        self.dist=dist
        self.predict=1e5
        self.state=False #是否已遍历，相当于将数据分到close表或open表
        self.beforcity=""
        self.point=point
file1="./cityname.txt"
file2="./dis_info.txt"
f = open(file1, 'r')
info=f.read()
f.close()
info
txt_info=[]
f = open(file2, 'r')
line = f.readline() # 读取第一行
while line:
    #txt_data = eval(line) # 可将字符串变为元组
    txt_info.append(line.replace("\n","")) # 列表增加
    line = f.readline() # 读取下一
#print(txt_info)
f.close()

cityList=[]
for info in txt_info:
    info=info.split("=")
    cityList.append(city(info[0],eval(info[1])))

可视化地图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
x_list=[]
y_list=[]
txt_list=[]
for tmp in cityList:
    txt_list.append(tmp.name)
    x_list.append(tmp.coordination[0])
    y_list.append(tmp.coordination[1])

#type(txt_list[1])
#可视化
import matplotlib.pyplot as plt
plt.figure(dpi=300,figsize=(8,8))
plt.scatter(x_list, y_list)
for i in range(len(y_list)):
    plt.annotate(txt_list[i], xy = (x_list[i], y_list[i]), xytext = (x_list[i]+1, y_list[i]+1)) # 这里xy是需要标记的坐标，xytext是对应的标签坐标
plt.show()

​

导入城市之间的相连信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
file3="./citymap.txt"
f = open(file3, 'r')
info=f.read()
f.close()
#info
#读取相邻节点
f = open(file3, 'r')#存相邻节点
line = f.readline() 
while line:
    tmp_list=line.replace("\n","").split(" ")
    tmpobject = [x for x in cityList if x.name == tmp_list[0]][0]
    for i in range(1,len(tmp_list),2):
        tmpobject.nextcity.append(neighbour(tmp_list[i],eval(tmp_list[i+1])))
    line = f.readline() # 读取下一行
f.close()

清除状态函数

1
2
3
4
5
6
def clearState(citylist):
    for city in citylist:
        tmp=city.nextcity
        for nei in tmp:
            nei.state=False
clearState(cityList)

利用dfs找到一个解就返回

1
2
3
4
record.append("Arad")
disrecord.append(0)
#dfs("Arad","Bucharest")
dfs("Arad","Bucharest")

修改起始和终点时
首先改变append中的城市名
其次更改dfs中的城市名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
clearState(cityList)
st = time.clock()
record=[]
disrecord=[]
def dfs(begin,end):#寻找一个符合要求的路径
    if begin==end:
        #print("!"*100)
        return
    currNeighbours = [x for x in cityList if x.name == begin][0].nextcity
    for curr in currNeighbours:
        if end in record:
            return
        if curr.state==True:
            continue
        else:
            curr.state=True
            if curr.name in record:
                continue
            #print("现在插入",curr.name)
            record.append(curr.name)
            disrecord.append(curr.dist)
            dfs(curr.name,end)
            if end in record:
                return
            record.pop(-1)
            disrecord.pop(-1)
    if currNeighbours[-1].state==True:
        record.pop(-1)
        disrecord.pop(-1)
        dfs(record[-1],end)
record.append("Arad")
disrecord.append(0)
#dfs("Arad","Bucharest")
dfs("Arad","Bucharest")
cost = time.clock()-st
print("路径",record)
print(disrecord)
print("路径总长度",sum(disrecord))
print("运行时间：",cost)
路径 ['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
[0, 75, 71, 151, 80, 97, 101]
路径总长度 575
运行时间： 0.00020789999999999998

利用dfs寻找所有的解

1
2
3
4
record.append("Arad")#如果起始值是什么就填什么
disrecord.append(0)
#dfs("Arad","Bucharest")
dfs("Arad","Sibiu")

操作同上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
clearState(cityList)
st = time.clock()


finalRecord=[]
finalDist=[]
record=[]
disrecord=[]
def dfs(begin,end):
    if begin==end:
        finalRecord.append(record[:])
        finalDist.append(disrecord[:])
        #print("!"*100)
        return
    currNeighbours = [x for x in cityList if x.name == begin][0].nextcity
    for curr in currNeighbours:
        if curr.state==True or curr.name in record:
            continue
        else:
            curr.state=True
            #print("现在插入",curr.name)
            record.append(curr.name)
            disrecord.append(curr.dist)
            dfs(curr.name,end)
            #print("现在弹出   ",record[-1],"   距离：",disrecord[-1])
            curr.state=False
            record.pop(-1)
            disrecord.pop(-1)
#     if currNeighbours[-1].state==True and currNeighbours[-1].name in record:
#         #print("!!!!!!!!!!!!现在弹出   ",record[-1],"   距离：",disrecord[-1])
#         record.pop(-1)
#         disrecord.pop(-1)
#         dfs(record[-1],end)
record.append("Arad")
disrecord.append(0)
dfs("Arad","Bucharest")
# dfs("Arad","Sibiu")
cost = time.clock()-st
# print(finalRecord)
# print(finalDist)
print("DFS所有可行路径：")
sumdis=[]
for i in range(len(finalRecord)):
    print(finalRecord[i])
    print("该路径长度：",sum(finalDist[i]))
    sumdis.append(sum(finalDist[i]))
    print('-'*100)
minindex=sumdis.index(min(sumdis))
print("最短路径是：",finalRecord[minindex])
print("长度为：",sumdis[minindex])

print("运行时间：",cost)
DFS所有可行路径：
['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
该路径长度： 575
----------------------------------------------------------------------------------------------------
['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Rimnicu', 'Craiova', 'Pitesti', 'Bucharest']
该路径长度： 762
----------------------------------------------------------------------------------------------------
['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 607
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Rimnicu', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 1119
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Bucharest']
该路径长度： 733
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 1030
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu', 'Pitesti', 'Bucharest']
该路径长度： 838
----------------------------------------------------------------------------------------------------
['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
该路径长度： 418
----------------------------------------------------------------------------------------------------
['Arad', 'Sibiu', 'Rimnicu', 'Craiova', 'Pitesti', 'Bucharest']
该路径长度： 605
----------------------------------------------------------------------------------------------------
['Arad', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 450
----------------------------------------------------------------------------------------------------
最短路径是： ['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
长度为： 418
运行时间： 0.0004011999999997684

利用BFS求全局最小解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
clearState(cityList)
st = time.clock()
def BFS(begin,end):
    finalRecord=[]
    finalDist=[]
    record=[]
    disrecord=[]
    record.append([begin])
    disrecord.append([0])
    while len(record)!=0:
        tmprecord=record.pop(0)
        tmpdis=disrecord.pop(0)
        if end in tmprecord:
            finalRecord.append(tmprecord[:])
            finalDist.append(tmpdis[:])
            continue
        currcity=tmprecord[-1]#当前扩展的节点
        currNeighbours = [x for x in cityList if x.name == currcity][0].nextcity
        for nei in currNeighbours:
            if nei.name in tmprecord:
                continue
            tmprecord.append(nei.name)
            tmpdis.append(nei.dist)
            record.append(tmprecord[:])
            disrecord.append(tmpdis[:])
            tmprecord.pop(-1)
            tmpdis.pop(-1)
#     print(finalRecord)
#     print(finalDist)
#     print(len(finalRecord))
    print("BFS所有可行路径：")
    sumdis=[]
    for i in range(len(finalRecord)):
        print(finalRecord[i])
        print("该路径长度：",sum(finalDist[i]))
        sumdis.append(sum(finalDist[i]))
        print('-'*100)
    minindex=sumdis.index(min(sumdis))
    print("最短路径是：",finalRecord[minindex])
    print("长度为：",sumdis[minindex])
        
BFS("Arad","Bucharest")
cost = time.clock()-st
print("运行时间：",cost)
BFS所有可行路径：
['Arad', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 450
----------------------------------------------------------------------------------------------------
['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
该路径长度： 418
----------------------------------------------------------------------------------------------------
['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 607
----------------------------------------------------------------------------------------------------
['Arad', 'Sibiu', 'Rimnicu', 'Craiova', 'Pitesti', 'Bucharest']
该路径长度： 605
----------------------------------------------------------------------------------------------------
['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
该路径长度： 575
----------------------------------------------------------------------------------------------------
['Arad', 'Zerind', 'Oradea', 'Sibiu', 'Rimnicu', 'Craiova', 'Pitesti', 'Bucharest']
该路径长度： 762
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Bucharest']
该路径长度： 733
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu', 'Pitesti', 'Bucharest']
该路径长度： 838
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 1030
----------------------------------------------------------------------------------------------------
['Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Rimnicu', 'Sibiu', 'Fagaras', 'Bucharest']
该路径长度： 1119
----------------------------------------------------------------------------------------------------
最短路径是： ['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
长度为： 418
运行时间： 0.0014346000000005077

1
2
3
4
5
6
7
8
9
10
def getdis(city1,city2):#获得两城市之间的直线距离,传的是元组
    return math.sqrt((city1[0]-city2[0])**2+(city1[1]-city2[1])**2)

#想为Dijkstra重新设计一个数据结构，发现neighbour刚好满足！
# class neighbour(object):#邻居
#     def __init__(self,name,dist):
#         self.name=name
#         self.dist=dist
#         self.state=False #是否已遍历    
#print(getdis((1,2),(2,3)))

Dijkstra求最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
st = time.clock()
def Dijkstra(begin,end):
    recordlist=[]
    #初始化recordlist
    for city in cityList:
        recordlist.append(neighbour(city.name,1e3))
    curr = [x for x in recordlist if x.name == begin][0]
    curr.dist=0
#     for rr in recordlist:
#         print(rr.name,rr.dist)
    
    #print(curr.name)
    for _ in range(len(recordlist)):
        #寻找最短且未打标记的路径
        mindis=1e3
        mincity=""
        for city in recordlist:
            if city.state==False:
                if city.dist<mindis:
                    mindis=city.dist
                    mincity=city.name
        if mincity==end:#如果已经找到就直接退出#利用栈的结构，将结果输出
            printlist=[]
            printlist.append(mincity)
            tmpfinal=[x for x in recordlist if x.name == mincity][0]
            finalmindis=tmpfinal.dist
    #             while
    #             print("最短路径",printlist)
            while tmpfinal.name!=begin:
                printlist.append(tmpfinal.beforcity)
                tmpfinal=[x for x in recordlist if x.name == tmpfinal.beforcity][0]          
            #print("找到了！")
            printlist=list(reversed(printlist))
            print(printlist)
            print("长度为：",finalmindis)
            break
        else:
            #print("当前扩展节点",mincity)
            curr = [x for x in recordlist if x.name == mincity][0]
            curr.state=True
            currNeighbours = [x for x in cityList if x.name == mincity][0].nextcity
            for tmpneighbour in currNeighbours:
                tmpnei= [x for x in recordlist if x.name == tmpneighbour.name][0]
                if tmpnei.state==False and curr.dist+ tmpneighbour.dist < tmpnei.dist:
                    tmpnei.dist=curr.dist+ tmpneighbour.dist
                    tmpnei.beforcity=mincity
                    #print(tmpnei.name)
#         for rr in recordlist:
#             print(rr.name,rr.dist,rr.state)
#        print("-"*20)
                 
            
Dijkstra("Arad","Bucharest")
cost = time.clock()-st
print("运行时间：",cost)
['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
长度为： 418
运行时间： 0.0009341000000002708

1
2
3
4
5
6
7
8
9
10
#手写一个优先队列，库函数的不能满足要求
# q=PriorityQueue()
# q.put((2,'a'))
# q.put((2.22,'b'))
# q.put((1,'c'))
# while not q.empty():
#     next_item=q.get()
#     print(next_item)
# print('-'*10)
# print(q.get())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
st = time.clock()
def astar(begin,end):
    recordlist=[]
    #初始化recordlist
    for city in cityList:
        recordlist.append(neighbour(city.name,1e4,city.coordination))
    finalpoint=[x for x in recordlist if x.name == end][0].point#记录目标终点的坐标
    curr = [x for x in recordlist if x.name == begin][0]
    curr.dist=0
    curr.predict=getdis(curr.point,finalpoint)
    for _ in range(len(recordlist)):
        #寻找最短且未打标记的路径
        currmincity=None
        #先对队列进行排序
        recordlist.sort(key=lambda x:x.predict)
        for city in recordlist:
            if city.state==False:
                    currmincity=city
                    break
        if currmincity.name==end:#如果已经找到就直接退出#利用栈的结构，将结果输出
            printlist=[]
            printlist.append(currmincity.name)
            finalmindis=currmincity.dist
            tmpfinal=currmincity
            while tmpfinal.name!=begin:
                printlist.append(tmpfinal.beforcity)
                tmpfinal=[x for x in recordlist if x.name == tmpfinal.beforcity][0]          
            #print("找到了！")
            printlist=list(reversed(printlist))
            print(printlist)
            print("长度为：",finalmindis)
            break
        else:
            #print("当前扩展节点",mincity)
            curr = currmincity
            curr.state=True
            currNeighbours = [x for x in cityList if x.name == currmincity.name][0].nextcity
            for tmpneighbour in currNeighbours:
                tmpnei= [x for x in recordlist if x.name == tmpneighbour.name][0]
                newpredict=getdis(tmpnei.point,finalpoint)
                if tmpnei.state==False and curr.dist+ tmpneighbour.dist+ newpredict < tmpnei.predict:
                    tmpnei.predict=curr.dist+ tmpneighbour.dist+ newpredict
                    tmpnei.dist=curr.dist+ tmpneighbour.dist
                    tmpnei.beforcity=currmincity.name
astar("Arad","Bucharest")    
cost = time.clock()-st
print("运行时间：",cost)     
['Arad', 'Sibiu', 'Rimnicu', 'Pitesti', 'Bucharest']
长度为： 418
运行时间： 0.0006135999999994368