一个面试的问题

Question

我今天去面试,考官给我出了道题.求地图上的最短距离.要实现的效果是随机出现50个点,然后再选取任意俩点.使之走最短路径并画出来...哪位高手有更简便的答案?求给之...

Answer 1

Dijkstra发明的贪婪算法(贪心算法)可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。
　　 设置顶点集合S并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S中只含源。 
　　 设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路径，并把这个特殊路径记录下来（例如程序中的dist[i，j]）。
　　 每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解 。

Answer 2

算法的讨论相当多，如果楼主对这个算法感兴趣，可以尝试google一下：邮递员问题，淬火问题，遗传算法，启发式算法等，基本都是这个算法的讨论其基本思路：
判断路径最短的一个显著标志是，必然不存在两个交叉的连线。算法：
使用Dijkstra来生成最初的节点，之后，随机提取两个线段，交换顶点，比如，线段ab、cd，交换之后变为ad、bc，然后计算两个线段的总和是否有缩短。提取的次数决定最后的理想度。
交换次数达到一个临界值之后，结果不能再优化。
这个算法存在一个比较大的缺陷，在这样的连线图中，必然存在一个线段从图的一边一直连接到另外一边。即，永远得不到最优解。改进算法：
需求：概率论和数理统计。
对上述交换算法的改进，在交换过程中，不是严格的判定是否缩短，而是允许在交换过程中，出现一定程度的总和增加的情况出现，增加比例可以计算。然后，算法中要求记录几步的交换过程，并，在几步之后，始终没有减少的情况下进行回退。反复叠代使用，直到达到没有任何两个连线之间存在交叉，达到最优解结果。所有相关数学模型因为篇幅原因未曾列出，只是表述一个大概思路，相信应该可以让你的面试官满意了！