（求助）把所有点连接可以是多段线段，但是要和最小。如何思考？

flowerson

求助各位大神：把下图所有点连接可以是多段线段，但是要和最小。如何思考？用lisp如何实现呢？

mahuan1279

(defun fp ()
    (setq sn (ssget ":N" '((0 . "point"))))
    (setq i 0 n (sslength sn) plst nil)
    (while (< i n)
        (setq plst (cons (cons (+ i 1) (cdr (assoc 10 (entget (ssname sn i))))) plst))
        (setq i (+ i 1))
    )
   (reverse plst)
)
(defun mindist (alst blst)
  (setq dlst nil)
  (foreach a alst
       (foreach b blst
            (setq dlst (cons (list (car a) (car b) (distance (cdr a) (cdr b)))  dlst))
        )
  )
  (setq qlst (car (vl-sort dlst '(lambda(a b) (< (last a) (last b)) ) )))
  qlst
)
(defun c:tt ()
   (setq ptlst (fp))
   (setq vlst (list (car ptlst)) rlst (cdr ptlst))
   (while (not (null rlst))
          (setq qlst (mindist vlst rlst))
          (command "line" (cdr (assoc (car qlst) vlst)) (cdr (assoc (cadr qlst) rlst)) "" )
          (setq vlst (cons (assoc (cadr qlst)  rlst) vlst))
          (setq rlst (vl-remove (assoc (cadr qlst)  rlst) rlst))
   )
)

flowerson

;最关键的点表对点表最短的求法，如下：(defun ptsort (lsta lstb / i ia mina nia pmina pmind)
  (setq pmina (list (car lsta) (car lstb)))
  (setq pmind (apply
                'distance
                pmina
              )
  )
  (setq i 0)
  (repeat (length lsta)
    (setq ia (nth i lsta))
    (setq mina (apply
                 'distance
                 (zg-nearestpt ia lstb)
               )
    )
    (if (> pmind mina)
      (progn
        (setq pmind mina)
        (setq nia (list ia (cadr (zg-nearestpt ia lstb))))
      )
    )
    (setq i (+ i 1))
  )
  nia
)


;只是实现了，还望各位大侠改进算法技巧什么的。多拍砖！

flowerson

感谢xyp1964院长的回复， 全部封闭的连接论坛里确实也有案例了。现在要的是所有点连接到，但是不一定是一条pline 可是是很多线段，只是要把所有连接好之后线段总和是最小的。

flowerson

3-5个点是比较好判断出来，但是很多点的时候就不知怎样下手了。

ntwison

感觉这种问题首先先得去找到算法，编程倒是小事。

flowerson

是那种算法比较合适呢？如果不是多段线段的论坛当中比较多（就是一条pl线连接的比较多）。

前生

先以某种条件确定一个点为其实点。
其他的点，做个循环。
理论上，最近的点相连，线的长度是最短的。

革天明

最小路径问题

vectra

没法思考时试着增加限定条件 比如指定起始点 增加两点连接的原则。。。

flowerson

感觉是点表和点表的最短是怎样求呢？感觉是这个。

xyp1964