AutoCAD平台下最短路径问题的研究与实现

姜松

摘要：本文讲述了在CAD平台下，利用Auto LISP编程语言，以一个收索图形为例对最短路径问题进行的研究，以及如何提高最短路径的检索速度，快速得出检索结果。

关键词： AutoCAD；Auto LISP；最短路径

Abstract: This paper describes in the CAD platform, using Auto LISP programming language, take a received a cable graphics for example to research on the shortest path problem and how to improve the retrieval speed of the shortest path, and quickly come to retrieve results.Key words: AutoCAD; the Auto the LISP; shortest path

中图分类号：P315.69 文献标识码：A文章编号：2095-2104（2012）

引言

最短路径问题在计算机科学、运筹学、交通工程学、地理信息系统等学科中是一个研究的热点，它是资源分配、线路选择等问题解决的基础，尤其是在诸如地图、车辆调度和路由选择方面有着广泛的应用。基于其具有广泛的应用性，所以本文以一个交通路线的选择为例对其进行了研究，希望能起到抛砖引玉的作用。

1 软件的运行平台及开发语言的简介

AutoCAD是美国Autodesk公司推出的通用计算机绘图软件，它以其强大的绘图功能和良好的开发环境，广泛应用于机械、电子、化工、建筑、测量与勘察等行业。对AutoCAD进行二次开发的手段很多，例如Auto LISP、ADS、ARX、VBA等，本程序使用的是Auto LISP编程语言，它已被嵌入CAD中。Auto LISP具有语法简单、功能强大、易学易用的特点，它的数据类型相当随意，可以组织处理不同长度和结构的数据类型，用户可以按要求和最佳结构设计使用自定义的结构类型数据，而不会感到组织数据结构上的困难。另外，Auto LISP擅长人机交互操作的过程，对用户输入的接受、错误识别、恢复操作等方面的优秀功能，是其它语言难以比及的。

2 程序具体实现

2.1 设计思路

研究最短路径问题，我们不得不提到宽度优先搜索算法（又称广度优先搜索），它是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

2.1.1在存储扩展成果表时采用分段存储方式，将点号按大小分成四段存储在四个表中，便于在检索点号时只检索其中的一个表即可，缩小检索点范围。

2.1.2设置检索距离，当检索距离大于已找到的终点检索距离后停止检索，避免做无用的检索。

2.1.3程序以起始点到终点的有向线段方向预设优先检索方向，先收索与之方向夹角小的路径，争取最短时间得到终点检索距离值，减小检索范围。

2.1.4在检索存储点号时对存储表采用二分法检索，以提高点号的获取速度。

2.2 程序原代码

(defun c:drj()

(setvar "CMDECHO" 0)

(setq SEHfbl1 nil SEHfbl2 nil SEHfbl3 nil SEHfbl4 nil) ;;设置存储块点点表

(setq lstDZbl1 nil lstDZbl2 nil lstDZbl3 nil lstDZbl4 nil);;设置对照点表

(setq SEHfh (SEHBLPX));;初始化块点点表

(setq QiShiDian (car (entsel " 选择起始点:")))

(setq SelQSDlst (entget QiShiDian))

(setq SelQSDxyh (cdr (assoc 10 SelQSDlst)))

(setq SelQSDh (fix (last SelQSDxyh)));;起始点点号

(princ " 您选择的起始点为:")

(princ SelQSDh)

(setq ZhongDian (car (entsel " 选择目的点:")))

(setq SelZDlst (entget ZhongDian))

(setq SelZDxyh (cdr (assoc 10 SelZDlst)))

(setq SelZDh (fix (last SelZDxyh)));;起始点点号

(princ " 您选择的目的点为:")

(princ SelZDh)

(command ".zoom" "e")

(alert "程序即将运行,可能需要一点时间,请耐心等候!")

(setq lstDKbl nil);;预置待扩点表

(setq lstJieGuo nil)

(setq finddist 0)

(setq lstTmp nil)

(setq lstKYbltmp nil);;预置扩延临时表

(setq Firstflag 0)

(setq lstTmp (LJDBall SelQSDh));;对起始点扩展

(if (vl-consp lstTmp) (progn;;如果lstTmp不为空表

(setq maini 0)

(repeat (length lstTmp)

(setq mainys (nth maini lstTmp))

(setq mainysb (list SelQSDh mainys))

(if (<= mainys SEHfh) (setq lstDZbl1 (cons mainysb lstDZbl1)))

(if (and (> mainys SEHfh) (<= mainys (* 2 SEHfh))) (setq lstDZbl2 (cons mainysb lstDZbl2)))

(if (and (> mainys (* 2 SEHfh)) (<= mainys (* 3 SEHfh))) (setq lstDZbl3 (cons mainysb lstDZbl3)))

(if (> mainys (* 3 SEHfh)) (setq lstDZbl4 (cons mainysb lstDZbl4)))

(setq lstDKbl (cons mainysb lstDKbl))

(setq maini (+ maini 1))

)

(setq lstDKbl (reverse lstDKbl));;生成待扩点表

(if (vl-consp lstDZbl1) (progn;;如果lstDZbl1(对照点表1)不为空

(setq lstDZbl1 (vl-sort lstDZbl1 (function (lambda (e1 e2) (< (cadr e1) (cadr e2))))));;对表进行排序点号从小到大

))

(if (vl-consp lstDZbl2) (setq lstDZbl2 (vl-sort lstDZbl2 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(if (vl-consp lstDZbl3) (setq lstDZbl3 (vl-sort lstDZbl3 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(if (vl-consp lstDZbl4) (setq lstDZbl4 (vl-sort lstDZbl4 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(setq lstDKbl (QCDFUN lstDKbl));;获得纯正的扩展点表

(while (vl-consp lstDKbl);;循环到lstDKbl为空表为止

(KYFUN lstDKbl SelQSDh);;对lstDKbl进行一次扩延

(setq lstDKbl (QCDFUN lstKYbltmp))

(setq lstDKbl (JJPL SelQSDh SelZDh lstDKbl));;按方向夹角从小到大排序

(setq lstKYbltmp nil)

)

))

(if (vl-consp lstJieGuo) (progn;;如果结果表不为空

(princ " 起点到目的点最短路径是:")

(princ " ")

(princ lstJieGuo)

(princ " 距离为:")

(princ finddist)

))

(if (not (vl-consp lstJieGuo)) (progn;;如果结果表为空

(princ " 从起点没有路径能到达目的点!!!")

))

(princ)

)

3 结束语

本程序是在CAD平台下开发的，其收索所需线画图的制作和更新都十分便捷，利用此程序对多个中小城市的道路图做收索实验，其最大范围的检索时间在十几秒之内，一般范围的收索均在几秒内完成，因此程序具有较强的实用价值。由于篇幅所限本文仅列出了主程序模块的原代码，有编写繁琐之处敬请批评指正。

参考文献

[1] 康博．中文版AutoCAD2000/2002 Visual LISP开发指南[M]，北京：清华大学出版社，2001.8

[2] 唐亮，等．AutoCAD2002开发教程[M]，北京：北京希望电子出版社，2002.8

[3]（美）Hamdy A.Taha.运筹学导论：初级篇（第8版）[M].北京：人民邮电出版社，2008

[4]（美）Cormen T.H.. 算法导论（第2版）[M]. 北京：机械工业出版社，2006

注：文章内所有公式及图表请以PDF形式查看。