Я искренне считаю, что вопросы по быстродействию имеют прямое отношение к переборным задачам, в том числе и к магическим квадратам и никак не могут быть
оффтопиком в данной теме. Поэтому и попробую высказать свои соображения по этому поводу, но, естественно, ни в коей мере не претендуя на "истину". Долгие века все вычисления проводились вручную и история оставила много поразительных, казалось бы невозможных, примеров. Зачем нужны вычисления в математике, к которой они практически не имеют отношения? На первом месте, конечно, стоит таинственность простейшей модели множества из бесконечного числа элементов - множества натуральных чисел. Все математические конструкции странным образом имеют свои прообразы в этом множестве. Часто эти конструкции описываются без привлечения понятия числа, например многие алгебраические конструкции, но это просто удобный способ описания.
На второе место я бы поставил аналогию "вычислений" с "экспериментом" у физиков. Это и проверка новых идей, это и источник новых идей. В основе человеческого мышления лежит
наблюдение. Только после накопления "базы наблюдений" наступает так называемое "вдохновение" и рождение "новых" (чаще всего только для автора) идей. Но ... очень важно помнить совет К.Пруткова: "Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою".
Простейший перебор представляет собой совокупность вложенных циклов по некоторым параметрам и объем этого перебора равен произведению
, где
- объем перебора
ого параметра. И, если ничего не предусмотрено для удаления "ненужных" веток, то при отсутствии "решения" весь этот объем машина пройдет. Поиск в расчете на "удачу" превращает его в "пустую забаву" и не представляет особого интереса (с точки зрения алгоритма перебора, но возможен и другой "интерес").
Но простейший он и есть простейший. Часто параметры и порождаемые ими веточки перебора устроены достаточно хитро, что и позволяет включать интересные проверки, резко сокращающие объем перебора. Исследование подобных проверок интересно само по себе и выходит далеко за пределы магических квадратов. При работе с квадратами мы сталкиваемся с понятием линейной зависимости параметров. Можно было бы проводить поиск по всем
параметрам, но это было бы очень печально. Сейчас мы стараемся подобные вещи исключить путем сокращения числа используемых параметров - фактически, путем исключения ненужных веток перебора. Часто используемый Наталией метод, когда она собирает квадраты из предварительно подготовленных специальных наборов, очень эффективен. Например, если существует всего 5 наборов из 6 чисел, которые дают данную магическую сумму, то дальше можно и не продолжать. А если таких наборов 14? Все подобные вещи ждут своего исследования и не стоит поддаваться искушению "быстрее найти", куда полезнее "смотреть на круги, ими образуемые".
Конкретика всегда интересна, в том числе и в реализации алгоритмов. "Черт прячется в деталях", вроде бы одинаковые алгоритмы, но одна реализация работает доли секунды, а другая часами. Конечно, это не одинаковые алгоритмы. Множество различных конкурсов по программированию хорошо это показывают. Так вот, частота процессора, избранный язык программирования с точки зрения скорости работы, хотя и имеют некоторое значение, но занимают самое последнее место. Грубо говоря, скорость линейно зависит от частоты - выигрыш может быть раза в 2, но никак не 10000. Язык, здесь важна конкретная реализация компилятора, но никак не сам язык. Пример с pb5 хорошо это показывает. Более того, современные машины играют с человеком злую шутку и, как уже многие заметили, могут привести к его деградации.
Ну вот, пока все. А Наталию прошу не обижаться, мы все ей признательны за ее неистовый интерес к магическим квадратам и отлично понимаем, что без нее эта ветка просто не существовала бы.
