主页 / coding / 问题 / 77888742
Accepted
Pandasonsleds
Asked: 2024-01-27 04:05:30 +0800 CST

Lisp dfs 不返回非循环路径

  • 772

我正在创建一个 lisp 程序来查找无向图中的非循环路径，并将该路径返回给用户。该路径不一定需要是最短路径。我的完整代码如下：

(defvar graph '((A B C)
                  (B A C)
                  (C A B D)
                  (D C)
                  ))

(defun getneighbours (graph node) ;Gets neighbors of the given node.
    (if (assoc node graph)
        (cdr (assoc node graph))
        '()
    )
)

(defun acyclicpath (graph start goal) 
    (setq visited '()) ;Reset the returnpath and visited variables for the next search.
    (setq returnpath '())
    (if (dfswithpath graph start goal) ;Path found reverse path and return.
        (reverse 'returnpath)
    )
    nil
)

(defun dfswithpath (graph node goal)
    (if (equal node goal) ;Goal reached return true.
        (push node returnpath)
        t
    )

    (push node visited) ;Update visited list.

    (dolist (neighbour (getneighbours graph node)) ;Call dfs on each neighbour of node if not already visited.
        (if (not (member neighbour visited))
            (if (dfswithpath graph neighbour goal)
                (push node returnpath)
                t
            )
        )
    )
    nil ;No path found
)

(print (acyclicpath graph 'A 'C))

运行此代码会导致 dfswithpath 函数始终返回 nil 值。我已将问题范围缩小到 dolist 函数中的递归 dfswithpath 调用。看起来它永远不会解析为 t，因此嵌套的推送函数永远不会被调用。但是，我不明白为什么会这样。

lisp

1 个回答

  1. Best Answer

    该dfswithpath函数返回 nil，因为该函数中的最后一个形式是nil。要从函数返回而不是通过执行到最后一个函数，您必须使用(return-from dfswithpath <value>).

    从风格上来说，只有当没有很好的方法以函数式风格编写函数时才应该使用它。

    (defun dfswithpath (graph node goal)
    (if (equal node goal) ;Goal reached return true.
        (push node returnpath)
        t
    )

    t您是否期望它从函数中返回？它不是。您需要它return-from，或者重新排列代码以使其变得不必要。

    此外，if将单个表达式作为参数，将 ist置于“else”位置：(if condition this else)。

        (dolist (neighbour (getneighbours graph node)) ;Call dfs on each neighbour of node if not already visited.
        (if (not (member neighbour visited))
            (if (dfswithpath graph neighbour goal)
                (push node returnpath)
                t
            )
        )
    )
    nil ;No path found

    在 内部dolist，您可以使用该值(return <value>)来终止表单。dolist如果自然终止，就会返回nil。所以你可以在函数结束时执行此操作：

    (dolist (neighbour ...)
  (if condition
    (return t))
  ...))

    就是这样；nil之后不需要。该函数的最后一种形式是dolist，nil如果它执行所有迭代，就会产生结果。（语法中有一个地方dolist可以指定一个表达式，即return-form，其值给出 的dolist返回值，但我们在这里不需要它）。

    • 0

相关问题