我一直在阅读很多关于模拟退火(SA)及其在解决 TSP 中的有效性的文献。这让我想到是否可以使用 SA 来优化source
路径destination
查找。
基本 SA 伪代码(来自 wiki)
s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count.
while k < kmax and e > emax // While time left & not good enough:
T ← temperature(k/kmax) // Temperature calculation.
snew ← neighbour(s) // Pick some neighbour.
enew ← E(snew) // Compute its energy.
if P(e, enew, T) > random() then // Should we move to it?
s ← snew; e ← enew // Yes, change state.
if enew < ebest then // Is this a new best?
sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'.
k ← k + 1 // One more evaluation done
return sbest // Return the best solution found.
这里s0
代表一个解决方案(所以在我的情况下它已经意味着一个源-目的地路径),我的问题是我如何生成这些“解决方案”,而不是使用最大流量算法或 dijikstra 的。