pseudocodesimulated-annealinglongest-path

How to implement simulated annealing to find longest path in graph


I've found a piece of pseudocode which explains simulated annealing for longest path problem, but there are a few details which I do not understand.

Currently I have implemented a structure representing graph, and method to generate random graph and random path in the graph - both uniform.

Here's the pseudocode of simulated annealing:

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

The details which I do not find clear enough to understand are:

RandomNeighbor(P, G)

Alpha(temp)

itermax = Beta(itermax)

What are these methods supposed to do ?


Solution

  • RandomNeighbor(P, G): This is probably the function that creates a new solution (or new neighboring solution) from your current solution (the neighbor is chosen randomly).

    Alpha(temp): That's the function that reduces the temperature (probably temp *= alpha)

    itermax = Beta(itermax): I can only assume that this one is changing (most probably, resetting) the counter on iterations since it's being used on the inner while. So, when your counter for iteration reaches its max, it's reset.