首页 > 编程语言 > 详细

【ACM算法回顾】搜索

时间:2017-07-07 14:00:19      阅读:191      评论:0      收藏:0      [点我收藏+]
  • 今天主要回顾一下几个搜索
    • DFS  ——Depth First Search
    • BFS  ——Breadth First Search
    • A* 
    • 迭代优先搜索

今天DFS和BFS的实现就不细讲了

我们先直接看A*算法的实现(python风格为主...带一点伪代码)

 1 def A_star_search
 2     q = PriorityQueue()
 3     #优先队列,顺便起到open表的作用
 4     q.put(qnode)
 5     came_from = {}
 6     #came_from为记录拓展过程的链表
 7     cost_so_far = {}
 8     #cost_so_far[p]为起点到节点p目前已知花费
 9     came_from[start_state] = None
10     cost_so_far[start_state] = 0
11 
12     while not q.empty():
13         cur_state = q.get()
14         if cur_state == goal_state:
15             break
16         #假设用邻接表存储,用边权矩阵原理类似
17         for nxt in G.neighbour(cur_state):
18             new_cost = cost_so_far[cur_state] + G.cost(cur_state, nxt)
19             if nxt not in cost_so_far or new_cost < cost_so_far[nxt]
20                 cost_so_far[nxt] = new_cost
21                 priority = new_cost + heuristic(goal_state, nxt)
22                 q.put(qnode(....including "priority", "nxt"))
23                 came_from[nxt] = cur_state
24 
25     return came_from, cost_so_far

 

核心思想在已知代价g的基础上引入估价函数h,由f=g+h确定搜索的顺序

无论是DFS还是BFS还是启发式搜索,关键在于,搜索中扩展顺序的确定

DFS和BFS都不在乎边权,而都是以层次为划分进行搜索,DFS的搜索顺序是深层节点优先,BFS的搜索顺序是同层节点优先

而A*搜索主要考虑边权和代价,由已知代价评估出“最有可能成为答案”的节点进行拓展

【ACM算法回顾】搜索

原文:http://www.cnblogs.com/KningTG/p/7131670.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!