我对寻找图的最小带宽的 NP 完全“最小带宽”问题很感兴趣。对于那些不熟悉的人，这里有一个关于它的链接......
http://en.wikipedia.org/wiki/Graph_bandwidth
我已经实现了 Cuthill-McKee 算法，这非常成功地为我提供了带宽减少的顶点的排列；但是，我正在寻找最小带宽，而不仅仅是接近的减少带宽。如果你们中的任何人有这个问题的经验，哪些算法提供的解决方案是最小的，而不仅仅是减少的？我不需要任何算法的实际实现，我只想要关于研究哪些算法可以产生实际最小带宽的建议。
这是一个有趣的问题，但是当我阅读 Wiki（您的链接）时：
未加权和加权版本都是二次瓶颈分配问题的特例。带宽问题是 NP 难的，即使对于某些特殊情况也是如此。 [4] 关于有效逼近算法的存在，众所周知，带宽是 NP-hard 在任何常数内逼近的，即使输入图仅限于毛毛虫树时也是如此 (Dubey, Feige & Unger 2010)。另一方面，许多多项式可解的特殊情况是已知的。
所以wiki说用任何常数来近似它是NP-Hard（所以这个问题没有PTAS），你的机会就是使用启发式算法，确保蛮力算法有效，（编号节点在1..n之间随机启动，之后使用蛮力），但你应该花 1000 年的时间来为 Caterpillar 解决它。您应该搜索启发式算法，而不是近似算法和精确算法。
由于它是 NP 完整的，因此您必须使用某种“蛮力”算法。所以主要是你有不同的蛮力作为选项，例如分支定界或线性编程（它的 LIP，所以它在 NP 中）。
由于它是 NP 完全的，您还可以通过从 NP 完全性证明转换问题实例，应用算法并将其转换回来，从而将每个解决方案用于不同的 NP 完全问题（TSP、SAT、...）。
您可以做的最简单的改进可能是获取您的 Cuthill-McKee 算法的结果并将Tabu Search扔在上面。
有关可以应用的一些算法的概述，请参阅此答案。