明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 19594|回复: 39

[【高飞鸟】] 【越飞越高讲堂10】分治、递归、分类和最小距离(更新至2012.7)

  [复制链接]
发表于 2006-11-25 13:34:00 | 显示全部楼层 |阅读模式
2012.7.16 程序更新在16楼。
=============================我是分割线=============================
给定平面上的一个数量为n的点集,如何能有效地找出距离最近的点对呢?(在实际中有着应用,而且给出的是点对的集合,也就是在误差范围内的所有点对都找出来)。
    这个问题很容易理解,似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出,找出达到最小距离的两个点即可。然而,这样做效率太低,需要O(n^2)的计算时间。当数量规模较小时,尚能解决,但一旦规模达到万级以上,其速度之慢,时间之长,无法令人忍受。下面我给出这个问题的一个θ(nlogn)算法。
在这个算法中,我利用了递归、分治和分类思想。
递归算法是自身调用自身函数的一种算法,例如求阶乘:
(defun jc(n) (if (= n 0) 1 (* n (jc (1- n)))))
分治算法是对于一个规模为n的问题,把它分解成为K个规模较小的子问题,这些子问题互相独立,且结构与原来问题的结构相同。在解这些子问题时,又对于每一个子问题进行进一步的分解,直到某个阈值为止。递归地解决这些子问题,再把各个子问题的解合并起来,就得到原来问题的解。因此递归一般和分治联系在一起。
对于求最小距离的解,我参考了一些资料,他们给出的大多是C++ 程序,我看不懂,只好按照算法和思想来设计lisp程序。
闲话少说,先看源程序:加载程序,运行TE

  1. (defun C:te (/ olderr en errmsg oldmode oce sl ss t0 ptlist pp pp1)
  2.   ;;定义错误函数和预处理
  3.   (setvar "errno" 0)
  4.   (setq olderr *error*)
  5.   (defun *error* (msg)
  6.     (setq en (getvar "errno"))
  7.     (setq errmsg (strcat "errno=" (itoa en) "\nError:" msg))
  8.     (alert errmsg)
  9.     (setq *error* olderr)
  10.   )
  11.   (graphscr)
  12.   (setq oldmode (getvar "osmode"))
  13.   (setq oce (getvar "cmdecho"))
  14.   (setvar "cmdecho" 0)
  15.   (command ".ucs" "W")
  16.   ;;也可以用其他方式取得点集
  17.   (setq sl '((0 . "POINT")))
  18.   (setq t0 (getvar "TDUSRTIMER"))
  19.   (setq ss (ssget sl))
  20.   (setq ptlist (getpt ss))
  21.   ;;分类
  22.   (setq t0 (getvar "TDUSRTIMER"))
  23.   (setq ptlist (sortx ptlist))
  24.   (princ "\n函数排序用时")
  25.   (princ (* (- (getvar "TDUSRTIMER") t0) 86400))
  26.   (princ "秒")
  27.   ;;函数用时估算,以了解函数性能
  28.   (setq t0 (getvar "TDUSRTIMER"))
  29.   (setq pp1 (f2 ptlist) pp (cadr pp1))
  30.   (princ "\n函数查找用时")
  31.   (princ (* (- (getvar "TDUSRTIMER") t0) 86400))
  32.   (princ "秒")
  33.   (if (= nil pp)
  34.     (progn
  35.       (alert "不存在有最小距离的一对点!")
  36.       (command ".ucs" "p")
  37.       (setvar "osmode" oldmode)
  38.       (setvar "cmdecho" oce)
  39.       (princ)
  40.     )
  41.     (progn
  42.       ;;画最短距离的点对集的连线,可能有多条
  43.       (setvar "osmode" 0)
  44.       (foreach nn pp
  45.         (entmake
  46.    (append
  47.      '((0 . "line")(100 . "AcDbEntity")(100 . "AcDbLine"))
  48.      (list (cons 10 (car  nn)))
  49.      (list (cons 11 (cadr nn)))
  50.      (list (cons 62 1))
  51.    )
  52.         )
  53.       )
  54.       (command ".ucs" "P")
  55.       (setvar "osmode" oldmode)
  56.       (setvar "cmdecho" oce)
  57.       (princ)
  58.     )
  59.   )
  60. )
  61. ;;取点函数,其中i为点的编号
  62. (defun getpt (ss / i listpp a b c)
  63.   (setq i 0 listpp nil )
  64.   (if ss
  65.     (repeat (sslength ss)
  66.       (setq a (ssname ss i))
  67.       (setq b (entget a))
  68.       (setq c (cdr (assoc 10 b)))
  69.       (setq listpp (cons c listpp))
  70.       (setq i (1+ i))  
  71.     )
  72.   )
  73.   (reverse listpp)
  74. )
  75. ;;从J到K的表
  76. (defun cut (ptlist j k / i ptlist1)
  77.   (setq i 0 ptlist1 nil)
  78.   (foreach n ptlist
  79.     (if (and (>= i j) (<= i k) )
  80.       (setq ptlist1 (cons n ptlist1))
  81.     )
  82.     (setq i (1+ i))
  83.   )
  84.   (reverse ptlist1)
  85. )
  86. ;;对X排序
  87. (defun sortX (ptlist)
  88.   (mapcar '(lambda (x) (nth x ptlist))
  89.     (vl-sort-i ptlist '(lambda (e1 e2) (< (car e1)(car e2))))
  90.   )
  91. )
  92. ;;在带形区域查找
  93. (defun searchX (ptlist1 x1 x2 / pp)
  94.   (setq pp nil)
  95.   (foreach n ptlist1
  96.     (if (and (>= (car n) x1)
  97.       (<= (car n) x2)
  98. )
  99.       (setq pp (cons n pp))
  100.     )
  101.   )
  102.   (reverse pp)
  103. )
  104. ;;在矩形区域查找
  105. (defun searchXY (ptlist2 x1 x2 y1 y2 / pp)
  106.   (setq pp nil)
  107.   (foreach n ptlist2
  108.     (if (and (>= (car  n) x1)
  109.       (<= (car  n) x2)
  110.       (>= (cadr n) y1)
  111.       (<= (cadr n) y2)
  112. )
  113.       (setq pp (cons n pp))
  114.     )
  115.   )
  116.   (reverse pp)
  117. )
  118. ;;最多6点最小距离
  119. (defun 6ptmin (ptlist4 pt / 6pmin 6plist)
  120.   (setq 6pmin (mapcar '(lambda (x) (distance x pt)) ptlist4))
  121.   (setq 6pmin (apply 'min 6pmin) 6plist nil)
  122.   (foreach 6name ptlist4
  123.     (if (equal (distance 6name pt) 6pmin 1e-8)
  124.       (setq 6plist (cons (list pt 6name) 6plist))
  125.     )  
  126.   )
  127.   (list (+ 6pmin 1e-8) 6plist)         
  128. )
  129. ;;***************
  130. ;;程序主段-------
  131. (defun f2 (ptlist / l p1 p2 p3 dd 3pmind 3plist ptlist1 ptlist2 ptlist3 ptlist4  
  132.           n m midpt mind1 mind2 mindt a b c d Dismin Dnmin nplist mindi)
  133.   (setq l (length ptlist))
  134.   (cond
  135.     ( (= l 2);;两点还用说   
  136.       (list (+ (distance (car ptlist) (cadr ptlist)) 1e-8)
  137.      (list ptlist)
  138.       )
  139.       ;;(list (apply 'distance ptlist) (list ptlist))
  140.     )
  141.     ( (= l 3);;三点最小距离直接求解点对
  142.       (progn
  143. (setq p1 (car ptlist) p2 (cadr ptlist) p3 (caddr ptlist))
  144. (setq dd
  145.           (list (list (distance p1 p2) (list p1 p2))
  146.   (list (distance p1 p3) (list p1 p3))
  147.   (list (distance p2 p3) (list p2 p3))
  148.    )
  149. )
  150. (setq 3pmind (apply 'min (mapcar 'car dd)))
  151. (setq 3plist nil)
  152. (foreach 3name dd
  153.    (if (equal (car 3name) 3pmind 1e-8)
  154.      (setq 3plist (cons (cadr 3name) 3plist))
  155.    )
  156. )
  157.         (list (+ 3pmind 1e-8) 3plist)
  158.       )
  159.     )
  160.     ( (> l 3)
  161.       (progn
  162. (setq n (/ l 2) m (- l n));;分治
  163. (setq ptlist1 (cut ptlist 0 (1- m)))
  164. (setq ptlist2 (cut ptlist m l))
  165. (setq midpt (last ptlist1))
  166. (setq mind1 (f2 ptlist1));;递归左边
  167. (setq mind2 (f2 ptlist2));;递归右边
  168. (setq mindT
  169.    (cond
  170.      ((equal (car mind1) (car mind2) 1e-8)(list (car mind1) (append (cadr mind1) (cadr mind2))))
  171.      ((< (car mind1) (car mind2)) mind1)
  172.      (t mind2)
  173.    )
  174. )
  175. (setq mindi (car mindT))
  176. (setq a (- (car midpt) mindi) b (car midpt))
  177. (setq ptlist3 (searchX ptlist1 a b))
  178. (if (/= ptlist3 nil)
  179.    (progn
  180.      (setq Dismin nil)
  181.             (foreach name ptlist3
  182.        (setq a (car midpt) b (+ (car midpt) mindi) c (- (cadr name) mindi) d (+ (cadr name) mindi))
  183.        (setq ptlist4 (searchXY ptlist2 a b c d))
  184.        (if (/= ptlist4 nil)
  185.                 (setq Dismin (cons (6ptmin ptlist4 name) Dismin))
  186.        )
  187.      )
  188.      (if (= Dismin nil)
  189.        mindT
  190.        (progn
  191.          (setq Dnmin (apply 'min (mapcar 'car Dismin)) nplist nil)
  192.   (foreach npname Dismin
  193.     (if (equal (car npname) Dnmin 1e-8)
  194.       (setq nplist (append (cadr npname) nplist))
  195.     )
  196.   )
  197.          (cond
  198.     ((equal (car mindT) Dnmin 1e-8) (list mindi (append nplist (cadr mindT))))
  199.     ((< (car mindT) Dnmin) mindT)  
  200.            (t (list Dnmin nplist))
  201.          );;for inest cond
  202.        );;for inest if-progn
  203.      );;for inest if
  204.    )mindT;;for if-progn
  205. );;for if
  206.       );;for cond-last-progn
  207.     );;for cond-last
  208.   );;for cond
  209. );;for defun
  210. ;;***************
比较了一些别人写的代码,(大都是平方级别的,有的甚至更高),发现在时间上还是比平方级以上的要快很多。但是还没有做最优处理,希望大家多多提意见给我。

highflybird@sina.com      
2006-11-25,kunming


以下图片给出了一个极端例子:

本帖子中包含更多资源

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

x

评分

参与人数 2威望 +1 明经币 +1 金钱 +10 贡献 +5 激情 +5 收起 理由
muwind + 1
mccad + 1 + 10 + 5 + 5 【精华】好程序

查看全部评分

"觉得好,就打赏"
    共1人打赏

本帖被以下淘专辑推荐:

 楼主| 发表于 2012-7-17 09:46:31 | 显示全部楼层


现在更新了程序。比以前的快了十倍。
同时附上国外的一个好方法。
命令是:test.

本帖子中包含更多资源

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

x
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2006-11-25 15:16:00 | 显示全部楼层

这个题的算法步骤如下:

1、首先把点集按照X从小到大分类,

2、先求两点和三点的最小距离点对。

3、对于大于三点以上的N个点,做如下考虑:

 a,把点按照中位数分开。(例如,19个点,则左边10个,右边9个,18个对分)

 b,对两边分别用递归方法求解。 得到两个最小的距离d1d2

c ,比较d1或者d2大小,取最小的为dmin

d ,设置中位点X坐标为xmid ,对于落在 (xmid-dmin,xmid) 区域上的点(xscan, yscan) 进行扫描X落在(dmin,xmid+dminY落在( yscan-dmin,yscan+xdmin) 右边的点(理论证明最多有6个这样的点),分别求左边扫描的点跟右边区域的点的距离,找到距离的最小,然后从最小的合集中找到最小 midarea-min,把这个值跟dmin做比较,这样就可以得出最小的距离以及它们的点对。

如果不明白的话,可以参考一些书籍和网上的资料。

点评

楼主写的好,借楼写下自己的理解  发表于 2014-6-21 16:43
所以任何题目都有可能使用分冶思路来提高效率,但并非一定,除非你在将问题规模缩小的同时还能找到使你提出的方法具有完备性的途径。  发表于 2014-6-21 16:37
3.比较1.2的所有结果,答案就在其中。 剩下的就是使用我们的编程技巧来实现上面的过程并求出结果.递归或非递归任你选择,如果你习惯用用数学公式去描述解决的方法,那就使用递归编程,会简练许多。  发表于 2014-6-21 16:36
1.对平面点集按x或y坐标分带,分带规模有你决定,对各分带运用O(n^2)算法,求出所有可能的最近点对. 2.分别对点集的分界线两侧一定范围的点求出所有可能的最近点对{注意点对的两点必然分布在分界线的两侧}.  发表于 2014-6-21 16:35
但如果将n分成一小撮一小撮,对每撮分别使用O(n^2)算法,结果并不完备,因为最近点对可能分布在其中的一小撮中,也可能点对的两个点分布在不同的小撮中. 因此想到这里该问题的分冶解法就形成了.  发表于 2014-6-21 16:34
简单地说,平面点集求解最近点对具有采用分冶思路解决的可能: O(n^2)计算时间的算法是求解平面或三维点集最近点对的基础算法,该算法是完备的,但当n极大时,效率变得难以接受.  发表于 2014-6-21 16:33
回复 支持 1 反对 0

使用道具 举报

发表于 2022-6-3 10:15:23 | 显示全部楼层
好贴,顶一个不解释
发表于 2006-11-25 13:42:00 | 显示全部楼层
好帖!顶到底。
发表于 2006-11-25 14:44:00 | 显示全部楼层
算法对程序来说至关重要,还请楼主给大伙讲一讲数据结构和算法。
发表于 2009-2-24 22:40:00 | 显示全部楼层
学习ing
发表于 2009-2-26 12:33:00 | 显示全部楼层
感谢版主分享,谢谢
发表于 2010-10-11 11:39:00 | 显示全部楼层

谢谢楼上的分享,参考下,很感激

发表于 2012-4-21 07:18:43 来自手机 | 显示全部楼层
我试用下有两问题,一是点有可能重合,二发现不能求得最小值,这个不知为什么
发表于 2012-5-6 19:07:02 | 显示全部楼层
好程序,谢谢分享
发表于 2012-5-6 19:12:23 | 显示全部楼层
本帖最后由 wowan1314 于 2012-5-6 19:15 编辑

NB,收藏了! 有时间下来好好学习研究.  谢谢楼主分享。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

GMT+8, 2024-11-13 14:49 , Processed in 0.310375 second(s), 31 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

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