algorithm - Fruchterman 和 Reingold 力导向图布局算法中的温度变量是什么意思？

Question

我计划在此处实现用于绘制图形的 Fruchterman 和 Reingold 算法:http://cs.brown.edu/people/rtamassi/gdhandbook/chapters/force-directed.pdf ，第 5 页。有一个温度变量“t”，但没有解释它是什么，还有一个通过迭代应用的“cool(t)”函数。有人对此有任何解释吗？谢谢。

Answer 1

首先，文章中对“温度”变量是什么有一个简短的描述:

The algorithm of Fruchterman and Reingold adds the notion of “temperature” which could be used as follows: “the temperature could start at an initial value (say one tenth the width of the frame) and decay to 0 in an inverse linear fashion.” The temperature controls the displacement of vertices so that as the layout becomes better, the adjustments become smaller. The use of temperature here is a special case of a general technique called simulated annealing, whose use in force-directed algorithms is discussed later in this chapter.

所以该算法是 Simulated annealing 的变体搜索函数的全局最优值的技术。下面是对该算法的直观描述:

您从问题在高温 的随机状态开始。你开始随机修改你的状态，优先选择可以提高函数值的新状态。首先，由于高温，您允许当前状态发生非常大的变化 - 包括不会提高函数值甚至使其变得更糟的变化(这有助于避免陷入局部最优)。通过迭代，您可以根据一些冷却计划降低温度(这就是 cool(t) 函数发挥作用的地方)，越来越倾向于只提高函数值的变化。

关于如何选择初始温度、冷却时间表、新状态的接受概率等有各种微妙之处。通常，这是一个非常具体的问题任务，很难提供一个通用的方法。