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

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

Bonny Clarke 1月前

58 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)
  • 如何对十几个“必须访问”的节点使用强力攻击。您可以轻松覆盖 12 个节点的所有可能组合,这样您就可以遵循最佳电路来覆盖它们。

    现在,您的问题就简化为找到从起始节点到电路的最佳路线,然后您沿着该路线走,直到覆盖它们,然后找到从那里到终点的路线。

    最终路径由以下部分组成:

    开始 -> 电路路径* -> 必须访问节点的电路 -> 结束路径* -> 结束

    你可以找到我用 * 标记的路径,如下所示

    从起始节点到电路上的每个点进行 A* 搜索,对每个点从电路上的下一个和前一个节点到结束进行 A* 搜索(因为您可以按照任一方向进行电路循环)您最终会得到很多搜索路径,您可以选择成本最低的路径。

    通过缓存搜索有很多优化的空间,但我认为这会产生好的解决方案。

    但它并没有去寻找最佳解决方案,因为这可能涉及在搜索中离开必须访问的电路。

返回
作者最近主题: