我正在学习图形和算法，我什至很难找到此类问题的名称，更不用说提出一个好的解决方案了。
如果我们只有一个未加权的无向图，那么找到从 A 到 B 的最短路径是微不足道的 (BFS)。
如果我们必须访问某些节点（“从 A 到 B，同时在节点 C 上拾取项目 1，在节点 D 上拾取项目 2.. 以任何顺序，允许多次访问一个节点”），那么事情就会变得更加困难，但是这仍然是一个容易发现问题 https://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes.
现在，如果每件物品都可以从多个节点拾取怎么办？只需要拾取一次，如何选择使用哪个节点，使得得到的路径尽可能最短？
每个项目可以在许多节点上可用，每个节点上最少可以没有可用项目，最多可以有所有项目。可以访问具有特定项目的多个节点，但每个项目只需要一个。
想想 ~10000 个节点，~10 个项目，每个项目最多可在 ~10 个节点中使用。暴力破解每个项目的所有可能性感觉是错误的，因为链接的解决方案specific节点集已经尝试了所有排列，因此这将非常复杂。
我发现与拣选器路由问题有一些相似之处，特别是混合货架仓库变体。问题是找到从仓库中的订单中提取每个物品的最短路线，其中每个物品都存放在仓库的多个位置。与我的情况相反，解决这些问题的论文考虑了特定形状的图（矩形仓库、平行过道），并且满足于最短路径的启发式近似。混合货架拣选器路由结果是 NP 困难的。
“贪婪”算法：
- 识别具有一个或多个所需项目的 L1 所有节点
- 使用旅行商 (TS) 算法找到从 A 到 B 的最短路径，该路径访问具有一个或多个所需物品的每个节点。
- 识别 L2 所有可以在其他节点拾取其物品的节点。
- LOOP
- Iterate N over L2
- 将 L3 设置为 L1，不带 N
- 解决 L3 上的 TS
- If TS on L3 shorter than best found
- 迭代结束
- 如果没有改善
完毕
- L1 = 最佳
- LOOP end
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
