0

我正在实现一个随机 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)))))

以及创建全局参数供求解器使用的主函数

(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 编码技能不谈，有没有我可以修复或改进的错误，以使生成的实例质量更高？

4

3 回答 3

0

一般来说，在生成基准时，应该修复所有参数并尝试只使用一个。后者通常与一些随机化的东西有关。在您的情况下，您似乎没有使用任何随机化。我强烈建议您添加例如一个参数，该参数表示在约束范围内将两个变量放在一起的概率，或者它们在一起的频率等。

另一方面，您可以使用现有的基准，例如http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html。有一系列问题，其中一些是二进制 CSP（例如“RAND”分​​类中的“标记”问题）。

于 2013-09-08T21:35:08.340 回答
0

基本事实：关于您的随机实例的每个决定都将反映在您的基准测试中。如果您想比较您的算法 A 和 B，有人可能会生成 A（或 B）占主导地位的随机实例。

大多数时候，有人对困难实例感兴趣（因为约束编程主要用于解决困难问题）。在这种情况下，我为您看到了两种可能性：

  1. 简单/实用的方法（如 Med 建议的）：使用现有的基准。有评估各种决策系统的竞赛，例如CSP Solver Competition。他们中的大多数提供了他们使用的所有实例，这些实例非常有价值。很多时间已经进入了这些世代。

  2. 硬/理论方法：考虑 3-SAT ->“你的问题”/CP 的转换，并在相变参数空间内使用随机生成的 3-SAT实例（Mezard，Parisi，Zecchina | 2002）。这些实例将非常困难（具有一些理论基础）！

于 2013-11-21T00:27:37.477 回答
0

关于基本编码风格有一些说明：

(loop for i from 0 upto (1- n) ...)

只是

(loop for i below n ...)

crea-dominio-nuevo是一个递归函数。在每次迭代中，您将一个项目添加到列表的末尾。这是在 Lisp 中使用单链表的最糟糕的方法。应避免将项目附加到列表的末尾。添加一个项目有一个便宜的操作，那就是把它放在前面。如果你真的需要添加到某事的末尾，有两种方法可以做到：

  • 使用向量并推到最后

  • 进行迭代，以使您在前面并在最后反转列表一次

crea-lista-restricciones有同样的问题。

length您多次调用列表是另一个问题。

于 2013-09-08T12:23:49.830 回答