×

Loading...
Ad by
  • 推荐 OXIO 加拿大高速网络，最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务
Ad by
  • 推荐 OXIO 加拿大高速网络，最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

@Manitoba

C++ source code for TSP 最短路径算法

jin_ting(jy)
Recently, the best way for solving such kind of NP-complete problem as
Traveling Salesman Problem (TSP), is to use Meta-heuristics such as Simulated Annealing (SA), Genetic Algorithms (GA), and other heuristic algorithms, or a combination of them. In my opinion, the main difference of the algorithms is efficiency (speed), not effectiveness (quality) of the solutions. So if speed is not your major concern (e.g not many cities), anyone of them will do the job very well. Some special cases of the TSP are not NP-hard problem, and therefore can be solved by an simple exact method.

The most effective and simple algorithm was done by LK back in 1973:

Lin, S. and Kernighan, B.W. An effective heuristic for the traveling-salesman problem. Oper. Res. 21 (1973)

Some C/C++ source code are listed in the following links:

http://www.lalena.com/ai/tsp/
http://www.netlib.org/c/numcomp-free-c
(#1278797@0)
Last Updated: 2003-7-10
This post has been archived. It cannot be replied.
Report

Replies, comments and Discussions:

  • 枫下家园 / 电脑用户 / 请教会C++的大侠：在哪可以找到有名的关于推销员推销产品，走最短路线的问题的code?非常感谢 -lovechina(lovechina); 2003-7-8 (#1275565@0)
    • 好像router的最短路径算法比较类似 -benii(自私且不爱国的搬运工); 2003-7-8 (#1275656@0)
    • 你是不是指TSP（traveling salesman problem)? If yes, then forget it because it is NP-hard. -jemacs(Jemacs); 2003-7-8 (#1275967@0)
    • C++ source code for TSP 最短路径算法 -jin_ting(jy); 2003-7-10 {902} (#1278797@0)
      Recently, the best way for solving such kind of NP-complete problem as
      Traveling Salesman Problem (TSP), is to use Meta-heuristics such as Simulated Annealing (SA), Genetic Algorithms (GA), and other heuristic algorithms, or a combination of them. In my opinion, the main difference of the algorithms is efficiency (speed), not effectiveness (quality) of the solutions. So if speed is not your major concern (e.g not many cities), anyone of them will do the job very well. Some special cases of the TSP are not NP-hard problem, and therefore can be solved by an simple exact method.

      The most effective and simple algorithm was done by LK back in 1973:

      Lin, S. and Kernighan, B.W. An effective heuristic for the traveling-salesman problem. Oper. Res. 21 (1973)

      Some C/C++ source code are listed in the following links:

      http://www.lalena.com/ai/tsp/
      http://www.netlib.org/c/numcomp-free-c

More Topics

  • 求教：考虑在黑五时找一个好的DEAL 买个 GAME PC,主要用来进行3D Modeling and rendering。 预算最好在$1500以内。请问买那个品牌的，Intel or AMD cpu? 那款 GPU 比较好。谢谢！
  • 俺的电脑，突然变得很慢，然后一两个小时自动关机，扫描没病毒。重置系统，由于自动关机，也搞不成。哪位大神指点一二。
  • 请问！我把bell手机号码转到freedom公司，我还需要给bell打电话确定cancel bell的手机计划吗？谢谢！
  • 请问：马斯克的星链电话功能什么手机可以用？加拿大可以用吗？什么价位一个月？
  • 看到网购手机充电线都写着Android Type C cable，请问这是适用于所有三星手机吗？谢谢
    • 枫下论坛主坛 /  枫下家园 /  电脑用户