Tag: np complete

使用模拟退火的图形着色

我正在尝试使用模拟退火来提出图形着色问题的算法。 在线有一般算法，但是当我看到它时，我无法理解如何将此算法应用于此问题。 图中的每个节点必须具有来自它的neibours的不同颜色。 我怎样才能使用模拟退火算法。 这个问题的“温度”，“时间表”是什么？ 请帮我理解这个。 谢谢

Java：旅行推销员 – 找到多项式算法

编辑 ：找到了对此算法的改进 。 欢迎您来看看。 这个问题是我老问题的改进。 现在我想向您展示Java代码示例 ，并更详细地解释我的算法。 我认为我找到了一个多项式算法来获得旅行商问题的精确解决方案。 我的实现是从5个步骤构建的： 1）快速设置 2） 搜索解决方案 3） 停止条件1 4）停止条件2 5）停止条件3 我想从第2步和第3步开始，如果我没有出错，我会告诉你其余部分。 所以我现在要向您展示的不是多项式算法 ，而是对Held-Karp算法的改进，它解决了时间问题O（n ^ 2 2 ^ n） 让我们说我们想用brout算法解决6个城市的路线。 有（6-1）！ = 120选项，我们将需要测试它们并返回建立的最短路线。 所以它看起来像那样（城市名称是：A，B，C，D，E，F）： 选项1：A – > B – > C – > D – > E – > F – > A. 选项2：A – > B – > C […]