Вирішення обмежень струни в MiniZinc - розбір, мініцинк

Я спробував визначити обмеження з оператором конкатенації рядків у MiniZinc, розв'язуючи для змінних a і b:

include "disjunctive.mzn";

var string:a;
var string:b;
constraint("var1/var2" = (a ++ "/" ++ b));

solve satisfy;
output ["nx=", show(a)];

Однак, здається, це синтаксична помилка:

MiniZinc: type error: type error in operator application for `++". No matching operator found with left-hand side type `string" and right-hand side type `var string"

Чи можна вирішити обмеження в MiniZinc за допомогою рядків або масивів як змінних?

Відповіді:

Обмеження безпосередньо на рядок досить рідкісніСпільнота програмування Constraint. Є деякі дослідження в цьому, хоча я не бачив жодної загальної системи КП, яка підтримує рядкові змінні.

У MiniZinc краще перетворювати рядки в цілі числа (наприклад, a = 1, b = 2 і т.д.), а потім імітувати всі операції як операції з цілим числом.

Один простий приклад - генератор кросвордів: http://hakank.org/minizinc/crossword3/crossword3.mzn, яка описана в http://hakank.org/minizinc/crossword3/.

Однією з важливих операцій рядка є конкатенація двох рядків, але оскільки MiniZinc підтримує лише статичні масиви (фіксованої довжини), це необхідно обробляти шляхом визначення досить великого "цільового масиву".

Що стосується Picat, модулі cp / sat не підтримуютьабо рядки, тому необхідно застосувати одне і те ж перетворення до цілих чисел. Але оскільки Picat є мовою логічного програмування (думаю, Prolog), можна використовувати традиційні підходи логічного програмування.

Зауважте, що MiniZinc і Picat - як і більшістьінші системи СР - підтримує глобальне обмеження "регулярні", які використовують DFA (детермінований кінцевий автомат) для створення обмежень. Див., Наприклад, вирішувач Nonogram: http://hakank.org/minizinc/nonogram_create_automaton2.mzn і декомпозицію глобального обмеження суміжності: http://hakank.org/minizinc/contiguity_regular.mzn

MiniZinc також підтримує NFA (недетермінований) варіант регулярного обмеження.

Тим не менш, існують системи, що використовують свого родупідхід до вирішення обмежень, який підтримує рядкові змінні, хоча AFAIK, як правило, підтримують лише рядкові змінні, а не загальний репертуар цілих чисел, наборів тощо.http://people.csail.mit.edu/akiezun/hampi/). Примітка: відтоді, як я перевірив ці спеціалізовані системи, було досить давно.