Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 20   вперед  Ctrl
 Пятничная задачка для ума за 1 миллион $  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 5229
https://news.mail.ru/society/30876968/?frommail=10

«задача о восьми ферзях» на доске 1000х1000
3 сен 17, 00:08    [20767577]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
scf
Member

Откуда:
Сообщений: 1352
Siemargl,

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

mail.ru такой mail.ru.
3 сен 17, 14:26    [20768098]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
Подобные премии в истории математики - не редкость. Их обычно вводят не для
того чтобы решить задачу. А для того чтобы подогреть интерес общества к науке.
Так - же было с поиском волшебной тройки чисел для Великой Теоремы Ферма.
Так же было с пятнашками (при этом хитрый создатель этой головоломки
предложил заведомо тупиковую стартовую комбинацию из которой не было
решения). И сейчас ЕМНИП между известными в мире университетами идет
соревнование на тему поиска следущего простого числа Мерсенна. А с ними
вообще треш. На обычных серверах они не решаются. Нужно как-то кластеризовать
задачку на кусочки и решить в параллелизме.

В данной задаче (идет речь о 1000 ферзей на 1000х1000 клеток) стоит не решать
ее а просто оценить время решения. К примеру мы знаем время ее решения на С++
для всех полей до 16х16 и оно экспоненциально.
3 сен 17, 14:44    [20768112]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 5229
Надо посмотреть алгоритм. Может он хорошо ляжет на рендеринговые возможности GPU
3 сен 17, 23:02    [20768592]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 5229
scf,

По моему идея очень хороша брать деньги за тупые комменты типа "поясните как нагуглить условие задачи" =)
3 сен 17, 23:04    [20768597]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
scf
Member

Откуда:
Сообщений: 1352
mayton,

https://geektimes.ru/post/292631/
Задачу о N ферзях признали NP-полной задачей
3 сен 17, 23:34    [20768639]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
Решать задачу в лоб переборным алгоритмом как в wiki будет "долговато".

Я взял последние сведения по time-статистике для С-программы для
нескольких значений доски (N) и попробовал экстраполировать. Вобщем
примерно с ростом N на единицу расчетное время умножается на
приблизительно на 7.

LibreOffice не смог мне показать число секунд сколько мы будем искать
все решения для 1000 на 1000. У него не хватило экспоненты.

В формуле получается что-то вроде:



Я даже не могу его ни с чем сравнить. Для этого надо его привести хотя-бы
к научному основанию 10. Потухнет солнце к тому времени или нет? Наверное - да.
Мы выпали из научной разрядной сетки.

Радует пока тот факт что нам не нужно искать все решения. Надо найти хотя-бы
первое. А сколько времени в среднем ищется первое? Я сведений не нашел пока.
3 сен 17, 23:36    [20768640]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2111
mayton,

на вскидку почему-то вспомнились фракталы,и тут же ссылка с вики

но с другой стороны под решением, наверное, подразумевается, что нужно найти все комбинации
4 сен 17, 07:40    [20768798]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
Ну что-же - миллион у нас уже в кармане. Осталось только написать письмо
Британским ботанам.

Но смущает что мы читаем какой-то репост на mail.ru где плохо описаны
условия того что надо собственно сделать. Найти первую попавшуюся
расстановку? - Фракталы рулят. Найти все? - Ну это ждать пока солнце не погаснет.

Вобщем нужен оригинал этой новости.
4 сен 17, 08:26    [20768838]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Dima T
Member

Откуда:
Сообщений: 11299
ИМХО одну комбинацию найти уже перебирать устанешь: Первый ферзь ставится 1 млн. способов, перекрывает 3000-8000 клеток, второй 992000-997000 вариантов и т.д.

Если вики глянуть, то количество решений тоже растет с размером доски, в итоге время на поиск одного хоть и растет, но уже не так сильно.

Перебирательных мощностей полно нынче, биткоины майнят ))), если какой-нибудь большой пул переключится на эту задачу, то может и замайнят случайно какое-нибудь решение за разумное время.
4 сен 17, 09:04    [20768878]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2111
mayton
Вобщем нужен оригинал этой новости.

вообще странно, тут написано, что
автор
The prize money of one million USD, awarded by Clay Mathematics Institute in the US is available to anyone who can solve the puzzle

в самом институте такой траблы не вижу, наверное нашли уже ... :-(
4 сен 17, 10:37    [20769097]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2111
во, есть оказывается
4 сен 17, 10:41    [20769103]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2111
автор
Dr Nightingale said: “However, this is all theoretical. In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that – for all practical purposes – it can’t be done.”

Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly so the rewards are high.”

т.е. всё таки все варианты надо найти
4 сен 17, 10:43    [20769108]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
scf
Member

Откуда:
Сообщений: 1352
Так они сами денег не предлагают. Денги выплатит Clay за алгоритм, находящий решение за полиномиальное время.
4 сен 17, 10:45    [20769111]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
Тогда фрактальных ферзи нам не помогут. Они покрывают частные случаи расстановки 1000 фигур.
4 сен 17, 14:32    [20769909]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2111
scf
Так они сами денег не предлагают. Денги выплатит Clay за алгоритм, находящий решение за полиномиальное время.
я вот одного понять не могу, количество решений явно растёт как O(N!), т.е. даже просто выводить результаты не получится за O(N^k)
4 сен 17, 16:31    [20770319]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 5229
Dima T
ИМХО одну комбинацию найти уже перебирать устанешь: Первый ферзь ставится 1 млн. способов, перекрывает 3000-8000 клеток, второй 992000-997000 вариантов и т.д.
...
Нет, первый всего лишь 1000 вариантов, второй - 999 итп. Это если в лоб
4 сен 17, 16:55    [20770427]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Dima T
Member

Откуда:
Сообщений: 11299
Siemargl
Dima T
ИМХО одну комбинацию найти уже перебирать устанешь: Первый ферзь ставится 1 млн. способов, перекрывает 3000-8000 клеток, второй 992000-997000 вариантов и т.д.
...
Нет, первый всего лишь 1000 вариантов, второй - 999 итп. Это если в лоб

1000*1000 = 1000000
Т.е. всего 1 млн. клеток, в любую можно первого поставить, можно на 2 поделить, т.к. зеркально доска отображается.
4 сен 17, 16:58    [20770440]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 5229
Dima T,

да блин, ферзи все одинаковые. потому достаточно одной строки.
миллион был бы если бы они были, ну скажем разноцветные.
4 сен 17, 17:11    [20770480]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
kealon(Ruslan)
scf
Так они сами денег не предлагают. Денги выплатит Clay за алгоритм, находящий решение за полиномиальное время.
я вот одного понять не могу, количество решений явно растёт как O(N!), т.е. даже просто выводить результаты не получится за O(N^k)

В этом и суть этой проблемы. Факториальная сложность нас ведёт в тупик. Мы не можем крутить факториалы от тысячи.

Ищем оптимизации которые уводят нас в класс полиномов.
4 сен 17, 17:11    [20770482]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
Siemargl,

непонятно, что считать решением.

Если решение - это все расположения, то оно может просто не уместиться на бумажке.
4 сен 17, 17:21    [20770531]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 2111
mayton
kealon(Ruslan)
пропущено...
я вот одного понять не могу, количество решений явно растёт как O(N!), т.е. даже просто выводить результаты не получится за O(N^k)

В этом и суть этой проблемы. Факториальная сложность нас ведёт в тупик. Мы не можем крутить факториалы от тысячи.

Ищем оптимизации которые уводят нас в класс полиномов.

да дело даже не в оптимизациях, само количество решений как экспонента от N (предположительно)
даже если удастся расписать формулу, которая тупо выводит следующий ответ за O(1), то сложность печати всех ответов будет больше, чем O(N^k)
4 сен 17, 19:06    [20770878]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
Могу предположить что сам по себе ответ их не особо интересует.

Кто силён в английском и может перевести текст задачи (по ссылкам выше)?
4 сен 17, 19:50    [20770959]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1314
mayton,

тут несколько вопросов:

Существует 3 варианта задачи:
1 найти любое расположение, при котором ферзи не бьют друг друга,
2 найти все такие расположения,
3 найти количество таких расположений.

Какой из вариантов им нужен?
Им надо "быстро" решить задачу. Что значит быстро? За полиномиальное время? Время на одно расположение или на полное решение?
Что значит решить? Алгоритм? Или дать развернутый ответ? )
4 сен 17, 20:45    [20771018]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка для ума за 1 миллион $  [new]
mayton
Member

Откуда: loopback
Сообщений: 35509
Машинный перевод гугла по ссылке


http://jair.org/papers/paper5512.html
Ян П. Гент, Кристофер Джефферсон и Питер Найтингейл (2017)
"Сложность решения проблемы n-Queens" том 59 страницы 815-848

Задача n-Queens состоит в том, чтобы разместить n шахматных ферзей на n n шахматной доске, чтобы никакие две королевы не находились в одной строке, столбце или диагонали. Задача о завершении n-Queens - вариант, датируемый 1850 годом, когда некоторые королевы уже размещены, а решатель может поместить остальных, если это возможно. Мы показываем, что n-Queens Completion - это NP-Complete и # P-Complete. Следствием является то, что любое не атакующее расположение ферзей может быть включено как часть решения более крупной проблемы n-Queens. Мы вводим генераторы случайных экземпляров для n-Queens Completion и тесно связанной задачи о блокированных n-Queens и исключенных диагоналях. Мы описываем три решателя для этих проблем и эмпирически анализируем твердость случайно сгенерированных экземпляров. Для задачи «Заблокированные n-Queens» и «Исключенные диагонали» мы показываем существование фазового перехода, при котором n-Queens Completion не генерирует последовательно жесткие экземпляры. Значение этой работы заключается в том, что проблема n-Queens использовалась во многих отношениях в качестве эталона в искусственном интеллекте. Наши результаты дают альтернативные критерии, которые теоретически и эмпирически трудны, но для которых методы, разработанные для n-Queens, требуют минимального или никакого изменения.
4 сен 17, 21:32    [20771090]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 20   вперед  Ctrl
Все форумы / Программирование Ответить