Ограничитель Удовлетворенность (Иерархический) Решатель
Мне нужно смоделировать проблему удовлетворения ограничений (CSP) в Java или.NET. Проблема требует, чтобы иерархия переменных была представлена. Таким образом, каждый узел дерева является переменной.
Например, если переменная C1 является дочерней по отношению к другой переменной C2 и если C1 имеет значение true, то C2 должен быть истинным, поскольку он является его родителем. В то же время, если переменный узел в ветви имеет значение true, это означает, что все переменные в других ветвях являются ложными, поскольку в иерархии может быть выбрана только одна ветвь.
Как я могу представить это как проблему CSP и какой инструмент я могу использовать в Java или.NET?
Я должен отредактировать это, чтобы предоставить больше деталей, потому что есть больше чем это:
В моей задаче есть 2 части: в 1-й части есть функция максимизации q1*x1+q2*x2+q3*x3.. где qi - коэффициент (действительное число), а xi - переменная (может быть 0 или 1) и я должен выбрать часть XI, которая максимизирует эту функцию. Другими словами, узлы могут быть только 0 или 1, и я должен максимизировать эту функцию, выбрав узел из иерархии.
Опять же, эти переменные xi являются узлами дерева, поэтому, когда я выбираю некоторые xi, они должны быть из одной и той же ветви дерева, и одновременно может быть выбрана только 1 ветвь. Поэтому мне нужно представить эти иерархические ограничения (2 часть). Возможно, лучше всего было бы представить все как проблему lp, но я не знаю, как представить дерево с ограничениями линейного программирования.
Я не знаю, могу ли я одновременно использовать задачу максимизации (1-я часть) и наложить ограничения CSP (а не использовать ограничения LP).
3 ответа
В Java существует множество решателей для проблем удовлетворения ограничений (CSP). Вот неполный список:
Тем не менее, я думаю, что использование решателя CSP в вашем случае является излишним, если у вас нет других ограничений, о которых вы не упомянули. Все, что вам нужно, это рассматривать вашу проблему как граф (дерево?) С узлами, соответствующими переменным. Затем, взяв листовой узел и пройдя весь путь до верха установки переменных по пути к true и установив все остальные переменные в false, вы получите решение. Все, что вам нужно для этого, это библиотека графов, такая как JGraphT
Choco - это решатель ограничений, который реализован на Java и предлагает Java API. Похоже, вы хотите использовать ограничения модели в вашей модели, то есть ограничения формы
reify(otherConstraint(...), variable)
где variable становится истинным или ложным в зависимости от того, otherConstraint доволен или нет. Вы можете смоделировать древовидную иерархию, введя вспомогательные переменные и добавив ограничения reification. Затем вы можете связать вспомогательные переменные с набором дополнительных ограничений для достижения таких эффектов, как вы описываете.
В качестве альтернативы вы можете использовать простые конъюнкции и дизъюнкции ограничений для моделирования дерева - будет ли это возможно, будет зависеть от других ограничений, которые определяют присваивания вашим переменным.
Drools Planner (с открытым исходным кодом, java) масштабируется за пределы традиционных реализаций CSP, а также более гибок в разработке оценки (нелинейные ограничения, веса и уровни нескольких оценок,...), но не распознает оптимальное решение, когда находит его,