使用模拟退火进行图形着色 [英] Graph Coloring with using Simulated Annealing

问题描述

我正在尝试使用模拟退火解决图形着色问题的算法.在线上有通用算法，但是当我看它时，我不明白如何在此问题上应用该算法.图中的每个节点必须与其临近点具有不同的颜色.

I am trying to come up with the algorithm for a Graph Coloring problem using Simulated Annealing. There is the general algorithm online, but when i look at it, I couldn't understand how can apply this algorithm on this problem. Each node in graph must had diffrent color from it's neibours.

如何为此使用模拟退火算法.
这个问题中的温度"，时间表"是什么?

How can I use the Simulated annealing algorithm for this.
What is the "temperature", "schedule" in this problem?

请帮助我理解这一点.谢谢

Please help me understand this. Thanks

推荐答案

图形的正确着色是将颜色分配给图形的顶点，以便没有两个相邻的顶点具有相同的颜色.
要解决此问题，假设您有一个具有N个节点的图G，那么您需要以下方法:

A proper coloring of a graph is an assignment of colors to the vertices of the graph so that no two adjacent vertices have the same color.
To solve this problem assume you have a graph G with N nodes then you need these methods:

• assignColor(graph):第一个结果
• assignColor(图形，节点):为点头设置新颜色
• isColoringValid(graph):检查当前着色是否有效
• lossFunction(graph):计算使用的颜色数量
• getProbability(oldValue，newValue，温度):计算是否接受新状态

最后编写一个递归方法，如SimulationAnnealing(graph，temp)，该方法包含一个主循环以更改每个节点的颜色，然后检查isColoringValid()是否可以计算出损失函数()和getProbability().因为在较高温度下您可以接受有价值的答案，但在较低温度下，则只能接受更好的答案，并且在方法结束时降低温度并调用simulatedAnnealing(graph，temp).

Finally write a recursive method as simulatedAnnealing(graph, temp) which contains a main loop to change color for each node then check isColoringValid() if it would ok calculate loss function() and getProbability(). Because in higher temperature you can accept worth answer but in lower temperature, only better answer is accepted and at the end of method reduce the temperature and call simulatedAnnealing(graph, temp).

您可以在我的github 中找到完整的解决方案.

You can find complete solution in my github.

这篇关于使用模拟退火进行图形着色的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！