前言：这个是我人工智能导论的作业（作业报告），参考了网上一些资料。写的不太全。两个算法的思路我没写，具体写的是代码实现思路和用Python的细节。 

一，Dijstra算法

案例：求从Arad到Bucharest两地的最短距离

代码：

# -*- coding: utf-8 -*-
"""
Created on Mon Aug 16 18:02:58 2021

@author: mxp
"""
from collections import deque
#使用宏定义第一个最大值inf代表着无穷大
INFINITY = float("inf")

#map.txt文件中数据的处理应该绘制无向图，因而得读入两遍的数据

class Graph:
    def __init__(self,filename):#将地图建成一个邻接表
        
        graph_edges=[]#边的长度
        with open(filename) as fhandle:#读取文件，一行一行的读
            for line in fhandle:
                if line=="\n":#读取截止条件，注意必须加否则会报错
                    break
                #将map.txt文件中的数据按空格分离并存储，*_代表这一行后面所有的元素。
                edge_from,edge_to,cost,*_=line.strip().split(" ")
                graph_edges.append((edge_from,edge_to,cost))#以元组的形式加入到graph_edges
        #建立节点，set() 函数创建一个无序不重复元素集，
        #可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。
        self.nodes =set()
        for edge in graph_edges:
            #初始化节点
            #update() 方法用于修改当前集合，可以添加新的元素或集合到当前集合中，
            #如果添加的元素在集合中已存在，则该元素只会出现一次，重复的会忽略。
            self.nodes.update([edge[0],edge[1]])
        #建立邻接表
        self.adjacency_list = {node: set() for node in self.nodes}
        for edge in graph_edges:
           #字典中的键表示图中的节点，而键值则是以字典的形式存在里面包括几组一元组的形式储存的
           #表示可达到节点以及权值
           self.adjacency_list[edge[0]].add((edge[1],edge[2]))
    def shortest_path(self, start_node, end_node):
        #使用Dijkstra算法找到从起始点到终点的最短路径，返回（path,distance）

        #创造一个未访问节点的集合初始化为所有节点
        unvisited_nodes = self.nodes.copy()  
        #创建一个字典表示每个点到起始点的距离，每个点先初始化为inf除了点本身初始化为0
        #当我们找到一个更短路径的时候更新这个字典所对应的值，数据结构为 节点：距离
        distance_from_start = {
            node: (0 if node == start_node else INFINITY) for node in self.nodes
        }

        #初始化前置节点也就是用来寻找路径的方法，结构为节点：节点其中后面的节点是前面
        #的前置节点，由此可以一步步找到路径，如果找到更短路径就更新这个字典
        previous_node = {node: None for node in self.nodes}
        while unvisited_nodes:
            #将当前节点设置为到目前为止在未访问节点这个字典中路径最短的节点
            current_node = min(
                #从unvisited_nodes中找到键值最小的节点作为当前节点
                unvisited_nodes, key=lambda node: distance_from_start[node]
            )
            #从未访问的节点中，移除当前节点
            unvisited_nodes.remove(current_node)
            #如果当前节点的距离为无穷大，则其余未访问的节点不会连接到开始节点，停止
            if distance_from_start[current_node] == INFINITY:
                break

            #遍历每个当前节点的邻居，检查一下从起始节点到当前节点再到邻居节点的距离的大小
            #与distance_form_start中的比较看看是否更小，是讲究更新distance中所对应的值
            for neighbor, distance in self.adjacency_list[current_node]:
                #新的路径的距离
                new_path = distance_from_start[current_node] + int(distance)
                if new_path < distance_from_start[neighbor]:
                    distance_from_start[neighbor] = new_path#更新值
                    previous_node[neighbor] = current_node#更新路径，将当前节点作为邻居的前置节点

        #为了找到我们所建立的最短路径，使用迭代器遍历每个点的前置节点即可找到路径
        #并且把他存入一个队列中之所以可以保证找得到前置节点，是因为算法完成时候每个点的前置节点都代表着
        #到起始点的最短路径
        path = deque()
        current_node = end_node
        while previous_node[current_node] is not None:
            path.appendleft(current_node)
            current_node = previous_node[current_node]
        path.appendleft(start_node)
        return path, distance_from_start[end_node]


def main():
    dijkstra(
        filename="map.txt",
        start="Arad",
        end="Bucharest",
        path=[],
        distance=12,
    )

def dijkstra(filename, start, end, path, distance):
    graph = Graph(filename)
    returned_path, returned_distance = graph.shortest_path(start, end)
    print('  地图  来源: {0}'.format(filename))
    print('终点，目的地: {0} -> {1}'.format(start, end))
    print('    最短路径: {0}'.format(returned_path))
    print('    路径大小: {0}'.format(returned_distance))


if __name__ == "__main__":
    main()
        
        
        

算法思路：略

代码思路：

1.数据处理：

所给的地图是无向带权图，故而用邻接表来表示图，也就是adjacency_list。Map.txt文档中数据结构是：Arad Zerind 118。这样的结构只能表示Arad->Zerind如果都是这样处理数据就变成有向图，因此得再加入Zerind Arad 118使得两边都可以连通整个图变成了无向图了。

数据处理后的样例：

Arad Zerind 75 
Arad Timisoara 118 
Arad Sibiu 140 
Zerind Oradea 71 
Oradea Sibiu 151 
Timisoara Lugoj 111

2.实现思路：

Dijstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

算法开始建立一个unvisited_nodes即未访问的节点集合初始化为全体节点，distance_from_start字典中表示键表示节点而其中的值表示起点到该节点的距离初始化为除了起始节点为0，其他为无穷大也就是inf，previous_node字典的键表示当前节点，值表示前一个节点，初始化为节点：None。

下一步是一个循环开始更新前面三个集合。首先遍历未访问的节点先设置一个当前节点，这个节点更新为distance_from_start中值最小的节点，然后遍历邻接表以当前节点为索引，访问当前节点的邻居neighbor和到其的距离，并将从起始节点到当前节点再到邻居节点的new_path的总值与distance_from_start中所存储的到neighbor的值比较，如果new_path的值更小则更新这个值，并且记录下这个路径，即把neighbor连在当前节点的后面形成新的路径，全部遍历完成即找到最短路径

之后再用一个队列的结构储存路径，方法是在previous_node中通过截止节点找前置节点，一直找到开始节点前一个。详细见代码注释。

运行结果：

 终点/目的地: Arad -> Bucharest
 最短路径: deque(['Arad', 'Sibiu', 'Rimmicu_Vilcea', 'Pitesti', 'Bucharest'])
 路径大小: 418

参考： https://www.dougmahugh.com/dijkstra/

二 ，A*算法实现

 代码：

# -*- coding: utf-8 -*-
"""
Created on Sun Nov  7 14:16:46 2021

@author: mxp
"""

from queue import PriorityQueue#优先队列，详细见Priority.py中
from collections import deque
import math

#从结果来看我所设置的启发式函数h*(n)>d(n),搜索速度快但不一定是最短路径
#当h*(n)<d(n),搜索速度慢但一定是最短路径，当h*(n)为零的时候即为dijstra算法
#h*(n)=d(n)的时候速度最快并且所找到的路径一定为最短路径。 `

class Graph:
    def __init__(self,filename1):#将地图建成一个邻接矩阵
        #self相当于这个类自己，self表示类的属性
        graph_edges=[]#边的长度
        with open(filename1) as fhandle:#读取文件，一行一行的读
            for line in fhandle:
                if line=="\n":#读取截止条件，注意必须加否则会报错
                    break
                #将map.txt文件中的数据按空格分离并存储，*_代表这一行后面所有的元素。
                edge_from,edge_to,cost,*_=line.strip().split(" ")
                graph_edges.append((edge_from,edge_to,cost))#以元组的形式加入到graph_edges
                
                
        #建立节点，set() 函数创建一个无序不重复元素集，
        #可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。
        self.nodes =set()
        for edge in graph_edges:
            #初始化节点
            #update() 方法用于修改当前集合，可以添加新的元素或集合到当前集合中，
            #如果添加的元素在集合中已存在，则该元素只会出现一次，重复的会忽略。
            self.nodes.update([edge[0],edge[1]])
        #建立邻接表
        self.adjacency_list = {node: set() for node in self.nodes}
        for edge in graph_edges:
           #字典中的键表示图中的节点，而键值则是以字典的形式存在里面包括几组以元组的形式储存的
           #表示可达到节点以及权值
           self.adjacency_list[edge[0]].add((edge[1],edge[2]))
           

             
    def shortest_path(self, start_node, end_node,filename2):
        frontier = PriorityQueue()#建立一个优先队列，效果是按照优先级出队列，这里的优先级是按照第一个参数priority
        frontier.put([0, start_node])#起点入队列，priority是这个节点的f()函数
        came_from = dict()#建立一个字典储存路径，方式是 节点：节点
        cost_so_far = dict()#建立一个字典储存从起始节点到该节点所花费的代价,这个是一个确定值
        came_from[start_node] = None
        cost_so_far[start_node] = 0#初始化起点的前一个节点为None，代价为0
        graph_node_xy={}#建立一个字典储存节点在坐标系的位置
        
        #读取保存了节点名字与x，y坐标的文件，并且把他放在graph_x_y中
        with open(filename2) as fhandle:
             for line in fhandle:
                if line=="\n":#读取截止条件，注意必须加否则会报错
                    break
                node,node_x,node_y,*_=line.strip().split(" ")
                # node_x=int(node_x)
                # node_y=int(node_y)#处理比例
                # node_x-=100
                # node_y-=100
                graph_node_xy[node]=(node_x,node_y)
        #k是一个比例系数，将图中两地的距离的长度与其所对应的权值相比，可以确定图中任意两点的权值。
        k=Graph.heuristic(self,"Arad","Zerind",graph_node_xy)/140
        #print(k)
        while not frontier.empty():
           current = frontier.get()[1]#优先队列取最小值作为当前节点
           if current == end_node:#如果当前节点为终点，break
              break
          #从邻接表中获取当前点的邻居节点以及他们之间的权值
           for next,distance in self.adjacency_list[current]:
              #邻居节点新的花费为从当前节点作为周转点到这个节点的花费，也就是当前节点的花费加上两个节点之间的距离
              new_cost = cost_so_far[current] + int(distance)
              #如果当前节点不在cost_so_far中或者new_cost小于cost_so_far[next]，更新cost_so_far[next]，并且重新计算f（）函数
              if next not in cost_so_far or new_cost < cost_so_far[next]:
                 cost_so_far[next] = new_cost
                 priority = new_cost + Graph.heuristic(self,end_node,next,graph_node_xy)*k#f(n)=g(n)+h(n);
                 frontier.put([priority, next])#将next入队列
                 came_from[next] = current#记录路径

        path = deque()#建造一个队列
        current_node = end_node
        while came_from[current_node] is not None:#找到None截止
            path.appendleft(current_node)#入栈
            current_node = came_from[current_node]#更新当前节点，更新值为前一个节点
        path.appendleft(start_node)#将起始节点加入路径中
        return path, cost_so_far[end_node]
    
    
    def heuristic(self,end_node,next,graph_node_xy):
        #这里我用的估计函数是欧几里得距离也就是图中两点之间距离
        #也可以用曼哈顿距离
        a=int(graph_node_xy[end_node][0])-int(graph_node_xy[next][0])
        b=int(graph_node_xy[end_node][1])-int(graph_node_xy[next][1])
        return math.sqrt(a*a+b*b)
        #return abs(a)+abs(b)
        
        
def main():
    A(
        filename1="map.txt",
        filename2="map_x_y.txt",
        start="Arad",
        end="Bucharest",
        path=[],
        distance=12,
    )

def A(filename1,filename2,start, end, path, distance):
    graph = Graph(filename1)
    returned_path, returned_distance = graph.shortest_path(start, end,filename2)
    print('  终点/目的地: {0} -> {1}'.format(start, end))
    print('    最短路径: {0}'.format(returned_path))
    print('    路径大小: {0}'.format(returned_distance))


if __name__ == "__main__":
    main()
        
        
        
     

算法思路： 

简单的说就用F*(n)=h*(n)+g*(n)这个函数。

A*算法中F*（n）=H*(n)+G*(n),其中H*（n）是估计函数，估算的是从当前节点到终点的花费cost，是一个估计值；而G*（n）代表着从起点到当前节点的花费，是一个确定值，两者相加则是F*（n）。

算法先从起点开始遍历附近的每一个节点，并且更新这些节点的F*（n）值选取有最小F*(n)值节点，更新当前节点为此节点，并且更新之前的节点放进一个集合里，记录路径。直至找到终点。

估计函数H*（n）这里我用的是欧几里得距离，可供选择的方法还有曼哈顿函数等

欧几里得距离就是图中两点中的直线距离，而曼哈顿距离是图中两点横纵坐标差值的绝对值

代码实现：

1.数据处理：

如同dijstra算法中一样，现将无向图以邻接表的方式储存（map.txt）。此外为了确立估计函数我在这个地图上建立直角坐标系（见map.py文件），并将图上的每一个点的横纵坐标记录下来（map_x_y.txt）

 

2.代码实现思路：

 与dijstra相同，先定义了一个class Graph处理数据并且设置了一个求最短路径和长度的函数。其中我把处理节点x，y值的代码放在shortest_path中（我把这个放在init函数会报错，我也不知道为啥）。具体代码功能参考A.py代码旁边的注释。

3.注意事项：

算法的执行结果找到的路径是否是最短路径以及算法运行的效率与H（n）这个函数有关。当h*(n)>d(n),搜索速度快，但不一定是最短路径

当h*(n)<d(n),搜索速度慢，但一定是最短路径，当h*(n)为零的时候即为dijstra算法

h*(n)=d(n)的时候速度最快并且所找到的路径一定为最短路径。

也就是一定要保证所设置的启发式函数的数值小于等于实际距离。

4.运行结果： 

 终点/目的地: Arad -> Bucharest
 最短路径: deque(['Arad', 'Sibiu', 'Rimmicu_Vilcea', 'Pitesti', 'Bucharest'])
 路径大小: 418

参考：https://www.redblobgames.com/pathfinding/a-star/introduction.html