Início / coding / Perguntas / 77888742
Accepted
Pandasonsleds
Asked: 2024-01-27 04:05:30 +0800 CST

Lisp dfs não retornando caminho acíclico

  • 772

Estou criando um programa lisp para encontrar um caminho acíclico em um gráfico não direcionado e retornar esse caminho ao usuário. O caminho não precisa necessariamente ser o caminho mais curto. Meu código completo é o seguinte:

(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))

A execução desse código resulta em um valor nulo sendo sempre retornado pela função dfswithpath. Limitei o problema à chamada recursiva dfswithpath na função dolist. Parece que ele nunca resolve t e, portanto, a função push aninhada nunca é chamada. No entanto, não consigo entender por que esse é o caso.

lisp

1 respostas

  1. Best Answer

    A dfswithpathfunção retorna nil porque a última forma dessa função é nil. Para retornar de uma função diferente da execução até a última, você deve usar (return-from dfswithpath <value>).

    Estilisticamente, isso só deve ser usado quando não houver uma maneira legal de escrever a função em um estilo funcional.

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

    Você espera que isso retorne tda função? Isso não. Você precisa disso return-fromou reorganizar o código para torná-lo desnecessário.

    Além disso, iftoma expressões únicas como argumentos, para que testeja na posição "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

    Dentro dolist, você pode usar (return <value>)para encerrar o dolistformulário, com esse valor. Se terminar naturalmente, retornará nil. Então você pode fazer isso no final da sua função:

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

    E é isso; não nilé necessário depois. A última forma da função é a dolist, que produz resultados nilse executar todas as iterações. (Há um lugar na dolistsintaxe para especificar uma expressão, o return-form , cujo valor fornece dolisto valor de retorno de , mas não precisamos disso aqui).

    • 0

relate perguntas