Здравствуйте!
Хочу услышать Ваше мнение по поводу решения задачи на замощение, а именно какими способами ее можно решать.
Постановка задачи. Дано клеточное поле размера nxn. В клетках записаны целые числа. Закройте поле костяшками домино (размер 2x1) таким образом, чтобы сумма произведений чисел внутри доминошек была максимальной (минимальной).
Например, есть поле 2x2:
+-+-+
|1|2|
+-+-+
|1|2|
+-+-+
Это поле можно замостить (разложить доминошки) двумя способами - положить их горизонтально или вертикально. В первом случае сумма будет 1*2+1*2=4, во втором (вертикально) 1*1+2*2=5.
Уже имеется несколько методов решения:
1) полный перебор
2) метод ветвей и границ
3) динамическое программирование

Какие методы решения можете предложить Вы?

На мой взгляд эта задача эквивалента задаче о покрытии при минимизации булевых функций методом карт Карно (или Карнау). Предлагаю построить булеву функцию - карта которой будет эквивалентна требуемому порытию. И мининимизировать ее методом Квайна, тогда, по моему, ядровые импликанты будут соответствовать доминошкам на карте. Однако не всегда существует одно минимальное расположение.

Интересно было бы доказательство вашей точки зрения увидеть.