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

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）

阿尔法（TEMP）

itermax = Beta（itermax）

这些方法应该做什么？

Answer 1

RandomNeighbor（P，G）：这可能是从当前解决方案（随机选择邻居）创建新解决方案（或新的邻居解决方案）的功能。

Alpha（temp）：这是降低温度的功能（可能是temp *= alpha）

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