2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение18.04.2012, 07:59 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Предлагаю вниманию форумчан небольшую статью о конкурсе:
http://www.natalimak1.narod.ru/contest4.doc

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение19.04.2012, 08:34 
Аватара пользователя


17/05/08
358
Анк-Морпорк
11е место - поздравляю!!!

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение19.04.2012, 08:39 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Спасибо!

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение19.04.2012, 11:25 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Короткий экскурс в историю конкурсов, в которых я приняла участие
http://www.natalimak1.narod.ru/contests.htm

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение20.04.2012, 06:03 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Объявили, что следующий конкурс начнётся 1 июня сего года.
Ну, почти полтора месяца отдыха :-)

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.04.2012, 11:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky улучшил рекорд конкурса в игре № 16, на конкурсе был получен максимальный результат 3118, он получил 3125:

Код:
16:C0, M2, L1, N0, J0, M0, N3, E12, F13, G5, K4, J3, K1, N5, L3, L0, I4, G9, K11, M7, M9, I5, F11, I9, L8, I9, J10, M10, N0, L2, N10, N10, N10, J11, H7, N9, N9, M1, N3, M3, M5, N6, L5, N5, N5, M5, M0

Пока этот рекорд не побит (браво, Pavlovsky!).

Я попыталась улучшить результат 3125 по своей программе. Покрутила. Интересно, что вариантов решений с результатом 3125 получается куча, например:

Код:
16:B0,M2,L1,M1,J0,L0,M3,E12,E13,F5,K4,J3,K1,M5,I4,I2,I4,E11,J11,L7,M9,I5,F11,H11,L8,I9,J10,M10,E7,J11,L10,N10,N10,J11,N9,N9,K2,J9,K6,N7,L6,M6,M6,N3,M3,M5,M0

Этот вариант существенно отличается от оригинального решения последовательностью ходов. Вот до этой позиции всё совпадает:

Изображение

А теперь в решении Pavlovsky удаляется синий блок, то есть делается ход N0, а в моём решении делается ход E7, и только потом удаляется синий блок. Далеко не всегда такое нарушение последовательности ходов не изменяет результат, в этом случае результат сохранился.

А вот перепрыгнуть этот результат не удаётся.

Второй интересный момент: от этого решения легко получается и результат 3118 (предыдущий рекорд), например:

Код:
16:B0,M2,L1,M1,J0,L0,M3,E12,E13,F5,K4,J3,K1,M5,I4,I2,I4,E11,J11,L7,M9,I5,F11,H11,L8,I9,J10,M10,E7,F2,I3,J11,L10,N10,N10,J11,N9,N9,J9,K6,N7,L6,M6,M6,N3,M3,M5,M0

Наконец, последний интересный момент: мне не удаётся получить результат между этими двумя рекордами, то есть такой результат x:
3118 < x < 3125.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 09:31 
Аватара пользователя


21/02/10
1594
Екатеринбург
До следующего конкурса более месяца. Можно неспешно поколдовать над рекордами предыдущего конкурса. Анализирую задание №12. Для анализа взял два лучших решения.

wes,"12","12:H4,L5,J10,H13,J4,J12,N10,B8,F5,F8,G6,K8,M9,L9,L4,I11,M8,M8,G2,D1,F0,E11,E2,K13,M8,J3,J0,J4,M9,L3,N8,M0,N1,N1,M1,M0,N0","5139"
spurious,"12","12:G1,I3,H3,K7,F0,E1,J9,F2,H12,J11,M10,F6,A8,I4,L3,F7,K7,M8,L8,I10,L8,E11,L8,M8,I4,K2,J12,F9,N0,M8,M3,J10,M0,N0,N2,N0,K1,M0,M1","5127"

Поменял в них порядок ходов, чтобы выявить одинаковые последователности ходов.

i12,j11,j9,g1,f0,f1,h3,l5,b8,f7,j4,f5,g6,k7,j8,n10,k8,k8,l8,n7,i9,e10,k12,l3,e1,j2,j0,m8,j4,l2,n8,m0,n1,n1,k1,m0,m1
i12,j11,j9,g1,f0,f1,j2,h3,l5,b8,f7,g2,g6,k7,j8,n10,k8,k8,l8,n7,i9,e10,k12,j4,l3,i4,k2,j0,m9,m4,n0,j10,n4,n0,n0,n0,k1,m0,m1

Видно, что решения очень похожи. Полностью совпадают первые 6 ходов и 3 последних хода. И в середине есть огромные совпадающие куски. Но мне надо чтобы все отличия были вынесены в единый непрерывный кусок последовательности ходов. Пока у меня полчился кусок, состоящий из 28 ходов (начинается с хода 7). Увы это слишком много, мой переборный алгоритм (К-оптимизация) максимум может обсчитать последовательность из 20-ти ходов.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 10:35 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Вы можете оптимизировать вашей К-оптимизацией последние 20 ходов?

Потом я попробую эти ваши варианты обрабатывать по своей программе полного перебора окончаний.
Для моей программы важно изменение последовательности последних n ходов.

Но, конечно, К-оптимизация не должна давать решения с более низким результатом, теряется смысл, как мне кажется.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 11:01 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #562922 писал(а):
Вы можете оптимизировать вашей К-оптимизацией последние 20 ходов?


Смысл К-оптимизации в том, что я могу оптимизировать любую последовательность ходов. Совсем не обзательно последние 20 ходов.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 11:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Это я поняла, что вы можете любую последовательность ходов оптимизировать.
Но мне важно, чтобы это была последовательность последних n ходов, потому что моя программа полного перебора окончаний работает именно с "хвостом" решения, начало решения она не трогает совсем, и ей безразлично, что там будет.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 13:41 
Аватара пользователя


21/02/10
1594
Екатеринбург
К-оптимизация позволяет изменять порядок ходов в большом диапозоне. При этом не ухудшает оценку решения по сравнению с исходным.
Пример:
Это рекордное решение для задания №13.
J11, C10, F10, K3, L11, F2, I14, M15, G19, L7, M4, F18, D19, B0, L20, L2, F14, D18, K1, N8, D13, G15, D12, L9, I2, D0, D6, K10, I12, G16, K0, I1, L13, I17, L16, K7, M13, H10, G0, L14, N1, N14, L4, L0, N1, N1, N4, N0, N0, N0

А вот примеры решений после обработки К-оптимизацией.
g19,f19,m20,g18,e18,m15,j14,f14,h15,h16,e13,j11,d10,f10,e12,m11,j9,l7,n8,k10,i12,m13,i17,n16,n13,i10,e6,k7,k3,f2,n4,l2,k1,j2,c0,e0,l0,i1,g0,l14,n15,n1,l4,l0,n6,n1,n1,n0,n0,n0

c0,k3,f2,n4,l2,k1,e0,l0,j2,i1,e6,l7,n8,f10,k7,m9,e10,h10,j11,m11,e13,e12,k10,i12,j14,m15,f14,g18,g19,f19,m20,e18,h15,m13,n13,m16,n16,i16,g0,n1,m4,m13,n14,l0,n1,n1,n0,n0,n3,n0

g19,f19,c0,m20,g18,e18,k3,f2,m15,n4,l2,k1,e0,l0,j2,j14,f14,h15,h16,i1,e13,e6,l7,j11,d10,f10,e12,m11,n8,m9,k10,i12,l13,i17,l16,n13,k7,h10,g0,n1,m13,m4,n14,l0,n1,n1,n0,n0,n3,n0

Все решения имеют рекордную оценку 9842. Специфика К-оптимизации такова, что она с трудом улучшает (или хотя бы изменяет большие группы). Поэтому после 38 хода, перед удалением большой группы, позиции получились одинаковыми. Но если смотреть позиции до 38 хода, то они очень сильно отличаются. А значит можно для каждого решения применять перебор хвостика.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 15:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
Но если смотреть позиции до 38 хода, то они очень сильно отличаются. А значит можно для каждого решения применять перебор хвостика.

Нет, вот как раз перебор "хвостика" здесь ничего не даёт!
После удаления красного блока во всех трёх решениях позиции делаются совершенно одинаковые, вот такие:

Изображение

И что же здесь теперь перебирать? Для всех трёх ваших вариантов полный перебор этого "хвостика" моментально выдаёт тот же самый результат - 9842.

А уровни до удаления красного блока моя программа не берёт (слишком много вариантов первого хода).

Мне нужно, чтобы "хвостики" (после удаления красного блока) сильно отличались, а не то, что перед "хвостиками"!
Понятно, что для одиниковых "хвостиков" и результаты будут одинаковые.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 15:16 
Аватара пользователя


21/02/10
1594
Екатеринбург
От удаления большой красной группы до конца, всего 12 ходов. Неужели ваш перебор не может считать на большую глубину?!

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение23.04.2012, 15:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ага, а ход назад сделайте и вариантов первого хода становится 18
[а ещё ход назад - и вариантов первого хода 21]!

Всё, от такого уровня полный перебор за реальное время сделать невозможно. Не говоря уже о следующих (более глубоких уровнях).
А вот 12 вариантов первого хода в данном случае перебирается за 1 сек.

На бОльшую глубину у меня работает программа случайного перебора, но это длительный процесс тоже: выбираю разные уровни, ищу оптимальный, делаю случайный перебор, потом дорабатываю полученное решение программой полного перебора.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение26.04.2012, 05:42 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Спросила на форуме конкурса, можно ли ввести вариант решения головоломки № 16 с максимальным результатом. Ничего не ответили. Смотрю, другие вводят варианты максимальных решений, ну и я сейчас ввела. Этот вариант здесь приведён, он существенно отличается от оригинального решения (автор Pavlovsky) последовательностью ходов.

Стало любопытно провести эксперимент.
Беру из БД конкурса решение А. Чернова в игре № 22:

Alex Chernov,"22","22:
G3,J6,N6,I12,C2,L4,N4,F3,C13,L6,L7,M6,P9,K4,O10,P9,K9,M9,O10,O10,O8,P10,E12,L9,M0,P3,
P13,L13,F2,L12,L13,M14,M10,H0,G1,I8,K12,O0,L8,M0,J2,I11,J3,K10,J1,N0,M0,L9,O1,M8,P3,
P2,M9,N0,P1,M5,M2,N7,P1,O6,O0,P0,P5,O4,P4,N5,P4,O3,P3,P3,O2,P2,P3,P2,P0,
"3295"

У меня в этой игре результат 2565, максимальный результат на конкурсе 3815.

Выбираю исходную позицию в этом решении, всего 10 вариантов первого хода:

Изображение

Запускаю программу полного перебора окончаний, через 5 минут получаю результат 3314:

22:G3,J6,M6,G12,C2,K4,M5,F3,B13,K6,K7,L5,P9,K3,N10,N11,J10,L10,O10,M10,O7,N10,E12,
L9,L0,P3,O13,L13,D1,L11,L13,L14,M10,H0,G1,I7,K12,N2,L8,M0,I2,I11,I3,J11,J0,N0,M0,L9,F8,
K8,N1,J11,M9,N10,M12,N10,O10,P9,P9,P9,O8,P8,P8,O7,O8,O7,P6,O6,N0,P1,P0,N1,O1,O0

Незначительное улучшение, но всё же есть.
А если по всем играм пробежаться с этой программой, да ещё уровни поглубже брать, то можно и кое-что ещё насобирать.

Попробовала ввести этот результат, нет, не приняли. Значит, вводить можно только результаты не меньше текущего максимума.

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

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



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

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


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

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