求最远路径的问题。。

wowan1314 · 发表于 2013-8-2 20:13:56

ayl1004 发表于 2013-8-2 20:05

解释下楼上的代码：

这个代码是在点取起点线段后，
获得所有与之相连线段的两点表（（P1 P2）(P2 P3)(P2 P4) (P4 P5) (P3 P6)....）后。

再使用楼上的代码就可求出所有路径的点表链。然后对比即可知道最长路径的点表链.

Lispboy · 发表于 2013-8-2 20:16:52

ayl1004 发表于 2013-8-2 20:05

哇，这个代码很简洁啊，能不能再提供一个求最短路径的函数？

Lispboy · 发表于 2013-8-2 20:17:40

wowan1314 发表于 2013-8-2 20:13
解释下楼上的代码：

这个代码是在点取起点线段后，

那葛老能不能根据上面的函数，给大家写一个算最大路径和最短路径的通用函数？

ayl1004 · 发表于 2013-8-2 20:24:30

wowan1314 发表于 2013-8-2 20:13
解释下楼上的代码：

这个代码是在点取起点线段后，

你说的是G版的那段代码，还是G版来解释吧

ayl1004 · 发表于 2013-8-2 20:27:54

Lispboy 发表于 2013-8-2 20:16
哇，这个代码很简洁啊，能不能再提供一个求最短路径的函数？

我这是根据点对表，按起点返回所有路径，最长最短都在里面了。如果回路比较复杂，就不适合了，毕竟用了递归。

wowan1314 · 发表于 2013-8-2 20:29:23

ayl1004 发表于 2013-8-2 20:24
你说的是G版的那段代码，还是G版来解释吧

我说的是你的那个代码使用的条件。。

而G的代码，很好理解。根据得到的线段的两点得到与之相连的下一段，并又到得到两点。然后就是递归得到所有相连的线。

ayl1004 · 发表于 2013-8-2 20:36:55

wowan1314 发表于 2013-8-2 20:29
我说的是你的那个代码使用的条件。。

而G的代码，很好理解。根据得到的线段的两点得到与之相连的下一 ...

G版这思路好，就象搜文件夹一样啊，把我这个函数的点改成直线，参数表去掉，变量PntLst1不要了，PntLst2就是和上一条直线相连的所有直线的表，
这样更简单了。

ayl1004 · 发表于 2013-8-2 20:55:51

ayl1004 发表于 2013-8-2 20:36
G版这思路好，就象搜文件夹一样啊，把我这个函数的点改成直线，参数表去掉，变量PntLst1不要了，PntLst2 ...

东西多了那只能套循环了

ayl1004 · 发表于 2013-8-2 22:19:27

本帖最后由 ayl1004 于 2013-8-2 22:47 编辑

楼主是说我的代码没看明白吗？
还是举个例子更能说明问题
比如起点是：P1
和它相连的点有：P2 P3 P4
那么：PntLst  '((P1 P2) (P1 P3) (P1 P4)...)
      PtLst0  '(P2 P3 P4)
      PtLst1  '((P1 P2) (P1 P3) (P1 P4))
因此，递归调用的参数是
P2 对应的是 '((P1 P3) (P1 P4)...) 其中子表 '(P1 P2) 被移除了
P3 对应的是 '((P1 P2) (P1 P4)...) 其中子表 '(P1 P3) 被移除了
P4 对应的是 '((P1 P2) (P1 P3)...) 其中子表 '(P1 P4) 被移除了
等等... 以此类推。

不知道说清楚了没有？？？

Free-Lancer · 发表于 2013-8-3 07:08:58

想到一种算法，选择集转表，并加编号索引，类似求交点，用两个循环，找出每个线相连的编号线(顺序向后，不重复)，最后根据索引编号合并出路径来自: Android客户端

wowan1314 · 发表于 2013-8-3 09:54:07

本帖最后由 wowan1314 于 2013-8-3 09:57 编辑

Free-Lancer 发表于 2013-8-3 07:08
想到一种算法，选择集转表，并加编号索引，类似求交点，用两个循环，找出每个线相连的编号线(顺序向后，不 ...

感谢回复。。等我先把递归搞明白先。

下面是我用递归的样子。。呵呵。拿出来让大家笑话下。

;(subst# 'm 'b '(a b (a b c) d D))
;最多套三层....
(defun subst# (a b c / a b c d e)
(defun subst3# (a b c / d )
(cond
((setq d (car c))
(cond
((atom d)
(cond
((eq d b)
(setq g (cons a g))
(subst3# a b (cdr c))
)
(t (setq g(cons d g))(subst3# a b (cdr c))
)
)
)
)
)
)
g
)
(defun subst2# (a b c / d g)
(cond
((setq d (car c))
(cond
((atom d)
(cond
((eq d b)
(setq f(cons a f))
(subst2# a b (cdr c))
)
(t (setq f(cons d f))(subst2# a b (cdr c))
)
)
)
(t (setq f (cons (subst3# a b d) f))(subst2# a b (cdr c))
)
)
)
)
f
)
(defun subst1# (a b c / d f)
(cond
((setq d (car c))
(cond
((atom d)
(cond
((eq d b)
(setq e(cons a e))
(subst1# a b (cdr c))
)
(t (setq e(cons d e))(subst1# a b (cdr c))
)
)
)
(t (setq e (cons (subst2# a b d) e))(subst1# a b (cdr c))
)
)
)
)
e
)
(subst1# a b c)
)

;(subst# 'm 'b '(a b (a b c) d D)) 
;最多套三层.... 
(defun subst# (a b c / a b c d e) 
    (defun subst3# (a b c / d ) 
        (cond 
            ((setq d (car c)) 
                (cond 
                    ((atom d) 
                        (cond 
                            ((eq d b) 
                                (setq g (cons a g)) 
                                (subst3# a b (cdr c)) 
                            ) 
                            (t (setq g(cons d g))(subst3# a b (cdr c)) 
                            ) 
                        ) 
                    ) 
                ) 
            ) 
        ) 
        g 
    ) 
    (defun subst2# (a b c / d g) 
        (cond 
            ((setq d (car c)) 
                (cond 
                    ((atom d) 
                        (cond 
                            ((eq d b) 
                                (setq f(cons a f)) 
                                (subst2# a b (cdr c)) 
                            ) 
                            (t (setq f(cons d f))(subst2# a b (cdr c)) 
                            ) 
                        ) 
                    ) 
                    (t (setq f (cons (subst3# a b d) f))(subst2# a b (cdr c)) 
                    ) 
                ) 
            ) 
        ) 
        f 
    ) 
    (defun subst1# (a b c / d f) 
        (cond 
            ((setq d (car c)) 
                (cond 
                    ((atom d) 
                        (cond 
                            ((eq d b) 
                                (setq e(cons a e)) 
                                (subst1# a b (cdr c)) 
                            ) 
                            (t (setq e(cons d e))(subst1# a b (cdr c)) 
                            ) 
                        ) 
                    ) 
                    (t (setq e (cons (subst2# a b d) e))(subst1# a b (cdr c)) 
                    ) 
                ) 
            ) 
        ) 
        e 
    ) 
    (subst1# a b c) 
)

ayl1004 · 发表于 2013-8-3 09:58:54

套循环不知道楼主搞定了没有，其实也很简单

(defun GetMaxPath (ent / Lst0 Lst1 Lst2 Lst3 Val0 Val1)
(setq Lst0 (list (list ent))
Val0 0
Lst3 nil
)
(while Lst0
(setq Lst2 (car Lst0)
Lst0 (cdr Lst0)
)
;;自定义一下GetLines函数
;;获取给定直线图元连接的所有直线
(if (setq Lst1 (GetLines (car Lst2)))
(setq Lst0
(append Lst0
(mapcar (function (lambda (x) (cons x Lst2))) Lst1)
)
)
(if (< Val0
(setq Val1
(apply '+
(mapcar (function (lambda (x)
(vlax-curve-GetDistAtPoint
x
(vlax-curve-GetEndPoint x)
)
)
)
Lst2
)
)
)
)
(setq Val0 Val1
Lst3 Lst2
)
)
)
)
(mapcar (function (lambda (x) (redraw x 3))) Lst3)
(princ Val0)
(getpoint)
(mapcar (function (lambda (x) (redraw x 4))) Lst3)
(princ)
)

(defun GetMaxPath (ent / Lst0 Lst1 Lst2 Lst3 Val0 Val1) 
  (setq Lst0 (list (list ent)) 
        Val0 0 
        Lst3 nil 
  ) 
  (while Lst0 
    (setq Lst2 (car Lst0) 
          Lst0 (cdr Lst0) 
    ) 
    ;;自定义一下GetLines函数 
    ;;获取给定直线图元连接的所有直线 
    (if        (setq Lst1 (GetLines (car Lst2))) 
      (setq Lst0 
             (append Lst0 
                     (mapcar (function (lambda (x) (cons x Lst2))) Lst1) 
             ) 
      ) 
      (if (< Val0 
             (setq Val1 
                    (apply '+ 
                           (mapcar (function (lambda (x) 
                                               (vlax-curve-GetDistAtPoint 
                                                 x 
                                                 (vlax-curve-GetEndPoint x) 
                                               ) 
                                             ) 
                                   ) 
                                   Lst2 
                           ) 
                    ) 
             ) 
          ) 
        (setq Val0 Val1 
              Lst3 Lst2 
        ) 
      ) 
    ) 
  ) 
  (mapcar (function (lambda (x) (redraw x 3))) Lst3) 
  (princ Val0) 
  (getpoint) 
  (mapcar (function (lambda (x) (redraw x 4))) Lst3) 
  (princ) 
)

前面要再加个entsel，就可以当命令使用了

Free-Lancer · 发表于 2013-8-3 15:25:03

贴几个准备函数

(defun ln&ln (l1 l2)
(or (or (equal (caadr l1) (caadr l2) 1e-6)
(equal (caadr l1) (cadadr l2) 1e-6)
)
(or (equal (cadadr l1) (caadr l2) 1e-6)
(equal (cadadr l1) (cadadr l2) 1e-6)
)
)
)
(defun ss->els (ss / sl i els e )
(setq sl (sslength ss)
i sl
)
(repeat sl
(setq e (ssname ss (setq i (1- i))))
(setq els (cons (list i
(list (vlax-curve-getstartpoint e)
(vlax-curve-getendpoint e)
)
e
)
els
)
)
)
els
)
(defun els->ss (l / s)
(setq s (ssadd))
(mapcar '(lambda (x) (ssadd (last x) s)) l)
s
)

wowan1314 · 发表于 2013-8-3 18:48:36

Free-Lancer 发表于 2013-8-3 15:25
贴几个准备函数

期待您的精彩。

st788796 · 发表于 2013-8-4 08:39:47

本帖最后由 st788796 于 2013-8-4 08:41 编辑

;;看了下28#代码, 思路应该是每个线形成一个表 (编号 (起点终点) 线实体)
;;ln&ln 判断两个线是否相连
;;ss->els 对选择集构造实体表 ((1 (sp1 ep1) ln1) (2 (sp2 ep2) ln2) ... (n (spn epn) lnn))
;;els->ss 将构造的路径生成选择集
;;这个算法可以生成选择集内的所有路径，虽然效率未知，好在都是表操作，应该可以接受的
;;下面按Freelancer思路续写一个在线表中找出与给定线相连线的函数
;;这个算法还可以在选择集中任意指定一个线找出通过该线的所有路径
(defun ln&lns (e el / l)
(while el
(if (ln&ln e (car el))
(setq l (cons (car el) l))
)
(setq el (cdr el))
)
(if l
(cons (car e) (cons e l))
(cons (car e) e)
)
)

账号		自动登录	找回密码
密码			立即注册

[研讨] 求最远路径的问题。。

点评

点评

点评

点评

点评

点评

评分

点评

评分

点评

评分

点评

评分

[研讨] 求 最 远路径的问题。。

点评

点评

点评

点评

点评

点评

评分

点评

评分

点评

评分

点评

评分

[研讨] 求最远路径的问题。。