Генерация случайных экземпляров двоичных проблем с ограничением ограничений

Question

Я реализую генератор случайных 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))))) 

Эта функция создает restriccions и он отклонил значения

(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 в сторону, есть ли какая-либо ошибка, которую я могу исправить или улучшить, которую я могу сделать для того, чтобы экземпляры сгенерировали более высокое качество?

Answer 1

Есть некоторые замечания по поводу основного стиля кодирования:

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

просто

(loop for i below n ...) 

crea-dominio-nuevo рекурсивная функция. На каждой итерации вы добавляете элемент в конец списка. Это самый худший способ использовать односвязный список в Lisp. Следует избегать добавления элементов в конец списка. Есть одна дешевая операция, чтобы добавить элемент, а это значит, что он стоит впереди. Если вы действительно нужно добавить в конец чего-то, есть два способа сделать это:

• использовать вектор и самокаты к концу

• сделать итерацию таким образом, что вы против к спереди и на конце развернуть список один раз

crea-lista-restricciones имеет ту же проблему.

То, что вы называете length в списках несколько раз, является другой проблемой.

Answer 2

В целом при создании контрольных показателей необходимо исправить все параметры и попытаться сыграть только с одним. Последнее обычно связано с некоторыми материалами рандомизации. В вашем случае кажется, что вы не используете рандомизацию. Я настоятельно рекомендую вам добавить, например, параметр, представляющий вероятность объединения двух переменных в область ограничения или частое совпадение и т. Д.

С другой стороны, вы можете использовать существующие тесты, такие как http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html , Существует скамья проблем, некоторые из которых являются двоичными (например, проблема «отметки» в категории «RAND»).

Answer 3

Основной факт: Каждое решение о ваших случайных экземплярах будет отражено в вашем тесте. Если вы хотите сравнить свои алгоритмы A и B, кто-то может генерировать случайные экземпляры, где доминирует A (или B).

В большинстве случаев кто-то заинтересован в жестких экземплярах (потому что ограничение-программирование в основном используется для сложных проблем). В этом случае, я вижу две возможности для вас:

1. Easy/Практический подход (как мед), предложенный: использовать существующие контрольные показатели. Конкурсы оценивают все типы систем принятия решений, такие как CSP Solver Competition. Большинство из них предоставляют все те экземпляры, которые они использовали, и эти примеры очень ценны. Много времени собиралось в их создание.

2. Hard/Теоретический подход: думать о трансформации 3-SAT -> "Ваша проблема"/CP и использовать случайно сгенерированных 3-SAT экземпляры в пределах фазового перехода параметров пространства (Mezard , Parisi, Zecchina | 2002). Эти случаи будут очень сложными (с некоторым теоретическим основанием)!