Имеется квадрат 4 на 4. В нем стоят числа от 1 до 16. Берутся произведения четырех цифр в каждой строке и в каждом столбике и складываются. Какая минимальная сумма может быть сумма и при какой расстановке?


+ -

Ответ

17112

Решение задачи

Ваши ответы на задачу

ответов: 17

R-2 2018-02-28 18:31:26 пишет:

16 2 15 36 29 17
19 23 26 4 31 6
34 8 33 35 1 27
13 30 11 5 18 22
9 32 3 28 25 14
7 24 20 12 21 10
sum = 101766462

R-2:
27 23 30 33 08 21 09
31 45 44 46 05 11 06
03 20 29 38 42 12 28
39 02 04 49 47 37 35
34 48 32 01 16 26 43
07 36 10 15 41 25 24
40 13 19 22 18 14 17
sum = 13040267712

не представился 2018-02-27 03:17:28 пишет:

Ну если по N, то 4 и 5 строка.

не представился 2018-02-27 03:08:57 пишет:

R-2, беру свою критику назад. Похоже Ваш метод имеет право на жизнь. Учитывая не слишком большое количество сочетаний из N^2 по 2 (даже для матрицы 10х10), и то что random все же выдает с некоторой вероятностью все варианты, то достаточно заложить многократно увеличенное количество циклов, с учетом количества сочетаний и вероятности random. По крайней мере, это намного эффективнее огромных затрат простого перебора.

R-2: Спасибо

не представился 2018-02-27 02:22:50 пишет:

ivana2000, конечно это не важно, но в 3 и 4 строках таблицы в порядках процентов ошибки.

R-2, ну опять же, вопрос в том, найдет ли кто-то (если кто-то захочет искать) результат меньше, или Ваш результат считать окончательным. Своеобразная неопределенность.

R-2: Третья строка вроде в порядке.

не представился 2018-02-27 00:14:48 пишет:

Ну, или употреблять последний столбец таблицы ivana2000. А интерес кого нибудь другого, улучшить результат, потратив в конечном случае бесконечно много времени.

не представился 2018-02-27 00:08:49 пишет:

Идея конечно интересная, но не более того. Вы же сами понимаете, что в ней все упирается в критерий количества отрицательных результатов после которого мы будем считать, что достигли минимума. И он стремится к бесконечности, так же, как и продолжает существовать ненулевая вероятность, что следующий swap даст положительный результат. Единственным железобетонным подходом является полный перебор, или знание дна и его достижения. Но даже теоретический ivana2000 результат для матрицы 5х5 (как и любой нечетной) не достижим и является только минимальным маркером. Поэтому в Вашем алгоритме, если не знаете ответа, Вы будете бесконечно ожидать вдруг опуститесь еще ниже. Для себя я понял, что эта тема бесперспективна.

ivana2000 2018-02-26 23:48:07 пишет:

Блеск!
Можно дополнить таблицу.

R-2 2018-02-26 23:19:02 пишет:

1 20 17 23 14
24 2 21 9 12
19 18 4 8 10
16 25 7 3 13
15 6 11 22 5
sum = 1091776

R-2 2018-02-26 20:35:40 пишет:

Есть еще одна идея. Расставлять числа случайным образом и проверять результат. Согласен что это долго и не надежно. Но алгоритм можно существенно улучшить, добавив случайный спуск. Выбираем два случайных места и меняем элементы местами. Если получилось хуже - отбрасываем. Если получилось лучше - продолжаем.

for(long i = 0; i != 2000; i++)
{
int s0 = sum(A);
int j = random.nextInt(N*N);
int k = random.nextInt(N*N);
swap(A, j, k);
int s1 = sum(A);
if(s1 < s0)
{
log(A);
log("sum = " + sum(A) );
log( "" + i );
continue;
}
swap(A, j, k);
}

Будет ли работать - это другой вопрос. Хотите верьте, хотите нет, но пока отлаживал получил искомый результат (для квадрата 4х4.)

Start.
1 9 12 15
5 3 10 13
7 2 16 6
8 4 11 14
sum = 47838
1 9 12 15
5 3 7 13
10 2 16 6
8 4 11 14
sum = 41613
0
...
10 6 5 7
15 8 9 2
1 12 16 11
14 4 3 13
sum = 17122
642
10 6 5 7
15 8 9 2
1 11 16 12
14 4 3 13
sum = 17112
681

R-2: Если подробнее: Мы проводим серию испытаний. Каждое испытание начинается со случайной расстановки. Мы пытаемся ее улучшить поменяв какие-то два элемента местами. Т.е. считаем сумму, меняем элементы. Еще раз считаем сумму. Если нам невезет какое-то (большое) число раз подряд, то бросаем и переходим к другой начальной расстановке.

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

Это самый дорогой (долгий) метод. Но он хорошо работает.

Второй метод заключается в сортировке сразу всех элементов в строке (или столбце.) Если мы сортируем элементы в строке, то произведения в строках не меняются, а меняются только произведения в столбцах. Мы можем опять сосчитать (массив) произведений оставшихся (кроме меняемой строки) элементов по столбцам. Дальше сортируем нашу строку так, чтобы большему произведению соответствовал меньший элемент (на встречу друг-другу.)

Это более дешевый метод но на нем одном далеко не уедешь. Когда он перестает работать приходиться продолжать методом обмена двух случайных элементов.

Еще один интересный метод заключается в перестановке всех элементов. Для каждого элемента мы считаем "минор." Т.е. сумму произведения оставшихся (кроме него самого) элементов в строке и произведения оставшихся элементов в столбце. И теперь сортируем элементы навстречу минорам. Да просто нумеруем все поля в порядке убывания миноров. Теперь наш квадрат просто не узнать. Но самое интересное, что это работает. Часто новый квадрат имеет меньшую сумму. (А потом циклится.)

Результаты получены путем комбинации методов два и три, и если ничего не помогает то применением метода один.

не представился 2018-02-26 05:54:26 пишет:

KoKos: ну почему сразу "сдул".
Просто, если бы я сразу написал таблицу в таком виде:

16 15 9 1
11 2 8 12
4 7 6 13
3 10 5 14

то Вы сразу бы догадались.
Вообщем логика оптимизации такова:
1. Упорядочиваем столбцы и строки (как и заметил R-2). Но, основная фишка в том, что в левый-верхний угол загоняем і1=16 и далее верхняя строка и левый столбец по убыванию по отношению к і1, т.е.
і2(15;6),
і3(14;2)<і2,
і4(13;1)<і3,
і5(14;3)<і2,
і6(15;1),
і7(15;1),
і8(15;1),
і9(13;2)<і5,
і10(15;1),
і11(15;1),
і12(15;1),
і13(12;2)<і9,
і14(15;1),
і15(15;1),
і16(15;1)

В скобках диапазон циклов.
Как видно, циклов 15, а не 16 ("выигрыш" 1/16). Из-за диапазонов тоже "экономим", например в самом внешнем цикле 5/15 и т.д.

Теперь почему с 16 и по убыванию:
2. Начиная с і4 вычисляем і1*і2*і3*і4 и сравниваем с имеющимся минимумом (сначала минимум делаем гарантировано большим, например 1000000). В і8 это будет і1*і2*і3*і4 + і5*і6*і7*і8. Если вычисленное значение больше имеющегося минимума, то делаем "Continue" цикла. Так как мы ищем минимум, то для бОльшей вероятности отсекания бОльших значений, самый внешний цикл лучше начинать с максимума и далее по убыванию. "Экономия" производительности просто огромная.

Вообщем, где то так:

count:= 0;
minSum:= 1000000;
i1:= 16;
timeBegin:= Now;
//for i1:= 1 to 16 do begin
for i2:= 15 downto 6 do begin
for i3:= 14 downto 2 do begin
if (i3 >= i2) then
Continue;
for i4:= 13 downto 1 do begin
if (i4 >= i3) then
Continue;
if ((i1*i2*i3*i4 + i1*6 + i2*6 + i3*6 + i4*6) >= minSum) then
Continue;
for i5:= 14 downto 3 do begin
if (i5 >= i2) or (i5 = i3) or (i5 = i4) then
Continue;
if ((i1*i2*i3*i4 + i5*6 + i1*i5*2 + i2*6 + i3*6 + i4*6) >= minSum) then
Continue;
for i6:= 15 downto 1 do begin
if (i6 = i2) or (i6 = i3) or (i6 = i4) or (i6 = i5) then
Continue;
if ((i1*i2*i3*i4 + i5*i6*2 + i1*i5*2 + i2*i6*2 + i3*6 + i4*6) >= minSum) then
Continue;
for i7:= 15 downto 1 do begin
if (i7 = i2) or (i7 = i3) or (i7 = i4) or (i7 = i5) or (i7 = i6) then
Continue;

......

end;
//end;

Итог выполнения:

69138 (16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1) (0:00:00);
68883 (16 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2) (0:00:00);
68823 (16 15 14 13 12 11 10 9 8 7 6 5 4 2 3 1) (0:00:00);
68313 (16 15 14 13 12 11 10 9 8 7 6 5 4 2 1 3) (0:00:00);
68253 (16 15 14 13 12 11 10 9 8 7 6 5 4 1 3 2) (0:00:00);

...

17146 (16 15 10 1 12 2 7 13 4 9 5 11 3 8 6 14) (0:01:54);
17146 (16 15 10 1 12 2 6 14 4 9 5 11 3 8 7 13) (0:01:54);
17141 (16 15 10 1 12 2 6 14 4 8 5 13 3 9 7 11) (0:01:54);
17136 (16 15 10 1 11 2 7 14 4 8 5 13 3 9 6 12) (0:01:54);
17134 (16 15 10 1 11 2 7 13 4 9 5 12 3 8 6 14) (0:01:54);
17122 (16 15 9 1 12 2 8 11 4 7 6 13 3 10 5 14) (0:02:05);
17120 (16 15 9 1 11 2 8 13 4 7 6 12 3 10 5 14) (0:02:06);
17112 (16 15 9 1 11 2 8 12 4 7 6 13 3 10 5 14) (0:02:06);
17112 (16 15) (0:03:16);
17112 (16 14) (0:05:03);
17112 (16 13) (0:06:34);
17112 (16 12 11 1 9 2 8 15 5 7 6 10 3 13 4 14) (0:06:40);
17112 (16 12) (0:07:45);
17112 (16 11) (0:08:35);
17112 (16 10) (0:09:06);
17112 (16 9) (0:09:22);
17112 (16 8) (0:09:29);
17112 (16 7) (0:09:31);
17112 (16 6) (0:09:32);
minSum = 17112
cycle = 440478935

в скобках время (как видите у меня получилось 9 с половиной минут). cycle - количество выполнения самого внутреннего цикла (там где сравниваем с минимумом и, если меньше или равно, то обновляем минимум и выводим результат. Это общее количество, не зависимо от результатов сравнения.

На счет 5х5, естественно, ни только логикой оптимизации, ни тупым перебором, найти нереально. Но можно попробовать, после очевидной (подобной вышеописанному) оптимизации, ручной оптимизацией диапазонов циклов и частичным программным перебором, постепенно максимально близко достичь "цели", указанной ivana2000. Но это, естественно не будет корректным решением (если конечно не найти именно 1091765), да и не сильно охота тратить время.

KoKos 2018-02-26 01:13:55 пишет:

:) Ну, вообще-то, если мне не изменяет память, моя программа была накорябана в визуальном васике от экселя, - так что на выборе нормального языка и оптимизации там наигрывается не один порядок, а добрых три-четыре. :))) Но признаю, Вы поколебали мою уверенность.

Что ж, есть ещё один очевидный способ, подходящий под наши симптомы - сдул откуда-то. 8)))

R-2 2018-02-25 20:06:01 пишет:

Ну хорошо, давайте "сложным" перебором. Мы можем переставлять строки и столбцы в любом порядке. Первое, загоняем единицу в левый-верхний угол. Упорядочиваем столбцы так чтобы в верхней строке числа шли по возрастанию. Упорядочиваем строки так чтобы в первом столбце числа шли по возрастанию. Мы избавились от неопределенности в записи квадратов. Теперь наша программа считает в 24*24 раз быстрее. Т.е. работает 1 год.
Еще есть отражение вокруг главной диагонали. Выигрыш еще в два раза, но не очень понятно как сделать. Еще можем наиграть порядок на выборе языка программирования. И еще 8 раз на распараллеливании вычислений по ядрам/процессорам. Итого, программа будет считать пару дней, что, в принципе, реально. Но 5 на 5 ...

R-2 2018-02-24 19:21:20 пишет:

Я предложил эту задачу именно потому, что она "простым" перебором не решается. Для квадрата 4х4 надо перебрать 16! вариантов. Это в 60М раз больше чем 9! для квадрата 3х3. Т.е. Ваша программа (5 минут для 3х3) будет считать 500 лет.

KoKos 2018-02-24 14:18:48 пишет:

:)) Ну, судя по тому, что решение было быстрым, без каких-либо пояснений, и сразу в двух вариантах - то простым перебором.

R-2 2018-02-24 06:07:31 пишет:

ivana2000, Извини - для квадрата 5х5 не могу. Честно говоря, я даже не представляю как "не представился" решил задачу для квадрата 4х4.

ivana2000 2018-02-24 02:33:18 пишет:

Решил составить таблицу.
N – размерность квадрата
M₀ – расчетное значение минимума суммы
M – реальное значение минимума
δ = |M–M₀|/M – относительная погрешность

Может кто-нибудь найдет M для N=5? Было бы интересно сравнить.

не представился 2018-02-21 20:22:41 пишет:

17112

1 9 15 16
12 8 2 11
13 6 7 4
14 5 10 3

или

1 10 14 15
11 6 4 8
12 7 13 2
16 5 3 9

R-2:

Добавьте комментарий:

© 2009-201x Логические задачи