Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY

Студент посылает домой закодированную телеграмму:

SEND

+MORE

________

MONEY

Задача состоит в нахождении 8 различных цифр, закодированных 8 бу­квами, использованными в телеграмме, так, чтобы получался арифметически правильный результат.

Заметим, что эта задача может быть записана с помощью модели цело­численного программирования (ЦП), но она содержит около сотни целочис­ленных переменных, причем эта модель ЦП трудна для решения с помощью классических подходов ЦП, таких, как алгоритмы ветвей и границ.

В то же время логический анализ задачи позволяет найти ее решение. Так, замечая, что ни Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №1 - открытая онлайн библиотека , ни Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №2 - открытая онлайн библиотека не могут быть нулями, получим: Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №3 - открытая онлайн библиотека . Далее, единственной возможностью для Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №2 - открытая онлайн библиотека является значение 1, т.е. Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №5 - открытая онлайн библиотека . Затем, из равенства Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №5 - открытая онлайн библиотека получаем, что Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №1 - открытая онлайн библиотека может быть равно только 9. Можно показать, что символу Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №8 - открытая онлайн библиотека соответствует цифра 0, т.е. Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №9 - открытая онлайн библиотека . Далее, пере­ходя к сотням, из Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №9 - открытая онлайн библиотека и условия, что Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №11 - открытая онлайн библиотека и Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №12 - открытая онлайн библиотека должны быть разичными, получим Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №13 - открытая онлайн библиотека . Продолжая аналогичным образом логический анализ ограничений, найдем решение задачи: Пример 10.6. Модель удовлетворения ограничений для задачи SEND MORE MONEY - №14 - открытая онлайн библиотека .

Основная сложность этой задачи состоит в необходимости учета огра­ничения «все цифры различны» (так называемое глобальное ограничение all-different).

Запишем ограничения задачи.