2 つの異なるアーク整合性アルゴリズム (AC3 と AC2001) の比較テストを行うために、ランダム CSP のジェネレーターを実装しています。インスタンスは、変数の数、ドメインのサイズ (すべての変数で同じ)、制約の数、および各制約によって拒否される値のペアの数 (すべての制約で同じ) のパラメーターを使用して生成されます。
私の実装では、変数 (名前とドメイン (リスト) の 2 つのフィールドを持つ構造体)、2 つのフィールドを持つ構造体、関連する変数と制約関数) を構築します。各制限に関係する変数をキーとして、値として、その制約によって拒否されたペアのリストを持つハッシュ テーブルを作成します。各制約を使用すると、変数に指定された値が拒否された値のリストに含まれているかどうかがチェックされます。
この実装は「機能」しますが、生成されたインスタンスのほとんどがアーク削減を必要とするため、テスト目的にはほとんど役に立ちません。コードは次のとおりです。
; This function generates the complete list of variables for the problem
(defun crea-lista-variables (nvars tdom p-v)
(loop for i from 0 to (1- nvars) collect
(crea-variable :nombre i
:dominio (crea-dominio-nuevo tdom p-v nil))))
; This function creates a variable's domain, without repetitions. It takes it's
; values from a list of possible values for the problem
(defun crea-dominio-nuevo (tdom p-v dominio)
(let ((candidato (nth (random (1- (length p-v))) p-v)))
(cond ((= tdom 0) dominio)
((not (pertenece candidato dominio))
(crea-dominio-nuevo (- tdom 1) p-v
(append dominio (list candidato))))
(t (crea-dominio-nuevo tdom p-v dominio)))))
この関数は制限を作成し、拒否された値です
(defun crea-lista-restricciones (nrest npares tdom p-p p-v
restricciones rechazados)
(let* ((variables (nth (random (1- (length p-p))) p-p))
(rest (crea-restriccion :variables variables
:funcion #'(lambda (x y &optional (z nil))
(not (pertenece (list x y)
z))))))
(cond ((= nrest 0) restricciones)
((null (gethash variables rechazados))
(crea-rechazados npares tdom variables p-v rechazados)
(crea-lista-restricciones (1- nrest) npares tdom p-p
p-v (append restricciones (list rest))
rechazados))
(t (crea-lista-restricciones nrest npares tdom p-p
p-v restricciones rechazados)))))
この関数は、拒否された値のハッシュ テーブルを作成します
(defun crea-rechazados (numpares tamdom variables posibles-valores rechazados)
(let* ((valor1 (nth (random (1- (length posibles-valores)))
posibles-valores))
(valor2 (nth (random (1- (length posibles-valores)))
posibles-valores))
(candidato (list valor1 valor2))
(lista (gethash variables rechazados)))
(cond ((= numpares 0) rechazados)
((not (pertenece candidato lista))
(setf (gethash variables rechazados)
(append lista (list candidato)))
(crea-rechazados (1- numpares) tamdom variables
posibles-valores rechazados))
(t (crea-rechazados numpares tamdom variables
posibles-valores rechazados)))))
そして、ソルバーが使用するグローバル パラメータを作成するメイン関数
(defun genera-problema (numvars tamdom numrest numpares)
(cond ((< numvars 2)
(format t "~&Error: Debe haber al menos 2 variables"))
((< tamdom 2)
(format t "~&Error: Los dominios deben tener al menos dos elementos"))
((or (< numrest 0) (> numrest (/ (* numvars (- numvars 1)) 2)))
(format t "~&Error: numero de restricciones incorrecto"))
((or (< numpares 1) (> numpares (- (* tamdom tamdom) 1)))
(format t "~&Error: numero de pares incorrecto"))
(t (let ((posibles-valores (loop for i from 0
to (1- (+ tamdom tamdom))
collect i))
(posibles-pares (loop for i from 0 to (- numvars 2) append
(loop for j from (+ i 1)
to (1- numvars)
collect (list i j)))))
(defparameter *RECHAZADOS*
(make-hash-table :test #'equalp))
(defparameter *VARIABLES-AC3*
(crea-lista-variables numvars tamdom posibles-valores))
(defparameter *VARIABLES-AC2001*
(loop for variable in *VARIABLES-AC3*
collect (crea-variable :nombre (psr-var-nombre var)
:dominio (copia-lista
(psr-var-dominio var)))))
(defparameter *RESTRICCIONES*
(crea-lista-restricciones numrest numpares tamdom
posibles-pares posibles-valores
nil *RECHAZADOS*))
(defparameter *ARCOS-AC3* 0)
(defparameter *ARCOS-AC2001* 0)))))
関数「pertenece」は、要素がリスト にあるかどうかをチェックします。スペイン語の名前でも理解できると思います。そうでない場合は、完全に翻訳できます。
では、私の恐ろしい Lisp コーディング スキルはさておき、生成されたインスタンスの品質を向上させるために修正できるエラーや改善できるエラーはありますか?