3

山登り法の検索を行うために変換しようとしているBFSのLisp実装があります。

私のBFSコードは次のようになります。

; The list of lists is the queue that we pass BFS.  the first entry and 
; every other entry in the queue is a list.  BFS uses each of these lists and 
; the path to search.  

(defun shortest-path (start end net)   
  (BFS end (list (list start)) net))

;We pass BFS the end node, a queue containing the starting node and the graph 
;being searched(net)   

(defun BFS (end queue net)
  (if (null queue) ;if the queue is empty BFS has not found a path so exit
      nil
      (expand-queue end (car queue) (cdr queue) net)))

(defun expand-queue (end path queue net)
  (let ((node (car path)))
    (if (eql node end)   ; If the current node is the goal node then flip the path
                         ; and return that as the answer
        (reverse path)
        ; otherwise preform a new BFS search by appending the rest of 
        ; the current queue to the result of the new-paths function
        (BFS end (append queue (new-paths path node net)) net))))

; mapcar is called once for each member of the list new-paths is passed
; the results of this are collected into a list
(defun new-paths (path node net)
  (mapcar #'(lambda (n) (cons n path))
         (cdr (assoc node net))))

これで、BFSのように常に左側のノードを拡張するのではなく、目標状態に最も近いと思われるノードを拡張する必要があることがわかりました。
私が使用しているグラフは次のようになります。

(a (b 3) (c 1))  
(b (a 3) (d 1))

上記のBFS実装でこれを機能させるための変換関数がありますが、このグラフ形式を使用してこれを山登り法に変換する必要があります。

どこから始めればいいのかわからず、何の役にも立たないように努力してきました。主に関数を変更して最も近いノードを展開する必要があることはわかってexpand-queueいますが、どのノードが最も近いかを判別する関数を作成できないようです。

助けてくれてありがとう！

4

1 に答える 1

0

リストの最後に何かを追加するのは間違っています。これは、リストで最もコストのかかる操作です。リスト全体がコピーされてから、他のリストが追加されます。再帰的な手順で使用します。つまり、ノードを展開して新しいパスを作成するたびに実行されます。

アイテムをキューに入れる場合は、これを行っている順序を確認する必要があります。幅優先では、次のレベルに移動する前に、レベル内の各ノードにアクセスします。山登りでは、重み付け関数を使用して「最良」の候補を並べ替える必要があります。したがって、現在のノードと次のノード候補から数値を計算する何らかの関数が必要です。次に、候補を並べ替えて、最初に「最適な」ノードを展開する必要があります。LIFO (後入れ先出し) キューの場合、これは最も有望なノードを最後にプッシュする必要があることを意味し、最初に展開されるようにします。LIFO キューは、単独でリンクされたリストに適していることに注意してください。FIFO（先入れ先出し）はそうではありません。

コンピューター サイエンスの典型的な考え方は、データの抽象化です。LIFO QUEUE がそのようなデータ構造である場合、MAKE-LIFO-QUEUE、EMPTY-QUEUE-P などの関数を定義する必要があります。これらの関数は、LIST、NULL などの代わりに使用し、目的を達成します。データ構造がより明確になります。これによりコードが長くなりますが、Lisp リストは一般的であり、あらゆる種類の使用シナリオで (悪用) 使用される可能性があるため、リスト操作だけを見てもその意図は明確になりません。これは、より複雑なグラフ アルゴリズムでは特に重要です。

于 2011-04-30T10:38:50.770 に答える