Al Zimmermann: Primorial Soup

[dimkadimon]

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

http://azspcs.com/Contest/PrimorialSoup

[ctac]

dimkadimon в сообщении #1250270 писал(а):

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

http://azspcs.com/Contest/PrimorialSoup

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

[dmd]

сходу не смог понять несколько моментов:

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

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

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

[ctac]

dmd в сообщении #1251698 писал(а):

сходу не смог понять несколько моментов:

Цитата:

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

Плоский

Цитата:

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

Нет

Цитата:

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

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

[iifat]

dmd в сообщении #1251698 писал(а):

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

Граф же. Простой советский граф.

dmd в сообщении #1251698 писал(а):

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

Граф же. Простой советский граф. Ну, который множество вершин и рёбер. Не тот, что калякают на листике.

dmd в сообщении #1251698 писал(а):

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

Особенно на первых двух, да?
На всякий случай: $K_n$ — это полный граф. В котором каждая вершина связана ребром с каждой другой.

[dimkadimon]

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

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

-- 30.09.2017, 07:58 --

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

[ctac]

dimkadimon в сообщении #1251896 писал(а):

Кстати задачу можно переформулировать с помощью матриц.

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

[dimkadimon]

ctac в сообщении #1251987 писал(а):

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

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

[Herbert Kociemba]

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.

[dimkadimon]

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 :)

[ctac]

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

[Scryer]

ctac в сообщении #1252610 писал(а):

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

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

[ctac]

Scryer в сообщении #1252645 писал(а):

ctac в сообщении #1252610 писал(а):

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

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

Thanks! Didn't occur to me

[as73251]

dimkadimon в сообщении #1251896 писал(а):

Нашел первые 4 оптимальных решения...

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

[dimkadimon]

as73251 в сообщении #1252958 писал(а):

dimkadimon в сообщении #1251896 писал(а):

Нашел первые 4 оптимальных решения...

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

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