照例先上视频:人工智能导论之一致代价搜索演示/video/1176109979474620416
再上算法伪代码描述:
接着,就是代码:
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
"*** YOUR CODE HERE ***"
# 初始化相关参数
result = []
explored = set()
frontier = util.PriorityQueue()
# 定义起始状态,其中包括开始的位置,对应的行动方案和行动代价
start = (problem.getStartState(), [], 0)
# 把起始状态放进frontier队列中,update方法会自动对其中的状态按照其行动代价进行排序
frontier.update(start,0)
# 构造循环,循环读取frontier中的状态,进行判定
while not frontier.isEmpty():
# 获取当前节点的各项信息
(node, path, cost) = frontier.pop()
# 如果弹出的节点状态满足目标要求,停止循环
if problem.isGoalState(node):
result = path
break
# 如果该节点该节点不满足目标要求,判定其是否访问过
if node not in explored:
explored.add(node)
# 遍历这个节点的子节点,更新frontier队列
for child,direction,step in problem.getSuccessors(node):
newPath = path + [direction]
newCost = cost + step
newNode = (child, newPath, newCost)
frontier.update(newNode, newCost)
# 返回计算结果,即一个行动方案
return result
同时再附上我第二次写的代码:
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
"*** YOUR CODE HERE ***"
# 初始化搜索状态
fringe = util.PriorityQueue()
node = {"state":problem.getStartState(), "path":[], "cost":0}
fringe.update(node, node["cost"])
explored = set()
# 构造循环展开搜索树
while (not fringe.isEmpty()):
# 获得待判定的叶子节点
node = fringe.pop()
# 判断节点是否满足目标要求,如果是一个可行解,就返回行动方案
if problem.isGoalState(node["state"]):
return node["path"]
# 否则,就继续从这个叶子节点往下展开
else:
# 先判断一下这个节点是不是已经展开过了,避免重复展开
if node["state"] not in explored:
for nextnode in problem.getSuccessors(node["state"]):
# 为了适应可能的数据结构为图,必须判定叶子节点是否已经访问过
if nextnode[0] not in explored:
nextnode = {"state":nextnode[0],
"path":node["path"]+[nextnode[1]],
"cost":node["cost"]+nextnode[2]}
# 如果没有访问过,就将叶子节点的信息更新到添加到待搜索的节点集合中
fringe.update(nextnode, nextnode["cost"])
# 最后不要忘记把搜索过的节点添加到访问过的节点集合中
explored.add(node["state"])
GitHub代码地址:GitHub地址
如果觉得《python反恐精英代码类似的编程_敲代码学Python:CS188之实现一致代价搜索》对你有帮助,请点赞、收藏,并留下你的观点哦!