Résolution des contraintes de chaîne dans MiniZinc - analyse, minizinc

J'ai essayé de définir une contrainte avec l'opérateur de concaténation de chaînes dans MiniZinc, en résolvant les variables a et b:

include "disjunctive.mzn";

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

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

Néanmoins, cela semble être une erreur de syntaxe:

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"

Est-il encore possible de résoudre les contraintes dans MiniZinc avec des chaînes ou des tableaux en tant que variables?

Réponses:

Les contraintes directement sur les chaînes sont assez rares dansla communauté de programmation par contraintes. Il ya quelques recherches dans ce domaine, bien que je n’aie jamais vu de système CP général prenant en charge les variables chaîne. (Voir ci-dessous pour les systèmes CP non généraux.)

Dans MiniZinc, il est préférable de convertir les chaînes en nombres entiers (par exemple, a = 1, b = 2, etc.), puis de simuler toutes les opérations sous forme d’opérations entières.

Un exemple simple est un générateur de mots croisés: http://hakank.org/minizinc/crossword3/crossword3.mzn, qui est décrit dans http://hakank.org/minizinc/crossword3/.

Une opération de chaîne importante est la concaténation de deux chaînes, mais étant donné que MiniZinc ne prend en charge que les tableaux statiques (longueur fixe), cette opération doit être gérée en définissant un "tableau cible" suffisamment grand.

En ce qui concerne Picat, les modules cp / sat ne prennent pas en chargeles chaînes non plus, donc la même conversion en nombres entiers doit être appliquée. Mais comme Picat est un langage de programmation logique (think Prolog), on peut utiliser les approches de programmation logique traditionnelles.

Notez que MiniZinc et Picat - ainsi que la plupart desautres systèmes CP - prend en charge la contrainte globale "régulière" qui utilise un DFA (automate fini déterministe) pour créer les contraintes. Voir par exemple un solveur Nonogram: http://hakank.org/minizinc/nonogram_create_automaton2.mzn et la décomposition de la contrainte de contiguïté globale: http://hakank.org/minizinc/contiguity_regular.mzn

MiniZinc prend également en charge une variante NFA (non déterministe) de la contrainte régulière.

Cela dit, il existe des systèmes utilisant une sorte deapproche de résolution de contraintes qui prend en charge les variables de chaîne, bien que, autant que je sache, ils tendent à ne prendre en charge que les variables de chaîne, pas le répertoire général des entiers, des ensembles, etc. Voir par exemple Hampi (http://people.csail.mit.edu/akiezun/hampi/). Remarque: cela fait longtemps que je n'ai pas vérifié ces systèmes dédiés.