在c / c ++中寻找一个开源的Traveling Salesman函数/库？
我知道那里有一些不同的旅行推销员项目，我和LKH玩了一下，但我想知道是否有人对其他任何人有任何建议？
我的项目是GPL，所以我需要一些与该许可兼容的东西。
输入http://sofzh.miximages.com/c%2B%2B/traveling-salesman-L.gif 输出http://sofzh.miximages.com/c%2B%2B/traveling-salesman-R.gif
通常， Space Filling Fractals将以最低的成本为您提供一些最佳结果。
特别是，我会推荐Sierpiński曲线 。
以下是使用它的示例实现：
(defvar *grid-width* 100000) (defvar *grid-heigth* 100000) (defvar *max-number-of-points* 1000) (defvar *search-area-width* (* 2 *grid-width*)) (defvar *search-area-heigth* (* 2 *grid-heigth*)) (defun make-random-point (max-x max-y) "makes a point in a random position of the grid" (complex (/ (random (* max-x 1000)) 1000) (/ (random (* max-y 1000)) 1000))) (defun make-random-point-list (max-len) "makes a list of random points up to max-len length" (let ((value ())) ; Make a set of random points (dotimes (n (random max-len) value) (setq value (cons (make-random-point *grid-width* *grid-heigth*) value))))) (defun get-printable-point-position (point) "Gets a rounded-off point that can be used to make a dot on a visual grid" (complex (round (realpart point)) (round (imagpart point)))) (defun euclid (point-a point-b) "calculates the euclidean distance in between two points" (let* ((p (- point-a point-b))) (sqrt (+ (expt (realpart p) 2) (expt (imagpart p) 2))))) (defstruct triangle "A triangle consists of 3 points. Complex numbers are used to construct the points, the real part signifying the X axis, and the imaginary part signifying the Y axis." abc) (defun avg (&rest numbers) "Gets the average of the numbers provided" (if (null numbers) 1 ; prevents divide by 0 (/ (apply #'+ numbers) (length numbers)))) ;/ (defun get-triangle-centre (triangle) "Gets the centre of a triangle" (avg (triangle-a triangle) (triangle-b triangle) (triangle-c triangle))) (defstruct (triangle-list (:include triangle)) point-list) (defun triangle-split (triangle) "Splits a triangle in two according to the rule: { a0->c1; b0->a1,c2; c0->a2; avg(c0,a0)->b1,b2 }" (let* ((old-a-point (triangle-a triangle)) (old-b-point (triangle-b triangle)) (old-c-point (triangle-c triangle)) (new-b-point (avg old-a-point old-c-point))) (list (make-triangle-list :a old-b-point :b new-b-point :c old-a-point) (make-triangle-list :a old-c-point :b new-b-point :c old-b-point)))) (defun triangle-list-split (triangle-list) "Split a triangle list and acomodate all the points in their right places" (let* ((triangles (triangle-split triangle-list)) (triangle-a (car triangles)) (triangle-b (cadr triangles)) (centre-a (get-triangle-centre triangle-a)) (centre-b (get-triangle-centre triangle-b))) (dolist (point (triangle-list-point-list triangle-list)) (if (< (euclid point centre-a) (euclid point centre-b)) (setf (triangle-list-point-list triangle-a) (cons point (triangle-list-point-list triangle-a))) (setf (triangle-list-point-list triangle-b) (cons point (triangle-list-point-list triangle-b))))) (let ((list-a (triangle-list-point-list triangle-a)) (list-b (triangle-list-point-list triangle-b))) (if (= 1 (length list-a)) (setf (triangle-list-point-list triangle-a) (car list-a))) (if (= 1 (length list-b)) (setf (triangle-list-point-list triangle-b) (car list-b)))) (list triangle-a triangle-b))) (defun print-point (out point &rest args) "Utility function - Pretty-prints a point" (format out "(X:~F, Y:~F)" (realpart point) (imagpart point)) args) (defun pprint-triangle-list (out triangle-list &rest args) "Utility function - Pretty-prints a triangle-list object" (format out " TRIANGLE{ A:~/print-point/ B:~/print-point/ C:~/print-point/ CENTRE:~/print-point/ POINTS:{~{~/print-point/~^,~% ~}}~& }" (triangle-a triangle-list) (triangle-b triangle-list) (triangle-c triangle-list) (get-triangle-centre triangle-list) (let ((points (triangle-list-point-list triangle-list))) (cond ((null points) ()) ((listp points) points) (t (list points))))) args) (defun print-list-of-triangle-list (lst) "Pretty-prints a list of triangle-list objects" (format t "(~{~/pprint-triangle-list/~^,~% ~}~&)" lst)) (defun explode (lst) "explodes a triangle-list list and gets all the points in the order they should be" (let ((l (flatten lst))) (cond ((null l) ()) ((triangle-list-p l) (explode (triangle-list-split l))) ((null (triangle-list-point-list (car l))) (explode (cdr l))) ((atom (triangle-list-point-list (car l))) (cons (car l) (explode (cdr l)))) (t (explode (append (triangle-list-split (car l)) (cdr l))))))) (defun flatten (lst) "Flattens a list (removes nesting and nulls)" (cond ((atom lst) lst) ((listp (car lst)) (append (flatten (car lst)) (flatten (cdr lst)))) (t (append (list (car lst)) (flatten (cdr lst)))))) (let ((triangle (make-triangle-list :a (complex 0 *search-area-heigth*) :b 0 :c *search-area-width* :point-list (make-random-point-list *max-number-of-points*)))) (print-list-of-triangle-list (explode triangle))) 我也有一个使用GA的版本（在C中有一个），但它存在于死硬盘中。
这个看起来不错。
我知道这不是一个好的答案，但如果你对改变技术持开放态度，那么scipy有一堆非常好的优化算法
这里有一个完全解决TSP，但它在PASCAL中。 但是，在当前forms中，距离是整数。 在C ++中不应该太难改写。