一致代价搜索是在广度优先搜索上进行扩展的，也被成为代价一致搜索，他的基本原理是：一致代价搜索总是扩展路径消耗最小的节点n。n点的路径消耗等于前一节点n-1的路径消耗加上n-1到n节点的路径消耗。
图的一致性代价搜索使用了优先级队列并在边缘中的状态发现更小代价的路径时引入的额外的检查。边缘的数据结构需要支持有效的成员校测，这样它就结合了优先级队列和哈希表的能力。
我们以前在高级人工智能第一篇讲无信息搜索的文章中（https://blog.csdn.net/suyebiubiu/article/details/100738725），有一个例子是有名的罗马尼亚的旅行问题。我们这次可以尝试着用一致代价搜索方式进行解决这个问题。
我们想要从arad到达bucharest，姑且认为是a和b两个位置，我们想要使用一致代价搜索方式
- 1.根据上图创建一个搜索树，以a为初始状态，b为目标状态
- 2.实现代价一致搜索的图搜索算法并记录搜索路径
frontier：边缘。存储未扩展的节点。优先级队列，按路径消耗来排列
explored：探索集。存储的是状态
2.1 流程分析：
1.如果边缘为空，则返回失败。操作：empty?(frontier)
2.否则从边缘中选择一个叶子节点。操作：pop(frontier)
3.目标测试：通过返回，否则将叶子节点的状态放在探索集
4.遍历叶子节点的所有动作
- 每个动作产生子节点
- 如果子节点的状态不在探索集或者边缘，则插入到边缘集合。操作：insert(child, frontier)
- 否则如果边缘集合中如果存在此状态且有更高的路径消耗，则用子节点替代边缘集合中的状态
a是起点，c是终点。
2.2 一致代价搜索算法执行：
- a放入frontier
- ---第1次
- 从frontier中取出a（此时路径消耗最小）检测发现不是目标
- a放入explored
- 遍历a的子节点，d和b放入frontier
- ---第2次
- 从frontier中取出d（此时路径消耗最小）检测发现不是目标
- d放入explored
- 遍历d的子节点，c放入frontier
- ---第3次
- 从frontier中取出b（此时路径消耗最小）检测发现不是目标
- b放入explored
- 遍历b的子节点，e放入frontier
- ---第4次
- 从frontier中取出e（此时路径消耗最小）检测发现不是目标
- e放入explored
- 遍历e的子节点，c准备放入frontier，发现此时frontier已有c，但路径消耗为8大于7，则替代frontier中的c
- ---第5次
- 从frontier中取出c（此时路径消耗最小）检测发现是目标，成功
- 最优路径：a->b->e->c
从上例可以看出，一致代价搜索具有最优性，关键在于frontier中存储是按路径消耗顺序来排序的。
2.3 算法性能分析：
2.3.1：分析一致代价搜索的完备性、最优性、时间和空间复杂度
2.3.2：指出无信息搜索策略和有信息搜索策略的不同
2.3.3：分析一致代价搜索如何保证算法的最优性
import pandas as pd
from pandas import series, dataframe
# 城市信息：city1 city2 path_cost
_city_info = none
# 按照路径消耗进行排序的fifo,低路径消耗在前面
_frontier_priority = []
# 节点数据结构
class node:
def __init__(self, state, parent, action, path_cost):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
def main():
global _city_info
import_city_info()
while true:
src_city = input('输入初始城市\n')
dst_city = input('输入目的城市\n')
# result = breadth_first_search(src_city, dst_city)
result = uniform_cost_search(src_city, dst_city)
if not result:
print('从城市: %s 到城市 %s 查找失败' % (src_city, dst_city))
else:
print('从城市: %s 到城市 %s 查找成功' % (src_city, dst_city))
path = []
while true:
path.append(result.state)
if result.parent is none:
break
result = result.parent
size = len(path)
for i in range(size):
if i < size - 1:
print('%s->' % path.pop(), end='')
else:
print(path.pop())
def import_city_info():
global _city_info
data = [{'city1': 'oradea', 'city2': 'zerind', 'path_cost': 71},
{'city1': 'oradea', 'city2': 'sibiu', 'path_cost': 151},
{'city1': 'zerind', 'city2': 'arad', 'path_cost': 75},
{'city1': 'arad', 'city2': 'sibiu', 'path_cost': 140},
{'city1': 'arad', 'city2': 'timisoara', 'path_cost': 118},
{'city1': 'timisoara', 'city2': 'lugoj', 'path_cost': 111},
{'city1': 'lugoj', 'city2': 'mehadia', 'path_cost': 70},
{'city1': 'mehadia', 'city2': 'drobeta', 'path_cost': 75},
{'city1': 'drobeta', 'city2': 'craiova', 'path_cost': 120},
{'city1': 'sibiu', 'city2': 'fagaras', 'path_cost': 99},
{'city1': 'sibiu', 'city2': 'rimnicu vilcea', 'path_cost': 80},
{'city1': 'rimnicu vilcea', 'city2': 'craiova', 'path_cost': 146},
{'city1': 'rimnicu vilcea', 'city2': 'pitesti', 'path_cost': 97},
{'city1': 'craiova', 'city2': 'pitesti', 'path_cost': 138},
{'city1': 'fagaras', 'city2': 'bucharest', 'path_cost': 211},
{'city1': 'pitesti', 'city2': 'bucharest', 'path_cost': 101},
{'city1': 'bucharest', 'city2': 'giurgiu', 'path_cost': 90},
{'city1': 'bucharest', 'city2': 'urziceni', 'path_cost': 85},
{'city1': 'urziceni', 'city2': 'vaslui', 'path_cost': 142},
{'city1': 'urziceni', 'city2': 'hirsova', 'path_cost': 98},
{'city1': 'neamt', 'city2': 'iasi', 'path_cost': 87},
{'city1': 'iasi', 'city2': 'vaslui', 'path_cost': 92},
{'city1': 'hirsova', 'city2': 'eforie', 'path_cost': 86}]
_city_info = dataframe(data, columns=['city1', 'city2', 'path_cost'])
# print(_city_info)
def breadth_first_search(src_state, dst_state):
global _city_info
node = node(src_state, none, none, 0)
# 目标测试
if node.state == dst_state:
return node
frontier = [node]
explored = []
while true:
if len(frontier) == 0:
return false
node = frontier.pop(0)
explored.append(node.state)
if node.parent is not none:
print('处理城市节点:%s\t父节点:%s\t路径损失为:%d' % (node.state, node.parent.state, node.path_cost))
else:
print('处理城市节点:%s\t父节点:%s\t路径损失为:%d' % (node.state, none, node.path_cost))
# 遍历子节点
for i in range(len(_city_info)):
dst_city = ''
if _city_info['city1'][i] == node.state:
dst_city = _city_info['city2'][i]
elif _city_info['city2'][i] == node.state:
dst_city = _city_info['city1'][i]
if dst_city == '':
continue
child = node(dst_city, node, 'go', node.path_cost _city_info['path_cost'][i])
print('\t孩子节点:%s 路径损失为%d' % (child.state, child.path_cost))
if child.state not in explored and not is_node_in_frontier(frontier, child):
# 目标测试
if child.state == dst_state:
print('\t\t 这个孩子节点就是目的城市')
return child
frontier.append(child)
print('\t\t 添加孩子节点到这个孩子')
def is_node_in_frontier(frontier, node):
for x in frontier:
if node.state == x.state:
return true
return false
def uniform_cost_search(src_state, dst_state):
global _city_info, _frontier_priority
node = node(src_state, none, none, 0)
frontier_priority_add(node)
explored = []
while true:
if len(_frontier_priority) == 0:
return false
node = _frontier_priority.pop(0)
if node.parent is not none:
print('处理城市节点:%s\t父节点:%s\t路径损失为:%d' % (node.state, node.parent.state, node.path_cost))
else:
print('处理城市节点:%s\t父节点:%s\t路径损失为:%d' % (node.state, none, node.path_cost))
# 目标测试
if node.state == dst_state:
print('\t 目的地已经找到了')
return node
explored.append(node.state)
# 遍历子节点
for i in range(len(_city_info)):
dst_city = ''
if _city_info['city1'][i] == node.state:
dst_city = _city_info['city2'][i]
elif _city_info['city2'][i] == node.state:
dst_city = _city_info['city1'][i]
if dst_city == '':
continue
child = node(dst_city, node, 'go', node.path_cost _city_info['path_cost'][i])
print('\t孩子节点:%s 路径损失为:%d' % (child.state, child.path_cost))
if child.state not in explored and not is_node_in_frontier(_frontier_priority, child):
frontier_priority_add(child)
print('\t\t 添加孩子到优先队列')
elif is_node_in_frontier(_frontier_priority, child):
# 替代为路径消耗少的节点
frontier_priority_replace_by_priority(child)
def frontier_priority_add(node):
"""
:param node node:
:return:
"""
global _frontier_priority
size = len(_frontier_priority)
for i in range(size):
if node.path_cost < _frontier_priority[i].path_cost:
_frontier_priority.insert(i, node)
return
_frontier_priority.append(node)
def frontier_priority_replace_by_priority(node):
"""
:param node node:
:return:
"""
global _frontier_priority
size = len(_frontier_priority)
for i in range(size):
if _frontier_priority[i].state == node.state and _frontier_priority[i].path_cost > node.path_cost:
print('\t\t 替换状态: %s 旧的损失:%d 新的损失:%d' % (node.state, _frontier_priority[i].path_cost,
node.path_cost))
_frontier_priority[i] = node
return
if __name__ == '__main__':
main()
输入初始城市
arad
输入目的城市
bucharest
处理城市节点:arad 父节点:none 路径损失为:0
孩子节点:zerind 路径损失为:75
添加孩子到优先队列
孩子节点:sibiu 路径损失为:140
添加孩子到优先队列
孩子节点:timisoara 路径损失为:118
添加孩子到优先队列
处理城市节点:zerind 父节点:arad 路径损失为:75
孩子节点:oradea 路径损失为:146
添加孩子到优先队列
孩子节点:arad 路径损失为:150
处理城市节点:timisoara 父节点:arad 路径损失为:118
孩子节点:arad 路径损失为:236
孩子节点:lugoj 路径损失为:229
添加孩子到优先队列
处理城市节点:sibiu 父节点:arad 路径损失为:140
孩子节点:oradea 路径损失为:291
孩子节点:arad 路径损失为:280
孩子节点:fagaras 路径损失为:239
添加孩子到优先队列
孩子节点:rimnicu vilcea 路径损失为:220
添加孩子到优先队列
处理城市节点:oradea 父节点:zerind 路径损失为:146
孩子节点:zerind 路径损失为:217
孩子节点:sibiu 路径损失为:297
处理城市节点:rimnicu vilcea 父节点:sibiu 路径损失为:220
孩子节点:sibiu 路径损失为:300
孩子节点:craiova 路径损失为:366
添加孩子到优先队列
孩子节点:pitesti 路径损失为:317
添加孩子到优先队列
处理城市节点:lugoj 父节点:timisoara 路径损失为:229
孩子节点:timisoara 路径损失为:340
孩子节点:mehadia 路径损失为:299
添加孩子到优先队列
处理城市节点:fagaras 父节点:sibiu 路径损失为:239
孩子节点:sibiu 路径损失为:338
孩子节点:bucharest 路径损失为:450
添加孩子到优先队列
处理城市节点:mehadia 父节点:lugoj 路径损失为:299
孩子节点:lugoj 路径损失为:369
孩子节点:drobeta 路径损失为:374
添加孩子到优先队列
处理城市节点:pitesti 父节点:rimnicu vilcea 路径损失为:317
孩子节点:rimnicu vilcea 路径损失为:414
孩子节点:craiova 路径损失为:455
孩子节点:bucharest 路径损失为:418
替换状态: bucharest 旧的损失:450 新的损失:418
处理城市节点:craiova 父节点:rimnicu vilcea 路径损失为:366
孩子节点:drobeta 路径损失为:486
孩子节点:rimnicu vilcea 路径损失为:512
孩子节点:pitesti 路径损失为:504
处理城市节点:drobeta 父节点:mehadia 路径损失为:374
孩子节点:mehadia 路径损失为:449
孩子节点:craiova 路径损失为:494
处理城市节点:bucharest 父节点:pitesti 路径损失为:418
目的地已经找到了
从城市: arad 到城市 bucharest 查找成功
arad->sibiu->rimnicu vilcea->pitesti->bucharest五：结果说明