Simulated annealing: Difference between revisions
Content deleted Content added
(6 intermediate revisions by 5 users not shown) | |||
Line 29:
We want to apply SA to the travelling salesman problem. There are 100 cities, numbered 0 to 99, located on a plane, at integer coordinates i,j : 0 <= i,j < 10 . The city at (i,j) has number 10*i + j. The cities are '''all''' connected : the graph is complete : you can go from one city to any other city in one step.
The salesman wants to start from city 0, visit all cities, each one time, and go back to city 0. The travel cost between two cities is the euclidian distance between
A path '''s''' is a sequence (0 a b ...z 0) where (a b ..z) is a permutation of the numbers (1 2 .. 99). The path length = E(s) is the sum d(0,a) + d(a,b) + ... + d(z,0) , where d(u,v) is the distance between two cities. Naturally, we want to minimize E(s).
Line 98:
<
--
-- The Rosetta Code simulated annealing task in Ada.
Line 508:
end simanneal;
----------------------------------------------------------------------</
Line 558:
Some might notice the calculations of random integers are done in a way that may introduce a bias, which is miniscule as long as the integer is much smaller than 2 to the 31st power. I mention this now so no one will complain about it later.
<
#include <stdio.h>
#include <stdlib.h>
Line 824:
return 0;
}</
{{out}}
Line 866:
=={{header|C++}}==
'''Compiler:''' [[MSVC]] (19.27.29111 for x64)
<
#include<array>
#include<utility>
Line 1,039:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,067:
=={{header|EchoLisp}}==
<
(lib 'math)
;; distances
Line 1,151:
(printf "E(s_final) %d" Emin)
(writeln 'Path s))
</syntaxhighlight>
{{out}}
<pre>
Line 1,183:
<
implicit none
Line 1,526:
write (*, 10)
end program simanneal</
Line 1,564:
Final E(s): 101.66
</pre>
=={{header|FreeBASIC}}==
Uses 'LCS' function from [[Longest common subsequence#FreeBASIC]]:
<syntaxhighlight lang="vbnet">Dim Shared As Double dists(0 To 9999)
' index into lookup table of Nums
Function dist(ci As Integer, cj As Integer) As Double
Return dists(cj*100 + ci)
End Function
' energy at s, to be minimized
Function Ens(path() As Integer) As Double
Dim As Double d = 0
For i As Integer = 0 To Ubound(path) - 1
d += dist(path(i), path(i+1))
Next
Return d
End Function
' temperature function, decreases to 0
Function T(k As Double, kmax As Double, kT As Double) As Double
Return (1 - k / kmax) * kT
End Function
' variation of E, from state s to state s_next
Function dE(s() As Integer, u As Integer, v As Integer) As Double
Dim As Integer su = s(u)
Dim As Integer sv = s(v)
' old
Dim As Double a = dist(s(u-1), su)
Dim As Double b = dist(s(u+1), su)
Dim As Double c = dist(s(v-1), sv)
Dim As Double d = dist(s(v+1), sv)
' new
Dim As Double na = dist(s(u-1), sv)
Dim As Double nb = dist(s(u+1), sv)
Dim As Double nc = dist(s(v-1), su)
Dim As Double nd = dist(s(v+1), su)
If v = u+1 Then Return (na + nd) - (a + d)
If u = v+1 Then Return (nc + nb) - (c + b)
Return (na + nb + nc + nd) - (a + b + c + d)
End Function
' probability to move from s to s_next
Function P(deltaE As Double, k As Double, kmax As Double, kT As Double) As Double
Return Exp(-deltaE / T(k, kmax, kT))
End Function
' Simulated annealing
Sub sa(kmax As Double, kT As Double)
Dim As Integer s(0 To 100)
Dim As Integer temp(0 To 98)
Dim As Integer dirs(0 To 7) = {1, -1, 10, -10, 9, 11, -11, -9}
Dim As Integer i, k, u, v, cv
Dim As Double Emin
For i = 0 To 98
temp(i) = i + 1
Next
Randomize Timer
For i = 0 To 98
Swap temp(i), temp(Int(Rnd * 99))
Next
For i = 0 To 98
s(i+1) = temp(i)
Next
Print "kT = "; kT
Print "E(s0) "; Ens(s())
Print
Emin = Ens(s())
For k = 0 To kmax
If k Mod (kmax/10) = 0 Then
Print Using "k: ####### T: #.#### Es: ###.####"; k; T(k, kmax, kT); Ens(s())
End If
u = Int(Rnd * 99) + 1
cv = s(u) + dirs(Int(Rnd * 8))
If cv <= 0 Or cv >= 100 Then Continue For
If Abs(dist(s(u), cv)) > 5 Then Continue For
v = s(cv)
Dim As Double deltae = dE(s(), u, v)
If deltae < 0 Or P(deltae, k, kmax, kT) >= Rnd Then
Swap s(u), s(v)
Emin = Emin + deltae
End If
Next k
Print
Print "E(s_final) "; Emin
Print "Path:"
For i = 0 To Ubound(s)
If i > 0 And i Mod 10 = 0 Then Print
Print Using "####"; s(i);
Next
Print
End Sub
' distances
For i As Integer = 0 To 9999
Dim As Integer ab = (i \ 100)
Dim As Integer cd = i Mod 100
Dim As Integer a = (ab \ 10)
Dim As Integer b = ab Mod 10
Dim As Integer c = (cd \ 10)
Dim As Integer d = cd Mod 10
dists(i) = Sqr((a-c)^2 + (b-d)^2)
Next i
Dim As Double kT = 1, kmax = 1e6
sa(kmax, kT)
Sleep</syntaxhighlight>
{{out}}
<pre>kT = 1
E(s0) 510.1804163299929
k: 0 T: 1.0000 Es: 510.1804
k: 100000 T: 0.9000 Es: 195.1253
k: 200000 T: 0.8000 Es: 182.4579
k: 300000 T: 0.7000 Es: 153.4156
k: 400000 T: 0.6000 Es: 150.7938
k: 500000 T: 0.5000 Es: 141.6804
k: 600000 T: 0.4000 Es: 128.4290
k: 700000 T: 0.3000 Es: 123.2713
k: 800000 T: 0.2000 Es: 117.4202
k: 900000 T: 0.1000 Es: 116.0060
k: 1000000 T: 0.0000 Es: 116.0060
E(s_final) 116.0060090954848
Path:
0 11 10 20 21 32 22 12 2 3
13 14 34 33 23 24 35 25 16 15
4 5 6 7 9 8 18 19 29 39
49 48 38 28 27 17 26 36 47 37
45 46 57 56 55 54 44 43 42 52
51 41 31 30 40 50 60 61 83 73
63 62 72 71 70 80 90 91 81 82
92 93 94 96 97 98 99 89 79 69
59 58 68 67 77 87 88 78 76 66
65 75 86 95 85 84 74 64 53 1
0
</pre>
=={{header|Go}}==
{{trans|zkl}}
<
import (
Line 1,682 ⟶ 1,823:
func main() {
sa(1e6, 1)
}</
{{out}}
Line 1,718 ⟶ 1,859:
=={{header|Icon}}==
{{trans|Fortran}}
<syntaxhighlight lang="icon">link printf
link random
Line 1,897 ⟶ 2,040:
}
return path
end</
{{out}}
Line 1,936 ⟶ 2,079:
Final E(s): 102.24
</pre>
=={{header|J}}==
Line 1,943 ⟶ 2,084:
Implementation:
<
satsp=:4 :0
Line 1,968 ⟶ 2,109:
end.
0,s,0
)</
Notes:
Line 1,984 ⟶ 2,125:
Sample run:
<
0 1 538.409
100000 0.9 174.525
Line 1,996 ⟶ 2,137:
900000 0.1 101.657
1e6 0 101.657
0 1 2 3 4 13 23 24 34 44 43 33 32 31 41 42 52 51 61 62 53 54 64 65 55 45 35 25 15 14 5 6 7 17 16 26 27 37 36 46 47 48 38 28 18 8 9 19 29 39 49 59 69 79 78 68 58 57 56 66 67 77 76 75 85 86 87 88 89 99 98 97 96 95 94 84 74 73 63 72 82 83 93 92 91 90 80 81 71 70 60 50 40 30 20 21 22 12 11 10 0</
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
This adaptation does not cache the distances
and can be used for any square grid of cities.
Since jq does not include a PRN generator, we assume an
external source of randomness, such as /dev/urandom.
Specifically, the following program assumes an invocation
of jq along the lines of:
<pre>
< /dev/urandom tr -cd '0-9' | fold -w 1 | jq -Rcnr -f sa.jq
</pre>
Since gojq does not include jq's `_nwise/1`, here is a suitable def:
<pre>
# Require $n > 0
def _nwise($n):
def _n: if length <= $n then . else .[:$n] , (.[$n:] | _n) end;
if $n <= 0 then "_nwise: argument should be non-negative" else _n end;
</pre>
<syntaxhighlight lang="jq">
## Pseuo-random numbers and shuffling
# Output: a prn in range(0;$n) where $n is `.`
def prn:
if . == 1 then 0
else . as $n
| ([1, (($n-1)|tostring|length)]|max) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
def randFloat:
(1000|prn) / 1000;
def knuthShuffle:
length as $n
| if $n <= 1 then .
else {i: $n, a: .}
| until(.i == 0;
.i += -1
| (.i + 1 | prn) as $j
| .a[.i] as $t
| .a[.i] = .a[$j]
| .a[$j] = $t)
| .a
end;
## Generic utilities
def divmod($j):
(. % $j) as $mod
| [(. - $mod) / $j, $mod] ;
def hypot($a;$b):
($a*$a) + ($b*$b) | sqrt;
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
def round($ndec): pow(10;$ndec) as $p | . * $p | round / $p;
def sum(s): reduce s as $x (0; . + $x);
def swap($i; $j):
.[$i] as $tmp
| .[$i] = .[$j]
| .[$j] = $tmp;
### The cities
# all 8 neighbors for an $n x $n grid
def neighbors($n): [1, -1, $n, -$n, $n-1, $n+1, -$n-1, $n+1];
# Distance between two cities $x and $y in an .n * .n grid
def dist($x; $y):
.n as $n
| ($x | divmod($n)) as [$xi, $xj]
| ($y | divmod($n)) as [$yi, $yj]
| hypot( $xi-$yi; $xj - $yj );
### Simulated annealing
# The energy of the input state (.s), to be minimized
# Input: {s, n}
def Es:
.s as $path
| sum( range(0; $path|length - 1) as $i
| dist($path[$i]; $path[$i+1]) );
# temperature function, decreases to 0
def T($k; $kmax; $kT):
(1 - ($k / $kmax)) * $kT;
# variation of E, from one state to the next state
# Input: {s, n}
def dE($u; $v):
.s as $s
| $s[$u] as $su
| $s[$v] as $sv
# old
| dist($s[$u-1]; $su) as $a
| dist($s[$u+1]; $su) as $b
| dist($s[$v-1]; $sv) as $c
| dist($s[$v+1]; $sv) as $d
# new
| dist($s[$u-1]; $sv) as $na
| dist($s[$u+1]; $sv) as $nb
| dist($s[$v-1]; $su) as $nc
| dist($s[$v+1]; $su) as $nd
| if ($v == $u+1) then ($na + $nd) - ($a + $d)
elif ($u == $v+1) then ($nc + $nb) - ($c + $b)
else ($na + $nb + $nc + $nd) - ($a + $b + $c + $d)
end;
# probability of moving from one state to another
def P($deltaE; $k; $kmax; $kT):
T($k; $kmax; $kT) as $T
| if $T == 0 then 0
else (-$deltaE / $T) | exp
end;
# Simulated annealing for $n x $n cities
def sa($kmax; $kT; $n):
def format($k; $T; $E):
[ "k:", ($k | lpad(10)),
"T:", ($T | round(2) | lpad(4)),
"Es:", $E ]
| join(" ");
neighbors($n) as $neighbors # potential neighbors
| ($n*$n) as $n2
# random path from 0 to 0
| {s: ([0] + ([ range(1; $n2)] | knuthShuffle) + [0]) }
| .n = $n # for dist/2
| .Emin = Es # E0
| "kT = \($kT)",
"E(s0) \(.Emin)\n",
( foreach range(0; 1+$kmax) as $k (.;
.emit = null
| if ($k % (($kmax/10)|floor)) == 0
then .emit = format($k; T($k; $kmax; $kT); Es)
else .
end
| (($n2-1)|prn + 1) as $u # a random city apart from the starting point
| (.s[$u] + $neighbors[8|prn]) as $cv # a neighboring city, perhaps
| if ($cv <= 0 or $cv >= $n2) # check the city is not bogus
then . # continue
elif dist(.s[$u]; $cv) > 5 # check true neighbor
then . # continue
else .s[$cv] as $v # city index
| dE($u; $v) as $deltae
| if ($deltae < 0 or # always move if negative
P($deltae; $k; $kmax; $kT) >= randFloat)
then .s |= swap($u; $v)
| .Emin += $deltae
end
end;
select(.emit).emit,
(select($k == $kmax)
| "\nE(s_final) \(.Emin)",
"Path:",
# output final state
(.s | map(lpad(3)) | _nwise(10) | join(" ")) ) ));
# Cities on a 10 x 10 grid
sa(1e6; 1; 10)
</syntaxhighlight>
{{output}}
<pre>
kT = 1
E(s0) 511.63434626356127
k: 0 T: 1 Es: 511.63434626356127
k: 100000 T: 0.9 Es: 183.44842684951274
k: 200000 T: 0.8 Es: 173.6522166458839
k: 300000 T: 0.7 Es: 191.88956498870922
k: 400000 T: 0.6 Es: 161.63509965859427
k: 500000 T: 0.5 Es: 173.6829125726551
k: 600000 T: 0.4 Es: 135.5154326151275
k: 700000 T: 0.3 Es: 174.33930236055193
k: 800000 T: 0.2 Es: 141.907500599355
k: 900000 T: 0.1 Es: 141.76740977979034
k: 1000000 T: 0 Es: 148.13930861301918
E(s_final) 148.13930861301935
Path:
0 1 2 11 10 20 21 22 23 24
14 5 4 3 13 12 32 42 33 25
15 16 6 7 8 9 19 29 39 28
18 17 27 26 36 46 35 34 43 52
41 30 31 44 45 55 56 38 37 49
48 47 65 64 54 53 51 72 91 81
80 71 70 61 62 40 50 60 92 82
83 73 63 57 67 66 75 74 84 93
94 95 78 77 68 58 87 76 86 99
89 79 69 59 88 98 97 96 85 90
0
</pre>
=={{header|Julia}}==
Line 2,002 ⟶ 2,350:
'''Module''':
<
using Random, Printf
Line 2,077 ⟶ 2,425:
end
end # module TravelingSalesman</
'''Main''':
<
const _citydist = collect(distance((ci % 10, ci ÷ 10), (cj % 10, cj ÷ 10)) for ci in 1:100, cj in 1:100)
TravelingSalesman.findpath(_citydist, 1_000_000, 1)</
{{out}}
Line 2,126 ⟶ 2,474:
=={{header|Nim}}==
<
const
Line 2,208 ⟶ 2,556:
echo fmt"path: {s}"
main()</
Compile and run: <pre>nim c -r -d:release --opt:speed travel_sa.nim</pre>
Line 2,230 ⟶ 2,578:
=={{header|Perl}}==
{{trans|Raku}}
<
use strict;
use warnings;
Line 2,308 ⟶ 2,656:
printf "@{['%4d' x 20]}\n", @s[$l*20 .. ($l+1)*20 - 1];
}
printf " 0\n";</
{{out}}
<pre>k: 0 T: 1.0 Es: 519.2
Line 2,331 ⟶ 2,679:
=={{header|Phix}}==
{{trans|zkl}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">hypot</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">a</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">*</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
Line 2,412 ⟶ 2,760:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">sa</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1_000_000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 2,437 ⟶ 2,785:
=={{header|Racket}}==
<
#lang racket
(require racket/fixnum)
Line 2,550 ⟶ 2,898:
(module+ main
(Simulated-annealing))</
{{out}}
<pre>T:1 E:552.4249706051347
Line 2,568 ⟶ 2,916:
(formerly Perl 6)
{{trans|Go}}
<syntaxhighlight lang="raku"
my \cities = 100; # number of cities
my \kmax = 1e6; # iterations to run
Line 2,622 ⟶ 2,970:
say "\nE(s_final): " ~ E-min-global.fmt('%.1f');
say "Path:\n" ~ s».fmt('%2d').rotor(20,:partial).join: "\n";</
{{out}}
<pre>k: 0 T: 1.0 Es: 522.0
Line 2,643 ⟶ 2,991:
28 38 48 49 39 29 19 9 8 7 6 5 4 14 13 12 11 2 3 1
0</pre>
=={{header|RATFOR}}==
{{trans|Fortran}}
{{works with|ratfor77|[https://sourceforge.net/p/chemoelectric/ratfor77/ public domain 1.0]}}
{{works with|gfortran|11.3.0}}
<syntaxhighlight lang="ratfor">#
# The Rosetta Code simulated annealing task, in Ratfor 77.
#
# This implementation uses the RANDOM_NUMBER intrinsic and therefore
# will not work with f2c. It will work with gfortran. (One could
# substitute a random number generator from the Fullerton Function
# Library, or from elsewhere.)
#
function rndint (imin, imax)
implicit none
integer imin, imax, rndint
real rndnum
call random_number (rndnum)
rndint = imin + floor ((imax - imin + 1) * rndnum)
end
function icoord (loc)
implicit none
integer loc, icoord
icoord = loc / 10
end
function jcoord (loc)
implicit none
integer loc, jcoord
jcoord = mod (loc, 10)
end
function locatn (i, j) # Location.
implicit none
integer i, j, locatn
locatn = (10 * i) + j
end
subroutine rndpth (path) # Randomize a path.
implicit none
integer path(0:99)
integer rndint
integer i, j, xi, xj
for (i = 0; i <= 99; i = i + 1)
path(i) = i
# Fisher-Yates shuffle of elements 1 .. 99.
for (i = 1; i <= 98; i = i + 1)
{
j = rndint (i + 1, 99)
xi = path(i)
xj = path(j)
path(i) = xj
path(j) = xi
}
end
function dstnce (loc1, loc2) # Distance.
implicit none
integer loc1, loc2
real dstnce
integer icoord, jcoord
integer i1, j1
integer i2, j2
integer di, dj
i1 = icoord (loc1)
j1 = jcoord (loc1)
i2 = icoord (loc2)
j2 = jcoord (loc2)
di = i1 - i2
dj = j1 - j2
dstnce = sqrt (real ((di * di) + (dj * dj)))
end
function pthlen (path) # Path length.
implicit none
integer path(0:99)
real pthlen
real dstnce
real len
integer i
len = dstnce (path(0), path(99))
for (i = 0; i <= 98; i = i + 1)
len = len + dstnce (path(i), path(i + 1))
pthlen = len
end
subroutine addnbr (nbrs, numnbr, nbr) # Add neighbor.
implicit none
integer nbrs(1:8)
integer numnbr
integer nbr
if (nbr != 0)
{
numnbr = numnbr + 1
nbrs(numnbr) = nbr
}
end
subroutine fndnbr (loc, nbrs, numnbr) # Find neighbors.
implicit none
integer loc
integer nbrs(1:8)
integer numnbr
integer icoord, jcoord
integer locatn
integer i, j
integer c1, c2, c3, c4, c5, c6, c7, c8
c1 = 0
c2 = 0
c3 = 0
c4 = 0
c5 = 0
c6 = 0
c7 = 0
c8 = 0
i = icoord (loc)
j = jcoord (loc)
if (i < 9)
{
c1 = locatn (i + 1, j)
if (j < 9)
c2 = locatn (i + 1, j + 1)
if (0 < j)
c3 = locatn (i + 1, j - 1)
}
if (0 < i)
{
c4 = locatn (i - 1, j)
if (j < 9)
c5 = locatn (i - 1, j + 1)
if (0 < j)
c6 = locatn (i - 1, j - 1)
}
if (j < 9)
c7 = locatn (i, j + 1)
if (0 < j)
c8 = locatn (i, j - 1)
numnbr = 0
call addnbr (nbrs, numnbr, c1)
call addnbr (nbrs, numnbr, c2)
call addnbr (nbrs, numnbr, c3)
call addnbr (nbrs, numnbr, c4)
call addnbr (nbrs, numnbr, c5)
call addnbr (nbrs, numnbr, c6)
call addnbr (nbrs, numnbr, c7)
call addnbr (nbrs, numnbr, c8)
end
subroutine nbrpth (path, nbrp) # Make a neighbor path.
implicit none
integer path(0:99), nbrp(0:99)
integer rndint
integer u, v
integer nbrs(1:8)
integer numnbr
integer j, iu, iv
for (j = 0; j <= 99; j = j + 1)
nbrp(j) = path(j)
u = rndint (1, 99)
call fndnbr (u, nbrs, numnbr)
v = nbrs(rndint (1, numnbr))
j = 1
iu = 0
iv = 0
while (iu == 0 || iv == 0)
{
if (nbrp(j) == u)
iu = j
else if (nbrp(j) == v)
iv = j
j = j + 1
}
nbrp(iu) = v
nbrp(iv) = u
end
function temp (kT, kmax, k) # Temperature.
implicit none
real kT
integer kmax, k
real temp
real kf, kmaxf
kf = real (k)
kmaxf = real (kmax)
temp = kT * (1.0 - (kf / kmaxf))
end
function prob (deltaE, T) # Probability.
implicit none
real deltaE, T, prob
real x
if (T == 0.0)
prob = 0.0
else
{
x = -(deltaE / T)
if (x < -80)
prob = 0 # Avoid underflow.
else
prob = exp (-(deltaE / T))
}
end
subroutine show (k, T, E)
implicit none
integer k
real T, E
10 format (1X, I7, 1X, F7.1, 1X, F10.2)
write (*, 10) k, T, E
end
subroutine dsplay (path)
implicit none
integer path(0:99)
100 format (8(I2, ' -> '))
write (*, 100) path
end
subroutine sa (kT, kmax, path)
implicit none
real kT
integer kmax
integer path(0:99)
real pthlen
real temp, prob
integer kshow
integer k
integer j
real E, Etrial, T
integer trial(0:99)
real rndnum
kshow = kmax / 10
E = pthlen (path)
for (k = 0; k <= kmax; k = k + 1)
{
T = temp (kT, kmax, k)
if (mod (k, kshow) == 0)
call show (k, T, E)
call nbrpth (path, trial)
Etrial = pthlen (trial)
if (Etrial <= E)
{
for (j = 0; j <= 99; j = j + 1)
path(j) = trial(j)
E = Etrial
}
else
{
call random_number (rndnum)
if (rndnum <= prob (Etrial - E, T))
{
for (j = 0; j <= 99; j = j + 1)
path(j) = trial(j)
E = Etrial
}
}
}
end
program simanl
implicit none
real pthlen
integer path(0:99)
real kT
integer kmax
kT = 1.0
kmax = 1000000
10 format ()
20 format (' kT: ', F0.2)
30 format (' kmax: ', I0)
40 format (' k T E(s)')
50 format (' --------------------------')
60 format ('Final E(s): ', F0.2)
write (*, 10)
write (*, 20) kT
write (*, 30) kmax
write (*, 10)
write (*, 40)
write (*, 50)
call rndpth (path)
call sa (kT, kmax, path)
write (*, 10)
call dsplay (path)
write (*, 10)
write (*, 60) pthlen (path)
write (*, 10)
end</syntaxhighlight>
{{out}}
An example run:
<pre>$ ratfor77 simanneal.r > sa.f && gfortran -O3 -std=legacy sa.f && ./a.out
kT: 1.00
kmax: 1000000
k T E(s)
--------------------------
0 1.0 547.76
100000 0.9 190.62
200000 0.8 187.74
300000 0.7 171.72
400000 0.6 153.08
500000 0.5 131.15
600000 0.4 119.57
700000 0.3 111.20
800000 0.2 105.31
900000 0.1 103.07
1000000 0.0 102.89
0 -> 1 -> 2 -> 12 -> 11 -> 32 -> 33 -> 43 ->
42 -> 52 -> 51 -> 41 -> 31 -> 30 -> 40 -> 50 ->
60 -> 61 -> 62 -> 63 -> 53 -> 54 -> 44 -> 34 ->
24 -> 25 -> 14 -> 15 -> 16 -> 26 -> 36 -> 35 ->
45 -> 55 -> 56 -> 46 -> 47 -> 57 -> 58 -> 68 ->
67 -> 77 -> 86 -> 76 -> 66 -> 65 -> 64 -> 74 ->
75 -> 85 -> 84 -> 83 -> 73 -> 72 -> 71 -> 70 ->
80 -> 90 -> 91 -> 81 -> 82 -> 92 -> 93 -> 94 ->
95 -> 96 -> 97 -> 87 -> 98 -> 99 -> 89 -> 88 ->
78 -> 79 -> 69 -> 59 -> 49 -> 48 -> 39 -> 38 ->
37 -> 27 -> 17 -> 18 -> 28 -> 29 -> 19 -> 9 ->
8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 13 -> 23 ->
22 -> 21 -> 20 -> 10 ->
Final E(s): 102.89
</pre>
=={{header|Scheme}}==
Line 2,656 ⟶ 3,394:
<
(r7rs)
(chicken (import r7rs)))
Line 2,857 ⟶ 3,595:
(display (path-length s-final))
(newline)))
(newline)</
{{out}}
Line 2,908 ⟶ 3,646:
<
(r7rs)
(chicken (import r7rs)))
Line 3,115 ⟶ 3,853:
(format #t "Final E(s): ~,5F~%" (E_s s-final))
(format #t "Final path length: ~,5F~%" (path-length s-final))
(newline)</
Line 3,238 ⟶ 3,976:
=={{header|Sidef}}==
{{trans|Julia}}
<
# Eₛ: length(path)
Line 3,330 ⟶ 4,068:
}.map(1..100)
TravelingSalesman::findpath(citydist, 1e6, 1)</
{{out}}
Line 3,378 ⟶ 4,116:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./math" for Math
import "./fmt" for Fmt
// distances
Line 3,476 ⟶ 4,214:
}
sa.call(1e6, 1)</
{{out}}
Line 3,513 ⟶ 4,251:
=={{header|zkl}}==
{{trans|EchoLisp}}
<
ab,cd,a,b,c,d:=abcd/100, abcd%100, ab/10,ab%10, cd/10,cd%10;
(a-c).toFloat().hypot(b-d)
Line 3,571 ⟶ 4,309:
println("E(s_final) %f".fmt(Emin));
println("Path: ",s.toString(*));
}</
<syntaxhighlight lang
{{out}}
<pre>
|