simple_tsp icon indicating copy to clipboard operation
simple_tsp copied to clipboard

Incorrect old edge checking

Open bkj opened this issue 5 years ago • 1 comments
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

bkj avatar May 27 '20 20:05 bkj

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

bkj avatar May 27 '20 20:05 bkj