У меня пока так вышло:
Points := { 1: [9,10], 2: [3,9], 3: [2,8], 4: [5,8,16], 5: [4,7,12], 6: [7,20], 7: [5,6], 8: [3,4,14,20], 9: [1,2,10,12,14], 10: [1,9,11], 11: [10,12]
, 12: [5,9,11,13], 13: [12,14,15], 14: [8,9,13,15], 15: [13,14,16], 16: [4,15,17,20], 17: [16,18], 18: [17,19], 19: [18,20], 20: [6,8,16,19] }
ways := GetShortWays(Points, 11, 20)
for k, v in ways {
text .= A_Index = 1 ? "" : "`n"
for k, v in v
text .= (A_Index = 1 ? "" : " —> ") . v
}
MsgBox, % text
GetShortWays(points, start, end)
{
max := 4
Loop {
if !IsObject(jumps := GetJumps(points, start, end, [start]))
Return [[start, end]]
ways := [], CurrentNode := {way: [start], jumps: jumps, PrevNode: ""}, max *= 2
while CurrentNode {
m := ways.1.MaxIndex(), c := CurrentNode.way.MaxIndex()
if ( c + 1 = m || c > max || !(NextPoint := CurrentNode.jumps.Pop()) ) {
CurrentNode := CurrentNode.PrevNode
continue
}
way := CurrentNode.way.Clone()
if jumps := GetJumps(points, NextPoint, end, way) {
if IsObject(jumps) && way.Push(NextPoint)
CurrentNode := {way: way, jumps: jumps, PrevNode: CurrentNode}
else
way.Push(NextPoint, jumps), (way.MaxIndex() < m && ways := []), ways.Push(way)
}
}
} until ways.1.1 || max > points.MaxIndex()
Return ways
}
GetJumps(points, p, end, way)
{
jumps := []
for k, v in points[p] {
if (v = end)
Return v
for i, c in way
if (v = c)
continue 2
jumps.Push(v)
}
Return jumps
}
Можно посоревноваться:
SetBatchLines, -1
length := 1000
MaxLinks := 5
Map := CreateMap(length, MaxLinks)
p := GetRandomNumbers(length, 2)
start := A_TickCount
text1 := GetWaysText(GetShortWays(Map, p[1], p[2]))
time1 := A_TickCount - start
SoundBeep
start := A_TickCount
text2 := ShortPath(p[1], p[2], Map, 1)
time2 := A_TickCount - start
MsgBox, % "teadrinker:`n`nTime = " time1 "`n" text1 "`n`nserzh82saratov:`n`nTime = " time2 "`n" text2
GetShortWays(points, start, end)
{
max := 4
Loop {
if !IsObject(jumps := GetJumps(points, start, end, [start]))
Return [[start, end]]
ways := [], CurrentNode := {way: [start], jumps: jumps, PrevNode: ""}, max *= 2
while CurrentNode {
m := ways.1.MaxIndex(), c := CurrentNode.way.MaxIndex()
if ( c + 1 = m || c > max || !(NextPoint := CurrentNode.jumps.Pop()) ) {
CurrentNode := CurrentNode.PrevNode
continue
}
way := CurrentNode.way.Clone()
if jumps := GetJumps(points, NextPoint, end, way) {
if IsObject(jumps) && way.Push(NextPoint)
CurrentNode := {way: way, jumps: jumps, PrevNode: CurrentNode}
else
way.Push(NextPoint, jumps), (way.MaxIndex() < m && ways := []), ways.Push(way)
}
}
} until ways.1.1 || max > points.MaxIndex()
Return ways
}
GetJumps(points, p, end, way)
{
jumps := []
for k, v in points[p] {
if (v = end)
Return v
for i, c in way
if (v = c)
continue 2
jumps.Push(v)
}
Return jumps
}
GetWaysText(ways)
{
for k, v in ways {
text .= A_Index = 1 ? "" : "`n"
for k, v in v
text .= (A_Index = 1 ? "" : ", ") . v
}
Return text
}
;***********************************************************************************************************
ShortPath(From, To, Map, RetText = 0) {
Bridge := [From], Index := [1], Exist := [], Finds := []
Loop
{
M := Bridge.MaxIndex(), B := Bridge[M], I := Index[M], N := Map[b][i], Exist[b] := 1
If (M = 1 && !N)
Break
If (!N || Min && M > Min)
{
Exist[Bridge.Pop()] := 0, Index.Pop(), ++Index[Bridge.MaxIndex()]
Continue
}
; If (I = 1 && (From = To ? M > 2 : 1)) ; для кольцевых маршрутов
If (I = 1)
For k, v in Map[b]
If (v = To)
{
Find := Bridge.Clone(), Find.Push(To), Finds.Push(Find), Min := M
If (M = 1)
Break 2
Exist[Bridge.Pop()] := 0, Index.Pop(), ++Index[Bridge.MaxIndex()]
Continue 2
}
If Exist[N]
++Index[M]
Else
Bridge.Push(N), Index.Push(1)
}
For k, v in Finds, Ret := []
v.MaxIndex() = Min + 1 ? Ret.Push(v) : 0
If RetText
For k, v in Ret
For k, v in v, Ret .= A_Index = 1 ? "" : "`n"
Ret .= (A_Index = 1 ? "" : ", ") . v
Return Ret
}
;********************************************************************************************************************
CreateMap(len, max)
{
arr := []
Loop % len
arr[A_Index] := []
IndexArr := []
Loop % len
IndexArr[A_Index] := A_Index
Loop % len {
i := A_Index
m := arr[i].MaxIndex(), (!m && m := 0)
rest := max - m
if (rest = 0)
continue
WithoutCurrent := IndexArr.Clone()
RemoveFromIdx(i, WithoutCurrent)
Random, rand, 1, rest
for k, v in keys := GetRandomNumbers(WithoutCurrent.MaxIndex(), rand) {
idx := WithoutCurrent[v]
arr[idx].Push(i)
( arr[idx].MaxIndex() >= max && RemoveFromIdx(idx, IndexArr) )
arr[i].Push(idx)
}
( arr[i].MaxIndex() >= max && RemoveFromIdx(i, IndexArr) )
}
Return arr
}
RemoveFromIdx(n, arr)
{
for k, v in arr
if (v = n)
break
arr.RemoveAt(k)
}
GetRandomNumbers(len, num)
{
arr := []
Loop % len
arr[A_Index] := A_Index
RetArr := []
Loop % num {
Random, rand, 1, arr.MaxIndex()
RetArr.Push(arr.RemoveAt(rand))
}
Return RetArr
}
Разработка AHK-скриптов:
e-mail
dfiveg@mail.ruTelegram
jollycoder
