旅行商关于额外部分订购的问题
我正在寻找此问题的名称或任何关于算法或源代码的线索：
示例：您想要找到访问 100 个最大城市的最佳路线美国（经典 TSP），但在您访问任何特定城市之前，您必须访问该城市所在州的首府。
示例：您正在收集几位教授的学生的许可单。你需要拜访每一位学生和每一位教授，但在你见过教授的所有学生之前，你不能拜访一位教授。
一些谷歌搜索发现了顺序排序问题或“SOP”，但没有太多文献让我确信这是一个被广泛接受的名称。
我不认为这些部分排序可以在经典的 TSP 中简单地通过选择在图中使用哪些边来表示（例如，您最初不能从纽约去芝加哥，但是一旦您访问了斯普林菲尔德，您可以< /em>) 或权重，但我可能是错的。
I am looking for a name for this problem or any leads on an algorithm or source code:
Example: You want to find the best route to visit the 100 largest cities in the US (classic TSP) but before you can visit any given city you must visit the capital of the state it is in.
Example: You are collecting permission slips from the students of several professors. You need to visit every student and every professor but you can't visit a professor until you have seen all of his students.
Some Googling turns up the sequential ordering problem or "SOP" but there is not so much literature that I am convinced that this is a widely accepted name.
I don't think these partial orderings can be represented within the classic TSP simply by choosing which edges to use in the graph (e.g. you can't initially go from New York to Chicago, but once you visit Springfield you can) or weights, but I may be wrong.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
顺序排序问题由 Escudero 于 1988 年在一篇题为“顺序排序问题的不精确算法”的论文中首次提出（该论文发表在《欧洲运筹学杂志》上） ，所以这是问题的原始名称。论文摘要如下：
埃斯库德罗和他的合作者发表了许多关于该主题的论文，并引用了更多内容。如果您正在查阅文献，搜索他的论文或引用本文的论文可能会对您有所帮助。
SOP 是经过充分研究的非对称旅行商问题的约束版本，因此许多有关 ATSP 的文献可能与之相关。
The Sequential Ordering Problem was first introduced by Escudero in 1988 in a paper entitled "An Inexact Algorithm for the Sequential Ordering Problem" (this appeared in the European Journal of Operational Research), so this is the original name for the problem. The abstract of the paper reads:
Escudero and his collaborators have a number of papers on the subject, with references to even more. Searching for papers by him or that reference this paper may help you if you're looking through the literature.
SOP is a well-studied constrained version of the Asymmetric Travelling Salesman Problem, so much of the literature on ATSP may be related.
您可以构建一个考虑订购要求的状态机，用您的权重注释转换，并解决旅行推销员的问题。除非你有更多的节点：2^（大写字母数量）乘以原始节点数量。
You could build a state machine that takes into account the ordering requirements, annotate the transitions with your weights, and solve the traveling salesman on that. Except you'd have a lot more nodes: 2^(number of capitals) times the original number of nodes.