2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение17.05.2012, 18:14 
Аватара пользователя


31/10/08
1244
Цитата:
Как и американцы, мы не делаем тупой полный перебор.
Есть алгоритмы построения различных типов магических квадратов, которые позволяют строить их довольно быстро.

То что перебор делается не просто, а с отсечением это и так понятно.
А вот алгоритм построения пока не видел. Может таки раскокаете? Пока что алгоритм svd и alex-black основаны на переборе всех вариантов.

Цитата:
Но массив чисел, из которых можно получить заданную магическую константу, в большинстве случаев содержит не 36 чисел, а гораздо больше. Вот тут и начинаются проблемы со временем.

Проблема не в этом, а в том что сложность задачи зависит экспоненциально. И все эти отсечения погоды не делают.

Я таки не понял, вы нашли магический квадрат с минимальным волшебным числом или нет?

 Профиль  
                  
 
 Re: Распараллеливание для многоядерных процессоров
Сообщение17.05.2012, 18:48 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavia в сообщении #572485 писал(а):
А вот алгоритм построения пока не видел. Может таки раскокаете? Пока что алгоритм svd и alex-black основаны на переборе всех вариантов.

Что вы имеете в виду под перебором всех вариантов?

Алгоритм построения очень хорошо описан в статье alexBlack.
Если вы не увидели там алгоритма, плохо смотрели, вероятно.

Алгоритм основан на двух "китах":
1) общая формула пандиагонального квадрата 6-го порядка, полученная путём решения системы линейных уравнений, описывающих пандиагональный квадрат, то есть все зависимости между его 36 элементами.
Эта формула приведена в самом начале указанной статьи.
2) зависимость между элементами пандиагонального квадрата 6-го порядка, найденная svb. Это отклонения от комплементарности. Подробно об этом опять же в теме "Магические квадраты" (где-то в районе стр. 125-127).

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

Цитата:
Я таки не понял, вы нашли магический квадрат с минимальным волшебным числом или нет?

Нет, пока не нашла.
Мне осталось проверить несколько потенциальных магических констант. После их проверки можно будет сказать, что для чисел вида 4(mod 9) проверка выполнена полностью (и минимальной останется константа 5100, если квадраты с меньшей константой не будут найдены). Однако, как я уже говорила, факт, что квадраты могут составляться только из чисел такого вида, строго не доказан.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group