guodong's blog

PhD@zhejiang university
   

算法:1.1机器人巡游优化

  • 2018年10月11日
  • 算法

一:总览

问题:机器人巡游优化 输入:集合P,包含平面上的n个点 输出:能访问P中所有点的最短环状巡游路线

二:方法 1、最邻近启发式方法(nearest-neighbor): 思路:从这个点开始,寻找所有点中距离它最近的并且从未访问过的点作为下一个节点。 伪代码: 但是这个方法有可能是错误的,比如下图: 考虑如果从0点出发,那么路线就会从左右左右跳动,这显然不是最简路线。最简路线就是从最左端出发一只到最右端,然后返回到最左端 2、最邻近点对启发式方法(closed-pair heuristic) 思路:将最接近的那对端点连接起来(端点指当前与其相连的顶点数不超过1),并保证对端点的连接不会引起提前收尾的问题。每个顶点开始仅仅以自己形成顶点链,当所有的一切合并完成时,我们会得到一条包含所有点的链,最后仅存两个端点,将他们连接一起形成一个闭环。 伪代码: 这个可以解决图1.3的问题。但对图1.4却可能不是最好的解法: 图1.4利用closed-pair时,过程如下: 先找到最相邻的两个顶点,比如1-4,然后3-6,2-5,然后对这些顶点链用边连接,发现距离比右边的稍长。  



上一篇:
下一篇:

头像

guodong

没有评论


你先离开吧:)



发表评论

电子邮件地址不会被公开。 必填项已用*标注