Shortest common supersequence: Difference between revisions
Added FreeBASIC
(Added FreeBASIC) |
|||
Line 339:
<pre>
abdcabdab
</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>
| |||