明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 17609|回复: 36

点集最短回路(TSP问题)讨论

    [复制链接]
发表于 2012-10-9 01:58:14 | 显示全部楼层 |阅读模式
本帖最后由 chlh_jd 于 2012-10-9 23:09 编辑

点集最短回路实际上是TSP问题的简化版,属于N-P难问题,目前针对这个问题国内已有很多研究。
       这里有篇TSP问题算法综述 :http://www.joces.org.cn/CN/article/downloadArticleFile.do?ttachType=PDF&id=9165
       维基百科主要列了:遗传算法、模拟退火、群集智能(词条上没有解释,个人猜想是一种结合人工智能把点簇归到一起最佳出路放置在点簇凸包上的一种组合算法、算法关键应该是在点集归簇,或者说其实质是模拟退火归簇与遗传算法的结合)、局部搜索和多主体优化系统。  http://zh.wikipedia.org/wiki/TSP
       美国 Richard Johnsonbaugh, Marcus Schaefer 著作 《大学算法教程》里面提及了一些NP完全的基本算法有:蛮干法、随机方法、近似方法、参数化方法、启发式搜索 等  。


二叉树描述法:有见过采用最优二叉树算法求解的TSP的,一般结合遗传算法作前期最优二叉树数据构造。
                      http://baike.soso.com/v6426781.htm

启发式搜索法:基于直观或经验构造的算法,现代优化算法中常常仅是其中的一步,单独用来求解TSP不太合适;应用实例还是有的:《一种改进的TSP问题启发式算法》
             TSP 问题的脂肪计算复杂性与启发式算法设计   

最邻近法:一种偏向于解决特定几何问题的弱算法,一般用于遗传算法的基因变异,也有人用来求解简单TSP:
                 单元划分法: 其结果与凸包塌陷方式接近,但凸包塌陷方式得全局性要比它好得多。

禁忌搜索法:常常容易陷入局部最优,需要设置一定的跳出关卡来扩散,以得到最大化的全局最优,
                  常用于解决排序问题(如车间作业排序、图案着色等);因为代码较容易实现,也有很多人用来求解TSP,
                 举例:   http://file.lw23.com/b/b4/b4a/b4a11e29-de82-4ccd-9ca1-3efc9c15c4a8.pdf
                              http://file.lw23.com/a/aa/aa2/aa230e4c-0bd3-4e8d-8eb2-258b576faa34.pdf
                              http://file.lw23.com/1/12/121/12126da9-4356-4a13-a16a-0c37f760bcf7.pdf
                             http://166.111.121.20:9080/mathjournal/XTGC803/xtgc803004.caj.pdf                             

神经网络法:清华大学数学系列教材的《现代优化计算方法》中有介绍一种叫弹性变形算法,其实质就是神经网络法,过程与凸包塌陷的逆过程相似。
               百度文库 《SOFM神经网络最近插入法混合算法在TSP问题中应用研究》                              
                              《Hopfield神经网络在TSP问题中的应用 》

模拟退火法:基于概率分布的局部搜索算法的推广,常用于解决下料问题;因为建模相对简单,也不乏用来解TSP的实例;
              http://www.vckbase.com/index.php/wv/1196
              旅行商问题(TS P)的改进模拟退火算法   
   

蚁群优化算法:常用于医疗数据挖掘;由于需要大量的信息积累,应用于TSP显得效率较低,常常需要结合其他手段来较好地实现。
    百度文库有篇讲稿 《蚁群算法》

遗传算法:目前公认解决TSP等NP-Hard问题的最佳算法,但人们常常不满足于他误差和效率,也因此衍生出非常多的其他算法应用到基因选取、种群优化、交叉变异等组合遗传算法。
编程过程较为复杂(尤其是采用VLISP来实现),目前的编码多数采用二进制,也有采用十进制、十六进制的。前些年要找些类似的源代码学习很困难,现在就很多了。   
有关研究非常多  《基于混合遗传算法的TSP问题优化研究 》

组合算法: 模拟退火+遗传算法
                 基于模拟退火的遗传优化算法在TSP问题中的应用
  
个人认为采用组合遗传算法解决这个问题比较合适,采用VLISP实现最好加个类库处理(如矩形分布、点簇分布、离散分布...)。
早年收集了些遗传算法的文章也上传在这里

俄罗斯的VLisp顶级高手ElpanovEvgeniy曾在Theswamp上提出来讨论,现在看来他已经采用遗传算法解决了这个问题。
http://www.theswamp.org/index.php?topic=30434.75

这里引用Evgeniy提供的2个表供大家讨论用




本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

x

评分

参与人数 3明经币 +6 金钱 +45 收起 理由
cheng5276 + 1 很给力!
qjchen + 2 + 15 很给力!
highflybir + 3 + 30 赞一个!

查看全部评分

本帖被以下淘专辑推荐:

  • · excel|主题: 80, 订阅: 2
发表于 2020-4-3 09:31:51 | 显示全部楼层
chlh_jd 发表于 2013-1-6 03:38
@zdqwy19
      我提供的TSP函数带有一定的遗传特性,并不一定能得到最优解,尤其对于规则点阵;该算法可 ...

你的程序每次运行结果都是一样的,没有看出遗传算法的随机性啊
发表于 2020-4-3 08:51:01 | 显示全部楼层
mahuan1279 发表于 2017-11-13 21:21
测试图为什么会出现交叉现象?

用遗传算法得到一个近优解。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

x
发表于 2012-10-9 08:25:09 | 显示全部楼层
 楼主| 发表于 2012-10-9 11:49:56 | 显示全部楼层
本帖最后由 chlh_jd 于 2012-10-9 11:51 编辑

贴出用 ElpanovEvgeniy 的方法改进 纯VLISP 版本 , 比较适用于不规则离散点集
  1. ;;;------------------------TSP------------------------------------------------------------;;;
  2. ;;;---------------------------------------------------------------------------------------;;;
  3. (defun c:test (/ foo f2 ptl lst l n i d0 l0 l1 d1)
  4.   ;;by GSLS(SS)
  5.   ;;refer ElpanovEvgeniy's method from  http://www.theswamp.org/index.php?topic=30434.75
  6.   ;;2012-8-10
  7.   (defun foo (l / D D0 D1)
  8.     (setq l0 (mapcar (function list) (cons (last l) l) l)) ;_  setq
  9. ;_  defun
  10.     (setq d0 (get-closedpolygon-length l))
  11.     (while
  12.       (> d0
  13.          (progn
  14.            (foreach a l0
  15.              (setq d (get-closedpolygon-length l))
  16.              (setq l1 (vl-remove (car a) (vl-remove (cadr a) l)))
  17.              (setq l1 (f1 (car a) l1))
  18.              (setq l1 (f1 (cadr a) l1))
  19.              (if (> d
  20.                     (setq d1 (get-closedpolygon-length l1))
  21.                  )
  22.                (setq d d1
  23.                      l l1
  24.                ) ;_  setq
  25.              ) ;_  if
  26.              (setq l1 (vl-remove (car a) (vl-remove (cadr a) l)))
  27.              (setq l1 (f1 (cadr a) l1))
  28.              (setq l1 (f1 (car a) l1))
  29.              (if (> d
  30.                     (setq d1 (get-closedpolygon-length l1))
  31.                  )
  32.                (setq d d1
  33.                      l l1
  34.                )
  35.              )
  36.            )
  37.            d
  38.          ) ;_  progn
  39.       ) ;_  <
  40.        (setq d0 d)
  41.     ) ;_  while   
  42.     (setq d (get-closedpolygon-length l))   
  43.     l
  44.   )
  45.   (defun f1 (a l)
  46.     (ins-lst a (get-closest-i l a) l)
  47.   )
  48.   (defun f2 (lst)
  49.     (mapcar (function (lambda (p0 p p1 / a)
  50.                         (setq a (- (angle p p0) (angle p p1)))
  51.                         (if (< a (- pi))
  52.                           (abs (+ a pi pi))
  53.                           (if (> a pi)
  54.                             (abs (- a pi pi))
  55.                             (abs a)
  56.                           )
  57.                         )
  58.                       )
  59.             )
  60.             (cons (last lst) lst)
  61.             lst
  62.             (reverse (cons (car lst) (reverse (cdr lst))))
  63.     )
  64.   )
  65.   (setq        ptl (my-getpt)
  66.         ptl (mapcar (function (lambda (p) (list (car p) (cadr p)))) ptl)
  67.   )
  68.   (setq t1 (getvar "MilliSecs"))
  69.   (setq lst (Graham-scan ptl))
  70.   (foreach a lst
  71.     (setq ptl (vl-remove a ptl))
  72.   )
  73.   (while (and (> (length ptl) 2) (setq l (Graham-scan ptl)))
  74.     (foreach p l
  75.       (setq ptl (vl-remove p ptl))
  76.       (setq n (get-minadddist-i lst p))
  77.       (setq lst (ins-lst p n lst))
  78.     )
  79.   )
  80.   (if ptl
  81.     (foreach p ptl
  82.       (setq n (get-minadddist-i lst p))
  83.       (setq lst (ins-lst p n lst))
  84.     )
  85.   )
  86.   (setq lst (foo lst))
  87.   (setq l (f2 lst))
  88.   (setq        i  0
  89.         l0 lst
  90.         n  (length lst)
  91.         d0 (get-closedpolygon-length lst)
  92.   )
  93.   (foreach a l
  94.     (if        (and (< a _pi3) (= (setq p (nth i lst)) (nth i l0)))
  95.       (progn
  96.         (if (= i 0)
  97.           (setq p0 (last lst))
  98.           (setq p0 (nth (1- i) lst))
  99.         )
  100.         (if (= i (1- n))
  101.           (setq p1 (car lst))
  102.           (setq p1 (nth (1+ i) lst))
  103.         )
  104.         (setq m        (list (list p0 p1 p)
  105.                       (list p1 p p0)
  106.                       (list p1 p0 p)
  107.                       (list p p0 p1)
  108.                       (list p p1 p0)
  109.                 )
  110.         )
  111.         (setq l1
  112.                (car (vl-sort (mapcar (function (lambda (x)
  113.                                                  (ch-para-lst x i lst)
  114.                                                )
  115.                                      )
  116.                                      m
  117.                              )
  118.                              (function (lambda (e1 e2)
  119.                                          (< (get-closedpolygon-length e1)
  120.                                             (get-closedpolygon-length e2)
  121.                                          )
  122.                                        )
  123.                              )
  124.                     )
  125.                )
  126.         )
  127.         (setq d1 (get-closedpolygon-length l1))
  128.         (if (< d1 d0)
  129.           (setq        d0  d1
  130.                 lst l1
  131.           )
  132.         )
  133.       )
  134.     )
  135.     (setq i (1+ i))
  136.   )
  137.   (setq l (f2 lst))
  138.   (setq        i  0
  139.         l0 lst
  140.         d0 (get-closedpolygon-length lst)
  141.   )
  142.   (foreach a l
  143.     (if        (and (< a _pi2) (setq p (nth i l0)))
  144.       (progn
  145.         (setq l1 (f1 p (vl-remove p lst)))
  146.         (setq d1 (get-closedpolygon-length l1))
  147.         (if (< d1 d0)
  148.           (setq        d0  d1
  149.                 lst l1
  150.           )
  151.         )
  152.       )
  153.     )
  154.     (setq i (1+ i))
  155.   )
  156.   (entmake
  157.     (append (list '(0 . "LWPOLYLINE")
  158.                   '(100 . "AcDbEntity")
  159.                   '(8 . "temp")
  160.                   '(62 . 1)
  161.                   '(100 . "AcDbPolyline")
  162.                   (cons 90 (length lst))
  163.                   '(70 . 1)
  164.             )
  165.             (mapcar (function (lambda (p) (cons 10 p))) lst)
  166.     )
  167.   )
  168.   (setq t2 (getvar "MilliSecs"))
  169.   (princ (strcat "\nTSP Length :" (rtos d0 2 0) "."))
  170.   (princ (strcat "\nUse Time :" (rtos (- t2 t1) 2 0) "ms."))
  171.   (princ)
  172. )
  173. ;;;Use Funtions
  174. ;;;--------------------------------------------------------------
  175. ;; Convex hull of pts , Graham scan method
  176. ;; by Highflybird
  177.   (defun Graham-scan (ptl / hPs rPs PsY Pt0 sPs P Q)
  178.     (if        (< (length ptl) 4)                ;3点以下
  179.       ptl                                ;是本集合
  180.       (progn
  181.         (setq rPs (mapcar (function (lambda (x)
  182.                                       (if (= (length x) 3)
  183.                                         (cdr x)        x)))
  184.                           (mapcar 'reverse ptl));_点表的X和Y交换
  185.               PsY (mapcar 'cadr ptl) ;_点表的Y值的表
  186.               Pt0 (reverse (assoc (apply 'min PsY) rPs)) ;_最下面的点      
  187.               sPs (sort-ad ptl Pt0) ;_按角度距离排序点集
  188.               hPs (list (caddr sPs) (cadr sPs) Pt0) ;_开始的三点
  189.         )
  190.         (foreach n (cdddr sPs)                ;从第4点开始
  191.           (setq        hPs (cons n hPs)        ;把Pi加入到凸集
  192.                 P   (cadr hPs)                ;Pi-1
  193.                 Q   (caddr hPs)                ;Pi-2
  194.           )
  195.           (while (and q (> (det n P Q) -1e-6)) ;如果左转
  196.             (setq hPs (cons n (cddr hPs)) ;删除Pi-1点
  197.                   P   (cadr hPs)        ;得到新的Pi-1点
  198.                   Q   (caddr hPs)        ;得到新的Pi-2点
  199.             )))
  200.         hPs                                ;返回凸集
  201.       ))
  202.   )
  203. ;;;以最下面的点为基点,按照角度和距离分类点集
  204. (defun sort-ad (pl pt)
  205.   (vl-sort pl
  206.            (function (lambda (e1 e2 / an1 an2)
  207.                (setq an1 (angle pt e1)
  208.                      an2 (angle pt e2))
  209.                (if (equal an1 an2 1e-6);_这里降低误差,以适应工程需求
  210.                  (< (distance pt e1) (distance pt e2))
  211.                  (< an1 an2)
  212.                ))))
  213. )
  214. ;;定义三点的行列式,即三点之倍面积
  215. (defun det (p1 p2 p3)
  216.   (- (* (- (car p2) (car p1)) (- (cadr p3) (cadr p1)))
  217.      (* (- (car p3) (car p1)) (- (cadr p2) (cadr p1)))
  218.   ))
  219. ;;;
  220. ;;;------------------------
  221. (defun my-getpt        (/ ss i en l)
  222.   (setq ss (ssget '((0 . "point"))))
  223.   (setq i -1)
  224.   (while (setq en (ssname ss (setq i (1+ i))))
  225.     (setq l (cons (cdr (assoc 10 (entget en))) l))
  226.   )
  227. )
  228. ;;;------------------------
  229. ;;;
  230. ;;(ins-lst 10 5 '(1 2 3 4 5))
  231. ;; i 为新插入元素的位置
  232. (defun ins-lst (new i lst / len fst)
  233.   (cond
  234.     ((minusp i)
  235.      lst
  236.     )
  237.     ((> i (setq len (length lst)))
  238.      lst
  239.     )
  240.     ((> i (/ len 2))
  241.      (reverse (ins-lst new (- len i) (reverse lst)))
  242.     )
  243.     (t
  244.      (append
  245.        (progn
  246.          (setq fst nil)
  247.          (repeat (rem i 4)
  248.            (setq fst (cons (car lst) fst)
  249.                  lst (cdr lst)
  250.            )
  251.          )
  252.          (repeat (/ i 4)
  253.            (setq fst (cons (cadddr lst)
  254.                            (cons (caddr lst)
  255.                                  (cons
  256.                                    (cadr lst)
  257.                                    (cons
  258.                                      (car lst)
  259.                                      fst
  260.                                    )
  261.                                  )
  262.                            )
  263.                      )
  264.                  lst (cddddr lst)
  265.            )
  266.          )
  267.          (reverse fst)
  268.        )
  269.        (list new)
  270.        lst
  271.      )
  272.     )
  273.   )
  274. )
  275. ;;;------------------------
  276. ;;
  277. ;;(ch-para-lst '(7 8 9) 3 '(1 2 3 4 5))
  278. (defun ch-para-lst (para i lst / len fst)
  279.   (setq len (length lst))
  280.   (cond
  281.     ((minusp i)
  282.      lst
  283.     )
  284.     ((> i (1- len))
  285.      lst
  286.     )
  287.     ((= i 0)
  288.      (cons (cadr para)
  289.            (cons (caddr para)
  290.                  (reverse (cons (car para) (cdr (reverse (cddr lst)))))
  291.            )
  292.      )
  293.     )
  294.     ((= i (1- len))
  295.      (reverse
  296.        (append (cdr (reverse para))
  297.                (cddr (reverse (cons (last para) (cdr lst))))
  298.        )
  299.      )
  300.     )
  301.     ((> i (/ len 2))
  302.      (reverse
  303.        (ch-para-lst (reverse para) (- len i 1) (reverse lst))
  304.      )
  305.     )
  306.     (t
  307.      (append
  308.        (progn
  309.          (setq fst nil)
  310.          (repeat (rem i 4)
  311.            (setq fst (cons (car lst) fst)
  312.                  lst (cdr lst)
  313.            )
  314.          )
  315.          (repeat (/ i 4)
  316.            (setq fst (cons (cadddr lst)
  317.                            (cons (caddr lst)
  318.                                  (cons
  319.                                    (cadr lst)
  320.                                    (cons
  321.                                      (car lst)
  322.                                      fst
  323.                                    )
  324.                                  )
  325.                            )
  326.                      )
  327.                  lst (cddddr lst)
  328.            )
  329.          )
  330.          (reverse
  331.            (cons (caddr para)
  332.                  (cons (cadr para) (cons (car para) (cdr fst)))
  333.            )
  334.          )
  335.        )
  336.        (cdr lst)
  337.      )
  338.     )
  339.   )
  340. )
  341. ;;;------------------------
  342. ;;
  343. (defun get-minadddist-i        (lst p)
  344.   (car
  345.     (vl-sort-i
  346.       (mapcar (function        (lambda        (p1 p2)
  347.                           (- (+ (distance p p1) (distance p p2))
  348.                              (distance p1 p2)
  349.                           )
  350.                         )
  351.               )
  352.               (cons (last lst) lst)
  353.               lst
  354.       )
  355.       '<
  356.     )
  357.   )
  358. )
  359. ;;;------------------------
  360. (defun get-closest-i (lst p)
  361.   (car
  362.     (vl-sort-i
  363.       (mapcar
  364.         (function
  365.           (lambda (p1 p2 / pt d d1 d2)
  366.             (setq pt (inters p
  367.                              (polar p (+ (/ pi 2.) (angle p1 p2)) 1.)
  368.                              p1
  369.                              p2
  370.                              nil
  371.                      )
  372.                   d  (distance p1 p2)
  373.                   d1 (distance p p1)
  374.                   d2 (distance p p2)
  375.             )
  376.             (if        pt
  377.               (if (equal (+ (distance pt p1) (distance pt p2)) d 1e-8)
  378.                 (distance p pt)
  379.                 d2
  380.               )
  381.               1e99
  382.             )
  383.           )
  384.         )
  385.         (cons (last lst) lst)
  386.         lst
  387.       )
  388.       '<
  389.     )
  390.   )
  391. )
  392. ;;;------------------------
  393. ;;
  394. (defun get-closedpolygon-length        (l)
  395.   (apply (function +)
  396.          (mapcar (function (lambda (p1 p2)
  397.                              (distance p1 p2)
  398.                            )
  399.                  )
  400.                  (cons (last l) l)
  401.                  l
  402.          )
  403.   )
  404. )

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

x
发表于 2012-10-9 15:51:21 | 显示全部楼层
比较深奥,不过很有用
发表于 2012-10-12 21:38:22 | 显示全部楼层
强大!学习!谢谢!
发表于 2012-10-14 14:42:21 | 显示全部楼层
收藏   
发表于 2012-10-14 16:42:24 | 显示全部楼层
深奥,太深奥
发表于 2012-12-29 19:08:21 | 显示全部楼层
好!效果如何,前一个和opendcl有冲突,新的不知道,回去试一下。
发表于 2013-1-3 19:16:53 来自手机 | 显示全部楼层
回去试了一下1300个点约2-3分钟,感觉有点慢,不过图形蛮理想。
 楼主| 发表于 2013-1-4 00:55:04 | 显示全部楼层
@zdqwy19
感谢您的测试,希望能有更好的建议。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2024-11-15 01:24 , Processed in 0.231189 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表