simple_tsp
simple_tsp copied to clipboard
Incorrect old edge checking
trafficstars
In this line:
https://github.com/cfld/simple_tsp/blob/master/simple_tsp/lk.py#L141
we should only be checking the old edges up to the current depth. Otherwise, you could get something like this which is incorrect
pre filter 33 32 36 35
old = [(32, 33), (35, 36)]
pass filter
pre filter 33 32 36 37
old = [(32, 33), (35, 36)]
no pass filter
I think the fix is if contains(cp1, cp2, old[:depth]): continue
Likewise, I think should also change
if contains(act, cp1, new): continue
to
if contains(act, cp1, new[:depth - 1]): continue