如何实现模拟退火以找到图中的最长路径

Question

我找到了一段伪代码，它解释了最长路径问题的模拟退火，但有一些细节我不明白。

目前我已经实现了一个表示图的结构，以及在图中生成随机图和随机路径的方法——两者都是统一的。

这是模拟退火的伪代码：

Procedure Anneal(G, s, t, P)
P = RandomPath(s, t, G)
temp = TEMP0
itermax = ITER0
while temp > TEMPF do
  while iteration  < itermax do
    S = RandomNeighbor(P, G)
    delta = S.len - P.len
    if delta > 0 then
       P = S
    else
      x = random01
      if x < exp(delta / temp) then
        P = S
      endif
    endif
    iteration = iteration + 1
  enddo
  temp = Alpha(temp)
  itermax = Beta(itermax)
enddo

我觉得不够清楚的细节是：

RandomNeighbor(P, G)

阿尔法（温度）

itermax = Beta(itermax)

这些方法应该做什么？

Answer 1

RandomNeighbor(P, G)：这可能是从您当前的解决方案（随机选择邻居）中创建新解决方案（或新的相邻解决方案）的函数。

Alpha(temp)：就是那个降低温度的函数（大概temp *= alpha）

itermax = Beta(itermax)：我只能假设这个正在改变（很可能是重置）迭代计数器，因为它被用于内部 while。因此，当您的迭代计数器达到最大值时，它会被重置。

如何实现模拟退火以找到图中的最长路径

How to implement simulated annealing to find longest path in graph

pseudocode

simulated-annealing

longest-path