人工智能——罗马利亚问题

题目：

根据上图以Zerind为初始状态，Bucharest为目标状态实现搜索，分别以贪婪搜索（只考虑直线距离）和A_plus算法求解最短路径。 按顺序列出贪婪算法探索的扩展节点和其估价函数值，A_plus算法探索的扩展节点和其估计值。

题目解析：
1.构建罗马利亚图
2.构建到B城市的直线距离
3.实现贪婪算法
4.实现A*算法
5.对所求路径及总长度进行输出

代码：

# 罗马利亚图存储
city_graph = [['A', 'Z', 75],['A', 'T', 118],['Z', 'O', 71],['O', 'S', 151],['A', 'S', 140],['S', 'F', 99],['S', 'R', 80],['R', 'P', 97],['R', 'C', 146],['T', 'L', 111],['L', 'M', 70],['M', 'D', 75],['D', 'C', 120],['C', 'P', 138],['P', 'B', 101],['F', 'B', 211],['B', 'G', 90],['B', 'U', 85],['U', 'V', 142],['V', 'I', 92],['I', 'N', 87],['U', 'H', 98],['H', 'E', 86]]
# B到其他城市的直线距离
to_B_distance = {'A': 366,'B': 0,'C': 160,'D': 242,'E': 161,'F': 176,'G': 77,'H': 151,'I': 226,'L': 244,'M': 241,'N': 234,'O': 380,'P': 100,'R': 163,'S': 253,'T': 329,'U': 80,'V': 199,'Z': 374}
start_city = 'Z'
end_city = 'B'
# 判断某条路是否走过
def is_visited(A_city, B_city, went_road):for i in range(len(went_road)):if went_road[i][0] == A_city and went_road[i][1] == B_city:return 1if went_road[i][0] == B_city and went_road[i][1] == A_city:return 1return 0
# 根据访问结点打印结果
def print_ans(ans, distance):print("路径为：", end="")for i in range(len(ans)):if i != len(ans) - 1:print(ans[i], "->", end="")else:print(ans[i])print("路径长度之和为：",distance)
# 贪婪算法，每次寻找离目标城市直线距离最短的城市走
def greedy(start, end):print("贪婪算法：")went_road = []ans_road = [start]while 1:# 查找开始结点的所有临近城市及边start_near_city = []for item in city_graph:if item[0] == start:start_near_city.append([item[1], item[2]])if item[1] == start:start_near_city.append([item[0], item[2]])# 挑选到目标结点直接距离最短的城市direct_distance = 999for item in start_near_city:if to_B_distance[item[0]] < direct_distance and is_visited(start, item[0], went_road) == 0:direct_distance = to_B_distance[item[0]]min_distance = item[1]min_city = item[0]# 如果找到一条直线距离最短的路且没有访问过，则选择走这条路并记录走过的这条路if direct_distance != 999:went_road.append([start, min_city, min_distance])print(min_city, direct_distance)start = min_cityans_road.append(start)else:print("终点不可达！")return 0# 找到终点返回路径及总长度if start == end:ans_distance = 0for i in range(len(went_road)):ans_distance += went_road[i][2]print_ans(ans_road, ans_distance)return 1
# A*算法，每次寻找f=g+h最小的值走
def A_plus(start, end):print("A*算法：")went_road = []ans_road = [start]while 1:# 扫描图，获取与start相连的所有边go_to_city = []for item in city_graph:if item[0] == start:go_to_city.append([item[1], item[2]])if item[1] == start:go_to_city.append([item[0], item[2]])# 寻找fx最小的可达城市和距离，不能走回访问过的路hx = 0for j in went_road:hx += j[2]fx_distance = 999for item in go_to_city:if hx+item[1]+to_B_distance[item[0]] < fx_distance and is_visited(start, item[0], went_road) == 0:fx_distance = hx+item[1]+to_B_distance[item[0]]min_distance = item[1]min_city = item[0]# 如果找到可达的最小城市，则将其访问过的路径加入went_roadif fx_distance != 999:went_road.append([start, min_city, min_distance])print(min_city, fx_distance)start = min_cityans_road.append(start)else:print("终点不可达！")return 0# 找到终点返回路径及总长度if start == end:ans_distance = 0for i in range(len(went_road)):ans_distance += went_road[i][2]print_ans(ans_road, ans_distance)return 1greedy(start_city, end_city)
A_plus(start_city, end_city)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！