Roger Hui wrote:
> Discussions of efficiency on this problem must
> involve Warnsdorff's algorithm, invented in 1823.
> ktourw 8 takes 0.003 seconds and ktourw 74
> takes roughly the same time as ktourx 8.
>
> The heuristic is that on each step, choose a
> successor having the fewest further moves.
> I don't know yet whether I've made a mistake
> in the implementation or whether the heuristic
> sometimes fails:
My implementation follows. It is not as fast as ktourw, but it agrees
with it, and gives plausible results for all arguments, including 11.
ktourw2=:3 : 0
m=.kmoves y
p=.*:y
stack=.<0
while. #stack do.
s=.>{: stack
if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
ms=.m-.&.> < s
t=.({:s){::ms
stack=.(}:stack), (<s),&.> t \: #&> t { ms
end.
)
To ensure it was doing the right thing, I reduced the graph each time.
Obviously this is quite expensive.
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
