8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

找到图中访问某些节点的最短路径

Bonny Clarke 1月前

55 0

我有一个无向图,其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”,一个节点标记为“结束”,还有大约十几个标记为“必须通过”。我需要找到通过的最短路径...

我有一个无向图,其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”,一个节点标记为“结束”,还有大约十几个标记为“必须通过”。

我需要找到该图中最短的路径,该路径始于“开始”,终于“结束”, 并经过所有“必须通过”节点(以任何顺序)。

http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是所讨论的图表 - 它代表了宾夕法尼亚州兰开斯特的一个玉米迷宫)

帖子版权声明 1、本帖标题:找到图中访问某些节点的最短路径
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由Bonny Clarke在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • Andrew Top 有正确的想法:

    1) Djikstra 算法2) 一些 TSP 启发式算法。

    我推荐 Lin-Kernighan 启发式方法:它是解决 NP 完全问题最著名的方法之一。唯一需要记住的是,在第 2 步之后再次展开图形后,展开的路径中可能会出现循环,因此您应该绕过这些循环(查看路径上顶点的度数)。

    我实际上不确定这个解决方案相对于最优方案有多好。可能有一些与短路有关的病态情况。毕竟,这个问题看起来很像 Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree ,你绝对不能仅通过收缩你的图并运行 Kruskal 来近似 Steiner Tree。

返回
作者最近主题: