Lispの2つのノード間の最長パスを見つける方法は?

2010年10月16日に質問されました。  ·  閲覧回数 1.5k回  ·  ソース

Jay picture
2010年10月16日

ノードを再訪せずに、2つのノード間の最長パスを見つけるLisp関数をプログラムする必要があります。 ただし、開始ノードと終了ノードが同じである場合は、このノードに再度アクセスできます。 関数は、再帰的で深さ優先探索の両方である必要があります。

私は何時間もこれを達成しようとしてきましたが、解決策を思い付くことができません。 関数の概要は知っていますが、正しくプログラムできません。 一部のコードおよびほとんどの場合は擬似コード:

(defun longest-path (start end net &optional (current-path nil))  
    (cond ((and (eql start end)
                (not (null current-path)))
          (list start))
          (t
           (find neighbors of start/node)
           (remove any previously traveled neighbors to avoid loop)
           (call longest-path on these neighbors)
           (check to see which of these correct paths is longest))))

ネットは '((ab)(bc))のように見えます。ここで、最初の項目はノードであり、他のすべてはその隣接ノードです(たとえば、ノードaには隣接bがあり、ノードbには隣接cがあります)。

はい、これは宿題用です。したがって、解決策またはその一部を投稿することに抵抗がある場合は、そうしないでください。 私はLispを初めて使用するので、まともなスタートを切るためのヒント/ヘルプが欲しいです。

ありがとう

編集:まあ、私が得ることができたのはこれでした:

(defun longest-path (start end net &optional (current-path nil))
  (cond ((and (eql start end)
              (not (null current-path)))
         (list start))
        (t
         (push start current-path)
         (let ((neighbors (cdr (assoc start net))))
           (let ((new-neighbors (set-difference neighbors current-path)))
             (let ((paths (mapcar #'(lambda (node)
                                      (longest-path node end net current-path))
                            new-neighbors)))
               (let ((longest (longest paths)))
                 (if longest
                     (cons start longest)
                   nil))))))))


(defun longest (lst)
  (do ((l lst (cdr l))
       (r nil (if (> (length (car l)) (length r))
                  (car l)
                r)))
      ((null l) r)))

開始ノードと終了ノードが同じである場合を除いて、正しい解が生成されます。 同じでも検索の仕方がわからない。

回答

asdr picture
2010年10月18日
3

私はこのアルゴリズムをPaulGrahamの本AnsiCommonLispから覚えています。 これが本からの1つの演習の解決策のリンクです。 これはあなたを助けるはずです。

解決

Rainer Joswig picture
2010年10月16日
2

私はあなたが3つのケースをチェックする必要があると思います:

  1. 終了に達しました->このパスを返します
  2. これ以上の選択肢はありません-> nilを返します
  3. 隣人の最長の道を見つける

コードの概要:

(defun longest-path (node end-node net current-path)
  (cond ((eql node end-node)
         (or current-path (list node end-node)))
        ((null (node-neighbors node net))
         ())
        (t
         (let* ((neighbors (node-neighbors node net))
                (not-visited-neighbors (set-difference neighbors current-path))
                (paths (mapcar (lambda (next-node)
                                 (longest-path next-node end-node net
                                               (cons node current-path)))
                               not-visited-neighbors)))
           (first (sort paths #'> :key #'length))))))