| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Решение задачи на замощение |
| Автор: Silent 21.6.2007, 12:57 |
| Здравствуйте! Хочу услышать Ваше мнение по поводу решения задачи на замощение, а именно какими способами ее можно решать. Постановка задачи. Дано клеточное поле размера nxn. В клетках записаны целые числа. Закройте поле костяшками домино (размер 2x1) таким образом, чтобы сумма произведений чисел внутри доминошек была максимальной (минимальной). Например, есть поле 2x2: +-+-+ |1|2| +-+-+ |1|2| +-+-+ Это поле можно замостить (разложить доминошки) двумя способами - положить их горизонтально или вертикально. В первом случае сумма будет 1*2+1*2=4, во втором (вертикально) 1*1+2*2=5. Уже имеется несколько методов решения: 1) полный перебор 2) метод ветвей и границ 3) динамическое программирование Какие методы решения можете предложить Вы? |
| Автор: IvanoffAndrey 27.6.2007, 06:07 |
| На мой взгляд эта задача эквивалента задаче о покрытии при минимизации булевых функций методом карт Карно (или Карнау). Предлагаю построить булеву функцию - карта которой будет эквивалентна требуемому порытию. И мининимизировать ее методом Квайна, тогда, по моему, ядровые импликанты будут соответствовать доминошкам на карте. Однако не всегда существует одно минимальное расположение. |
| Автор: esperant0 27.6.2007, 07:45 | ||
Интересно было бы доказательство вашей точки зрения увидеть. |