在LispWorks中进行编程22：地图
Category:UI界面编写地图
在这个项目中，我们将编写一个Lisp程序来找到两个地方之间的最短路径。该计划说明了每个汽车导航系统以及AA路线规划师等网站需要解决的重要问题。此版本将使您能够创建自己的个人路线规划器; 例如，您可以使用它来查找您家乡周围最快的自行车路线。
完整列表
例
我们的地图程序将地图存储为道路列表，其中每条道路互连两个位置。这是我们用来测试程序的地图：
为简单起见，每个位置都有一个单字母的名称，例如“A”，但在实际应用中，它们可以是“Home”“School”“Swimming Pool”等。
数字显示了每对地点之间的时间，以分钟为单位，我们的目标是尽可能以最快的路线从“A”到“Z”。
输入数据
地图数据将存储在一个名为map-data的全局变量中，我们将其定义为：
(defparameter map-data nil)
地图将存储为道路列表，每个道路定义为：
(from to time road)
在道路两端的位置和地点，时间是在位置之间进行的时间，道路是道路的可选名称。例如：
(“Home” “Swimming Pool” 6 “High St.”)
这是添加道路到数据库的过程add-road：
(defun add-road (from to time &optional road) (setq map-data (cons (list from to time road) (cons (list to from time road) map-data))))
例如，要添加我们输入的道路：
CL-USER > (add-road “Home” “Swimming Pool” 6 “High St.”)
并且map-data的值变为：
((“Home” “Swimming Pool” 6 “High St.”) (“Swimming Pool” “Home” 6 “High St.”))
请注意，添加道路两次添加道路，一次从“家”到“游泳池”，再次“游泳池”到“家”。该程序可以满足单行道，但添加道路假设所有道路是双向的。
维护队列
现在我们可以进入地图，程序如何找到最短的路线？该技术被称为“墨水印迹”或“广度优先”搜索。这就像把墨水倒入起始城市的中心，并观察它沿着道路网络均匀分布，在到达它时为每个位置着色。到达目的地的最短路线将是墨水河首先到达的路线。
要做到这一点，我们将保留墨水流动的道路列表，这样就可以安排下次到达的位置。这种有序列表称为优先级队列。我们将它存储在全局变量map-queue中：
(defparameter map-queue nil)
我们将条目存储为：
(time location from)
其中时间是从起点开始的总时间，位置是墨水印迹到达的位置，而且是我们来自的位置。
这是将项添加到队列并返回新队列的过程add-item：
(defun add-item (item queue) (if (null queue) (cons item queue) (if (< (first item) (first (first queue))) (cons item queue) (cons (first queue) (add-item item (rest queue))))))
为方便起见，我们还有以下过程 add-to-queue ，它 使用新值更新变量 map-queue：
(defun add-to-queue (time location via) (setf map-queue (add-item (list time location via) map-queue)))
例如，如果我们想要添加道路
(3 “E” “F”)
到队列：
((2 “A” “B”) (4 “C” “D”))
我们的确是：
CL-USER 45 > (add-to-queue 3 “E” “F”)((2 “A” “B”) (3 “E” “F”) (4 “C” “D”))
它被插入到正确的位置，条目按时间排序。
处理新位置
当墨水到达新位置时，我们希望添加从该位置延伸到队列的所有道路。这是通过常规添加道路完成的，这会添加从当前位置到队列的所有道路：
(defun add-roads (location start) (dolist (item map-data) (let* ((from (first item)) (to (second item)) (time (third item))) (if (string= from location) (add-to-queue (+ start time) to location)))))
它的工作原理如下：
对于地图数据中的每个条目：
- 如果地图数据中的from项与当前位置匹配，请将路径添加到队列，并将时间添加到我们的开始时间。
越来越多的搜索
我们现在准备编写将墨水从起始位置传播到我们到达目的地的主要程序。我们将返回墨水传播时遇到的所有位置的列表，以及我们来自的位置：
(defun grow-search (here to) (if (string= here to) nil (let* ((best (first map-queue)) (from (second best))) (setf map-queue (rest map-queue)) (add-roads from (first best)) (cons (list from (third best)) (grow-search from to)))))
要了解增长搜索是如何工作的，我们设置一个非常简单的地图：
清除地图数据：
CL-USER > (setq map-data nil)NIL
添加A和B之间的道路：
CL-USER > (add-road “A” “B” 2)((“A” “B” 2 NIL) (“B” “A” 2 NIL))
添加B和C之间的道路：
CL-USER > (add-road “B” “C” 1)((“B” “C” 1 NIL) (“C” “B” 1 NIL) (“A” “B” 2 NIL) (“B” “A” 2 NIL))
清除地图队列：
CL-USER > (setq map-queue nil)NIL
将起始位置添加到队列中，开始时间为0：
CL-USER > (add-to-queue 0 “A” nil)((0 “A” NIL))
然后长出墨水印迹，直到我们到达目的地“C”：
CL-USER > (grow-search “A” “C”)((“A” NIL) (“B” “A”) (“C” “B”))
程序grow-search返回所访问位置的列表，并在每种情况下返回我们来自的位置。
要完成项目，我们需要从访问过的位置列表中创建实际路线。
列出路线
以下是列出路线的程序。第一个find-in-list查找具有指定位置的被访问列表中的第一个项目：
(defun find-in-list (item list) (if (null list) nil (if (string= (first (first list)) item) (first list) (find-in-list item (rest list)))))
然后list-route调用它来查找访问列表中的路由：
(defun list-route (from to visited) (if (string= from to) (list from) (cons to (list-route from (second (find-in-list to visited)) visited))))
最后，find-route调用grow-search和list-route来查找地图上的最短路径：
(defun find-route (from to) (setq map-queue nil) (add-to-queue 0 from nil) (reverse (list-route from to (grow-search from to))))
例
让我们试一下路线图程序，找到本节开头地图中最短的路线。这是定义地图的过程：
(defun make-map () (add-road “A” “B” 2) (add-road “B” “C” 3) (add-road “A” “D” 9) (add-road “B” “E” 3) (add-road “C” “F” 7) (add-road “D” “E” 3) (add-road “E” “F” 6) (add-road “D” “G” 2) (add-road “E” “H” 8) (add-road “F” “Z” 6) (add-road “G” “H” 2) (add-road “H” “Z” 4))
所以我们执行：
(setq map-data nil)(make-map)(find-route “A” “Z”)
答案回来了：
(“A” “B” “E” “D” “G” “H” “Z”)
如果你调查你会发现这确实是从A到Z的最短路线。
http://mip.i3geek.com
