2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 12  След.
 
 Al Zimmermann: Primorial Soup
Сообщение24.09.2017, 14:02 
Аватара пользователя


01/06/12
971
Adelaide, Australia
Друзья с радостью хочу сообщить очень приятную новость - началось новое соревнование Ал Зиммерманн! Задача про некоторые полные графы:

http://azspcs.com/Contest/PrimorialSoup

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение28.09.2017, 12:58 


09/03/16
34
dimkadimon в сообщении #1250270 писал(а):
Друзья с радостью хочу сообщить очень приятную новость - началось новое соревнование Ал Зиммерманн! Задача про некоторые полные графы:

http://azspcs.com/Contest/PrimorialSoup


Выглядит как еще одно перемешивание простых чисел. Или все же какие-то теоремы из теории графов могут оказаться тут полезными?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение29.09.2017, 07:59 


16/08/05
1110
сходу не смог понять несколько моментов:

- имеется ввиду плоский граф или объёмный?

- условие не-пересечения рёбер действует или нет?

- разные вершины могут быть связаны с разным количеством рёбер, или с одинаковым, как на рисунках описания?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение29.09.2017, 12:43 


09/03/16
34
dmd в сообщении #1251698 писал(а):
сходу не смог понять несколько моментов:


Цитата:
- имеется ввиду плоский граф или объёмный?

Плоский

Цитата:
- условие не-пересечения рёбер действует или нет?

Нет

Цитата:
- разные вершины могут быть связаны с разным количеством рёбер, или с одинаковым, как на рисунках описания?


С одинаковым: n*(n-1) / 2

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение29.09.2017, 15:12 
Заслуженный участник


16/02/13
3833
Владивосток
dmd в сообщении #1251698 писал(а):
имеется ввиду плоский граф или объёмный?
Граф же. Простой советский граф.
dmd в сообщении #1251698 писал(а):
условие не-пересечения рёбер действует или нет?
Граф же. Простой советский граф. Ну, который множество вершин и рёбер. Не тот, что калякают на листике.
dmd в сообщении #1251698 писал(а):
разные вершины могут быть связаны с разным количеством рёбер, или с одинаковым, как на рисунках описания?
Особенно на первых двух, да?
На всякий случай: $K_n$ — это полный граф. В котором каждая вершина связана ребром с каждой другой.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение30.09.2017, 01:36 
Аватара пользователя


01/06/12
971
Adelaide, Australia
Нашел первые 4 оптимальных решения, а вот дальше никак не получается. Если не найдешь оптимальное (или близкое к нему) то получаешь очень мало очков.

Проверил жадный алгоритм. Начинаем на всех ребрах по 1. Потом вставляем простые числа по одному в порядке убывания. Выбираем вставление которое дает самую маленькую сумму. Алгоритм работает быстро даже для больших $N$, но результаты не очень.

-- 30.09.2017, 07:58 --

Кстати задачу можно переформулировать с помощью матриц. Найдите $n\times n$ симметричную матрицу $M$ из первых $n(n-1)/2$ простых (на главной диагонали все 1) у которой минимальная оценка: $\sum_r \prod_c M_{rc}$ .

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение30.09.2017, 14:01 


09/03/16
34
dimkadimon в сообщении #1251896 писал(а):
Кстати задачу можно переформулировать с помощью матриц.


Т.е. все-таки задача сводится к некоему перемешиванию простых чисел и знание теории графов здесь не поможет?

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение30.09.2017, 15:19 
Аватара пользователя


01/06/12
971
Adelaide, Australia
ctac в сообщении #1251987 писал(а):
Т.е. все-таки задача сводится к некоему перемешиванию простых чисел и знание теории графов здесь не поможет?

С одной стороны задачу можно решить без теории графов (используя матрицы), но с другой стороны немного теории графов не помешает...

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение30.09.2017, 22:34 
Аватара пользователя


25/08/12
160
Germany
dimkadimon в сообщении #1251896 писал(а):
Кстати задачу можно переформулировать с помощью матриц. Найдите $n\times n$ симметричную матрицу $M$ из первых $n(n-1)/2$ простых (на главной диагонали все 1) у которой минимальная оценка: $\sum_r \prod_c M_{rc}$ .


In the language of graph theory this matrix is more or less the adjacency matrix of the weighted graph. Btw. I did not try your approach yet, but eventually this approach gives better results if you make the algorithm more flexible by adding a treshhold and allow also suboptimal values to be added and do something like beam search.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение01.10.2017, 02:49 
Аватара пользователя


01/06/12
971
Adelaide, Australia
Herbert Kociemba в сообщении #1252091 писал(а):
In the language of graph theory this matrix is more or less the adjacency matrix of the weighted graph. Btw. I did not try your approach yet, but eventually this approach gives better results if you make the algorithm more flexible by adding a treshhold and allow also suboptimal values to be added and do something like beam search.

In fact, it IS the adjacency matrix of that complete graph. Yes I was thinking that beam search may be the way to go. I just hate implementing it :)

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение02.10.2017, 23:53 


09/03/16
34
Не могу понять зачем в определении Target в описании задачи, понадобилась двойка, т.е. возводить в квадрат произведение n простых чисел на ребрах графа. Может кто объяснит? :cry:

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение03.10.2017, 03:29 
Аватара пользователя


09/06/12
26
ctac в сообщении #1252610 писал(а):
Не могу понять зачем в определении Target в описании задачи, понадобилась двойка, т.е. возводить в квадрат произведение n простых чисел на ребрах графа. Может кто объяснит? :cry:

There are two copies of each prime: one in each of the end-point nodes.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение03.10.2017, 13:18 


09/03/16
34
Scryer в сообщении #1252645 писал(а):
ctac в сообщении #1252610 писал(а):
Не могу понять зачем в определении Target в описании задачи, понадобилась двойка, т.е. возводить в квадрат произведение n простых чисел на ребрах графа. Может кто объяснит? :cry:

There are two copies of each prime: one in each of the end-point nodes.


Thanks! Didn't occur to me :x

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение04.10.2017, 10:02 


04/10/17

153
dimkadimon в сообщении #1251896 писал(а):
Нашел первые 4 оптимальных решения...

Для 4-го оптимального (в смысле: наилучшего) решения (7 вершин в графе) даже хорошо оптимизированный алгоритм потребует несколько часов работы на 1000 ядрах для полного перебора возникающих варинтов. В связи с этим у меня к Вам нескромный вопрос: какова "мощность" железа, которое Вы используете? Я думаю, что Jarek Wroblewski и не искал оптимальное решение для 7 вершин, но при этом с громадным отрывом занимает первое место: я имею в виду, что большинство конкурсов Al нивелирует мощность железа и на первое место выходит оригинальный алгоритмический подход.

 Профиль  
                  
 
 Re: Al Zimmermann: Primorial Soup
Сообщение05.10.2017, 03:45 
Аватара пользователя


01/06/12
971
Adelaide, Australia
as73251 в сообщении #1252958 писал(а):
dimkadimon в сообщении #1251896 писал(а):
Нашел первые 4 оптимальных решения...

Для 4-го оптимального (в смысле: наилучшего) решения (7 вершин в графе) даже хорошо оптимизированный алгоритм потребует несколько часов работы на 1000 ядрах для полного перебора возникающих варинтов. В связи с этим у меня к Вам нескромный вопрос: какова "мощность" железа, которое Вы используете? Я думаю, что Jarek Wroblewski и не искал оптимальное решение для 7 вершин, но при этом с громадным отрывом занимает первое место: я имею в виду, что большинство конкурсов Al нивелирует мощность железа и на первое место выходит оригинальный алгоритмический подход.


У меня один 5ти-летний компьютер quad-core. Сила в алгоритме. Правда 8 вершин никак не могу решить...

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

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



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

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


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

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