我正在寻找此问题的名称或算法或源代码的任何线索：
示例：您想找到访问美国 100 个最大城市（经典 TSP）的最佳路线，但在访问任何给定城市之前，您必须先访问其所在州的首府。
示例：您正在收集几位教授的学生的许可单。你需要拜访每一位学生和每一位教授，但你不能拜访一位教授，除非你见过他所有的学生。
一些谷歌搜索出现了顺序排序问题或“SOP”，但没有太多文献我相信这是一个被广泛接受的名称。
我认为这些偏序不能简单地通过选择要在图中使用的边（例如，您最初不能从纽约到芝加哥，但是一旦您访问斯普林菲尔德就可以）或权重来表示在经典 TSP 中，但我可能错了。
Sequential Ordering Problem是 Escudero 于 1988 年在一篇题为“ An Inexact Algorithm for the Sequential Ordering Problem ”的论文中首次引入的（该论文发表于 European Journal of Operational Research），因此这是该问题的原始名称。论文摘要如下：
给定有向的 G= (N, A) 和惩罚矩阵 C，顺序排序问题（以下简称 SOP）包括从集合 N 中找到节点的排列，从而最小化基于 C 的函数并且不违反集合 A 给出的优先关系。 SOP 实例不可行的强充分条件嵌入在 SOP 预处理过程中。请注意，它是任何试图解决 SOP 的算法中的关键步骤之一。通过删除与优先关系相关的约束，SOP 可以转换为经典的非对称旅行商问题（以下简称 ATSP）。该算法通过修改相关分配问题的最优解来获得（希望）令人满意的解（以下，AP），如果它不是可行的顺序排序（以下简称 FSO）。新的解决方案“修补”子路径（如果有的话），优先使用链接弧中成本为零的修补程序。通过使用 [1] 中给出的一些程序，对 ATSP 的最佳解决方案基于 AP 的下限进行了收紧。在任何情况下，都会执行本地搜索以改进初始 FSO；它使用基于 3 和 4 变化的程序。报告了广泛案例的计算结果。执行改进初始 FSO 的本地搜索；它使用基于 3 和 4 变化的程序。报告了广泛案例的计算结果。执行改进初始 FSO 的本地搜索；它使用基于 3 和 4 变化的程序。报告了广泛案例的计算结果。
埃斯库德罗和他的合作者有很多关于这个主题的论文，引用的甚至更多。如果您正在浏览文献，搜索他的论文或参考这篇论文可能会对您有所帮助。
SOP 是Asymmetric Traveling Salesman Problem的一个经过充分研究的约束版本，因此很多关于 ATSP 的文献可能与此相关。
您可以构建一个考虑订购要求的状态机，用您的权重注释转换，然后解决旅行推销员的问题。除了你会有更多的节点：2 ^（大写字母的数量）乘以原始的节点数量。