最小带宽问题
我对 NP 完全“最小带宽”问题感兴趣，用于查找图的最小带宽。对于那些不熟悉的人，这里有一个关于它的链接...
http://en.wikipedia.org/wiki /Graph_bandwidth
我已经实现了 Cuthill-McKee 算法，这非常成功地为我提供了带宽减少的顶点排列；但是，我正在寻找最小带宽，而不仅仅是接近的减少的带宽。如果你们中的任何人有解决此问题的经验，哪些算法提供的解决方案是最小值，而不仅仅是减少 ？我不需要任何算法的实际实现，我只是想要建议研究哪些算法可以产生实际的最小带宽。
I'm interesting the NP-complete "minimum bandwidth" problem for finding the minimum bandwidth of a graph. For those not familiar, here is a link about it...
http://en.wikipedia.org/wiki/Graph_bandwidth
I've implemented the Cuthill-McKee algorithm, and this was very successful at giving me a permutation of the vertices in which the bandwidth was reduced; however, I'm looking for the minimum bandwidth, not just a reduced bandwidth that is close. If any of you have experience with this problem, what algorithms provide solutions that are the minimum and not just reduced? I don't need actual implementation of any algorithm, I just want suggestions for what algorithms to research that yield actual minimum bandwidths.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这是一个有趣的问题，但是当我阅读维基（你的链接）时：
所以wiki说用任何常数来近似它是NP-Hard（所以这个问题没有PTAS），你的机会就是使用启发式算法，当然蛮力算法是有效的，（在1..n之间随机编号节点启动，之后使用暴力），但你应该花 1000 年来解决毛毛虫的问题。
您应该搜索启发式算法，而不是近似算法和精确算法。
That's interesting problem, but when I read Wiki (your link):
So wiki says it's NP-Hard to approximate it with any constant (So there is no PTAS for this problem) and your chance is just use heuristic algorithms, sure brute force algorithm works, (numbering node with numbers between 1..n randomly in startup, after that use brute force) but you should spend 1000 year to solve it for caterpillar.
You should search for heuristic algorithms, not approximation and exact algorithms.
由于它是 NP 完全的，你必须使用某种“蛮力”算法。所以主要你有不同的强力作为选项，例如分支定界或线性编程（它的 LIP，所以它是 NP）。
由于它是 NP 完备的，因此您还可以通过从 NP 完备性证明转换问题实例，应用算法，然后将其转换回来，将每个解决方案应用于不同的 NP 完备问题（TSP、SAT，...）。
As it is NP complete you have to use some kind of "brute force" algorith. So mainly you have the different brute force as option, e.g. like branch-and-bound or linear programming (its LIP, so its in NP).
As it is NP complete you can also take every solution to a different NP complete problem (TSP, SAT,...) by transforming the problem instance from the NP-completeness proof, apply the algorith, and transform it back.
您可以做的最简单的改进可能就是获取 Cuthill-McKee 算法的结果并对其进行禁忌搜索。
请参阅此答案，了解一些可应用的算法的概述。
The simplest improvement you can do, is probably to take the result of your Cuthill-McKee algorithm and throw Tabu Search on it.
See this answer for an overview on some of the algorithms that can be applied.