Как реализовать имитацию отжига, чтобы найти самый длинный путь в графе

Я нашел фрагмент псевдокода, который объясняет имитацию отжига для задачи наибольшего пути, но есть несколько деталей, которые я не понимаю.

В настоящее время я реализовал структуру, представляющую граф, и метод для создания случайного графа и случайного пути в графе - оба однородны.

Вот псевдокод имитации отжига:

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

Детали, которые я не нахожу достаточно ясными, чтобы понять:

Случайный сосед(P, G)

Альфа (временная)

itermax = бета(itermax)

Что должны делать эти методы?


longest-path pseudocode simulated-annealing
person Zarrie    schedule 10.04.2019    source источник
comment
У вас есть ссылка, где вы это нашли?   -  person EhsanK    schedule 25.04.2019
comment
Вот файл, на который я ссылался: scholvin.com/thesis.pdf   -  person Zarrie    schedule 25.04.2019

Ответы (1)


arrow_upward
1
arrow_downward

RandomNeighbor(P, G): вероятно, это функция, которая создает новое решение (или новое соседнее решение) из вашего текущего решения (соседние выбираются случайным образом).

Alpha(temp): это функция, которая снижает температуру (вероятно, temp *= alpha).

itermax = Beta(itermax): я могу только предположить, что этот счетчик меняет (скорее всего, сбрасывает) счетчик итераций, поскольку он используется на внутреннем while. Итак, когда ваш счетчик итераций достигает своего максимума, он сбрасывается.

person EhsanK    schedule 25.04.2019