2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 45, 46, 47, 48, 49, 50, 51 ... 67  След.
 
 Re: Prime Sums
Сообщение20.12.2012, 10:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #660992 писал(а):
Получется схем 1798 больше тысячи, распределений чисел по группам 14, наборов простых чисел для каждой схемы разное, но в среднем штук 20. 1000*14*20 примерно 200 000. Только начальная подготовка займет дня два-три. Сколько будет работать основной алгоритм, посчитать на пальцах невозможно.

Ну, в таком случае проще отказаться вообще от поиска решений.
Логично :D

Цитата:
1000*14*20 примерно 200 000

Это уже примерно 280 000 :-)

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


21/02/10
1594
Екатеринбург
whitefox в сообщении #660991 писал(а):
На выходе получил все канонические схемы с оценкой не выше 1816.


Искал схемы с оценкой до 1810 (максимум 3090). Как то сразу решил не размениваться на промежуточные результаты, а искать только рекорды. К тому же алгоритмы поиска по заданным схемам принимают искомую сумму в качестве входных данных.

 Профиль  
                  
 
 Re: Prime Sums
Сообщение20.12.2012, 11:38 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Pavlovsky в сообщении #660992 писал(а):
Единственоое отличие. Я перебор делал с ограничениями:
1) Количество линий каждого типа примерно одинаково. То есть для N=7 равно 3 или 4. Реализовать это ограничение при переборе не трудно.
2) Есть хотя бы одна ячейка, где пересекаются 4 линии.

Эти ограничения я добавил во второй версии программы, когда проверял Ваши результаты. Для схем с оценкой меньше 1806 эта версия выдала результаты аналогичные результатам первой версии.

-- 20 дек 2012, 12:46 --

Pavlovsky в сообщении #660992 писал(а):
То есть перебираю схемы, где всегда есть линии 1,5,8,22

Может Вы имели ввиду 1,8,15,22 ?

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #660948 писал(а):
Ну, вот и разберитесь, кто напутал, а то сразу и заняться нечем


Не, не буду искать косяк в программе. Подумаешь потерял пару десятков неизоморфных схем. Того что есть вполне достаточно.
Я лучше пошлифую свой основной алгоритм. После последних улучшений он стал работать заметно шустрее. В качестве теста подсунул задачу поиска решений 1802. Уже нашел около десятка различных решений.

-- Чт дек 20, 2012 13:50:04 --

whitefox в сообщении #661001 писал(а):
Может Вы имели ввиду 1,8,15,22


Блин конечно да. Это была учебная ошибка, проверка на понимание. :D

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #661002 писал(а):
Подумаешь потерял пару десятков неизоморфных схем.

Ну, да, если ещё потерянные схемы добавить, то и в 200 000 не уложитесь :D

Цитата:
Того что есть вполне достаточно.

Достаточно для чего?

Цитата:
Я лучше пошлифую свой основной алгоритм. После последних улучшений он стал работать заметно шустрее. В качестве теста подсунул задачу поиска решений 1802. Уже нашел около десятка различных решений.

Пора уже выдавать рекорды :-)

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #661007 писал(а):
Пора уже выдавать рекорды


На моем домашнем компьютере 4 ядра. Три копии программы ищут рекорды. Перспективы нахождения рекорда близки к нулю.

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


22/03/08

7154
Саратов
У меня 2 ядра. Одновременно работают 4 программы. При этом свободно пишу сюда, пишу письма. Вот только кино смотреть уже нельзя :-)
Так что вам надо запускть не 3 копии, а по крайней мере 7 копий. Попробуйте.
Мой компьютер вполне тянет. А программы-то, похоже, не сильно отличаются.
Сейчас вот уже почти 7 часов крутится поиск решений 1800 и 3098 (отдельно две копии программы). Конечно, я не жду полных решений, но полуфабрикатов много, в том числе с 12 выставленными зачётными линиями. Насчёт 13 пока не знаю, может есть, а может нет. Скорее всего, нет.
С 14 линиями, наверное, есть, но опять не из той оперы :D

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #660038 писал(а):
Готовое решение с 12 выставленными зачётными линиями могу показать, если никто не возражает
Выставленные зачётные линии имеют значения:


Код:
233,239,227,251,229,197,241,211,193,191,223,199

Не выставленные зачётные линии имеют значения 232 и 236.


232+236=468

Код:
79,389
89,379
101,367
109,359
131,337
137,331
151,317
157,311

В этих парах одно число слишком маленькое другое слишком большое.

Код:
191,277
197,271
199,269
211,257
227,241
229,239

В этих парах присутствут уже использованные числа

-- Чт дек 20, 2012 16:34:17 --

Когда выбрана схема и задано распределение чисел по группам, легко посчитать минимально (максимально) возможную сумму которую можно выставить в зачетных линиях. Для маленьких N (в т.ч. для N=7) эти пределы существенно сокращают количество допустимых наборов простых чисел.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #661073 писал(а):
...
В этих парах одно число слишком маленькое другое слишком большое.
...
В этих парах присутствут уже использованные числа

Так вот поэтому полное решение и не получилось.
Я понимаю, что тут плохое разложение Q на 14 простых.
Увы, я не могу сама изменить программу whitefox. На мой взгляд главная беда его очень хорошей программы - это то, что он не привязал поиск к конкретному разложению Q на простые числа.
Поэтому программа и ищет всё, кроме того, что нужно :-(

Через пару часов прерву программы поиска решений 1800 и 3098. Буду их просматривать (в программе Эда просматриваю), хорошие полуфабрикаты выложу.

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


22/03/08

7154
Саратов
За 11 часов работы программа поиска решения с Q=3098 нашла 39 приближений к решению.
Загоняю все эти решения в программу проверки решений, получаю вот такие результаты:

(Оффтоп)

Код:
2910
0
0
2898
0
2892
2900
2910
0
0
0
0
0
2880
0
0
0
0
2892
2910
2922
0
2898
0
2898
0
2902
0
2880
0
0
0
2898
2892
0
2904
0
3018
0

Где нули, в этих решениях количество выставленных зачётных линий меньше или больше 14; а где их ровно 14, получены готовые решения.
Аналогично программа поиска решений с Q=1800 за те же 11 часов работы нашла 38 приближений к решению. При проверке сумм в этих квадратах примерно такая же картина, только результаты поменьше.

Сейчас собираюсь просмотреть все эти решения.

-- Пт дек 21, 2012 12:39:05 --

Просмотрела 39 квадратов.
Нашла интересные приближения к решению с Q=3098.

1. 18 выставленный зачётных линий, 17 различных; выставлены все столбцы:

Код:
29,19,13,24,1,15,45,
28,17,18,8,2,6,46,
48,49,11,42,27,21,31,
36,43,25,37,44,10,38,
5,7,26,40,3,20,16,
4,23,12,34,22,9,33,
47,35,14,41,39,30,32

2. выставлено 12 зачётных линий:

Код:
23,18,4,21,3,11,44,
24,16,29,13,1,14,38,
48,47,7,39,27,34,26,
36,43,32,40,45,15,46,
5,6,30,41,2,28,17,
8,19,10,22,20,12,31,
49,42,9,35,37,33,25

3. выставлены 13 зачётных линий :!:

Изображение

Значение 14-ой зачётной линии равно 207.
Такое вот близкое приближение к решению, всего одна зачётная линия немножко неправильная. Так, может, решение Q=3098 существует :?:

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


22/03/08

7154
Саратов
Для Q=1800 нашла два интересных приближения.

1. выставлено 12 зачётных линий:

Код:
3,21,19,4,33,8,9,
24,18,6,28,16,12,23,
30,46,32,11,36,22,37,
29,48,44,14,35,39,17,
31,40,41,47,34,15,20,
7,10,38,26,25,1,2,
13,49,45,27,43,42,5

2. выставлены все 14 зачётных линий, но... две одинаковые:

Изображение

Почти готовое решение :-) Ну, чуточку не так.

Сегодня у меня программа ищет решения для Q=3096 и Q=3094.
Кстати, не мешало бы собрать все готовые решения, выдаваемые программой - для базы данных всех решений.
dimkadimon уже начал эту работу.
У меня тоже есть очень много решений, можно все прогнать через программу проверки решений, посмотреть все результаты.

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


22/03/08

7154
Саратов
Рассмотрела "почти решение" Q=1800 более подробно.
Очень красивое получилось решение. Прямо обидно, что две зачётные линии приняли одинаковое значение.

Изображение

Структура решения: 2,16,13,16,2 - симметричная.
Схему писать не буду, её легко восстановить по решению.
Разбиение:

$M_0=(48,49)

M_1=(32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47)

M_2=(19,20,21,22,23,24,25,26,27,28,29,30,31)

M_3=(2,3,5,6,7,8,9,10,11,12,13,14,15,16,17,18)

M_4=(1,4)$
Перестановкой всего двух чисел в двух весовых классах легко получить разбиения с близкими оценками Q=1798 и Q=1802.

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


21/02/10
1594
Екатеринбург
Как всегда, под конец конкурса в голову полезли супер идеи. Но уже нет времени их реализовывать. Да и негде их применять. Все места где были хорошие шансы найти рекорд, проверил. А молотить пустую породу нет стимула.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #661390 писал(а):
Все места где были хорошие шансы найти рекорд, проверил.

Этого не может быть.
Мест таких очень и очень много. Не вы ли писали о 200 000?
Никто не доказал, что для "семёрки" невозможно найти улучшения.
Во всяком случае, я такого доказательства не видела.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #661393 писал(а):
Не вы ли писали о 200 000

Сегодня вечером запущу проверку. Но это все порожняк. Больше 9 выставленных линий не видел.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 45, 46, 47, 48, 49, 50, 51 ... 67  След.

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



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

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


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

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