2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 67  След.
 
 Re: Prime Sums
Сообщение07.01.2013, 11:53 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Например, структура 2,14,8,6,6, оценка Q=1760 (при естественном разбиении).
Схема:

Код:
0 2 0 3 0 3
3 1 3 2 3 2
0 2 0 3 0 3
3 1 3 2 3 2
1 3 1 4 1 4
3 1 3 2 3 2

Не даёт решения 1760?

Я использовала эту схему при поиске решения 1758, но разбиение было не естественное, точнее: разбиений мне whitefox прислал 14 штук. Попробовала первое разбиение, мимо. Тогда взяла и попробовала сразу 14-ое :D И тут улыбнулась удача.

-- Пн янв 07, 2013 12:58:05 --

Pavlovsky в сообщении #668307 писал(а):
Nataly-Mak в сообщении #668299 писал(а):
А кто-нибудь доказал, что результат 1758 для N=6 неулучшаем


Пробовал немного. Выставлялось максимум половина линий. Поэтому быстро бросил эту затею.

Жаль, что бросили. Вот самые интересные моменты у нас остаются за бортом. Это плохо.

У меня программа полного перебора для "шестёрки" работает не так скоро, как у svb ("минуты-секунды"). Однако всё же работает; у меня наоборот: в случае отсутствия решения программа работает долго, а в случае его наличия находит за пару минут :-)

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:00 
Аватара пользователя


20/01/10
765
Нижний Новгород
Pavlovsky
Цитата:
Пробовал немного. Выставлялось максимум половина линий. Поэтому быстро бросил эту затею.
Запустил сейчас проверку случайной схемы 887 для поиска 1760. Через несколько секунд найдено 11 простых линий.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:02 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb
надо действовать прицельно! Не случайные схемы, а методично и последовательно всё исследовать.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:07 
Аватара пользователя


20/01/10
765
Нижний Новгород
Nataly-Mak
Цитата:
надо действовать прицельно! Не случайные схемы, а методично и последовательно всё исследовать.
В том то и дело. Даже 1758 я получаю с трудом - как повезет :-)
А тут кроме схемы еще накладывается выбор распределения, которых запредельное число :-(

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:11 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #668317 писал(а):
Через несколько секунд найдено 11 простых линий.


Вот недостаток вашей эвристики, с сортировкой линий. Вы играете в поддавки. :D Лихо находите 11 линий, а на 12-й полный затык. Хотя простая проверка на ранних стадиях перебора, могла показать, что 12 линию выставить уже невозможно.

Цитата:
Выставлялось максимум половина линий


Это не потому что мой алгоритм не может выставить 11 линий. Просто он бросает перебор, когда видит что дальше смотреть бесполезно.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:15 
Аватара пользователя


20/01/10
765
Нижний Новгород
Pavlovsky
Цитата:
Хотя простая проверка на ранних стадиях перебора, могла показать, что 12 линию выставить уже невозможно.
Так то оно так, но зато у меня нет ограничения по выбору простых чисел :-)
А вот, что проверять, пока не вижу.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:17 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb в сообщении #668321 писал(а):
Nataly-Mak
Цитата:
надо действовать прицельно! Не случайные схемы, а методично и последовательно всё исследовать.
В том то и дело. Даже 1758 я получаю с трудом - как повезет :-)
А тут кроме схемы еще накладывается выбор распределения, которых запредельное число :-(

Тогда я ничего не понимаю.
Вы пишете, что при конкретно выбранной схеме-разбиении у вас программа полного перебора для "шестёрки" работает "минуты-секунды".
Так в чём проблемы?
Здесь выкладывали все уникальные схемы для "шестёрки", или, по крайней мере, большинство. И разбиений совсем не запредельное число! Если брать схемы, скажем, точно с оценкой Q=1760, то для каждой уникальной схемы разбиение всего одно.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:23 
Аватара пользователя


20/01/10
765
Нижний Новгород
Nataly-Mak
Цитата:
Если брать схемы, скажем, точно с оценкой Q=1760, то для каждой уникальной схемы разбиение всего одно.
Но я беру схему с оценкой 887(1777) и количество разбиений получается запредельным, и для каждого распределения имеется 11 простых линий.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:23 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #668326 писал(а):
но зато у меня нет ограничения по выбору простых чисел


А кто мешает сформировать все допустимые наборы простых чисел? Если использовать изощренные способы проверки допустимости, то для N=6,7 их будет очень немного.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb в сообщении #668331 писал(а):
Nataly-Mak
Цитата:
Если брать схемы, скажем, точно с оценкой Q=1760, то для каждой уникальной схемы разбиение всего одно.
Но я беру схему с оценкой 887(1777) и количество разбиений получается запредельным, и для каждого распределения имеется 11 простых линий.

А почему надо брать только схему с оценкой 887/1777? Что мешает рассмтривать схемы с другими оценками? Ведь при этом количество разбиений перестаёт быть запредельным.

Вот по поводу приведённой мной чуть выше структуры 2,14,8,6,6 с оценкой Q=1760 очень интересная информация из письма whitefox:

Цитата:
Последние два решения получены по различным, но изоморфным схемам:

0,2,0,3,0,3
3,1,3,2,3,2
0,2,0,3,0,3
3,1,3,2,3,2
1,3,1,4,1,4
3,1,3,2,3,2

0,2,0,3,0,3
3,1,3,2,3,2
1,3,1,4,1,4
3,1,3,2,3,2
0,2,0,3,0,3
3,1,3,2,3,2

со структурой 2,14,8,6,6 и с максимальной оценкой 1760.

С точностью до изоморфизма существует только одна схема со структурой
2,14,8,6,6 и только одна двойственная ей схема со структурой 6,6,8,14,2.
Этими двумя классами изоморфных схем исчерпываются все схемы с
максимальной оценкой 1760.

Для структуры 2,14,8,6,6 существует только 14 разбиений с оценкой 1758,
аналогично и для структуры 6,6,8,14,2.
Вот эти разбиения:

для 2,14,8,6,6

(Оффтоп)

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

для 6,6,8,14,2

(Оффтоп)

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

Именно этими разбиениями я и воспользовалась при нахождении решения 1758.
А если искать решение 1760, то разбиение будет для каждой схемы всего одно - естественное.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:37 
Аватара пользователя


21/02/10
1594
Екатеринбург
N=6 четное. Там есть еще дополнительное условие на наборы простых чисел! Наборов простых чисел получается совсем немного. Для четных N у меня программа выдает наборы простых чисел разбитые на три группы. Отдельно простые числа для прямых диагоналей, обратных диагоналей и остальное для строк и колонок. Что сильно сокращает перебор при работе основоного алгоритма.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:52 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вот оно - решение 1758 с приведённой выше структурой 2,14,8,6,6 и с 14-ым разбиением из приведённой цитаты whitefox (схема первая в цитате):

Изображение

Я не проверяла другие разбиения; как только нашла решение, сразу перешла к другим задачам.

whitefox писал здесь, что если бы не удалось найти решение 1758 по схемам с оценкой 1760, пришлось бы искать его по схемам с максимальной оценкой 1768, и тогда разбиений было бы намного больше.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 12:53 
Аватара пользователя


20/01/10
765
Нижний Новгород
Pavlovsky
Цитата:
А кто мешает сформировать все допустимые наборы простых чисел?
Пробовал использовать конкретный набор простых чисел - незаметное ускорение работы, а может и замедление. Любые дополнительные проверки замедляют перебор - нужно серьезное отсечение вариантов на ранней стадии. Вот его я не вижу, а оно должно быть. Либо ... думать надо :D

Nataly-Mak
Чем дальше оценка схемы лежит от искомого результата, тем больше шансов найти решение - это почти экспериментальный факт.

Pavlovsky
Цитата:
N=6 четное. Там есть еще дополнительное условие на наборы простых чисел! Наборов простых чисел получается совсем немного. Для четных N у меня программа выдает наборы простых чисел разбитые на три группы. Отдельно простые числа для прямых диагоналей, обратных диагоналей и остальное для строк и колонок. Что сильно сокращает перебор при работе основоного алгоритма.
Не очень понятно, но, похоже, в этом что-то есть. Простое сокращение простых чисел мне ничего не даст, но вот, если на каком-то шаге перебора знать, что уже найденные простые не вписываются в предварительно определенные наборы, то ... была такая мысль, но так и осталась нереализованной :-(

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 13:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
svb в сообщении #668348 писал(а):
Чем дальше оценка схемы лежит от искомого результата, тем больше шансов найти решение - это почти экспериментальный факт.

Стоп! Если я не ошибаюсь, Pavlovsky говорил прямо противоположное :-)

-- Пн янв 07, 2013 14:07:10 --

Вот здесь смотрим:

Pavlovsky в сообщении #663398 писал(а):
Но я бы поработал над выбором схемы. Схема 2,14,8,6,6 имеет теоретическую оценку 1760. Что далековато от 1752. Надо поискать схему теоретическая оценка которой близка к 1752. Увы мои алгоритмы поиска схем заточены на поиск схем близких к оптимальной. Схемы с теоретической оценкой рядом с 1752 искать отказываются.

Кстати, Vovka17 обещал выложить решение 1752. Мне очень интересно, какая в этом решении схема.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение07.01.2013, 13:07 
Аватара пользователя


21/02/10
1594
Екатеринбург
Для четных N
Цитата:
Зачетных прямых диагоналей должно быть N/2, зачетных обратных диагоналей тоже должно быть N/2. Если квадрат раскрасить в черно-белые цвета, как шахматную доску. То зачетные диагонали должны быть одноцветными (либо черными, либо белыми). Отсюда сумма зачетных прямых диагоналей должна равняться сумме зачетных обратных диагоналей.


Если схема у вас удовлетворяет этому условию, а это должно быть так. Тогда ищем наборы простых чисел отдельно для прямых диагоналей, отдельно для обратных диагоналей. Суммы простых чисел для этих типов линий должны быть равны. И остальные простые числа для строк и колонок.

-- Пн янв 07, 2013 15:15:41 --

Nataly-Mak в сообщении #668335 писал(а):
С точностью до изоморфизма существует только одна схема со структурой
2,14,8,6,6 и только одна двойственная ей схема со структурой 6,6,8,14,2.
Этими двумя классами изоморфных схем исчерпываются все схемы с
максимальной оценкой 1760.

Если по этим схемам искать решение 1760. Для схемы со структурой 2,14,8,6,6 нет допустимых наборов простых чисел. Для схемы со структурой 6,6,8,14,2 существует 4 допустимых набора простых чисел. Основной алгоритм максимум чего выжал это 6 выставленных линий.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 67  След.

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



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

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


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

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