7

ノードを再訪せずに、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)))

開始ノードと終了ノードが同じ場合を除いて、正しいソリューションが生成されます。同じなのに検索の仕方がわかりません。

4

2 に答える 2

3

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

解決

于 2010-10-18T13:29:59.230 に答える
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))))))
于 2010-10-15T23:55:07.617 に答える