根据您正在查看的旅行商问题 (TSP)的哪个版本，它要么是NP 难的（寻找最短的可能路线），要么是NP 完全的（称为 TSP 的决策版本；给定一个长度$L$，确定给定图的任何游览的长度是否小于或等于$L$）。

两者之间的区别是微妙的，但很重要：NP-hard 问题至少与NP中的任何问题一样难。你展示一个问题的方式至少和另一个问题一样难，那就是使用所谓的reduce。减少是将给定问题转换为您想与之比较的问题的一种方式。在这种情况下，如果您想将 TSP 与已知的 NP 问题进行比较，例如3-SAT（由包含 3 个文字的子句组成的布尔语句的可满足性），您可以尝试将 TSP 简化为 3-SAT。这个想法是转换一个问题的实例$a$我们还不知道如何解决问题$b$我们确实知道如何解决，这样的解决方案$b$可用于确定解决方案$a$. 然后，通过转换$a$到$b$并解决$b$，我们构建了一个算法来解决$a$. 如果我们知道转换过程（即减少）需要多长时间，并且我们知道解决问题需要多长时间$b$，然后我们可以计算出解决问题需要多长时间的上限$a$.

我在介绍性研究生水平的计算理论课程中看到的最常见和最有用的归约类型称为多项式时间归约，这是一种归约过程，其算法将多项式时间作为问题大小的某个度量的函数，以产生它的输出。然后使用这个概念来定义NP-complete 的含义。一个问题$p$如果它在 NP 中，则它是 NP 完全的，并且对于 NP 中的每个问题，存在从该问题到问题的多项式时间缩减$p$. NP-hard可以用类似的方式定义：一个问题$p$如果存在从 NP 完全问题到多项式时间减少的多项式时间，则为 NP-hard$p$.

现在所有这些术语都已经不存在了，回答你的问题：

• 如果您谈论的是 TSP 的 NP 完全决策版本，那么 NP 中的任何问题都可以在多项式时间内简化为 TSP。全局优化问题往往是 NP 难的（虽然我不确定它们都是，但我知道非凸优化问题是 NP 难的）。由于根据定义，NP-hard 问题是 NP-complete 问题的多项式时间缩减，TSP 可以是多项式时间缩减为 NP-hard 全局优化问题。
• 如果您谈论的是 TSP 的 NP-hard 版本，则不能就减少 NP-hard 全局优化问题作出任何陈述。
• 没有任何迹象表明 NP-hard 优化问题可以简化为任一版本的 TSP。但是，已知0-1 整数规划是一个 NP 完全问题，因此可以将其简化为 TSP。

Michael Sipser 的《计算理论导论》第 2 版是一个很好但很密集的参考资料。（免责声明： Sipser 教授教我的计算课理论。）

如果我正确理解了您的问题，您要计算的通常称为Lennard-Jones cluster minimization。在 Google Scholar 中快速搜索将为您提供与该主题最相关的出版物列表。

几年前我自己研究过这个问题，我认为这不能被建模为 TSP。如果您考虑使用 Lennard-Jones/Van der Waals 势作为距离度量的所有粒子的路径，那么对于每个粒子，尽管它与所有邻居相互作用，但只考虑到其他两个粒子的能量。此外，您的交互潜力可能允许负值，从而导致负距离，这可能会导致大多数 TSP 算法出现问题。