Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Incorrect old edge checking #1

Open
bkj opened this issue May 27, 2020 · 1 comment
Open

Incorrect old edge checking #1

bkj opened this issue May 27, 2020 · 1 comment

Comments

@bkj
Copy link
Contributor

bkj commented May 27, 2020

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
Copy link
Contributor Author

bkj commented May 27, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant