Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78кстати, зеркалирование доски рассматривали? оно теоретически ускоряет в 4 раза скорость перебора т.е. каждая доска это 4 разных доски, где паттерн зеркалится во все стороны нечистые доски не зеркалятся ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 15:26 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovtip78кстати, зеркалирование доски рассматривали? оно теоретически ускоряет в 4 раза скорость перебора т.е. каждая доска это 4 разных доски, где паттерн зеркалится во все стороны нечистые доски не зеркалятся чавойта? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 15:29 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78, если на доски уже стоят несколько ферзей, зеркало не поможет, сколько перед ним ни ходи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 15:49 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovtip78, если на доски уже стоят несколько ферзей, зеркало не поможет, сколько перед ним ни ходи. кстати, вместе с зеркалированием ещё и вращание доски можно устроить... 4 раза я не понял, почему не поможет, ну стоит там хоть 7 ферзей, разверните доску на 180 по горизонтали и перенесите на новую доску и по вертикали/диагоналям тоже потом каждый ход на исходной доске зеркалируется также на остальные 3 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 16:41 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
по сути надо просто положения ферзей исходные запоминать, от которых идут все остальные ходы и НЕ делать их же в других зеркальных вариациях но это всё не избавляет нас от перебора... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 16:47 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78, у тебя УЖЕ стоят 2 ферзя. они БУДУТ в решении. те перестановки, которые ты будешь генерировать уже должны включать этих ферзей. смысла вращать и зеркалить нет, потому что сдвинешь заданных ферзей ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 16:59 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Несколько мыслей. 1) Итеративный рекурсивный поиск (ИРП). (та ботва что опубликована в Вики) Работает долго. Очень долго. Очень-очень. Зато перебирает все варианты. Варианты уникальны. Никакой доп-проверки не нужно. Рекурсия гарантирует. O(a^x). Экспонента предположительно. Плюсы. Гарантировано выдаст все решения. Минусы. Выдает медленно. Не дождемся в обозримом будущем. 2) Случайный выбор (СВ). Полиномиален по отношению к одной комбинации. Генерирует неуникальную расстановку. Требуется доп-проверка уникальности. А здесь подвох. Британские ботаны обещали стартовую расстановку для 1000х1000. Условий больше нет. Это значит что имеют право поставить 1 ферзя и это будет тоже стартовые условия. Далее. Алгоритм генерит случайные расстановки. Их надо ГДЕ-ТО хранить. Учитывая факториальные оценки. Вангую что не хватит никаких баз. Сколько надо места? Петабайт? Эксабайт? Столько места нет у гугла и амазона. Это первое. Второе. Даже если мы найдем столько места. Купим хостинг у инопланетян на альфа-центавре. У них - молекулярные 3д SSD диски. Тогда нас ждет еще один сюрприз. Тот-же что и постиг копателей биткоинов. Будет замедление нахождения новых решений. Мы будем делать промахи и попадать в существующие решения. И наконец когда будет найдено 99.999% последнее решение мы не найдем никогда. В обозримом будущем. O(x^n). Полином. На старте полином. На финише - тормоз. Итак. Плюсы. Со старта начинает выдавать какие-то решения. Минусы. Хаотичный порядок. Нет системы. Скорость выдачи решения со временем падает. Требуется платить за хостинг гуманоидам с Центавры. А хостинг у них дорогой. В обоих случаях у нас нет progress-bar. Тоесть точно не знаем сколько уже накопали а сколько еще впереди. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 21:51 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78кстати, зеркалирование доски рассматривали? оно теоретически ускоряет в 4 раза скорость перебора т.е. каждая доска это 4 разных доски, где паттерн зеркалится во все стороны Да. Давайте 1 раз прокашляем этот вопрос в топике. Чтоб больше к нему не возвращаться. Для для доски 8х8 существуют только 12 уникальных расстановок. 92 получаются путем - поворота уникальной доски на 90 градусов. - отражения горизонтально или вертикально или от диагонали. В данной задаче нас будет интересовать вопрос. Если мы нашли очередное решение то нужно ли срочно выдать еще несколько производных от него? Зависит от алгоритма. Для рекурсивного - скорее всего не нужно он и так их всех переберет. Для начальной расстановки - надо проверить что повороты и отражения не нарушают этой расстановки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 22:12 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
mayton, зачем вообще возиться с зеркалированием? Ведь в нашем случае: 1. при поиске всех перестановок зеркалирование не дает выигрыша по времени, 2. никто не спрашивает, сколько уникальных решений было найдено. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.09.2017, 23:11 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, мы так запутаемся. В топике есть минимум два алгоритма. О каком алгоритме вы сейчас говорите? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 11:33 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
maytonAleksandr Sharahov, мы так запутаемся. В топике есть минимум два алгоритма. О каком алгоритме вы сейчас говорите? Мы решаем задачу завершения расстановки ферзей. В общем случае начальная позиция не переходит в себя при поворотах и отражениях. Поэтому безразлично, какой алгоритм мы используем для поиска очередного решения, поиск с возвратом и направленный спуск. В любом случае, мы заранее не знаем, будет ли очередное найденное решение уникальным или нет. Даже если окажется, что у полученного решения есть зеркальное, которое тоже нам подходит, совершенно бессмысленно его выдавать, потому что потом еще придется отсеивать его среди найденных. И генерация зеркального решения, и отсев только увеличат общие временные затраты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 12:34 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovmaytonAleksandr Sharahov, мы так запутаемся. В топике есть минимум два алгоритма. О каком алгоритме вы сейчас говорите? Мы решаем задачу завершения расстановки ферзей. В общем случае начальная позиция не переходит в себя при поворотах и отражениях. Поэтому безразлично, какой алгоритм мы используем для поиска очередного решения, поиск с возвратом и направленный спуск. В любом случае, мы заранее не знаем, будет ли очередное найденное решение уникальным или нет. Даже если окажется, что у полученного решения есть зеркальное, которое тоже нам подходит, совершенно бессмысленно его выдавать, потому что потом еще придется отсеивать его среди найденных. И генерация зеркального решения, и отсев только увеличат общие временные затраты. да нет же, если сразу самого первого ферзя из этого патnерна зафиксировать и далее этот паттерн не рассматривать, так как ВСЕ ферзи из него уже рассмотрены ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 14:09 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78да нет же, если сразу самого первого ферзя из этого патnерна зафиксировать и далее этот паттерн не рассматривать, так как ВСЕ ферзи из него уже рассмотрены И...? Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 14:23 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr SharahovВ общем случае начальная позиция не переходит в себя при поворотах и отражениях. Давай раскроем суть этой твоей фразы. Я утверждаю что генерация производных позиций может оказаться полезной для перечисления всех решений. Или она их ускорит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 14:43 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
mayton, значит, вас двое ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 14:48 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Но не для рекурсии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 17:12 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovtip78да нет же, если сразу самого первого ферзя из этого патnерна зафиксировать и далее этот паттерн не рассматривать, так как ВСЕ ферзи из него уже рассмотрены И...? Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет. если фигуры заранее фиксировать, то никак не поможет а так сократит в несколько раз объём перебора, потому что не надо будет делать тоже самое, но с другой стороны (сторон) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 19:24 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78Aleksandr Sharahovпропущено... И...? Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет. если фигуры заранее фиксировать, то никак не поможет а так сократит в несколько раз объём перебора, потому что не надо будет делать тоже самое, но с другой стороны (сторон) Хорошо, но мало ) Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет с другой стороны. Как именно это будет выглядеть в твоем алгоритме? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 20:09 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovtip78пропущено... если фигуры заранее фиксировать, то никак не поможет а так сократит в несколько раз объём перебора, потому что не надо будет делать тоже самое, но с другой стороны (сторон) Хорошо, но мало ) Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет с другой стороны. Как именно это будет выглядеть в твоем алгоритме? спасибо за предоставленную возможность (с) но волшебные слова никто не отменял. на доске 64 варианта первого ферзя каждый одинокий ферзь на доске это некое дерево остальных ферзей до упора, где ВСЕ варианты заполнения опробованы т.е. всё что надо это разбить доску на 4 квадрата и заполнить стартовыми ходами только 1 из них поворачивание тут, кстати, уже и не нужно просто есть квадраты по 16 клеток, как бы не начал на любом из них, на остальных будет зеркально тоже самое дерево и результаты ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 22:45 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78просто есть квадраты по 16 клеток, как бы не начал на любом из них, на остальных будет зеркально тоже самое дерево и результаты Понятно, что зеркальные варианты расположения ферзей существуют, непонятно только, каким образом этот факт нам поможет в поиске всех решений. Хотелось бы, наконец, узнать конкретно, какой участок алгоритма упростится, почему и насколько сократится общее время расчета всех решений, как будет организован отсев неуникальных решений. Только после этого можно будет говорить, что зеркалирование - наше все. Основная проблема здесь в том, что для отсева решения надо знать, уникальное ли оно, а для этого его придется сначала получить. Т.е. придется получить *ВСЕ* решения. А если решение уже получено, то его проще показать, чем возиться с отсевом и ведением списка уникальных решений, которые еще надо отзеркалить во все стороны. Зеркалирование ровным счетом ничего не дает, кроме лишней работы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.09.2017, 23:50 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
т.е. непонятно, что надо будет начинать только в 1м квадрате 16x16, а не в 4х? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.09.2017, 00:20 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78т.е. непонятно, что надо будет начинать только в 1м квадрате 16x16, а не в 4х? непонятно, что это дает. Лучшим доказательством того, что идея зеркалирования работает, будет реализация этого замечательного алгоритма, а не слова. Вот тогда можно будет сравнить время его работы и количество перебираемых вариантов с аналогичным алгоритмом, но без зеркалирования. Реализуйте, например, поиск с возвратом двумя способами ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.09.2017, 00:32 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Все самому приходится делать. Алгоритм: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. Вывод с учетом симметрии: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. Итого получилось быстрее несимметричного варианта почти в 2 раза. Внутренние структуры алгоритма уже раньше были изменены под градиентный спуск и в данном случае это позволило добиться ускорения. Хитрость состоит в порядке перебора, чтобы обеспечить получение алгоритмом только уникальных решений: 1. Порядок перебора для строк: 0, N-1, ... 1. 2. Порядок перебора для столбцов строки N-1: Min(Col-1,BoardSize-1-Col), ... 0, где Col - текущий столбец строки 0. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.09.2017, 10:46 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahovtip78т.е. непонятно, что надо будет начинать только в 1м квадрате 16x16, а не в 4х? непонятно, что это дает. Лучшим доказательством того, что идея зеркалирования работает, будет реализация этого замечательного алгоритма, а не слова. Вот тогда можно будет сравнить время его работы и количество перебираемых вариантов с аналогичным алгоритмом, но без зеркалирования. Реализуйте, например, поиск с возвратом двумя способами ) чё-то мне влом да и денег у вас не хватит моё время оплачивать. в чём тут сложность понимания то? весь алгоритм в том, что первый ферзь ставится только в 16 клеток, а не в 64 как 64 может быть быстрее 16 для меня загадка. алгоритм в помойку. первый ферзь ставится в любую точку на доске после этого пошёл поиск места для следующего у каждого ферзя есть своё дерево ходов до полного исчезновения свободных клеток (ходов будут миллионы-миллиарды, но они конечны и ограничены) 8й ферзь отработает все свободные клетки после чего 7й ферзь сдвинется на следующую свободную клетку и снова 8й ферзь будет пробивать все свободные когда у 7го закончатся клетки, сдвинется 6й итд и вот ровно такие же действия (зеркально) для каждого ферзя, но на другой стороне поля, будут происходить, если поставить первого ферзя в другой противоположный квадрат. это же перебор. ВСЕ свободные клетки на доске будут задействованы для каждого ферзя. В одном квадрате 1й ферзь встаёт на 3:4, 2й на 1:1, в противоположном они же займут 6:5 и 8:8, после чего ровно также 2й пойдёт пробивать все клетки, получая ровно те же (зеркальные) результаты я хз, как ещё понятнее объяснить, вроде элементарно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.09.2017, 11:10 |
|
||
|
Пятничная задачка для ума за 1 миллион $
|
|||
|---|---|---|---|
|
#18+
tip78чё-то мне влом да и денег у вас не хватит моё время оплачивать. С чего вы взяли, что тут вас кто-то наймет? Для поиска работы есть другой форум. tip78в чём тут сложность понимания то? весь алгоритм в том, что первый ферзь ставится только в 16 клеток, а не в 64 как 64 может быть быстрее 16 для меня загадка. алгоритм в помойку. Да запросто: алгоритм-64 есть и у него есть время работы, а алгоритм-16 пока только у вас в голове и его время работы там же. tip78первый ферзь ставится в любую точку на доске после этого пошёл поиск места для следующего у каждого ферзя есть своё дерево ходов до полного исчезновения свободных клеток (ходов будут миллионы-миллиарды, но они конечны и ограничены) 8й ферзь отработает все свободные клетки после чего 7й ферзь сдвинется на следующую свободную клетку и снова 8й ферзь будет пробивать все свободные когда у 7го закончатся клетки, сдвинется 6й итд и вот ровно такие же действия (зеркально) для каждого ферзя, но на другой стороне поля, будут происходить, если поставить первого ферзя в другой противоположный квадрат. это же перебор. ВСЕ свободные клетки на доске будут задействованы для каждого ферзя. В одном квадрате 1й ферзь встаёт на 3:4, 2й на 1:1, в противоположном они же займут 6:5 и 8:8, после чего ровно также 2й пойдёт пробивать все клетки, получая ровно те же (зеркальные) результаты я хз, как ещё понятнее объяснить, вроде элементарно. Да всем это понятно. Не это надо объяснять. Объясните, как ваш алгоритм будет использовать факт симметрии решений для ускорения работы. А то что вы рассказываете уже в который раз - не алгоритм. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.09.2017, 11:33 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39518641&tid=1340254]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
68ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
68ms |
get tp. blocked users: |
1ms |
| others: | 13ms |
| total: | 188ms |

| 0 / 0 |
