Come evitare il loop in una ricerca dept in un grafico?

Question

Come evitare il loop in una ricerca dept in un grafico?

#1 da (1 voti)

0

Devo implementare, in Lisp, un algoritmo di ricerca di profondità in un grafico implicito (cioè un grafico in cui ho il nodo di partenza, il nodo obiettivo e la funzione successore, f, che danno a un nodo la creazione dei suoi successori). C'è un limite di profondità d. L'algoritmo deve restituire un percorso (ovviamente non può essere minimo).

Il mio problema è come gestire il loop.

La mia prima domanda è: se utilizzo questo seguente metodo stupido, lo lavoro?

Ho 2 lista. Il primo è un LIFO ((lo chiamo list1) quando inserisco nella testa i nodi succesor.Evry time espongo il nodo nella testa.

Nel secondo elenco (lo chiamo list2) tengo una lista in cui tutti i nodi sono già stati soddisfatti e ogni volta che espongo un nodo, controllo se i nodi successori ottenuti sono nella lista sopra (lista2). Per i nodi che ci sono dentro (in list2) non li inserisco in list1.

Questo metodo fa schifo perché nel peggiore dei casi devo tenere in lista 2 tutti i nodi del grafico e devo cercare ad ogni espansione se alcuni nodi successivi sono nella lista2. (ad esempio, questo metodo funziona sicuramente con la ricerca in ampiezza) Ma almeno funziona? O rischierei di tagliare percorsi rilevanti?

La seconda domanda è: Come posso implementarlo in modo efficiente (pseudocodice, o semplicemente idea)?

Grazie in anticipo

lisp artificial-intelligence graph-traversal

posta Nicola 08.07.2015 - 13:28

fonte

1 risposta

Leggi altre domande sui tag lisp artificial-intelligence graph-traversal

Accesso ai dati nel widget Come lavorare con un motivo di errore [duplicato]

score 1 · Answer 1

Usa ricorsione:

;; you might want to implement sets using hash tables
(defun make-set (&rest elements)
  elements)
(defun set-empty-p (s)
  (null s))
(defun set-union (s1 s2)
  (union s1 s2))
(defun depth-search (start end next max-depth
                     &key (seen (make-set start))
                       (depth 0) (path (list start)))
  ;; untested!
  (when (eq start end)
    (return path))
  (when (= depth max-depth)
    (return t))                 ; no path
  (let ((candidates (set-difference (funcall next start) seen)))
    (loop for candidate in candidates
      for path = (depth-search candidate end next max-depth
                               :seen (set-union seen (make-set candidate))
                               :depth (1+ depth) :path (cons candidate path))
      do (when (listp path) (return path))
      finally (return t))))