Simulated annealing: Difference between revisions
Content added Content deleted
(Added Go) |
No edit summary |
||
Line 537: | Line 537: | ||
76, 75, 84, 83, 93, 92, 91, 100, 90, 11 |
76, 75, 84, 83, 93, 92, 91, 100, 90, 11 |
||
1</pre> |
1</pre> |
||
=={{header|Nim}}== |
|||
<lang Nim>import math, random, sugar, strformat |
|||
from times import cpuTime |
|||
const |
|||
kT = 1 |
|||
kMax = 1_000_000 |
|||
proc randomNeighbor(x: int): int = |
|||
case x |
|||
of 0: |
|||
rand([1, 10, 11]) |
|||
of 9: |
|||
rand([8, 18, 19]) |
|||
of 90: |
|||
rand([80, 81, 91]) |
|||
of 99: |
|||
rand([88, 89, 98]) |
|||
elif x > 0 and x < 9: # top ceiling |
|||
rand [x-1, x+1, x+9, x+10, x+11] |
|||
elif x > 90 and x < 99: # bottom floor |
|||
rand [x-11, x-10, x-9, x-1, x+1] |
|||
elif x mod 10 == 0: # left wall |
|||
rand([x-10, x-9, x+1, x+10, x+11]) |
|||
elif (x+1) mod 10 == 0: # right wall |
|||
rand([x-11, x-10, x-1, x+9, x+10]) |
|||
else: # center |
|||
rand([x-11, x-10, x-9, x-1, x+1, x+9, x+10, x+11]) |
|||
proc neighbor(s: seq[int]): seq[int] = |
|||
result = s |
|||
var city = rand s |
|||
var cityNeighbor = city.randomNeighbor |
|||
while cityNeighbor == 0 or city == 0: |
|||
city = rand s |
|||
cityNeighbor = city.randomNeighbor |
|||
result[s.find city].swap result[s.find cityNeighbor] |
|||
func distNeighbor(a, b: int): float = |
|||
template divmod(a: int): (int, int) = (a div 10, a mod 10) |
|||
let |
|||
(diva, moda) = a.divmod |
|||
(divb, modb) = b.divmod |
|||
hypot((diva-divb).float, (moda-modb).float) |
|||
func temperature(k, kmax: float): float = |
|||
kT * (1 - (k / kmax)) |
|||
func pdelta(eDelta, temp: float): float = |
|||
if eDelta < 0: 1.0 |
|||
else: exp(-eDelta / temp) |
|||
func energy(path: seq[int]): float = |
|||
var sum = 0.distNeighbor path[0] |
|||
for i in 1 ..< path.len: |
|||
sum += path[i-1].distNeighbor(path[i]) |
|||
sum + path[^1].distNeighbor 0 |
|||
proc main = |
|||
randomize() |
|||
var |
|||
s = block: |
|||
var x = lc[x | (x <- 0 .. 99), int] |
|||
template shuffler: int = rand(1 .. x.len-1) |
|||
for i in 1 .. x.len-1: |
|||
x[i].swap x[shuffler()] |
|||
x |
|||
let startTime = cpuTime() |
|||
echo fmt"E(s0): {energy s:6.4f}" |
|||
for k in 0 .. kMax: |
|||
var |
|||
temp = temperature(float k, float kMax) |
|||
lastenergy = energy s |
|||
newneighbor = s.neighbor |
|||
newenergy = newneighbor.energy |
|||
if k mod (kMax div 10) == 0: |
|||
echo fmt"k: {k:7} T: {temp:6.2f} Es: {lastenergy:6.4f}" |
|||
var deltaEnergy = newenergy - lastenergy |
|||
if pDelta(deltaEnergy, temp) >= rand(1.0): |
|||
s = newneighbor |
|||
s.add 0 |
|||
echo fmt"E(sFinal): {energy s:6.4f}" |
|||
echo fmt"path: {s}" |
|||
#echo fmt"ended after: {cpuTime() - startTime}" |
|||
main()</lang> |
|||
Compile and run: <pre>nim c -r -d:release --opt:speed travel_sa.nim</pre> |
|||
{{out}} |
|||
Sample run: |
|||
<pre> |
|||
E(s0): 505.1591 |
|||
k: 0 T: 1.00 Es: 505.1591 |
|||
k: 100000 T: 0.90 Es: 196.5216 |
|||
k: 200000 T: 0.80 Es: 165.6735 |
|||
k: 300000 T: 0.70 Es: 159.3411 |
|||
k: 400000 T: 0.60 Es: 144.8330 |
|||
k: 500000 T: 0.50 Es: 131.7888 |
|||
k: 600000 T: 0.40 Es: 127.6914 |
|||
k: 700000 T: 0.30 Es: 113.9280 |
|||
k: 800000 T: 0.20 Es: 104.7279 |
|||
k: 900000 T: 0.10 Es: 103.3137 |
|||
k: 1000000 T: 0.00 Es: 103.3137 |
|||
E(sFinal): 103.3137 |
|||
path: @[0, 10, 11, 22, 21, 20, 30, 31, 41, 40, 50, 51, 61, 60, 70, 71, 81, 80, 90, 91, 92, 93, 82, 83, 73, 72, 62, 63, 53, 52, 42, 32, 33, 23, 13, 14, 24, 34, 35, 25, 15, 16, 26, 36, 47, 48, 38, 39, 49, 59, 58, 57, 68, 69, 79, 89, 99, 98, 97, 96, 95, 94, 84, 74, 75, 85, 86, 87, 88, 78, 77, 67, 76, 66, 65, 64, 54, 43, 44, 45, 55, 56, 46, 37, 27, 28, 29, 19, 9, 8, 18, 17, 7, 6, 5, 4, 3, 2, 12, 1, 0] |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|zkl}} |
{{trans|zkl}} |