Имеется квадрат 4 на 4. В нем стоят числа от 1 до 16. Берутся произведения четырех цифр в каждой строке и в каждом столбике и складываются. Какая минимальная сумма может быть сумма и при какой расстановке?
R-2: Если подробнее: Мы проводим серию испытаний. Каждое испытание начинается со случайной расстановки. Мы пытаемся ее улучшить поменяв какие-то два элемента местами. Т.е. считаем сумму, меняем элементы. Еще раз считаем сумму. Если нам невезет какое-то (большое) число раз подряд, то бросаем и переходим к другой начальной расстановке.
Мы заинтересованны перебирать варианты как можно быстрее. Т.е. мы должны научиться быстро считать суммы. Мы также можем считать не сумму всех произведений, а только тех которые изменяются при перестановке элементов. Еще точнее мы можем сосчитать (для наших двух меняемых местами элементов) сумму произведения оставшихся элементов в строке и произведения оставшихся элементов в столбце. Тогда большему элементу должна соответствовать меньшая из двух сумм. Если это не так, то перестановка этих двух элементов местами ведет к выигрышу.
Это самый дорогой (долгий) метод. Но он хорошо работает.
Второй метод заключается в сортировке сразу всех элементов в строке (или столбце.) Если мы сортируем элементы в строке, то произведения в строках не меняются, а меняются только произведения в столбцах. Мы можем опять сосчитать (массив) произведений оставшихся (кроме меняемой строки) элементов по столбцам. Дальше сортируем нашу строку так, чтобы большему произведению соответствовал меньший элемент (на встречу друг-другу.)
Это более дешевый метод но на нем одном далеко не уедешь. Когда он перестает работать приходиться продолжать методом обмена двух случайных элементов.
Еще один интересный метод заключается в перестановке всех элементов. Для каждого элемента мы считаем "минор." Т.е. сумму произведения оставшихся (кроме него самого) элементов в строке и произведения оставшихся элементов в столбце. И теперь сортируем элементы навстречу минорам. Да просто нумеруем все поля в порядке убывания миноров. Теперь наш квадрат просто не узнать. Но самое интересное, что это работает. Часто новый квадрат имеет меньшую сумму. (А потом циклится.)
Результаты получены путем комбинации методов два и три, и если ничего не помогает то применением метода один.