2

一般的な Lisp を使用して 2 つのビット ベクトル間の距離を計算する際に問題が発生しています。

私はLispを初めて使用し、これが人工知能の宿題の最後の宿題の問題であり、私が遭遇している問題は構文の問題であると信じています。

質問は次のとおりです。

1 と 0 のリストで表される同じ長さの 2 つのビット ベクトル間に再帰関数 DISTANCE を記述します。例えば、

(距離 '(1 0 1 1) '(0 1 0 1))

答え: 3

ベクトルの長さが異なる場合、何をしなければならないかを議論します。

私の理解では、2 つのビット ベクトル間の距離は、単純に 2 つを XOR してから 1 をカウントアップすることです。

この例を使用すると、1011 ^ 0101 = 1110 となり、3 になります。

これが距離を計算する正しい方法であると仮定すると、私の問題は、これを再帰的にすることに加えて、lisp で XOR する方法を見つけることです。

logxor 2 つのリストを取得して(ここに表示)のような形式に変換し、結果のリストの 1 を数え上げるにはどうすればよいでしょうか?

やろうとすると(logxor '(1 0 1 1) '(0 1 0 1))、'(1 0 1 1) は整数ではないためlogxor、リストでは機能しないようで、途方にくれます。

あなたが提供できる助けをいただければ幸いです

ありがとう！

4

5 に答える 5

7
于 2014-02-10T01:06:41.797 に答える
4

LOGXOR は数値で機能します。

CL-USER 43 > (logxor 2 1)
3

数字を0と1で書く表記もあります。

CL-USER 44 > (logxor #b1010 #b0101)
15

以下も参照してください。

CL-USER 45 > (logcount (logxor #b1011 #b0101))
3
于 2014-02-09T20:17:51.817 に答える
1

単純な再帰バージョンは末尾再帰ではありません。

(defun distance (v u)
  (cond ((null v) (length u)) ; assume that missing is different from both 0 & 1
        ((null u) (length v)) ; ditto
        (t (+ (if (= (first u) (first v)) 0 1) 
              (distance (rest v) (rest u))))))

これは、次のような距離 (不一致の数) の公理的な定義に対応します。

  1. 一方のベクトルが空の場合、距離はもう一方の長さになります
  2. 距離は加算されdist(v1,u1)+dist(v2,u2)=dist(v1+v2,u1+u2)ますlength(v1)=length(u1)。+連結を意味します
  3. もしlength(v1)=length(v2)=1、その後dist(v1,v2):=(v1==v2? 0 : 1)

末尾再帰バージョン (コンパイラーによって反復に簡単に変換できる) が必要な場合は、関数で部分的な結果を運ぶ必要があります。

于 2014-02-09T20:43:35.640 に答える
1

logxorリストにマップするだけです：

? (mapcar #'logxor '(1 0 1 1) '(0 1 0 1))
(1 1 1 0)

そしてそれらを数えます：

? (count 1 (mapcar #'logxor '(1 0 1 1) '(0 1 0 1)))
3

または、すべてを一緒に追加します。

? (apply #'+ (mapcar #'logxor '(1 0 1 1) '(0 1 0 1)))
3

これを再帰的に変換するだけです

(defun distance (lst1 lst2)
  (if (or (null lst1) (null lst2))
    0
    (+ (logxor (car lst1) (car lst2))
       (distance (cdr lst1) (cdr lst2)))))

または末尾再帰バージョン:

(defun distance (lst1 lst2 &optional (res 0))
  (if (or (null lst1) (null lst2))
    res
    (distance (cdr lst1) 
              (cdr lst2) 
              (+ res (logxor (car lst1) (car lst2)))))))

それから

? (distance '(1 0 1 1) '(0 1 0 1))
3
于 2014-02-09T19:59:33.810 に答える
0

単純な defun ステートメントを 1 つ使用したい場合は、いつでも次のようにすることができます。

(defun distance (a b)
     (cond
          ((equal nil a) 0)
          (t (+ (rem (+ (first a) (first b)) 2) (distance (rest a) (rest b))))
     )
)
于 2014-02-09T20:18:26.040 に答える