AutoCAD平台下最短路径问题的研究与实现姜松摘要：本文讲述了在CAD平台下，利用AutoLISP编程语言，以一个收索图形为例对最短路径问题进行的研究，以及如何提高最短路径的检索速度，快速得出检索结果。关键词：AutoCAD；AutoLISP；最短路径Abstract:ThispaperdescribesintheCADplatform,usingAutoLISPprogramminglanguage,takeareceivedacablegraphicsforexampletoresearchontheshortestpathproblemandhowtoimprovetheretrievalspeedoftheshortestpath,andquicklycometoretrieveresults.Keywords:AutoCAD;theAutotheLISP;shortestpath：P315.69文献标识码：A：2095-2104（2012）引言最短路径问题在计算机科学、运筹学、交通工程学、地理信息系统等学科中是一个研究的热点，它是资源分配、线路选择等问题解决的基础，尤其是在诸如地图、车辆调度和路由选择方面有着广泛的应用。基于其具有广泛的应用性，所以本文以一个交通路线的选择为例对其进行了研究，希望能起到抛砖引玉的作用。1软件的运行平台及开发语言的简介AutoCAD是美国Autodesk公司推出的通用计算机绘图软件，它以其强大的绘图功能和良好的开发环境，广泛应用于机械、电子、化工、建筑、测量与勘察等行业。对AutoCAD进行二次开发的手段很多，例如AutoLISP、ADS、ARX、VBA等，本程序使用的是AutoLISP编程语言，它已被嵌入CAD中。AutoLISP具有语法简单、功能强大、易学易用的特点，它的数据类型相当随意，可以组织处理不同长度和结构的数据类型，用户可以按要求和最佳结构设计使用自定义的结构类型数据，而不会感到组织数据结构上的困难。另外，AutoLISP擅长人机交互操作的过程，对用户输入的接受、错误识别、恢复操作等方面的优秀功能，是其它语言难以比及的。2程序具体实现2.1设计思路研究最短路径问题，我们不得不提到宽度优先搜索算法（又称广度优先搜索），它是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。2.1.1在存储扩展成果表时采用分段存储方式，将点号按大小分成四段存储在四个表中，便于在检索点号时只检索其中的一个表即可，缩小检索点范围。2.1.2设置检索距离，当检索距离大于已找到的终点检索距离后停止检索，避免做无用的检索。2.1.3程序以起始点到终点的有向线段方向预设优先检索方向，先收索与之方向夹角小的路径，争取最短时间得到终点检索距离值，减小检索范围。2.1.4在检索存储点号时对存储表采用二分法检索，以提高点号的获取速度。2.2程序原代码(defunc:drj()(setvar"CMDECHO"0)(setqSEHfbl1nilSEHfbl2nilSEHfbl3nilSEHfbl4nil);;设置存储块点点表(setqlstDZbl1nillstDZbl2nillstDZbl3nillstDZbl4nil);;设置对照点表(setqSEHfh(SEHBLPX));;初始化块点点表(setqQiShiDian(car(entsel"选择起始点:")))(setqSelQSDlst(entgetQiShiDian))(setqSelQSDxyh(cdr(assoc10SelQSDlst)))(setqSelQSDh(fix(lastSelQSDxyh)));;起始点点号(princ"您选择的起始点为:")(princSelQSDh)(setqZhongDian(car(entsel"选择目的点:")))(setqSel政法lst(entgetZhongDian))(setqSel政法xyh(cdr(assoc10Sel政法lst)))(setqSel政法h(fix(lastSel政法xyh)));;起始点点号(princ"您选择的目的点为:")(princSel政法h)(command".zoom""e")(alert"程序即将运行,可能需要一点时间,请耐心等候!")(setqlstDKblnil);;预置待扩点表(setqlst激eGuonil)(setqfinddist0)(setqlstTmpnil)(setqlstKYbltmpnil);;预置扩延临时表(setqFirstflag0)(setqlstTmp(LJDBallSelQSDh));;对起始点扩展(if(vl-consplstTmp)(progn;;如果lstTmp不为空表(setqmaini0)(repeat(lengthlstTmp)(setqmainys(nthmainilstTmp))(setqmainysb(listSelQSDhmainys))(if(<=mainysSEHfh)(setqlstDZbl1(consmainysblstDZbl1)))(if(and(>mainysSEHfh)(<=mainys(*2SEHfh)))(setqlstDZbl2(consmainysblstDZbl2)))(if(and(>mainys(*2SEHfh))(<=mainys(*3SEHfh)))(setqlstDZbl3(consmainysblstDZbl3)))(if(>mainys(*3SEHfh))(setqlstDZbl4(consmainysblstDZbl4)))(setqlstDKbl(c...