Как реализовать моделируемый отжиг, чтобы найти самый длинный путь в графе - PullRequest
Новая
       31

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

0 голосов
/ 10 апреля 2019

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

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

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

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)

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

1 Ответ

1 голос
/ 25 апреля 2019

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

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

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

...