KISS(Keep It Simple, Standard)

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  10 Posts :: 0 Stories :: 24 Comments :: 0 Trackbacks

常用链接

留言簿(10)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

最近做了路径搜索,看了网上的描述真是晦涩,所以自己就整理下!
图画的不太好, :)
绿色的是节点,红色的为权值,箭头为可通行的标志.

现在我们要从 0 节点 到 12 节点 找一条最优路径:
首先咱们要解决NODE点存贮的信息(结构):
struct NodeBaseInfo
{
   unsigned short nNodeID;   //番号
   unsigned long  nMeasure;            //权值
   NodeBaseInfo *pParent;            //父节点
};

我写了简单的结构大家可以根据自己需要定义(定义这个结构是为了更好理解)
下面讲的是最主要的了:
DIJKSTAR算法中要定义两个表:OPEN 和 CLOSE  (其实可以看作链表)
他的原理就是把没有遍历的点放在 OPEN 表中,把从 OPEN表中遍历到的最短权值的点放入
CLOSE 表中,当插入 CLOSE表中的节点的番号于我们要的重点时算法结束;然后按照父节点(pParent)
向上递归就可以得到我们要的最优路径了。

第一步:应为 OPEN 和CLOSE表都是空的,把起点(0节点)插入CLOSE标中,它的权值为0。把起点(0节点)附近的节点(因该为可通行的)插入OPEN 表中(最好按权值从大道小的顺序插入,这样取得最优值时,这样速度就会很快)。(如示例图)

第2步:从OPEN表中找到权值最小的节点,把它插入CLOSE 表中, 把这个节点的可连通的节点查入OPEN
表,(如果OPEN表中存在要查入的点,如果要插入的节点的权值比已经存在的小,就把已经查入的权值该为最小的,如果要插入的节点的权值比已经存在的大,就忽落它.)
(为了更好的理解我把父节点也加入了,如示例图)

posted on 2008-02-01 16:13 QUIRE-0216 阅读(3873) 评论(12)  编辑 收藏 引用 所属分类: Arithmetic(算法)

Feedback

# re: 关于Dijkstra算法我的理解(上) 2008-07-28 19:54 duzhihua
看看在说,别处写的的确晦涩难懂,而且几乎所有地方的描述都一样  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2008-10-07 12:56 Vincent
不错,支持原创
自己的研究成果,Dijkstra的进化。。。

鄙视网上的大抄特抄  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2008-10-07 15:36 Vincent
的确是Dijkstra

毕竟是有限状态空间的穷举搜索,面对大规模数据时,不可以预测的情况增多,效率低下,任务甚至不能完成。

优点:准确性高

  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2008-10-07 16:00 Vincent
使用权值 也就是A*里面的估价值重排Open表,有启发式搜索的味道

没有点名使用估值函数,因为他已经吧估值函数的结果表示为权值了 呵呵



就是A*了  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2009-04-28 22:17 vision
简单明了... 至少我看懂了... 其他页面上的实在看不懂...  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2009-07-29 18:05 kfue
dd  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2009-07-29 18:05 kfue
非常好
  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2009-08-14 20:37 D.K.
顶你  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2009-08-31 20:27 Johnnx
好象错别字有些多  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2009-09-18 16:57 popo
终于通过你这篇文章弄懂了Dijkstra算法...网上不少帖子,看得我不停走神
你的文章虽然错别字不少,但的的确确一目了然。赞一个!  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上)[未登录] 2009-09-20 16:58 quire
谢谢,Johnnx,popo两位老兄提醒,下次一定注意,但是两位仁兄也没指出那儿错了!很长时间没上CPPBLOG了,看了Johnnx的主页,好像都是算法,看来Johnnx数据结构研究的蛮多,还望赐教!  回复  更多评论
  

# re: 关于Dijkstra算法我的理解(上) 2010-08-20 22:29 ri
完全就不通顺  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理