Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 12
Текст из файла (страница 12)
Второй прототип строится на основе первого, и можетрассматриваться как его расширение. В общем случае, «спиральная»модель жизненного цикла программы может включать несколькопрототипов.Для поиска пути на графе существует две стратегии: поиск вглубь и поисквширь. Алгоритм поиска вглубь предполагает последовательноерассмотрение всех возможных путей, начинающихся из стартовойвершины. На первом шаге текущей является стартовая вершина, ирассматриваются все вершины, непосредственно связанные с ней. Из этихвершин выбирается одна (например, первая) и становится текущей. Еслитекущая вершина является искомой, то алгоритм останавливается. Иначеиз списка вершин, непосредственно связанных с данной, выбираетсяследующая текущая вершина. Процесс повторяется, пока искомая вершинане будет достигнута или все возможности поиска по этому пути не будутисчерпаны (достигнута точка возврата).
Если при этом искомая вершина64не была достигнута, то алгоритм возвращается на предыдущий шаг, и вкачестве текущей выбирается следующая вершина из списка (backtracking).Заметим, что на каждом шаге достаточно хранить информацию только ободном текущем пути. Алгоритм прост и подразумевает рекурсивнуюреализацию. К достоинствам этого алгоритма можно отнестиминимальные расходы памяти на поддержание рекурсии.
Альтернативныйалгоритм поиска вширь просматривает все возможные пути одновременно,начиная со стартовой вершины, и пока искомая вершина не будетдостигнута на одном из путей, либо все пути не будут отвергнуты.С точки зрения реализации поиск вглубь является более простымалгоритмом, и поэтому для первого прототипа программы логичноиспользовать именно его. Переменная nodes задает список всех вершинграфа с их координатами. В переменной paths хранится список реберграфа. Функция init-length строит новый список, содержащийинформацию о ребрах графа и их длинах, вычисленных на основекоординат вершин с помощью функций slow-path-length и distbetween-points. Функция find-connected-nodes возвращает списоквершин, непосредственно связанных с заданной. Функция depth ищет путьмежду двумя заданными вершинами, используя алгоритм поиска вглубь.(d e fin e( d e fi n e( y- co o r d x )(x-coord x)(define nodes '((nl(n2(n3(n4(n5(пб(n7(n8(n9(nl0(nil(t ru n c a t e ( c a d r x ) ))(truncate (car x)))(60 402))(50 310))(110 60) )(220 375))(192 220))(260 4 4 ) )(305 300))(347 404))(351 262))(400 110))(415 404) )))(define paths '(( nl n2) ( n2 n3) ( n3 n5 ) ( nЗ n6 ) ( n6 nl0)( n9 nl0) ( n7 n9) ( nl n4) ( n4 n2) ( n5 n8)(n8 n4) (n7 nil)))(define (init-lengths pathlist)(let ((new-path-list '())(pathlength 0)(path-with-length '())) (do((path pathlist (cdr path)))65((null? path))(set! pathlength (slow-path-length (car path)))(set! path-with-length(append (car path) (list pathlength)))(set! new-path-list(cons path-with-length new-path-list)))new-path-list)); "As the crow flies" distance between; the starting and ending nodes on a path:(define (slow-path-length path)(let ((nodel (car path))(node2 (cadr path))) (let((nl (assoc nodel nodes))(n2 (assoc node2 nodes))) (dist-betweenpoints (cadr nl) (cadr n2))))); Calculate the Cartesian distance between points:(define (dist-between-points pointl point2)(let ((x-dif (- (X-coord point2) (X-coord pointl)))(y-dif (- (Y-coord point2) (Y-coord pointl)))) (sqrt(+ (* x-dif x-dif) (* y-dif y-dif))))); Change the global path list to include distance between; adjacent nodes:(set! paths (init-lengths paths)) ;(pp paths)(define (find-connected-nodes a-node)(let ((ret-list '()))(do ((1 paths (cdr 1)))((null? 1))(let ((path (car 1))) ; (nodel node2 distance)=path(if (equal? a-node (car path))(set! ret-list (cons (cadr path) ret-list)))(if (equal? a-node (cadr path))(set! ret-list (cons (car path) ret-list)))))ret-list)); (find-connected-nodes 'n2)(define (depth path goal) (if (equal? (car(last-pair path)) goal) path ; done withsearch (let ((new-nodes (find-connectednodes(car (last-pair path)))) (keepsearching #t) (ret-val '())) (do ((nn newnodes (cdr nn)))66( (or(null? nn)(equal? keep-searching #f)))(if (not (member (car nn) path))(let ((temp (depth(append path (list (car nn)))goal)))(if (not (null? temp))(begin(set! ret-val temp) (set! keep-searching #f) ) ) ) ) )ret-val)))Функции testl и test2 используются для проверки работы функцииdepth.
Функция testl изображает на экране граф, а функция test2 рисуетна нем найденный между двумя вершинами путь.;Test code with graphics support:(load "Graph.ss") (define(testl) (open-gr) (pen-width1) (do ((p paths (cdr p)))((null? p ) )(display "(car p)=") (display (car p)) (newline)(let ((from (cadr (assoc (caar p) nodes))) (to(cadr (assoc (cadar p) nodes)))) (plot-line(x-coord from) (y-coord from)(x-coord to) (y-coord to)"black"))) (do ((n nodes (cdrn)))((null? n))(let ((n-val (cadar n)))(plot-string(+ 2 (x-coord n-val)) (y-coordn-val) (symbol->string (caarn))))))(define (test2)(define (draw-path pi)(pen-width 3)(let ((nodel (cadr (assoc (car pi) nodes))))(set! pi {cdr pi)) (do ((p pi (cdr p)))((null? p))(plot-line (x-coord nodel)(y-coord nodel)(x-coord (cadr (assoc (car p) nodes)))(y-coord (cadr (assoc (car p) nodes)))67"red")(set! nodel (cadr (assoc (car p) nodes))))))(draw-path (depth ' (n1) 'nil)))(testl)(test2)Чтобы проследить последовательность рекурсивных вызовов функцииdepth, можно воспользоваться встроенной функцией Scheme trace.Функция depth проста в реализации и для небольших графов эффективна.Но если первый выбранный путь является ошибочным и граф достаточновелик, то потеря в эффективности может быть существенна.
Программарекурсивно просматривает неверный путь до конца, и затем поднимаетсяпо каждой точке возврата. Для реальных поисковых задач пространствопоиска велико и требуется определенная устойчивость по времени поискав зависимости от исходных данных. В среднем стратегия поиска вширьявляется более эффективной, чем поиск вглубь. Поэтому требования кпрограмме, реализующей поиск пути в графе, дополняются требованиемэффективности для «средних» случаев поиска. Созданный первыйпрототип программы уже не удовлетворяет этому требованию.Для построения следующего прототипа программы, отвечающегорасширенным требованиям, можно воспользоваться уже написаннойпрограммой, просто заменив в ней функцию depth на функцию breadth.Все вспомогательные функции и функции рисования графа остаются безизменения, и могут быть повторно использованы в следующем прототипепрограммы.(define (breadth start-node goal-node) (let((visited-list (list start-node))(search-list (list(list start-node start-node 0 .
0 ) ) ) )(define (next s-list) (let((new-s-list ' ())) (do ((1s-list (cdr 1))). ((null? 1)) (let((path (car 1))) (let((last-node (car(last-pair (except-last-pair path)))))(let ((connected-nodes(find-connected-nodes last-node)))(do ((n connected-nodes (cdr n)))((null? n))(if (not (member (car n) visited-list))(begin(set! new-s-list (cons (append68(except-last-pair path)(list (car n)) (list (+(car (last-pair path)) ; old distance(slow-path-length (list (car (last-pair(except-last-pair path))) (car n))) ))) new-s-list)) (set! visitedlist(cons (earn) visited-list)))))))))new-s-list))(define (found-goal-node?)(let ((good-path '())) (do((1 search-list (cdr 1)))((null? 1)(not (null? good-path))) (if(member goal-node (car 1))(begin(set!good-path(car 1))(display "Found a good path:")(display good-path) (newline))))good-path))(let ((a-good-path •()))(do ((iter 0 (+ iter 1) ) )((or(equal? iter (length nodes)) (not(null? a-good-path) ) ) ) (set!search-list (nextsearch-list))(newline)(display "search level=") (display iter) (newline)(display "current visited list:") (newline) (displayvisited-list) (newline) (display "current searchlist:") (newline) (display search-list) (newline)(set! a-good-path (found-goal-node?))) (cdr a-goodpath))))Функция breadth, реализующая стратегию поиска вширь, несколькосложнее предшествующей функции depth из-за необходимости на каждомшаге хранить информацию обо всех рассматриваемых путях.Печать последовательности шагов функции breadth, позволяет убедитьсяв том, что реализованная стратегия осуществляет поиск вширь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
