我正在实现一个随机CSP生成器，用于对两种不同的弧一致性算法（AC3和AC2001）进行比较测试。实例是使用变量数、所有变量的域大小为 8相同的参数、约束数和每个约束拒绝的值对数（所有约束相同）生成的。
我的实现构建了变量（具有两个字段的结构，名称和域（列表）），约束8结构具有两个字段，涉及的变量和约束函数））。它创建一个哈希表，其中包含每个限制中涉及的变量作为键，并作为值作为所述约束拒绝的对列表。使用时，每个约束都会检查变量的给定值是否包含在拒绝的值列表中。
这种实现"有效"，但生成的实例中很少需要减少电弧，因此它们对于测试目的大多无用。这是代码：
; 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)))))
以及创建全局参数供求解器使用的 main 函数
(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编码技能不谈，我是否可以修复或改进任何错误，以使生成的实例具有更高的质量？
有一些关于基本编码风格的评论：
(loop for i from 0 upto (1- n) ...)
只是
(loop for i below n ...)
crea-dominio-nuevo是一个递归函数。在每次迭代中，将项添加到列表的末尾。这是在 Lisp 中使用单向链表的最糟糕的方法。应避免将项目追加到列表末尾。添加一个项目有一个便宜的操作，那就是把它骗到前面。如果你真的需要添加到某件事的末尾，有两种方法可以做到：
使用向量并推到最后
进行迭代，以便您骗到前面，最后反转列表一次
crea-lista-restricciones也有同样的问题。
您在列表中多次调用length是另一个问题。
一般来说，在生成基准测试时，应该修复所有参数并尝试只使用一个参数。后者通常与一些随机化的东西有关。在您的情况下，您似乎没有使用任何随机化。例如，我强烈建议您添加一个参数，表示在约束范围内将两个变量放在一起的概率，或者它们在一起的频率等。
另一方面，您可以使用现有的基准测试，例如 http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html。有一堆问题，其中一些是二进制CSP（例如"RAND"导管中的"标记"问题）。
基本事实：关于随机实例的每个决策都将反映在您的基准测试中。如果你想比较你的算法A和B，有人可以生成A（或B）占主导地位的随机实例。
大多数时候，有人对硬实例感兴趣（因为约束编程主要用于困难的问题）。在这种情况下，我认为您有两种可能性：
-
简单/实用的方法（如Med提出的）： 使用现有的基准。有评估各种决策系统的竞赛，如CSP求解器竞赛。他们中的大多数提供了他们使用的所有实例，这些实例非常有价值。很多时间已经进入了这些的产生。
-
硬/理论方法：考虑3-SAT的变换->"你的问题"/CP，并在相变参数空间中使用随机生成的3-SAT实例（Mezard，Parisi，Zecchina | 2002）。这些实例将非常困难（有一些理论骨干）！