Exact Held-Karp dynamic programme (O(2^n n^2)) or a nearest-neighbour tour
from node 1 improved by first-improvement 2-opt; "auto" is exact for
n <= max_exact. Tours start at node 1 with the smaller neighbour second.
Usage
TravellingSalesman(
points = NULL,
dist = NULL,
method = c("auto", "exact", "heuristic"),
max_exact = 13
)
Arguments
- points
Coordinate matrix (rows are nodes), or NULL.
- dist
Symmetric distance matrix, or NULL.
- method
"auto", "exact" or "heuristic".
- max_exact
Largest n solved exactly under "auto".
Value
list(tour (1-based), length, method).
References
Held, M. and Karp, R. M. (1962). A dynamic programming approach
to sequencing problems. Journal of SIAM 10, 196-210.
Croes, G. A. (1958). A method for solving traveling-salesman problems.
Operations Research 6, 791-812.
Examples
TravellingSalesman(rbind(c(0, 0), c(1, 0), c(1, 1), c(0, 1)))$length
#> [1] 4
