Connect-the-dots methods: branch and bound
| ← Previous revision | Revision as of 20:00, 12 October 2021 | ||
| Line 191: | Line 191: | ||
|
::It’s working, but it’s not working that well. So far, the best we’ve gotten is about a 70% confidence on the actual end-points, and in the most problematic datasets, that drops down to about 50%.
|
::It’s working, but it’s not working that well. So far, the best we’ve gotten is about a 70% confidence on the actual end-points, and in the most problematic datasets, that drops down to about 50%.
|
||
|
::I greatly appreciate the suggestion! It’s just me and one of my programmers working on this (I’ve got the others on a more pressing issue), so we hadn’t considered whether a TS-heuristic might help. I’ll be looking into that straight away. Thanks again. [[Special:Contributions/74.175.117.2|74.175.117.2]] ([[User talk:74.175.117.2|talk]]) 18:16, 12 October 2021 (UTC)
|
::I greatly appreciate the suggestion! It’s just me and one of my programmers working on this (I’ve got the others on a more pressing issue), so we hadn’t considered whether a TS-heuristic might help. I’ll be looking into that straight away. Thanks again. [[Special:Contributions/74.175.117.2|74.175.117.2]] ([[User talk:74.175.117.2|talk]]) 18:16, 12 October 2021 (UTC)
|
||
| + |
:::How many dots do you typically have. For moderate numbers, finding an exact solution to the TSP while pruning the search using [[branch and bound]]<sup>[https://www.techiedelight.com/travelling-salesman-problem-using-branch-and-bound/]</sup> may be doable. –{{#ifeq:{{FULLPAGENAME}}|{{#invoke:Redirect|main|User talk:Lambiam}}|Lambiam|{{#if:Lambiam|[[User talk:Lambiam|Lambiam]]|[[User talk:Lambiam]]}}}} 19:59, 12 October 2021 (UTC)
|
||