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