在 Racket 中寻找两点之间的路径 [英] Finding path between 2 points in Racket

问题描述

我有以下连接列表:

(define routelist
  (list
      (list'a 'b)
      (list'a 'c)
      (list'b 'e)
      (list'b 'f)
      (list'b 'c)
      (list'a 'd)
      (list'e 'f)
      (list'f 'g)))

要找到 'a 和 'g 之间的路由.此页面显示了 Prolog 中的解决方案:http://www.anselm.edu/homepage/mmalita/culpro/graf1.html

Routes between 'a and 'g are to be found. This page shows a solution in Prolog: http://www.anselm.edu/homepage/mmalita/culpro/graf1.html

我可以管理以下解决方案，尽管它是迭代的:

I could manage following solution, though it is iterative:

(define (mainpath routelist start end (outl '()))
  (if (equal? start end)
      (println "Same start and end points.")
  (for ((item routelist)) 
    (when (equal? start (list-ref item 0))
          (set! outl (cons start outl))
          (if (equal? end (list-ref item 1))
              (begin 
                ; PATH FOUND:
                (set! outl (cons end outl))
                (println (reverse outl)))
              (begin 
                (mainpath (rest routelist) (list-ref item 1) end outl)
                (set! outl (rest outl))))))))

(mainpath routelist 'a 'g)

输出:

'(a b e f g)
'(a b f g)

如何在 Racket 中实现功能性解决方案?

How can a functional solution be achieved in Racket?

推荐答案

这是一个非常简单的解决方案:

Here is a very simple solution:

(define (mainpath routelist start end)
  (define (neighbors node)
    (map second (filter (lambda (x) (eq? (first x) node)) routelist)))
  (define (visit node visited)
    (when (not (member node visited))
      (when (eq? node end)
        (println (reverse (cons node visited))))
      (let ((new-visited (cons node visited)))
        (map (lambda (x) (visit x new-visited)) (neighbors node)))))
  (visit start '())
  "No more paths")

这个递归函数也可以管理带有循环的图，保留一个沿当前路径已经访问过的节点列表，并在它访问了从起始节点可到达的所有节点时停止.当前节点为结束节点时，打印当前路径.

This recursive function, that can manage also graphs with loops, keeps a list of nodes already visited along the current path and stops when it has visited all the nodes reachable from the start node. When the current node is the end node, the current path is printed.

这篇关于在 Racket 中寻找两点之间的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！