寻找通过一系列节点的无环路径？
Finding a loopless path passing through a series of nodes?
给定一个有向图，它有 n 个点，有 k "must pass" 个点，其中 k < n-2。
如何在不重新访问任何节点的情况下找到从起始节点到结束节点的路径，该路径通过所有 "must pass" 点？也许这是一个 NP 完全问题......似乎 TSP 与这个问题非常相似。
这个问题确实是NP难的。要看到这一点，您可以将 Hamiltonian path problem 减少到这个，方法是从原始图开始，添加两个没有连接到任何东西的新节点，然后请求一条路径穿过图中除了这两个节点之外的每个节点新的。
您可以使用一些专为在图中寻找长路径而设计的技术，例如 color coding 或动态编程技术，来避免暴力搜索，但考虑到这个问题的性质，我怀疑你将能够比蛮力做得更好。
给定一个有向图，它有 n 个点，有 k "must pass" 个点，其中 k < n-2。
如何在不重新访问任何节点的情况下找到从起始节点到结束节点的路径，该路径通过所有 "must pass" 点？也许这是一个 NP 完全问题......似乎 TSP 与这个问题非常相似。
这个问题确实是NP难的。要看到这一点，您可以将 Hamiltonian path problem 减少到这个，方法是从原始图开始，添加两个没有连接到任何东西的新节点，然后请求一条路径穿过图中除了这两个节点之外的每个节点新的。
您可以使用一些专为在图中寻找长路径而设计的技术，例如 color coding 或动态编程技术，来避免暴力搜索，但考虑到这个问题的性质，我怀疑你将能够比蛮力做得更好。