3

2つのノード名（AとEなど）を取り、再帰的に使用されるオプションのパラメーター（キュー）を持つ既存のヒルクライム関数を変更しようとしています。あるパスが別のパスよりも安いかどうかを評価する関数「cheaper」を定義しようとしています。また、1つのゴールノードの代わりに、ゴールノードのリストを渡そうとしています。これらのノードの1つに到達すると、関数は評価を停止します。

問題は、入力した開始ノードと空のリストを除いて、関数が何も返さないことです。

これが私のネットワーク/グラフと関連するコストです：

(setf (get 's 'coordinates) '(0 3)
      (get 'a 'coordinates) '(4 6)
      (get 'b 'coordinates) '(7 6)
      (get 'c 'coordinates) '(11 9)
      (get 'd 'coordinates) '(2 0)
      (get 'e 'coordinates) '(9 2)
      (get 'f 'coordinates) '(11 3))


(setf (get 's 'cost) 0
      (get 'a 'cost) 16
      (get 'b 'cost) 4
      (get 'c 'cost) 10
      (get 'd 'cost) 5
      (get 'e 'cost) 12
      (get 'f 'cost) 14)

そして、これが私の修正されたヒルクライム関数です：

(defun hill-climb (start finish &optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'(lambda (p1 p2)
                                                      (cheaper p1 p2 
                                                               finish)))
                                            (rest queue))))))

最後に、「コスト」関数と「安価」関数を次に示します。

(defun cost (path)
  (apply '+ (mapcar #'(lambda (x) (get x 'cost)) path)))


(defun cheaper (p1 p2)
  (< (cost p1)
     (cost p2)))

編集：申し訳ありませんが、ここに「拡張」があります：

(defun extend (path)
  (print (reverse path))
  (mapcar #'(lambda (new-node) (cons new-node path))
          (remove-if #'(lambda (neighbor) (member neighbor path))
                     (get (first path) 'neighbors))))
4

1 に答える 1

2

何が問題なのかよくわかりません。あなたのexpandでneighborは、あなたの質問で与えられていないプロパティが使用されています。このプロパティがすべてのノードに対して定義されている場合、コードは機能します。

間に別のノードがなく、隣接するすべてのノードを想定します（これは、データにとって意味があると思われる唯一のオプションです。これは、代替ノード、つまり接線ノード（つまり、一方または両方に対して+/- 1のノード）のみを作成するためです。座標）ネイバー、あなたの例ではネイバーをまったく生成しません）：

(setf (get 's 'neighbors) '(a d)
      (get 'a 'neighbors) '(s b d)
      (get 'b 'neighbors) '(a c e)
      (get 'c 'neighbors) '(b)
      (get 'd 'neighbors) '(s a e)
      (get 'e 'neighbors) '(b d f)
      (get 'f 'neighbors) '(e))

(defun hill-climb (start finish &optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'cheaper)
                                            (rest queue))))))

（欠落している部分はあなたの投稿と同じままです。lambda周りを落とすなどの小さな調整と、への追加の引数のみcheaperです。）

正しい結果が得られます：

CL-USER> (hill-climb 's '(b))

(S) 
(S D) 
(S D E) 
(S D E B)
CL-USER> (hill-climb 's '(b d))

(S) 
(S D)

新しいプロパティを導入しない場合は、expand関数内のネイバーをチェックする必要があります（これは、ノードのリストを渡す必要があることも意味します）。

于 2011-10-11T21:31:46.120 に答える