Fruchterman和Reingold力定向图布局算法中的温度变量意味着什么



我计划在这里实现Fruchterman和Reingold算法来绘制图形:http://cs.brown.edu/people/rtamassi/gdhandbook/chapters/force-directed.pdf,第5页。有这个温度变量"t",但没有解释它是什么,还有这个"酷(t)"函数通过迭代应用。有人对此有什么解释吗?谢谢

首先,文章中对"温度"变量有一个简短的描述:

Fruchterman和Reingold的算法添加了"温度"的概念,可以如下使用:"温度可以从初始值(比如帧宽度的十分之一)开始,然后以逆线性方式衰减到0。"温度控制顶点的位移,因此随着布局的改善,调整也会变小。这里温度的使用是一种称为模拟退火的通用技术的特殊情况,本章稍后将讨论其在力定向算法中的使用。

因此,该算法是用于搜索函数的全局最优值的模拟退火技术的变体。以下是对算法的直观描述:

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

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

最新更新