Comments 59
Извините, я устал читать. Не покажете место, где кончаются очевидные вещи и начинается ноу хау?
Можно суть вкратце?
Ну пару абзацев в TL; DR; стиле со ссылками на части статьи.
Труд заслуживает уважения, но читать нереально.
автору пара вопросов:
1. ваш алгоритм опирается на случайные числа, может ли он найти все возможные расстановки ферзей на доске?
2. как были вычислены магические числа baseLevel2/3 и их формулы?
3. Вы рассмотрели сильные стороны своего алгоритма, а каковые его слабые стороны?
1. ваш алгоритм опирается на случайные числа, может ли он найти все возможные расстановки ферзей на доске?
2. как были вычислены магические числа baseLevel2/3 и их формулы?
3. Вы рассмотрели сильные стороны своего алгоритма, а каковые его слабые стороны?
Я в одну контору как собеседовение, решал задачу. Даны размеры доски (K x N), дан произвольный набор фигур (не только ферзи). Найти все решения. Написать на языке, которым не пользовался до тех пор в практике. (Я писал на Ada).
Статья в самом деле большая. Для тех, кто пытался решать подобные задачи, наверное статья представит интерес. Для других, кто хочет кратко — достаточно посмотреть только Выводы (в конце статьи).
Проблема, которая рассматривается в публикации, принципиально важная и достаточно сложная. Мне показалось, что будет правильным привести подробное изложение результатов исследования, без «темных» мест.
Вопрос:… может ли он найти все возможные расстановки ферзей на доске?
Все возможные расстановки ферзей на доске означает все полные решения n-Queens Problem для шахматной доски размера n x n. Я разрабатывал такой алгоритм и находил список всех решений (полных и коротких) с целью поиска закономерностей в этих последовательных списках. Результаты исследования были опубликованы мною на Хабре. Сам алгоритм я не публиковал.
Программа последовательного поиска всех решений и программа комплектации произвольной композиции из k ферзей — это разные программы (у них разные цели).
Вопрос:… как были вычислены магические числа baseLevel2/3 и их формулы?
Прежде чем ответить на вопрос, хочу привести простой пример. Пусть на шахматной доске размером 1000 х 1000 клеток была непротиворечиво расставлена композиция из 345 ферзей. От нас требуют комплектовать данную композицию до полного решения, либо доказать, что данная композиция отрицательная, т.е. не имеет решения. Пусть в результате решения удалось расставить ферзи на 600 свободных строках, так что общее количество строк, на которых расставлены ферзи — составляет 945. Но, при этом оказалось, что данная ветвь поиска является тупиковой. Нужно выполнить процедуру Back Tracking, т.е. вернуться назад.
Тогда возникает вопрос: «А на какой из предыдущих уровней следует возвращаться?» Может кто-нибудь подсказать? Я был уверен, что какой-то намек или рациональную идею удастся найти в публикациях, которые просмотрел. Увы, ничего не нашел. Хотя, количество публикаций, которые прямо или косвенно касаются теме Back Tracking, скорее всего превышает пол-тысячи.
Тогда у меня возникла идея формирования базовых уровней. Они должны были примерно соответствовать границе, когда кончается работа одного алгоритма формирования ветви поиска решения и начинается работа другого алгоритма. Когда появилась такая прозрачная цель, было проведено большое число вычислительных экспериментов, что позволило получить выборку граничных значений, при достижении которых, тот или иной алгоритм теряет свою эффективность. После этого, значения baseLevel2, baseLevel3 были «привязаны» к значению n на основе модели регрессии.
Вопрос: «Вы рассмотрели сильные стороны своего алгоритма, а каковые его слабые стороны?»
Назначение алгоритма — эффективно решать поставленную задачу. Если где-то «он проявляет себя слабо» и не может решить задачу, там и проявляется его слабость. В том диапазоне значений n (от 7 до 100 миллионов), где я проводил исследование, программа честно выполняла свои обязанности. Построить алгоритм, который может формировать ветвь поиска решения в огромном пространстве состояния, и при этом в 50% случаях, на интервале n= ( 320,…,22500), ни разу не использовать процедуру Back Tracking — говорит об эффективности данного алгоритма. Но ничего абсолютно совершенного нет. Я буду рад, если Вы или кто-то другой честно и обоснованно покажет слабые стороны данного алгоритма. Ведь цель нашего общения — в обмене информацией и развитии.
Проблема, которая рассматривается в публикации, принципиально важная и достаточно сложная. Мне показалось, что будет правильным привести подробное изложение результатов исследования, без «темных» мест.
Вопрос:… может ли он найти все возможные расстановки ферзей на доске?
Все возможные расстановки ферзей на доске означает все полные решения n-Queens Problem для шахматной доски размера n x n. Я разрабатывал такой алгоритм и находил список всех решений (полных и коротких) с целью поиска закономерностей в этих последовательных списках. Результаты исследования были опубликованы мною на Хабре. Сам алгоритм я не публиковал.
Программа последовательного поиска всех решений и программа комплектации произвольной композиции из k ферзей — это разные программы (у них разные цели).
Вопрос:… как были вычислены магические числа baseLevel2/3 и их формулы?
Прежде чем ответить на вопрос, хочу привести простой пример. Пусть на шахматной доске размером 1000 х 1000 клеток была непротиворечиво расставлена композиция из 345 ферзей. От нас требуют комплектовать данную композицию до полного решения, либо доказать, что данная композиция отрицательная, т.е. не имеет решения. Пусть в результате решения удалось расставить ферзи на 600 свободных строках, так что общее количество строк, на которых расставлены ферзи — составляет 945. Но, при этом оказалось, что данная ветвь поиска является тупиковой. Нужно выполнить процедуру Back Tracking, т.е. вернуться назад.
Тогда возникает вопрос: «А на какой из предыдущих уровней следует возвращаться?» Может кто-нибудь подсказать? Я был уверен, что какой-то намек или рациональную идею удастся найти в публикациях, которые просмотрел. Увы, ничего не нашел. Хотя, количество публикаций, которые прямо или косвенно касаются теме Back Tracking, скорее всего превышает пол-тысячи.
Тогда у меня возникла идея формирования базовых уровней. Они должны были примерно соответствовать границе, когда кончается работа одного алгоритма формирования ветви поиска решения и начинается работа другого алгоритма. Когда появилась такая прозрачная цель, было проведено большое число вычислительных экспериментов, что позволило получить выборку граничных значений, при достижении которых, тот или иной алгоритм теряет свою эффективность. После этого, значения baseLevel2, baseLevel3 были «привязаны» к значению n на основе модели регрессии.
Вопрос: «Вы рассмотрели сильные стороны своего алгоритма, а каковые его слабые стороны?»
Назначение алгоритма — эффективно решать поставленную задачу. Если где-то «он проявляет себя слабо» и не может решить задачу, там и проявляется его слабость. В том диапазоне значений n (от 7 до 100 миллионов), где я проводил исследование, программа честно выполняла свои обязанности. Построить алгоритм, который может формировать ветвь поиска решения в огромном пространстве состояния, и при этом в 50% случаях, на интервале n= ( 320,…,22500), ни разу не использовать процедуру Back Tracking — говорит об эффективности данного алгоритма. Но ничего абсолютно совершенного нет. Я буду рад, если Вы или кто-то другой честно и обоснованно покажет слабые стороны данного алгоритма. Ведь цель нашего общения — в обмене информацией и развитии.
Автор заявляет о революции — о наличии линейного решения для NP-полной задачи. Такое заявление требует убедительных доказательств, т.к. если бы это было правдой, то была бы опровергнута гипотеза P ≠ NP. Обычно же это свидетельствует о том, что в ходе рассуждений где-то закралась ошибка.
Немного критики
desktop-13
Скорость выполнения алгоритма на конкретном компьютере не имеет отношения к линейному/нелинейному времени. На мой взгляд, это только добавляет "воды" в статью.
Очевидно, что данный алгоритм по времени счета является линейным относительно n.
Краеугольным камнем P≠NP является оценка сложности. Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде, и видеть оценку в стандартной О-нотации.
n-Queens Completion problem является классической не детерминированной задачей.
это утверждение противоречит формулировке задачи, данной в разделе "1. Введение". Там задача сформулирована детерминировано, как и положено задачам класса NP.
Таким образом, автор подменяет одну задачу другой.
False Negative решения
В детерминированном алгоритме решения NP-полных задач таких решений быть не может. Таким образом, предложенное автором решение не является решением задачи n-Queens Completion problem
Т.е. программа работает, но в конечном итоге, формального доказательства не будет и, очевидно никакого «прорыва» — просто качественный алгорим, который работает на подмножестве параметров.
Естественно, что найти контрпримеры будет довольно сложно и не понятно стоит ли в принципе заморачиваться.
Естественно, что найти контрпримеры будет довольно сложно и не понятно стоит ли в принципе заморачиваться.
Про дядю Вову
Похоже на Рыбинкина, но гораздо более адекватного. Тот тоже и P=NP «доказал», и информацию сжимал.
Вопрос: « Автор заявляет о революции — о наличии линейного решения для NP-полной задачи.»
О революции нигде в тексте нет и намека. Это другая материя. А то, что временная сложность алгоритма линейная – так это правда. Это же легко проверить. Я в предисловии к статье писал, если у Вас есть возможность запустить программу на Матлабе, то напишите мне (в предисловии есть мой e-mail). Я вышлю Вам программу (алгоритм) для тестирования. Это не займет у Вас много времени, программа работает очень быстро.
«Такое заявление требует убедительных доказательств, …»
Корректно сформулированные вычислительные задачи можно решить на основе строгих математических методов (на основе определений, формулировке лемм и доказательстве теорем), либо с помощью алгоритмической математики на основе Computational Simulation. С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно. Об этом в конце статьи есть «философское замечание». Я тоже хотел строго математически, но заблуждался, причем долго. Подобного рода задачи можно решить только на основе алгоритмической математики. Что в принципе и было сделано (правда, для этого потребовалось слишком много времени).
А теперь, по поводу «убедительных доказательств…». Есть алгоритмическое решение данной задачи. Я уверен, что Вы серьезный человек, поэтому предлагаю Вам проверить работу алгоритма. Это совсем не сложно, и даст вам возможность обоснованно оценить работу алгоритма и сделать выводы.
«…то была бы опровергнута гипотеза P ≠ NP»
У страха глаза велики – я тоже «боялся», до определенной поры. Не надо демонизировать. Все гораздо сложнее и интереснее. Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики. В каждом случае будет свой подход, хотя, что-то общее в алгоритме решения будет их объединять. Утверждать, что после решения n-Queens Completion Problem, все остальные задачи из множества NP-Complete сразу завалятся, будет неверно. Я не говорю об полиномиальном сведении решения одной сложной задачи к решению другой задачи. Я имею ввиду разработку эффективного алгоритма для решения конкретной задачи.
О революции нигде в тексте нет и намека. Это другая материя. А то, что временная сложность алгоритма линейная – так это правда. Это же легко проверить. Я в предисловии к статье писал, если у Вас есть возможность запустить программу на Матлабе, то напишите мне (в предисловии есть мой e-mail). Я вышлю Вам программу (алгоритм) для тестирования. Это не займет у Вас много времени, программа работает очень быстро.
«Такое заявление требует убедительных доказательств, …»
Корректно сформулированные вычислительные задачи можно решить на основе строгих математических методов (на основе определений, формулировке лемм и доказательстве теорем), либо с помощью алгоритмической математики на основе Computational Simulation. С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно. Об этом в конце статьи есть «философское замечание». Я тоже хотел строго математически, но заблуждался, причем долго. Подобного рода задачи можно решить только на основе алгоритмической математики. Что в принципе и было сделано (правда, для этого потребовалось слишком много времени).
А теперь, по поводу «убедительных доказательств…». Есть алгоритмическое решение данной задачи. Я уверен, что Вы серьезный человек, поэтому предлагаю Вам проверить работу алгоритма. Это совсем не сложно, и даст вам возможность обоснованно оценить работу алгоритма и сделать выводы.
«…то была бы опровергнута гипотеза P ≠ NP»
У страха глаза велики – я тоже «боялся», до определенной поры. Не надо демонизировать. Все гораздо сложнее и интереснее. Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики. В каждом случае будет свой подход, хотя, что-то общее в алгоритме решения будет их объединять. Утверждать, что после решения n-Queens Completion Problem, все остальные задачи из множества NP-Complete сразу завалятся, будет неверно. Я не говорю об полиномиальном сведении решения одной сложной задачи к решению другой задачи. Я имею ввиду разработку эффективного алгоритма для решения конкретной задачи.
временная сложность алгоритма линейная
т.е. O(n).
Может и так. Просто тот алгоритм, который Вы предлагаете, не решает поставленную задачу. Заголовок сформулирован "n-Queens Completion Problem — линейный алгоритм решения", то есть предполагается, что алгоритм, который Вы предлагаете в статье, даёт решение задачи "n-Queens Completion Problem". Если бы это было так, то это была бы революция.
Как оказалось, исходная задача заменена на другую, и поэтому революции не случилось.
С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно
Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.
Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики
Как я понимаю, NP-полные задачи, в силу их специфики, люди решают с помощью перебора с некоторыми эвристиками. Например, задача SAT, несмотря на свою NP-полноту, достаточно успешно решается на практике. Поэтому предлагаемый Вами алгоритм, вероятно, следует отнести к тому же классу.
Строгий математический подход необходим в любом случае. Если мы явно объявим, что решаем другую задачу, тогда можно спокойно применять математический аппарат и приходить к верным результатам.
А когда можно будет выложить исходники в паблик? Матлаб это сильно специфично. А так люди перепишут на плюсы и погоняют на множестве вариантов. Может и нелинейные варианты найдутся.
Вопрос: «Скорость выполнения алгоритма на конкретном компьютере не имеет отношения к линейному/нелинейному времени.»
— нигде в тексте нет и не может быть намека на то, что временная сложность алгоритма зависит от вычислительного устройства. Так же, выбор языка программирования не будет влиять на временную сложность. Не могу понять, откуда у Вас такая ассоциация.
Характеристики вычислительного устройства, обычно приводятся в публикациях, чтобы читатель мог оценить время выполнения тех или иных решений.
Вопрос: «…Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде»
Скриптовый язык Матлаба, это почти тот же псевдокод. В ближайшее время, исходный код с подробными комментариями, будет опубликован на Хабре. Это даст возможность проверить.
Изначально, я ставил цель оценить временную сложность на основе вычислительных экспериментов. Что, в принципе и было сделано.
Вопрос: «n-Queens Completion problem является классической не детерминированной задачей. это утверждение противоречит формулировке задачи, данной в разделе «1. Введение». Там задача сформулирована детерминировано, как и положено задачам класса NP.»
Вы затронули сложный и важный вопрос, поэтому давайте рассмотрим его чуть подробнее. Располагая ферзь в ячейку ( i, j ) матрицы решения n x n, мы, после этого, полностью исключаем строку i и столбец j. Кроме этого, мы исключаем все ячейки матрицы решения, которые расположены вдоль левой и правой диагоналей матрицы, проходящих через ячейку ( i, j ). Все действия здесь детерминированные. Но, мы не ведем учет состояния каждой ячейки матрицы решения. Ведь, даже для n=106 пришлось бы держать массив n=1012, и каждый раз проводить диагональные исключения, чтобы по ходу знать статус каждой ячейки. А как быть, если n будет равно сто миллионам? Это путь неэффективный, и нереальный для больших n. Получается, что в процессе решения задачи, мы не знаем статус ячеек в оставшихся свободных строках. Выбирая строку для расположения ферзя, мы должны:
— проверить все ячейки этой строки,
— выделить индексы свободных ячеек,
— выбрать одну из этих ячеек, так, чтобы не ошибиться.
То, что каждый раз необходимо определить статус ячейки (он неопределенный, пока это не установим) делает недетерминированным решение задачи. Хотя, изначальные действия детерминированные. Именно это имеется ввиду в тексте статьи.
Вопрос: «False Negative решения… В детерминированном алгоритме решения NP-полных задач таких решений быть не может».
False Negative решения появляются тогда, когда некое «изначально верное решение» алгоритм « считает» ошибочным. Это не связано с формулировкой задачи, это свойство алгоритма ошибаться. Чем лучше алгоритм, тем меньше False Negative решений.
В задаче n-Queens Completion встречаются композиции, для которых очень сложно найти решение. Если программа 1000 раз выполняет процедуру Back Tracking и не может комплектовать данную композицию, то дальнейший поиск прекращается. Принимается решение, что данная композиция отрицательная, хотя изначально известно, что данная композиция может быть комплектована. Это компромисс затрат времени счета и эффективности работы алгоритма.
А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом.
— нигде в тексте нет и не может быть намека на то, что временная сложность алгоритма зависит от вычислительного устройства. Так же, выбор языка программирования не будет влиять на временную сложность. Не могу понять, откуда у Вас такая ассоциация.
Характеристики вычислительного устройства, обычно приводятся в публикациях, чтобы читатель мог оценить время выполнения тех или иных решений.
Вопрос: «…Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде»
Скриптовый язык Матлаба, это почти тот же псевдокод. В ближайшее время, исходный код с подробными комментариями, будет опубликован на Хабре. Это даст возможность проверить.
Изначально, я ставил цель оценить временную сложность на основе вычислительных экспериментов. Что, в принципе и было сделано.
Вопрос: «n-Queens Completion problem является классической не детерминированной задачей. это утверждение противоречит формулировке задачи, данной в разделе «1. Введение». Там задача сформулирована детерминировано, как и положено задачам класса NP.»
Вы затронули сложный и важный вопрос, поэтому давайте рассмотрим его чуть подробнее. Располагая ферзь в ячейку ( i, j ) матрицы решения n x n, мы, после этого, полностью исключаем строку i и столбец j. Кроме этого, мы исключаем все ячейки матрицы решения, которые расположены вдоль левой и правой диагоналей матрицы, проходящих через ячейку ( i, j ). Все действия здесь детерминированные. Но, мы не ведем учет состояния каждой ячейки матрицы решения. Ведь, даже для n=106 пришлось бы держать массив n=1012, и каждый раз проводить диагональные исключения, чтобы по ходу знать статус каждой ячейки. А как быть, если n будет равно сто миллионам? Это путь неэффективный, и нереальный для больших n. Получается, что в процессе решения задачи, мы не знаем статус ячеек в оставшихся свободных строках. Выбирая строку для расположения ферзя, мы должны:
— проверить все ячейки этой строки,
— выделить индексы свободных ячеек,
— выбрать одну из этих ячеек, так, чтобы не ошибиться.
То, что каждый раз необходимо определить статус ячейки (он неопределенный, пока это не установим) делает недетерминированным решение задачи. Хотя, изначальные действия детерминированные. Именно это имеется ввиду в тексте статьи.
Вопрос: «False Negative решения… В детерминированном алгоритме решения NP-полных задач таких решений быть не может».
False Negative решения появляются тогда, когда некое «изначально верное решение» алгоритм « считает» ошибочным. Это не связано с формулировкой задачи, это свойство алгоритма ошибаться. Чем лучше алгоритм, тем меньше False Negative решений.
В задаче n-Queens Completion встречаются композиции, для которых очень сложно найти решение. Если программа 1000 раз выполняет процедуру Back Tracking и не может комплектовать данную композицию, то дальнейший поиск прекращается. Принимается решение, что данная композиция отрицательная, хотя изначально известно, что данная композиция может быть комплектована. Это компромисс затрат времени счета и эффективности работы алгоритма.
А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом.
А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этомПеребор же
я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом.Единственный алгоритм нахождения точного решения NP задач — это полный переборвариантов; иначе задача не является NP. И любой последовательный перебор является детерминированным алгоритмом — т.к. не содержит случайного выбора вариантов и потому на идентичных входных данных всегда даст идентичный ответ.
Любая эвристика, находящая близкий к оптимальному результат и не содержащая случайного выбора, тоже будет детерминированной.
Скорость выполнения алгоритма на конкретном компьютере
Зависит от целей статьи. Если Вы хотите продемонстрировать, что алгоритм имеет сложность O(n), то сведения о времени работы алгоритма на конкретном компьютере не сильно помогают. Обычно сложность можно оценить путём анализа кода алгоритма.
То, что каждый раз необходимо определить статус ячейки (он неопределенный, пока это не установим) делает недетерминированным решение задачи.
Насколько я понимаю, единственный источник недетерминированности — использование генератора случайных чисел. Во всём остальном алгоритм должен быть детерминированным, т.е. давать одинаковый результат при одинаковых входных значениях.
Ведь, даже для n=10 пришлось бы держать массив n=10, и каждый раз проводить диагональные исключения, чтобы по ходу знать статус каждой ячейки.
Как мне кажется, вы используете более подходящую структуру данных для хранения заполненности диагоналей — линейный массив, — так что нет необходимости хранить большой массив. По-видимому, этот аргумент не относится к вопросу детерминированности/недетерминированности.
False Negative решения… Это не связано с формулировкой задачи, это свойство алгоритма ошибаться.
По-моему, это как раз и говорит о том, что предложенный алгоритм исходную задачу не решает. Разве нет?
я не знаю детерминированных алгоритмов решения NP-полных задач
Что Вы имеете в виду? В свете https://ru.wikipedia.org/wiki/NP-полная_задача, насколько я понимаю, для всех NP-полных задач существуют детерминированные алгоритмы решения. Другое дело, что они могут быть непрактичны для больших n.
Вопрос: «Т.е. программа работает, но в конечном итоге, формального доказательства не будет и, очевидно никакого «прорыва» — просто качественный алгорим, который работает на подмножестве параметров.»
— ценю Ваш юмор, только давайте подойдем к вопросу серьезно. Выше я уже писал, что на основе строгого математического подхода, данную задачу и другие аналогичные задачи решить невозможно. Я утверждаю, что задачи такого класса, с большой вероятностью могут быть решены на основе алгоритмической математики с использованием Computational Simulation. Поэтому формального доказательства, в данной задаче, и других подобных задачах быть не может. Я не ставил перед собой цель строго математически доказать P=NP или P ≠ NP. Возьму на себя смелость нагло утверждать, что строго математически это никто не докажет, и что самое интересное, в этом нет никакого смысла. Нужно просто брать конкретную задачу из множества NP-Complete и «конкретно» ее решать. То, что одну из задач из этого семейства удалось решить, пока говорит только о том, что это возможно. И не более того.
Я не люблю и не использую слова «революция», «прорыв» или что-то подобное. Оно здесь не к месту. Считаю полезным концентрироваться на задаче, и если удастся – жить внутри задачи. «Там изнутри все видно».
Не знаю, как относиться к Вашим словам, про «просто качественный алгоритм, который работает на подмножестве параметров.». Воспринимаю как намек на положительную оценку. А если серьезно, то давайте подумаем. В интернет публикации n-Queens bibliography — 342 references приводятся ссылки на 342 статьи, которые прямо или косвенно, относятся к тематике n-Queens Problem. Можете найти хотя бы одну публикацию, в которой использовался такой огромный объем результатов вычислительных экспериментов. Ведь я рассматривал диапазон значений размера шахматной доски от 7 до 100 миллионов. Причем, там, где это было приемлемо по времени, размер сформированной выборки составлял один миллион. Это только для одного конкретного значения n. Прежде чем вынести полученные результаты на обсуждение, алгоритм многократно тестировался. Не будет ошибкой, если я скажу, что за полтора года алгоритм тестировался несколько десятков миллионов раз.
« Про дядю Вову»
В России только «один дядя Вова», думал Вы про него. Раскрыл – оказалось совсем другое.
Не может быть и речи о том, что «информацию сжимал». Я готов предоставить любому члену нашего Хабра-Сообщества исходный текст программы (на Матлабе) для всевозможного прогона. Об этом я писал в предисловии к статье. Это важная и сильная составляющая Хабра-Сообщества, когда члены сообщества могут свободно проверить те или иные алгоритмы и открыто высказать свое мнение.
— ценю Ваш юмор, только давайте подойдем к вопросу серьезно. Выше я уже писал, что на основе строгого математического подхода, данную задачу и другие аналогичные задачи решить невозможно. Я утверждаю, что задачи такого класса, с большой вероятностью могут быть решены на основе алгоритмической математики с использованием Computational Simulation. Поэтому формального доказательства, в данной задаче, и других подобных задачах быть не может. Я не ставил перед собой цель строго математически доказать P=NP или P ≠ NP. Возьму на себя смелость нагло утверждать, что строго математически это никто не докажет, и что самое интересное, в этом нет никакого смысла. Нужно просто брать конкретную задачу из множества NP-Complete и «конкретно» ее решать. То, что одну из задач из этого семейства удалось решить, пока говорит только о том, что это возможно. И не более того.
Я не люблю и не использую слова «революция», «прорыв» или что-то подобное. Оно здесь не к месту. Считаю полезным концентрироваться на задаче, и если удастся – жить внутри задачи. «Там изнутри все видно».
Не знаю, как относиться к Вашим словам, про «просто качественный алгоритм, который работает на подмножестве параметров.». Воспринимаю как намек на положительную оценку. А если серьезно, то давайте подумаем. В интернет публикации n-Queens bibliography — 342 references приводятся ссылки на 342 статьи, которые прямо или косвенно, относятся к тематике n-Queens Problem. Можете найти хотя бы одну публикацию, в которой использовался такой огромный объем результатов вычислительных экспериментов. Ведь я рассматривал диапазон значений размера шахматной доски от 7 до 100 миллионов. Причем, там, где это было приемлемо по времени, размер сформированной выборки составлял один миллион. Это только для одного конкретного значения n. Прежде чем вынести полученные результаты на обсуждение, алгоритм многократно тестировался. Не будет ошибкой, если я скажу, что за полтора года алгоритм тестировался несколько десятков миллионов раз.
« Про дядю Вову»
В России только «один дядя Вова», думал Вы про него. Раскрыл – оказалось совсем другое.
Не может быть и речи о том, что «информацию сжимал». Я готов предоставить любому члену нашего Хабра-Сообщества исходный текст программы (на Матлабе) для всевозможного прогона. Об этом я писал в предисловии к статье. Это важная и сильная составляющая Хабра-Сообщества, когда члены сообщества могут свободно проверить те или иные алгоритмы и открыто высказать свое мнение.
>> n-Queens Completion Problem — линейный алгоритм решения
Вопросы выше связаны с неправильным названием статьи. Тема «n-Queens Completion Problem» предполагает именно строгое математическое решение, без ложно-негативных и прочих недетерминированных. Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?
Проблема в общем случае за линейное время не решается. Есть набор эвристик, которые в среднем дают хороший результат, но в частных случаях уводят время в полиномиальное, а то и в экспоненциальное. Собственно противоречие между заявлением про «линейное время» и заявленной темой (n-Queens Completion Problem) и составляют суть комментариев выше (от тех, кто решил возразить).
Ну а для тех, кто ничего не понял, действительно стоит подать содержимое покороче. Например — выбран набор эвристик, позволяющий в среднем в большинстве случаев получить решение задачи за линейное время. В некоторых частных случаях линейное время остаётся недостижимым и n-Queens Completion Problem остаётся нерешённой.
Хотя вообще, автор проделал большой труд и убил очень много времени. Поэтому он молодец. Но всё же пока что его результат неидеален. Идеал — это линейное время во всех случаях.
Как получить идеальное решение? Вот рядом есть статья с вроде бы далёкой темой, но очень показательная. Там предлагается решить проблему сходимости реккурентной последовательности вида x/2=y => y*3+1=x. В той проблеме точно так же, как и в проблеме ферзей, возможны алгоритмические решения, не дающие при этом общего подхода. При этом проблема хороша своей простотой, а потому в ней легко выделить узкое место, которое нужно доказать для получения общего подхода. Там всё сводится к получение доказательства обязательного ухода последовательности к нечётным значениям, менее стартового. Это очевидно на примере частного случая более общей задачи вида x/k1=y => y*k2+1=x. Самый простой частный случай такой — x/2=y => y*1+1=x. В последнем случае очевидно, что (y+1)/2 всегда будет меньше y, а потому такая последовательность всегда сойдётся в единицу. Что это означает для автора статьи про ферзей?
Автору нужно выделить такую же узкую проблему, как показано выше для задачи с реккурентной последовательностью. И далее доказать, что узкая проблема неизбежно решается в рамках таких ограничений, которые приводят к гарантированному наличию решения задачи ферзей. Вот так вот всё просто. И вот так вот всё сложно.
Вопросы выше связаны с неправильным названием статьи. Тема «n-Queens Completion Problem» предполагает именно строгое математическое решение, без ложно-негативных и прочих недетерминированных. Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?
Проблема в общем случае за линейное время не решается. Есть набор эвристик, которые в среднем дают хороший результат, но в частных случаях уводят время в полиномиальное, а то и в экспоненциальное. Собственно противоречие между заявлением про «линейное время» и заявленной темой (n-Queens Completion Problem) и составляют суть комментариев выше (от тех, кто решил возразить).
Ну а для тех, кто ничего не понял, действительно стоит подать содержимое покороче. Например — выбран набор эвристик, позволяющий в среднем в большинстве случаев получить решение задачи за линейное время. В некоторых частных случаях линейное время остаётся недостижимым и n-Queens Completion Problem остаётся нерешённой.
Хотя вообще, автор проделал большой труд и убил очень много времени. Поэтому он молодец. Но всё же пока что его результат неидеален. Идеал — это линейное время во всех случаях.
Как получить идеальное решение? Вот рядом есть статья с вроде бы далёкой темой, но очень показательная. Там предлагается решить проблему сходимости реккурентной последовательности вида x/2=y => y*3+1=x. В той проблеме точно так же, как и в проблеме ферзей, возможны алгоритмические решения, не дающие при этом общего подхода. При этом проблема хороша своей простотой, а потому в ней легко выделить узкое место, которое нужно доказать для получения общего подхода. Там всё сводится к получение доказательства обязательного ухода последовательности к нечётным значениям, менее стартового. Это очевидно на примере частного случая более общей задачи вида x/k1=y => y*k2+1=x. Самый простой частный случай такой — x/2=y => y*1+1=x. В последнем случае очевидно, что (y+1)/2 всегда будет меньше y, а потому такая последовательность всегда сойдётся в единицу. Что это означает для автора статьи про ферзей?
Автору нужно выделить такую же узкую проблему, как показано выше для задачи с реккурентной последовательностью. И далее доказать, что узкая проблема неизбежно решается в рамках таких ограничений, которые приводят к гарантированному наличию решения задачи ферзей. Вот так вот всё просто. И вот так вот всё сложно.
Вопрос:
«А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом
Перебор же »
— Я в самом деле не встречал публикаций, в которых приводится детерминированный алгоритм решения какой-либо из NP-полных задач в широком диапазоне изменчивости основного параметра задачи. Мне реально это интересно, поэтому, если Вы знаете такую публикацию, выложите ссылку.
Решить задачу детерминировано, означает последовательно формировать ветвь поиска решения от начала до конца, нигде не «спотыкаясь». Это означает получить решение задачи, и ни разу не использовать процедуру Back Tracking, так как идете «верной дорогой». Можете Вы привести какой либо алгоритм решения одной из задач семейства NP-Complete, в которой бы не использовалась процедура Back Tracking?
Думаю, что не удастся. Мы выполняем Back Tracking и возвращаемся назад, чтобы с какой-то позиции снова продолжать строить ветвь поиска решения, надеясь, что «на этот раз повезет» и дойдем до цели. Если есть Back Tracking, значит есть неопределенность в том, что выбирать. Чем меньше число случаев использования процедуры Back Tracking, тем более эффективным является алгоритм.
Я целенаправленно занимался этим вопросом, после того, как был разработан алгоритм решения n-Queens Completion Problem. Это заняло слишком много времени, но, в итоге удалось изменить алгоритм таким образом, что на достаточно широком интервале значений n, в 50% случаях процедура Back Tracking ни разу не используется при формировании полного решения.
«А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом
Перебор же »
— Я в самом деле не встречал публикаций, в которых приводится детерминированный алгоритм решения какой-либо из NP-полных задач в широком диапазоне изменчивости основного параметра задачи. Мне реально это интересно, поэтому, если Вы знаете такую публикацию, выложите ссылку.
Решить задачу детерминировано, означает последовательно формировать ветвь поиска решения от начала до конца, нигде не «спотыкаясь». Это означает получить решение задачи, и ни разу не использовать процедуру Back Tracking, так как идете «верной дорогой». Можете Вы привести какой либо алгоритм решения одной из задач семейства NP-Complete, в которой бы не использовалась процедура Back Tracking?
Думаю, что не удастся. Мы выполняем Back Tracking и возвращаемся назад, чтобы с какой-то позиции снова продолжать строить ветвь поиска решения, надеясь, что «на этот раз повезет» и дойдем до цели. Если есть Back Tracking, значит есть неопределенность в том, что выбирать. Чем меньше число случаев использования процедуры Back Tracking, тем более эффективным является алгоритм.
Я целенаправленно занимался этим вопросом, после того, как был разработан алгоритм решения n-Queens Completion Problem. Это заняло слишком много времени, но, в итоге удалось изменить алгоритм таким образом, что на достаточно широком интервале значений n, в 50% случаях процедура Back Tracking ни разу не используется при формировании полного решения.
Ваш комментарий показывает только то, что вы не понимаете смысл термина «детерминированный алгоритм». Единственным критерием детерминированности алгоритма является то, что он всегда возвращает один и тот же результат на одних и тех же входных данных. И это всё!
Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.
Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.
Ваше понимание "детерминированности" очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — http://rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.
Вопрос: ««Единственный алгоритм нахождения точного решения NP-полных задач — это полный перебор всех возможных вариантов; иначе задача не является NP-полной.»
Мне кажется, что Вы хотели написать что-то очень интересное, но оно не так вышло. Вот смотрите, одна из задач из множества NP-Complete (n-Queens Completion Problem). Пусть размер стороны шахматной доски n=100. Число способов выбора в произвольном порядке 100 строк для расположения ферзя равно 100!.. Когда мы выбираем строку, то среди оставшихся свободных позиций, мы должны выбрать одну позицию, чтобы расположить там ферзь. Среднее число всех возможных вариантов выбора произвольной свободной позиции во всех строках равно 10124 (это значение получено на основе 100 000 вычислительных экспериментов). Итого, пространство перебора всех возможных вариантов составляет 100! * 10124. Представим себе, что на шахматной доске 100 х 100 правильно расставлена композиция из 27 ферзей. Вы полагаете, что для комплектации данной композиции до полного решения мне нужен «полный перебор всех возможных вариантов»? Этого категорически делать не надо. Наоборот, цель будет состоять в том, чтобы максимально избегать этого. Нужно найти правила, которые позволят «лавировать» в этом огромном пространстве выбора и достичь своей цели. Нужно «стараться знать», что выбирать на каждом шаге, чтобы не ошибиться и дойти до цели.
«…иначе задача не является NP-полной»
Вы грамотный специалист, советую посмотреть определение NP-Complete задач. Необходимость полного перебора всех возможных вариантов никак не связано с тем, относится ли задача к множеству NP-Complete.
Мне кажется, что Вы хотели написать что-то очень интересное, но оно не так вышло. Вот смотрите, одна из задач из множества NP-Complete (n-Queens Completion Problem). Пусть размер стороны шахматной доски n=100. Число способов выбора в произвольном порядке 100 строк для расположения ферзя равно 100!.. Когда мы выбираем строку, то среди оставшихся свободных позиций, мы должны выбрать одну позицию, чтобы расположить там ферзь. Среднее число всех возможных вариантов выбора произвольной свободной позиции во всех строках равно 10124 (это значение получено на основе 100 000 вычислительных экспериментов). Итого, пространство перебора всех возможных вариантов составляет 100! * 10124. Представим себе, что на шахматной доске 100 х 100 правильно расставлена композиция из 27 ферзей. Вы полагаете, что для комплектации данной композиции до полного решения мне нужен «полный перебор всех возможных вариантов»? Этого категорически делать не надо. Наоборот, цель будет состоять в том, чтобы максимально избегать этого. Нужно найти правила, которые позволят «лавировать» в этом огромном пространстве выбора и достичь своей цели. Нужно «стараться знать», что выбирать на каждом шаге, чтобы не ошибиться и дойти до цели.
«…иначе задача не является NP-полной»
Вы грамотный специалист, советую посмотреть определение NP-Complete задач. Необходимость полного перебора всех возможных вариантов никак не связано с тем, относится ли задача к множеству NP-Complete.
С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно
Вопрос:
«Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.»
Я хочу попросить Вас, все таки, не спешить и вникнуть в суть того, что сказано. Фраза «С помощью строгих математических методов» — означает, только то, что проблема решается только на основе определений, формулировке лемм и доказательстве теорем. Без применения методов алгоритмической математики и компьютерного моделирования. А каком «полиномиальном времени» строгих математических методов Вы говорите.
«прямым перебором или обычным backtracking'ом»
— Back Tracking является неотъемлемым компонентом прямого перебора, для поиска всех решений. Поэтому, здесь «или» не уместна. Когда Вы ищите все возможные решения, то постоянно «заходите» в тот или иной тупик, и вынуждены возвращаться назад на один шаг назад (если опять тупик — то на два или более шагов назад). Для этого Вы должны запомнить все основные параметры нескольких последовательных уровней, чтобы можно было восстановить исходное состояние на данном уровне. Попробуйте, это все очень интересно.
Вопрос:
«Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.»
Я хочу попросить Вас, все таки, не спешить и вникнуть в суть того, что сказано. Фраза «С помощью строгих математических методов» — означает, только то, что проблема решается только на основе определений, формулировке лемм и доказательстве теорем. Без применения методов алгоритмической математики и компьютерного моделирования. А каком «полиномиальном времени» строгих математических методов Вы говорите.
«прямым перебором или обычным backtracking'ом»
— Back Tracking является неотъемлемым компонентом прямого перебора, для поиска всех решений. Поэтому, здесь «или» не уместна. Когда Вы ищите все возможные решения, то постоянно «заходите» в тот или иной тупик, и вынуждены возвращаться назад на один шаг назад (если опять тупик — то на два или более шагов назад). Для этого Вы должны запомнить все основные параметры нескольких последовательных уровней, чтобы можно было восстановить исходное состояние на данном уровне. Попробуйте, это все очень интересно.
Ваше понимание "строгих математических методов", на мой взгляд, узко. Обычные алгоритмы являются вполне себе строгими и математическими. Можно даже доказать, что алгоритм решает задачу. Например, алгоритм Евклида для поиска НОД. Или http://toccata.lri.fr/gallery/why3.en.html — целый ряд алгоритмов, доказанных математически.
Back Tracking является неотъемлемым компонентом прямого перебора
Боюсь, не могу с Вами согласиться. Back tracking — это лишь один из способов обхода решений. Простейший перебор всех вариантов:
for k = 0..n^n-1
for i = 0..n-1
q[i] = k / n^i % nС проверкой каждого варианта (O(n)) сложность получается O(n^n*n^2) — экспоненциальная. Такой алгоритм, очевидно, не содержит backtracking'а.
Коммент:
«Вопросы выше связаны с неправильным названием статьи. Тема «n-Queens Completion Problem» предполагает именно строгое математическое решение, без ложно-негативных и прочих недетерминированных. Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?»
Я снова хочу сказать, что n-Queens Completion Problem и другие проблемы подобного рода невозможно решить на основе строгих математических методов. Они могут быть решены на основе алгоритмической математики с применением Computational Simulation. Об этом, в ответах на комментарии, я уже писал несколько раз. В статье есть раздел «Замечание», и там есть «Философское замечание» с примером, который достаточно нагляден, и позволит ответить на поставленный вопрос. Будет правильно, если, все таки, Вы посмотрите хотя бы этот раздел.
Коммент:
«Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?»
В реальности, данный алгоритм имеет линейную временную сложность. Размер выборки случайных композиций, которые были сформированы для определения времени решения n-Queens Completion Problem для n=1000, был равен одному миллиону. Это была своего рода контрольная точка. Для остальных значений n, из базового списка значений, размер выборки составлял 100 000 или меньше. Во всех случаях распределение времени решения для различных значений n является унимодальным, с длинным правым хвостом. Думаю, что объективное свойство именно данной задачи, а не алгоритма. Какой бы ни был замечательный алгоритм решения данной задачи, всегда будут «неудобные» композиции, которые потребуют большего времени для комплектации. Так вот, в статье я использовал среднее значение выборки времени решения для каждого значения n, и на его основе был построен график и были сделаны соответствующие выводы. Если в качестве основной характеристики времени счета использовать: модальное значение, медианное значение, минимальное значение, максимальное значение или усредненное значение из ограниченного интервала в единицах стандартного отклонения, то во всех случаях (подчеркиваю, во всех случаях) временная сложность алгоритма оказывается линейной. Я выбрал среднее значение как наиболее «содержательную» характеристику времени счета. Еще раз хочу ответить на Ваш вопрос – это то, что мы видим в реальности.
Коммент:
«Проблема в общем случае за линейное время не решается. Есть набор эвристик, которые в среднем дают хороший результат, но в частных случаях уводят время в полиномиальное, а то и в экспоненциальное. Собственно противоречие между заявлением про «линейное время» и заявленной темой (n-Queens Completion Problem) и составляют суть комментариев выше (от тех, кто решил возразить).»
Я, в общем случае, проблему решения задач из семейства NP-Complete нигде в публикации не рассматривал. Всюду речь идет только об одной конкретной задаче: n-Queens Completion. Я не могу говорить за все задачи из этого семейства, но конкретно про n-Queens Completion я утверждаю, что предложенный алгоритм решает данную задачу за линейное время. Причем, на всем диапазоне значений n от 7 до 100 миллионов. Это же легко проверить, я уже полдня объясняю это уважаемым коллегам. Зачем выдумывать что-то с потолка, если можно потратить 10-15 минут и убедиться в этом.
Как можно утверждать, что алгоритм «в частных случаях уводят время в полиномиальное, а то и в экспоненциальное». Откуда это следует? Как я писал выше, какой бы показатель распределения времени счета вы не выбрали, вы получите график, который показывает, что временная сложность является линейной. Ваше высказывание эквивалентно утверждению, что данные в таблице 2 неверные. Хотя, возможно, Вы что-то другое имели ввиду.
Коммент:
«Хотя вообще, автор проделал большой труд и убил очень много времени. Поэтому он молодец. Но всё же пока что его результат неидеален. Идеал — это линейное время во всех случаях.»
Спасибо, что сказали доброе слово в мой адрес. Хоть кто-то, сознательный об этом подумал.
Я не знаю, как выглядит идеальный алгоритм, поэтому использую термин эффективный. Хотя, ни тот не другой не имеют объективной единицы измерения, и при сравнении двух алгоритмов, решающих одну и ту же задачу, все сводится к временной сложности, сложности по требуемой памяти и т.д.
Если, Вы считаете, что «Идеал — это линейное время во всех случаях.», то я хочу снова подтвердить, что здесь линейное время во всех случаях, хотя это я еще не считаю идеалом.
«Вопросы выше связаны с неправильным названием статьи. Тема «n-Queens Completion Problem» предполагает именно строгое математическое решение, без ложно-негативных и прочих недетерминированных. Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?»
Я снова хочу сказать, что n-Queens Completion Problem и другие проблемы подобного рода невозможно решить на основе строгих математических методов. Они могут быть решены на основе алгоритмической математики с применением Computational Simulation. Об этом, в ответах на комментарии, я уже писал несколько раз. В статье есть раздел «Замечание», и там есть «Философское замечание» с примером, который достаточно нагляден, и позволит ответить на поставленный вопрос. Будет правильно, если, все таки, Вы посмотрите хотя бы этот раздел.
Коммент:
«Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?»
В реальности, данный алгоритм имеет линейную временную сложность. Размер выборки случайных композиций, которые были сформированы для определения времени решения n-Queens Completion Problem для n=1000, был равен одному миллиону. Это была своего рода контрольная точка. Для остальных значений n, из базового списка значений, размер выборки составлял 100 000 или меньше. Во всех случаях распределение времени решения для различных значений n является унимодальным, с длинным правым хвостом. Думаю, что объективное свойство именно данной задачи, а не алгоритма. Какой бы ни был замечательный алгоритм решения данной задачи, всегда будут «неудобные» композиции, которые потребуют большего времени для комплектации. Так вот, в статье я использовал среднее значение выборки времени решения для каждого значения n, и на его основе был построен график и были сделаны соответствующие выводы. Если в качестве основной характеристики времени счета использовать: модальное значение, медианное значение, минимальное значение, максимальное значение или усредненное значение из ограниченного интервала в единицах стандартного отклонения, то во всех случаях (подчеркиваю, во всех случаях) временная сложность алгоритма оказывается линейной. Я выбрал среднее значение как наиболее «содержательную» характеристику времени счета. Еще раз хочу ответить на Ваш вопрос – это то, что мы видим в реальности.
Коммент:
«Проблема в общем случае за линейное время не решается. Есть набор эвристик, которые в среднем дают хороший результат, но в частных случаях уводят время в полиномиальное, а то и в экспоненциальное. Собственно противоречие между заявлением про «линейное время» и заявленной темой (n-Queens Completion Problem) и составляют суть комментариев выше (от тех, кто решил возразить).»
Я, в общем случае, проблему решения задач из семейства NP-Complete нигде в публикации не рассматривал. Всюду речь идет только об одной конкретной задаче: n-Queens Completion. Я не могу говорить за все задачи из этого семейства, но конкретно про n-Queens Completion я утверждаю, что предложенный алгоритм решает данную задачу за линейное время. Причем, на всем диапазоне значений n от 7 до 100 миллионов. Это же легко проверить, я уже полдня объясняю это уважаемым коллегам. Зачем выдумывать что-то с потолка, если можно потратить 10-15 минут и убедиться в этом.
Как можно утверждать, что алгоритм «в частных случаях уводят время в полиномиальное, а то и в экспоненциальное». Откуда это следует? Как я писал выше, какой бы показатель распределения времени счета вы не выбрали, вы получите график, который показывает, что временная сложность является линейной. Ваше высказывание эквивалентно утверждению, что данные в таблице 2 неверные. Хотя, возможно, Вы что-то другое имели ввиду.
Коммент:
«Хотя вообще, автор проделал большой труд и убил очень много времени. Поэтому он молодец. Но всё же пока что его результат неидеален. Идеал — это линейное время во всех случаях.»
Спасибо, что сказали доброе слово в мой адрес. Хоть кто-то, сознательный об этом подумал.
Я не знаю, как выглядит идеальный алгоритм, поэтому использую термин эффективный. Хотя, ни тот не другой не имеют объективной единицы измерения, и при сравнении двух алгоритмов, решающих одну и ту же задачу, все сводится к временной сложности, сложности по требуемой памяти и т.д.
Если, Вы считаете, что «Идеал — это линейное время во всех случаях.», то я хочу снова подтвердить, что здесь линейное время во всех случаях, хотя это я еще не считаю идеалом.
>> предложенный алгоритм решает данную задачу за линейное время
Не решает.
Вы сами в другом ответе заявили, что после 1000 возвратов работа алгоритма прерывается и задача считается нерешаемой. То есть вы исключили сложные случаи и заявляете, что раз все остальные решаются за линейное время, то значит все случаи решаются за линейное время, что является очевидным ложным утверждением.
Теперь вы будете оспаривать слово «все», но я вам ещё раз приведу цитату из вашего сообщения:
То есть вы путаете смысл слова «все» со смыслом фразы «почти все». Ну и упорно не желаете признавать сей прискорбный факт.
Возможно, вам стоит перечитать это сообщение ещё раз (да и другие тоже). Мне кажется, что вы просто невнимательны. Вы зациклились на идее «победы», мол вот я достиг линейной скорости, а эти все «нехорошие люди» меня не понимают. Но проблема в том, что как раз вы не понимаете «нехороших людей», а они-то вам всего лишь пытаются донести истинное положение вещей.
Не решает.
Вы сами в другом ответе заявили, что после 1000 возвратов работа алгоритма прерывается и задача считается нерешаемой. То есть вы исключили сложные случаи и заявляете, что раз все остальные решаются за линейное время, то значит все случаи решаются за линейное время, что является очевидным ложным утверждением.
Теперь вы будете оспаривать слово «все», но я вам ещё раз приведу цитату из вашего сообщения:
предложенный алгоритм решает данную задачу за линейное время
То есть вы путаете смысл слова «все» со смыслом фразы «почти все». Ну и упорно не желаете признавать сей прискорбный факт.
Возможно, вам стоит перечитать это сообщение ещё раз (да и другие тоже). Мне кажется, что вы просто невнимательны. Вы зациклились на идее «победы», мол вот я достиг линейной скорости, а эти все «нехорошие люди» меня не понимают. Но проблема в том, что как раз вы не понимаете «нехороших людей», а они-то вам всего лишь пытаются донести истинное положение вещей.
Давайте вместе выясним, как Вы говорите «истинное положение вещей». (Надеюсь, что Вы внимательно прочитали текст публикации)
1. Все случайные композиции, размера k для произвольной шахматной доски размера n x n, условно можно разделить на два множества:
a) композиции, которые можно комплектовать до полного решения, в статье такие композиции называются «положительными»
b) композиции, которые невозможно комплектовать до полного решения, в статье такие композиции называются «отрицательными»
2. Как определить, является ли композиция положительной или отрицательной?
В предложенном алгоритме, заложено правило: «при формировании ветви поиска решения, на каждом шаге, прежде, чем установить ферзь, проверяется, свободна ли данная ячейка».
3. Это имеет принципиально важное значение. Это означает, что какую бы отрицательную композицию мы не рассматривали, алгоритм все время будет находиться в состоянии счета, пока не остановим.
4. С другой стороны, если алгоритм эффективный, то он должен быть в состоянии комплектовать любую положительную композицию за определенное время. Если мы сможем установить границу, когда любая положительная композиция обязательно комплектуется, то, после этой границы, композиция относится к множеству отрицательных композиций (так как никак не комплектуется).
5 Как установить границу, разделяющую зону, до которой все положительные композиции комплектуются?
Для этого был проведен, достаточно длительный по времени, вычислительный эксперимент:
Приведу текст из статьи с небольшим добавлением:
« Вначале был разработан достаточно быстрый алгоритм формирования массивов решений nQueens Problem для произвольного значения n.
Потом, на основе этой программы были сформированы большие выборки решений для базового списка значений n.
Размеры полученных выборок решений nQueens Problem для различных значений n, соответственно были равны:
(10)--1000,
(20, 30, …, 90, 100, 200, 300, 500, 800, 1000, 3000, 5000,10000)--10000,
(30 000, 50 000, 80 000)--5000,
(100 000, 300 000)--3000,
(500 000, 800 000, 1 000 000)--1000,
(3 000 000)--300,
(5 000 000)--200,
(10 000 000)--100,
(30 000 000)--50,
(50 000 000)--30,
(80 000 000, 100 000000)--20.
Здесь, в скобках указывается список значений n, а через двойное тире — размер выборки полученных решений. После этого, на основе каждой выборки решений формировались достаточно большие выборки случайных композиции произвольного размера (см. Таблицу 2). Например, для каждого из 10 000 решений для n=1000, было сформировано по 100 случайных композиций произвольного размера. В результате была получена выборка из одного миллиона композиций. Так как любая композиция произвольного размера, сформированная на основе существующего решения, может быть комплектована до полного решения хотя бы один раз, то задача состояла в том, чтобы на основе алгоритма решения n-Queens Completion Problem, комплектовать каждую композицию из сформированной выборки до полного решения.»
В результате анализа полученных данных, было установлено, все положительные композиции (за небольшим исключением) комплектуются до полного решения, если допустить, чтобы процедура Back Tracking могла быть использована в программе до 1000 раз. При этом, в ряде выборок положительных композиций, были такие, которые не были комплектованы до полного решения. Количество таких False Negative решений приведено в таблице. Их доля в выборке не превышает 0.0001, и уменьшается с ростом значения n.
(Следует отметить, что изначально не было понятно, что выбрать в качестве меры для формирования границы. Число случаев применения процедуры Back Tracking для этого хорошо подходит.)
6. После того, как было определено значение границы, было сформулировано правило, на основе которого работает алгоритм: «Если, на вход программы подается произвольная случайная композиция, то допускается до 1000 случаев применения процедуры Back Tracking. Если композиция положительная, то решение будет найдено, и мы получим результат. Если процедура Back Tracking выполняется 1000 раз, и решение не найдено, то композиция считается отрицательной. Значение ошибки при принятии такого решения не превышает 0.0001.
7. Если увеличить граничное значение до 2000, то уменьшится доля False Negative решений (т.е. уменьшится значение ошибки принятия решения), но увеличится время ожидания, когда будет принято решение, что композиция является отрицательной. Значение 1000 оказалось достаточным, чтобы получить эффективное решение.
Заданный Вами вопрос касается сути рассматриваемой проблемы. Если, и далее, что-то будет непонятно, напишите — я на них отвечу. Только, прошу Вас, войти в русло нормальной дискуссии. Не следует использовать фразы: »… упорно не желаете признавать сей прискорбный факт.", "… зациклились на идее «победы»". Я не думаю. что это Ваша обычная манера разговора.
1. Все случайные композиции, размера k для произвольной шахматной доски размера n x n, условно можно разделить на два множества:
a) композиции, которые можно комплектовать до полного решения, в статье такие композиции называются «положительными»
b) композиции, которые невозможно комплектовать до полного решения, в статье такие композиции называются «отрицательными»
2. Как определить, является ли композиция положительной или отрицательной?
В предложенном алгоритме, заложено правило: «при формировании ветви поиска решения, на каждом шаге, прежде, чем установить ферзь, проверяется, свободна ли данная ячейка».
3. Это имеет принципиально важное значение. Это означает, что какую бы отрицательную композицию мы не рассматривали, алгоритм все время будет находиться в состоянии счета, пока не остановим.
4. С другой стороны, если алгоритм эффективный, то он должен быть в состоянии комплектовать любую положительную композицию за определенное время. Если мы сможем установить границу, когда любая положительная композиция обязательно комплектуется, то, после этой границы, композиция относится к множеству отрицательных композиций (так как никак не комплектуется).
5 Как установить границу, разделяющую зону, до которой все положительные композиции комплектуются?
Для этого был проведен, достаточно длительный по времени, вычислительный эксперимент:
Приведу текст из статьи с небольшим добавлением:
« Вначале был разработан достаточно быстрый алгоритм формирования массивов решений nQueens Problem для произвольного значения n.
Потом, на основе этой программы были сформированы большие выборки решений для базового списка значений n.
Размеры полученных выборок решений nQueens Problem для различных значений n, соответственно были равны:
(10)--1000,
(20, 30, …, 90, 100, 200, 300, 500, 800, 1000, 3000, 5000,10000)--10000,
(30 000, 50 000, 80 000)--5000,
(100 000, 300 000)--3000,
(500 000, 800 000, 1 000 000)--1000,
(3 000 000)--300,
(5 000 000)--200,
(10 000 000)--100,
(30 000 000)--50,
(50 000 000)--30,
(80 000 000, 100 000000)--20.
Здесь, в скобках указывается список значений n, а через двойное тире — размер выборки полученных решений. После этого, на основе каждой выборки решений формировались достаточно большие выборки случайных композиции произвольного размера (см. Таблицу 2). Например, для каждого из 10 000 решений для n=1000, было сформировано по 100 случайных композиций произвольного размера. В результате была получена выборка из одного миллиона композиций. Так как любая композиция произвольного размера, сформированная на основе существующего решения, может быть комплектована до полного решения хотя бы один раз, то задача состояла в том, чтобы на основе алгоритма решения n-Queens Completion Problem, комплектовать каждую композицию из сформированной выборки до полного решения.»
В результате анализа полученных данных, было установлено, все положительные композиции (за небольшим исключением) комплектуются до полного решения, если допустить, чтобы процедура Back Tracking могла быть использована в программе до 1000 раз. При этом, в ряде выборок положительных композиций, были такие, которые не были комплектованы до полного решения. Количество таких False Negative решений приведено в таблице. Их доля в выборке не превышает 0.0001, и уменьшается с ростом значения n.
(Следует отметить, что изначально не было понятно, что выбрать в качестве меры для формирования границы. Число случаев применения процедуры Back Tracking для этого хорошо подходит.)
6. После того, как было определено значение границы, было сформулировано правило, на основе которого работает алгоритм: «Если, на вход программы подается произвольная случайная композиция, то допускается до 1000 случаев применения процедуры Back Tracking. Если композиция положительная, то решение будет найдено, и мы получим результат. Если процедура Back Tracking выполняется 1000 раз, и решение не найдено, то композиция считается отрицательной. Значение ошибки при принятии такого решения не превышает 0.0001.
7. Если увеличить граничное значение до 2000, то уменьшится доля False Negative решений (т.е. уменьшится значение ошибки принятия решения), но увеличится время ожидания, когда будет принято решение, что композиция является отрицательной. Значение 1000 оказалось достаточным, чтобы получить эффективное решение.
Заданный Вами вопрос касается сути рассматриваемой проблемы. Если, и далее, что-то будет непонятно, напишите — я на них отвечу. Только, прошу Вас, войти в русло нормальной дискуссии. Не следует использовать фразы: »… упорно не желаете признавать сей прискорбный факт.", "… зациклились на идее «победы»". Я не думаю. что это Ваша обычная манера разговора.
Все это никак не противоречит тому, о чем говорит ваш оппонент. Вы используете некоторые термины, но их общепринятое понимание отличается от того, что подразумеваете под ними вы.
И снова вынужден повторить — вы сами пишете про наличие вариантов, решения для которых ваш алгоритм не может найти за линейное время, но тем не менее продолжаете настаивать на своём.
Вот ваши слова:
Здесь вы обосновываете предел, после которого алгоритм «сдаётся» и перестаёт искать решения. Но вы поймите одну простую вещь — решение задачи не принимается, если хоть один вариант алгоритм не осилил. А вы сами указываете, что не менее 100 решений из миллиона ваш алгоритм отказывается «досчитывать». То есть алгоритм не находит всех решений. Решение, вполне возможно, есть, но вы его не ищете, потому что это угрожает «линейности» решения задачи. Но тогда разве вы решили задачу?
Вы нашли способ получения близкого к линейному алгоритма для некоторых комбинаций. Для всех остальных (которых 100 на миллион) вы задачу не решили. Потому что вы не довели программу до состояния, когда она найдёт все возможные решения. И да, при этом время вполне может стать экспоненциальным. И да, это убьёт заявление про решение задачи за линейное время. Но извините — такова истина.
Ещё раз — вы решили не задачу про ферзей, а вы нашли способ отсечения сложных вариантов. Если их не отсекать — задача (если вообще будет решена) перейдёт в разряд нелинейных. Какая точно там будет зависимость — должны выяснить вы. Потому что это объективная потребность реального исследователя. И в итоге нужно признать свою неправоту. Ну либо продемонстрировать всем, что ваша программа не исключает ни одного варианта и при этом сохраняет линейную скорость (да хотя бы полиномиальную). Но вы же этого не продемонстрировали. Так против чего вы возражаете? Против указания на неполноту вашей собственной работы?
Я понимаю, что потраченного времени жаль, но к сожалению, работа реально неполная. Я сам когда-то давно удивлялся «ну что они все такие упёртые, не понимают, как я тут всё круто изобрёл!». Но потом всё же углубился в причины возражений и понял, что «изобрёл» я всего лишь часть решения. А без оставшейся части оно никому не интересно. Вот такая вот жизнь.
Вот ваши слова:
После того, как было определено значение границы, было сформулировано правило, на основе которого работает алгоритм: «Если, на вход программы подается произвольная случайная композиция, то допускается до 1000 случаев применения процедуры Back Tracking. Если композиция положительная, то решение будет найдено, и мы получим результат. Если процедура Back Tracking выполняется 1000 раз, и решение не найдено, то композиция считается отрицательной. Значение ошибки при принятии такого решения не превышает 0.0001.
Здесь вы обосновываете предел, после которого алгоритм «сдаётся» и перестаёт искать решения. Но вы поймите одну простую вещь — решение задачи не принимается, если хоть один вариант алгоритм не осилил. А вы сами указываете, что не менее 100 решений из миллиона ваш алгоритм отказывается «досчитывать». То есть алгоритм не находит всех решений. Решение, вполне возможно, есть, но вы его не ищете, потому что это угрожает «линейности» решения задачи. Но тогда разве вы решили задачу?
Вы нашли способ получения близкого к линейному алгоритма для некоторых комбинаций. Для всех остальных (которых 100 на миллион) вы задачу не решили. Потому что вы не довели программу до состояния, когда она найдёт все возможные решения. И да, при этом время вполне может стать экспоненциальным. И да, это убьёт заявление про решение задачи за линейное время. Но извините — такова истина.
Ещё раз — вы решили не задачу про ферзей, а вы нашли способ отсечения сложных вариантов. Если их не отсекать — задача (если вообще будет решена) перейдёт в разряд нелинейных. Какая точно там будет зависимость — должны выяснить вы. Потому что это объективная потребность реального исследователя. И в итоге нужно признать свою неправоту. Ну либо продемонстрировать всем, что ваша программа не исключает ни одного варианта и при этом сохраняет линейную скорость (да хотя бы полиномиальную). Но вы же этого не продемонстрировали. Так против чего вы возражаете? Против указания на неполноту вашей собственной работы?
Я понимаю, что потраченного времени жаль, но к сожалению, работа реально неполная. Я сам когда-то давно удивлялся «ну что они все такие упёртые, не понимают, как я тут всё круто изобрёл!». Но потом всё же углубился в причины возражений и понял, что «изобрёл» я всего лишь часть решения. А без оставшейся части оно никому не интересно. Вот такая вот жизнь.
Вы согласитесь с тем, что:
1. Все отрицательные композиции, какими бы они не были, для произвольного значения n, будут точно установлены алгоритмом как отрицательные.
2. На интервале значений n от 800 до 100 миллионов алгоритм комплектует все положительные композиции без какой-либо ошибки. Этот участок составляет 99.9998% всего исследованного интервала значений n (от 7 до 100 миллионов)
( Я думал над тем, почему, когда n>= 800, в большой серии экспериментов ни разу не было False Negative решений. Пока, только предположение, что появляется «простор» для формирования ветви поиска решения, и алгоритм справляется с поставленной задачей)
3. В выделенном интервале значений n (от 7 до 799, что составляет примерно 0.0002% от всего рассмотренного интервала), алгоритм в 99.99% случаях комплектует любую случайную композицию до полного решения. И на этом интервале, лишь в одном случае из каждых 10 000 случайных положительных композиций, алгоритм ошибочно относит положительную композицию к группе отрицательных.
Скажите, разве это соответствует тому, что вы написали:
«Вы нашли способ получения близкого к линейному алгоритма для некоторых комбинаций».
На всем интервале значений n (от 7 до 100 миллионов), временная сложность работы алгоритма остается линейной, какой бы параметр распределения времени счета Вы не взяли бы.
В принципе, можно провести исследование, и на участке (7, ..., 800) добиться такого результата, что ошибка будет в 1000 раз меньше, и составит 0.0000001. Я не вижу пока в этом смысла.
1. Все отрицательные композиции, какими бы они не были, для произвольного значения n, будут точно установлены алгоритмом как отрицательные.
2. На интервале значений n от 800 до 100 миллионов алгоритм комплектует все положительные композиции без какой-либо ошибки. Этот участок составляет 99.9998% всего исследованного интервала значений n (от 7 до 100 миллионов)
( Я думал над тем, почему, когда n>= 800, в большой серии экспериментов ни разу не было False Negative решений. Пока, только предположение, что появляется «простор» для формирования ветви поиска решения, и алгоритм справляется с поставленной задачей)
3. В выделенном интервале значений n (от 7 до 799, что составляет примерно 0.0002% от всего рассмотренного интервала), алгоритм в 99.99% случаях комплектует любую случайную композицию до полного решения. И на этом интервале, лишь в одном случае из каждых 10 000 случайных положительных композиций, алгоритм ошибочно относит положительную композицию к группе отрицательных.
Скажите, разве это соответствует тому, что вы написали:
«Вы нашли способ получения близкого к линейному алгоритма для некоторых комбинаций».
На всем интервале значений n (от 7 до 100 миллионов), временная сложность работы алгоритма остается линейной, какой бы параметр распределения времени счета Вы не взяли бы.
В принципе, можно провести исследование, и на участке (7, ..., 800) добиться такого результата, что ошибка будет в 1000 раз меньше, и составит 0.0000001. Я не вижу пока в этом смысла.
Вы согласитесь с тем, что:
1. Все отрицательные композиции, какими бы они не были, для произвольного значения n, будут точно установлены алгоритмом как отрицательные.
Реально отрицательные варианты являются лишь частью множества вариантов, заявленных вашим алгоритмом как отрицательные.
Если вы этого не понимаете (а это следует из уже наверное десятка постов с объяснениями вам, как от меня, так и от других), то я не знаю, как вам ещё объяснять.
Точно так же, ваши указания на какую-то статистику совершенно неинтересны. Какая может быть статистика в вопросе «да или нет»? Если нет однозначного ответа — вы ничего не решили. Можно быть убитым с вероятностью 0.0001? И ходить при этом в гости? Можно видеть яблоко на столе с такой вероятностью? Я либо вижу, либо не вижу яблоко. И никакие вероятности здесь не играют никакой роли. Если в вашем мире всё по другому — ну что-ж, это ваш мир, значит вам и объяснять всем остальным, как можно быть на 0.001% убитым. Но предупреждаю — вас не поймут. А вы к этому не готовы.
К рис.7.
log(1000*t) = — 0.628927 + 0.781568*log(n)имеется комментарий
Видно, что время комплектации растет линейно, с увеличением значения n.
Если я правильно понимаю Ваше уравнение, его можно немного преобразовать:
3 + log(t) = — 0.628927 + 0.781568*log(n)
log(t) = — 3.628927 + 0.781568*log(n)
log(t) = — 3.628927 + log(n^0.781568)
log(t) = log(n^0.781568*10^(-3.628927))
t = n^0.781568*10^(-3.628927)- Где здесь "время комплектации растет линейно, с увеличением значения n"?
- Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
Коммент-1
«Ваш комменёарий показывает только то, что вы не понимаете смысл термина «детерминированный алгоритм». Единственным критерием детерминированности алгоритма является то, что он всегда возвращает один и тот же результат на одних и тех же входных данных. И это всё!
Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Коммент-2
«Ваше понимание «детерминированности» очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.»
Я хотел бы ответить на оба комментария, они близки по смыслу. Надеюсь коллеги не обидятся. Для этого, прошу вначале внимательно прочитать мой ответ на комментарий, приведенный выше (Комментарий – О недетерминированном поиске)
Думаю, что очевидный термин «детерминированный алгоритм» мы все понимаем одинаково, поэтому не стоит на это терять время. Кстати, я нигде не сравнивал детерминированность самой задачи с процедурой Back Tracking, это разные вещи. Не знаю, почему это привязываете ко мне. Здесь интересно другое. Вы пишите:
«Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Я думаю, что Вы здесь имели в виду не «выбор следующей ветви», а продолжение формирования ветви с заданного уровня. Ветвь мы не выбираем, а формируем ветвь на каждом шаге поиска решения.
В предложенном алгоритме, на последнем, самом ответственном этапе формирования ветви поиска решения возникает ситуация, когда:
— в списке строк, ранжированных по определенному критерию приоритета, встречаются две или более строки с одинаковым приоритетом. В этом случае, выбор индекса строки производится случайным образом,
— среди свободных позиций, в отобранной строке, встречаются две или более позиции, с одинаковым приоритетом. В этом случае, выбор индекса свободной позиции в отобранной строке так же производится случайным образом.
Я решил привести это, так как Ваш комментарий предполагает, что Вы понимаете о чем идет речь.
«Ваш комменёарий показывает только то, что вы не понимаете смысл термина «детерминированный алгоритм». Единственным критерием детерминированности алгоритма является то, что он всегда возвращает один и тот же результат на одних и тех же входных данных. И это всё!
Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Коммент-2
«Ваше понимание «детерминированности» очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.»
Я хотел бы ответить на оба комментария, они близки по смыслу. Надеюсь коллеги не обидятся. Для этого, прошу вначале внимательно прочитать мой ответ на комментарий, приведенный выше (Комментарий – О недетерминированном поиске)
Думаю, что очевидный термин «детерминированный алгоритм» мы все понимаем одинаково, поэтому не стоит на это терять время. Кстати, я нигде не сравнивал детерминированность самой задачи с процедурой Back Tracking, это разные вещи. Не знаю, почему это привязываете ко мне. Здесь интересно другое. Вы пишите:
«Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Я думаю, что Вы здесь имели в виду не «выбор следующей ветви», а продолжение формирования ветви с заданного уровня. Ветвь мы не выбираем, а формируем ветвь на каждом шаге поиска решения.
В предложенном алгоритме, на последнем, самом ответственном этапе формирования ветви поиска решения возникает ситуация, когда:
— в списке строк, ранжированных по определенному критерию приоритета, встречаются две или более строки с одинаковым приоритетом. В этом случае, выбор индекса строки производится случайным образом,
— среди свободных позиций, в отобранной строке, встречаются две или более позиции, с одинаковым приоритетом. В этом случае, выбор индекса свободной позиции в отобранной строке так же производится случайным образом.
Я решил привести это, так как Ваш комментарий предполагает, что Вы понимаете о чем идет речь.
Хочу, чуточку забегая вперед, ответить на комментарий нашего коллеги. с ником
primetalk
Коммент:
t = n^0.781568*10^(-3.628927)
1. Где здесь «время комплектации растет линейно, с увеличением значения n»?
2. Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
Здесь ошибки нет. В тексте публикации об этом сказано в одном месте:
«В полученной зависимости линейный коэффициент (0.781568) меньше единицы, что приводит к тому, что с ростом значения n, линия регрессии и диагональ квадранта расходятся.»
и подробно объяснено чуть дальше по курсу:
«Такое поведение алгоритма, на первый взгляд кажется ошибочным, так как нет объективных причин, почему при малых значениях n алгоритм будет считать медленнее, чем при больших значениях. Однако, здесь ошибки нет, и это является объективным свойством данного алгоритма. Связано это с тем, что данный алгоритм является композицией из трех алгоритмов, которые работают с разной скоростью. Причем, количество строк, обрабатываемых каждым из этих алгоритмов, изменяется с ростом значения n. Именно по этой причине растет время счета на начальном интервале значений n=(10, 20, 30, 40), так как все расчеты на этом маленьком участке проводятся только на основе пятого блока процедур, который работает очень эффективно, но не так быстро, как первый блок процедур. Таким образом, учитывая, что время счета, необходимое для расположения ферзя на одной строке, уменьшается с увеличением размера шахматной доски, временную сложность данного алгоритма можно назвать убывающей – линейной»
Я не хотел на этом акцентировать внимание. И так разговоры только о том, что это невозможно. Вместо того, чтобы просто взять и проверить, все комментарии свелись к общипыванию ромашки – верю не верю.
А Вам, спасибо за настырность! Ценю таких.
primetalk
Коммент:
t = n^0.781568*10^(-3.628927)
1. Где здесь «время комплектации растет линейно, с увеличением значения n»?
2. Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
Здесь ошибки нет. В тексте публикации об этом сказано в одном месте:
«В полученной зависимости линейный коэффициент (0.781568) меньше единицы, что приводит к тому, что с ростом значения n, линия регрессии и диагональ квадранта расходятся.»
и подробно объяснено чуть дальше по курсу:
«Такое поведение алгоритма, на первый взгляд кажется ошибочным, так как нет объективных причин, почему при малых значениях n алгоритм будет считать медленнее, чем при больших значениях. Однако, здесь ошибки нет, и это является объективным свойством данного алгоритма. Связано это с тем, что данный алгоритм является композицией из трех алгоритмов, которые работают с разной скоростью. Причем, количество строк, обрабатываемых каждым из этих алгоритмов, изменяется с ростом значения n. Именно по этой причине растет время счета на начальном интервале значений n=(10, 20, 30, 40), так как все расчеты на этом маленьком участке проводятся только на основе пятого блока процедур, который работает очень эффективно, но не так быстро, как первый блок процедур. Таким образом, учитывая, что время счета, необходимое для расположения ферзя на одной строке, уменьшается с увеличением размера шахматной доски, временную сложность данного алгоритма можно назвать убывающей – линейной»
Я не хотел на этом акцентировать внимание. И так разговоры только о том, что это невозможно. Вместо того, чтобы просто взять и проверить, все комментарии свелись к общипыванию ромашки – верю не верю.
А Вам, спасибо за настырность! Ценю таких.
Под линейной зависимостью обычно понимают t=k*n + b. В данном случае зависимость — нелинейная t=c*n^d, причём d < 1.
Здесь, на мой взгляд — две ошибки. Во-первых, в терминологии, чёрное называется белым (нелинейная зависимость — линейной), и, во-вторых, в фактуре, т.к. тем самым Вы утверждаете, что алгоритм имеет сложность O(n^0.781568), что, на мой взгляд, невозможно даже в той задаче, которую Вы решаете. По-видимому, при построении графика производился отбор данных. Например, отбрасывались тупиковые случаи, когда алгоритм был выполнен, но получен отрицательный ответ.
Коллеги не обидятся. Однако хотелось бы отметить, что, по-видимому, Вы используете демагогический приём — strawman.
Оба наших комментария относятся к корректному использованию терминологии. А именно, слово "детерминированный" имеет вполне определённый смысл, отличающийся от того, который Вы в него вкладываете.
В настоящем же комментарии Вы сообщаете, что Ваш алгоритм является недетерминированным. Это мы уже поняли, как только Вы написали, что используете генератор случайных чисел. Тем самым, вы подменяете тезис и спорите уже с другим тезисом.
Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм.
Стоит ли и говорить, что даже простые эвристики, как правило, сильно упрощают решение NP-полных задач на большинстве инпутов. Именно поэтому доказывать эффективность алгоритма, предлагая сгенерировать случайный инпут, бессмысленно — алгоритм будет работать быстро на нём, но экспоненциальное время на нетривиальных контрпримерах (которые ещё нужно найти). То, что вы называете «алгоритмической математикой», не поможет вам обосновать эффективность вашего алгоритма, потому что природа задачи очень сложна.
Комент:
«Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм»
Странно, Вы уже пишите 7-ой комментарий, так и ни разу не коснувшись самой сути алгоритма. Все вокруг определения понятий детерминированный, недетерминированный,… Судя по комментариям, у меня создается впечатление, что статью до конца Вы так и не прочитали.
В статье достаточно ясно написано, что Back Tracking совершается только на один из трех базовых уровней, если на данном шаге решения, ветвь поиска решения приводит в тупик. Это никак не связано с тем, каким образом формировалась ветвь поиска, начиная с базового уровня. На основе некоторых выделенных правил, на основе генератора случайных чисел (ГСЧ). Не имеет значения, производится возврат на один из базовых уровней в зависимости от уровня решения задачи. Поэтому никакой взаимосвязи между использованием ГСЧ и применением процедуры Back Tracking нет. Думаю, это Вы поняли из самой статьи.
То, что я писал Вам в комментарии, никак не связано с Back Tracking, и я их никак не связывал. Мне показалось, что Вам будет интересно узнать, каким способом используются оставшиеся ресурсы на последнем этапе, когда каждый шаг имеет принципиальное значение. Думаю, мы поняли друг друга.
«Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм»
Странно, Вы уже пишите 7-ой комментарий, так и ни разу не коснувшись самой сути алгоритма. Все вокруг определения понятий детерминированный, недетерминированный,… Судя по комментариям, у меня создается впечатление, что статью до конца Вы так и не прочитали.
В статье достаточно ясно написано, что Back Tracking совершается только на один из трех базовых уровней, если на данном шаге решения, ветвь поиска решения приводит в тупик. Это никак не связано с тем, каким образом формировалась ветвь поиска, начиная с базового уровня. На основе некоторых выделенных правил, на основе генератора случайных чисел (ГСЧ). Не имеет значения, производится возврат на один из базовых уровней в зависимости от уровня решения задачи. Поэтому никакой взаимосвязи между использованием ГСЧ и применением процедуры Back Tracking нет. Думаю, это Вы поняли из самой статьи.
То, что я писал Вам в комментарии, никак не связано с Back Tracking, и я их никак не связывал. Мне показалось, что Вам будет интересно узнать, каким способом используются оставшиеся ресурсы на последнем этапе, когда каждый шаг имеет принципиальное значение. Думаю, мы поняли друг друга.
Товарищ ericgrig, под каждым комментарием есть кнопка "Ответить", на которую, как следует из названия, надо нажимать, если вы хотите ответить на этот комментарий. При этом форма ввода текста появляется под ним. Не надо копипастить комментарии целиком и отвечать на них внизу обсуждения.
Выглядит это вот так
Напишите мне, если у Вас есть возможность оказать помощь другу, я сразу вышлю Вам эти три программы.
А почему в открытый доступ не выложите? Описание алгоритма же и так всем доступно из статьи. Залили бы на GitHub, или хотя бы на Google-диск, как тестовые файлы, так больше людей сможет протестировать.
Спасибо!
Вы затронули важный вопрос. С самого начала я планировал выложить исходный код в открытый доступ. Об этом я написал в пункте 7 предисловия:
«7. Я подготовил исходный текст программы, с подробными комментариями, который, надеюсь, в ближайшее время будет опубликован на Хабре. Думаю, что те, кто интересуется решением сложных задач из семейства NP-Complete, найдут для себя что-нибудь интересное.»
Немного задержался с «подробными комментариями». В течение нескольких дней выложу на англоязычном Хабре. Программу генерации случайной композиции для матрицы решения произвольного размера, выставлю на Google-диск (она построена на базе основной программы, нет смысла публиковать ее на Хабре).
На GitHub почему-то «не потянуло», не знаю почему. Следующий проект выложу там.
Я был уверен, что в процессе живого «комментарного» общения кто-то из членов Хабра-Сообщества откликнется на мой просьбу и протестирует алгоритм. Было интересно узнать объективное мнение независимого эксперта. Но не повезло, экспертов в обсуждении не было. После первого комментария:
«Извините, я устал читать. Не покажете место, где кончаются очевидные вещи...»
я понял, что дальше серьезного разговора не будет.
Вы затронули важный вопрос. С самого начала я планировал выложить исходный код в открытый доступ. Об этом я написал в пункте 7 предисловия:
«7. Я подготовил исходный текст программы, с подробными комментариями, который, надеюсь, в ближайшее время будет опубликован на Хабре. Думаю, что те, кто интересуется решением сложных задач из семейства NP-Complete, найдут для себя что-нибудь интересное.»
Немного задержался с «подробными комментариями». В течение нескольких дней выложу на англоязычном Хабре. Программу генерации случайной композиции для матрицы решения произвольного размера, выставлю на Google-диск (она построена на базе основной программы, нет смысла публиковать ее на Хабре).
На GitHub почему-то «не потянуло», не знаю почему. Следующий проект выложу там.
Я был уверен, что в процессе живого «комментарного» общения кто-то из членов Хабра-Сообщества откликнется на мой просьбу и протестирует алгоритм. Было интересно узнать объективное мнение независимого эксперта. Но не повезло, экспертов в обсуждении не было. После первого комментария:
«Извините, я устал читать. Не покажете место, где кончаются очевидные вещи...»
я понял, что дальше серьезного разговора не будет.
Простите, если пропустил, но не увидел прямого сравнения эффективности вашего алгоритма с другими. Вы пишете что он эффективен, но насколько по-сравнению с известными?
Возможно реакция хабра объясняет отказы в публикации вашей статьи? Особенно, если заголовок был именно такой. ИМХО Заменить слово «линейный» на эффективный и половина вопросов отпадёт.
Возможно реакция хабра объясняет отказы в публикации вашей статьи? Особенно, если заголовок был именно такой. ИМХО Заменить слово «линейный» на эффективный и половина вопросов отпадёт.
Я не нашел публикацию, в которой описывался бы конкретный алгоритм решения поставленной задачи. Есть алгоритмы для поиска списка всех решений n-Queens Problem, есть алгоритмы для быстрого нахождения одного решения для произвольного n. Но алгоритма, который конкретно решал бы задачу n-Queens Completion Problem я не нашел.
Поэтому, об эффективности можно судить по нескольким характеристикам:
— линейная временная сложность алгоритма,
— среднее значение времени решения для любой случайной композиции, при некотором фиксированном значении n ( например, для n=1000, среднее время решения одной случайной композиции равно 0.062157 с.)
— уменьшение числа случаев применения процедуры Back Tracking, при формировании ветви поиска решений.
По поводу изменения названия — возможно, Вы правы. (Такой себе, смягчающий психологический эффект). Но, я написал как есть. Уже поздно что-то менять.
Поэтому, об эффективности можно судить по нескольким характеристикам:
— линейная временная сложность алгоритма,
— среднее значение времени решения для любой случайной композиции, при некотором фиксированном значении n ( например, для n=1000, среднее время решения одной случайной композиции равно 0.062157 с.)
— уменьшение числа случаев применения процедуры Back Tracking, при формировании ветви поиска решений.
По поводу изменения названия — возможно, Вы правы. (Такой себе, смягчающий психологический эффект). Но, я написал как есть. Уже поздно что-то менять.
В любом случае — спасибо за проделанную работу! Было очень любопытно и результат впечатляет. Но подача материала и его объём не для научно-популярного ресурса(и для меня в том числе).
Мне кажется — вам нужен редактор. После соответствующего редактирования — статья представляла бы огромный интерес для большинства даже незаинтересованных. Люди науки нечасто бывают хорошими ораторами, так что стоит делегировать эти функции.
Вы, как выразились — «живёте» внутри задачи, потому ваше видение сильно отличается. Вещи которые уже кажутся вам очевидными и не стоящими внимания у остальных вызывают вопросы, и акцентируясь на таких вещах, обсуждение уходит от сути…
Мне кажется — вам нужен редактор. После соответствующего редактирования — статья представляла бы огромный интерес для большинства даже незаинтересованных. Люди науки нечасто бывают хорошими ораторами, так что стоит делегировать эти функции.
Вы, как выразились — «живёте» внутри задачи, потому ваше видение сильно отличается. Вещи которые уже кажутся вам очевидными и не стоящими внимания у остальных вызывают вопросы, и акцентируясь на таких вещах, обсуждение уходит от сути…
мне кажется автору нужен не сколько редактор, сколько второй автор — какой-нибудь профессор, который бы сделал из статьи выжимку самого важного, убрал воду и переформулировал задачу
Спасибо за совет!
«Дыма без огня не бывает». Раз так среагировали те участники, кто комментировал, значит на то были причины. Жаль, что ни один из участников не задал вопрос, который был бы связан с сутью проблемы или с результатами исследования. Там в самом деле очень много интересного. За полтора года накопилось много чего интересного, и описание полученных результатов примерно в полтора раза больше, чем я выложил на Хабре.
Вы правы в том, что нужно было произвести процедуру селекции и сжатия материала, и подать результаты в сокращенном виде. Наверное, тогда вопросы касались бы теме изложения.
«Дыма без огня не бывает». Раз так среагировали те участники, кто комментировал, значит на то были причины. Жаль, что ни один из участников не задал вопрос, который был бы связан с сутью проблемы или с результатами исследования. Там в самом деле очень много интересного. За полтора года накопилось много чего интересного, и описание полученных результатов примерно в полтора раза больше, чем я выложил на Хабре.
Вы правы в том, что нужно было произвести процедуру селекции и сжатия материала, и подать результаты в сокращенном виде. Наверное, тогда вопросы касались бы теме изложения.
Не только сокращение, а и немного истории возникновения самой задачи, потому как людям незнакомым с задачей заранее, придется гуглить — о чем собственно статья и к чему алгоритм. Я даже будучи знакомым с ней, до середины статьи не был уверен на 100% что речь действительно о ней. Плавно подведите читателя к сути вашей работы. Популяризуйте. Те кто действительно хорошо разбираются в вопросе — разыщут ваш труд и без Хабра и разберутся в нём без объяснений но ведь их не так уж много. А чтобы вопросы были по теме — опишите отдельно например самые узкие места и народ начнёт соображать как их можно обойти — задавать вопросы, а возможно и предложат что-то дельное.
На самом деле, просто хочу поддержать. Так как отрицательная оценка многим очень сильно отбивает желание двигаться вперёд. А вы уже получили отказ в двух журналах и несколько отрицательную реакцию на Хабре. И судя по
Всем добра.
На самом деле, просто хочу поддержать. Так как отрицательная оценка многим очень сильно отбивает желание двигаться вперёд. А вы уже получили отказ в двух журналах и несколько отрицательную реакцию на Хабре. И судя по
я понял, что дальше серьезного разговора не будет.это вас таки задело. Да любого заденет, что результат длительной работы «пинают» даже не разобравшись в сути. И причина, как мне видится, только в неверной подаче.
Всем добра.
Спасибо за поддержку!
Вы даете дельный совет, наверное стоило все это разбить на части, и иначе преподнести.
На счет узких мест — да там много разных узких мест. В самом изложении, я как-то на это не акцентировал внимание. Немного коснулся этой темы в предисловии, но это лишь небольшая часть.
Бог с ними, с отрицательными оценками. Люди разные бывают, я на них не обижаюсь. Я предполагаю, что это славные ребята, просто погорячились.
Я жалею только о том, что время потеряно, но не было содержательной дискуссии. Столько нюансов осталось за бортом, а это кому то могло быть полезным на практике.
Вы даете дельный совет, наверное стоило все это разбить на части, и иначе преподнести.
На счет узких мест — да там много разных узких мест. В самом изложении, я как-то на это не акцентировал внимание. Немного коснулся этой темы в предисловии, но это лишь небольшая часть.
Бог с ними, с отрицательными оценками. Люди разные бывают, я на них не обижаюсь. Я предполагаю, что это славные ребята, просто погорячились.
Я жалею только о том, что время потеряно, но не было содержательной дискуссии. Столько нюансов осталось за бортом, а это кому то могло быть полезным на практике.
Журналы ведь платные не для того, чтобы просто выложить вашу работу, а чтобы проверить его.
Не совсем так. Среди журналов с открытым доступом, есть такие, где публикация проходит независимое рецензирование. Ниже перечислены некоторые из таких журналов, куда я обращался:
— Journal of Artificial Intelligence Research
— SMAI Journal of Computational Mathematics
— Discrete Mathematics & Theoretical Computer Science
В первых двух отказали, в последнем предстоит рассмотрение. Как писал в предисловии, чтобы публиковать статью в «Discrete Mathematics & Theoretical Computer Science», нужно вначале опубликовать ее в arXiv.org. Что и было сделано.
Я думаю, что платные журналы необоснованно продают результаты труда ученых, за работу и исследования которых оплатили налогоплательщики. Этим вопросом должны заниматься на государственном уровне. Считаю, что информация должна быть в открытом доступе.
— Journal of Artificial Intelligence Research
— SMAI Journal of Computational Mathematics
— Discrete Mathematics & Theoretical Computer Science
В первых двух отказали, в последнем предстоит рассмотрение. Как писал в предисловии, чтобы публиковать статью в «Discrete Mathematics & Theoretical Computer Science», нужно вначале опубликовать ее в arXiv.org. Что и было сделано.
Я думаю, что платные журналы необоснованно продают результаты труда ученых, за работу и исследования которых оплатили налогоплательщики. Этим вопросом должны заниматься на государственном уровне. Считаю, что информация должна быть в открытом доступе.
UFO just landed and posted this here
Я ценю, если коллеги пишут комментарии к публикации. Не важно какую, с «положительным» оттенком, или с «отрицательным». Равнодушие хуже всего. Я очень хотел бы, чтобы комментарии прямо или косвенно касались сути и содержания публикации. Ведь Хабр замечателен тем, что здесь можно услышать всестороннее обсуждение и объективную критику. Где еще можно получить такое? Я могу где-то что-то упустить, а коллеги это заметят. В этом и есть направляющая сила.
А теперь о «путанице с детерминированностью». Хочу отметить, что как в остальных ответах на комментарии, так и здесь, я остаюсь в рамках предложенной публикации, и не выхожу на общие рассуждения. (Хотя, это мне нравится, но это отдельный разговор).
Задача называется детерминированной, если при при одном и том же входном значении, на выходе всегда получается один и тот же результат. (Я привел простое и понятное определение. Исправьте меня, если что-то не так. Через Google можно найти много определений, по сути сходящихся к данному.)
Теперь, рассмотрим задачу n-Queens Completion Problem.
— на входе мы получаем случайную композицию из k ферзей, непротиворечиво расставленных на произвольной шахматной доске размера n x n.
— на выходе, мы получаем завершенное решение, если он есть, либо принимается решение о том, что данная композиция не может быть комплектована.
Так вот, каждый раз, запуская задачу на исполнение, мы всегда на выходе получаем разные решения. Исходная композиция из k ферзей остается на местах, а все остальное, что было расставлено до получения полного решения, в разных решениях отличается друг от друга.
В качестве примера, для n=1000, можно формировать случайную композицию из k=377 ферзей, и после этого миллион раз повторно комплектовать только эту композицию. Ни одно решение не будет полностью совпадать, с каким либо из остальных решений.
В этом смысле задача является не детерминированной.
Если, в качестве входных данных, рассмотреть позиции всех ферзей (позиции ферзей из композиции + позиции ферзей, найденных в процессе решения), то получим список из n позиций, который характеризует данное конкретное решение. Список позиций и есть решение, и он всегда будет постоянным для одного и того же решения. Тогда вопрос о детерминированности задачи будет звучать так: " Если на вход подать список позиций, который является решением, то на выходе мы получим этот список как решение". Получается какая то несуразица, хотя все в пределах логики определения детерминированности.
Сравнив эти два варианта, я выбрал первую. (на входе есть композиция — на выходе разные решения)
А теперь, про «про отбрасывание сложных решений».
Смотрите, для n=1000, при решении задачи для одного миллиона случайных композиций, не было ни одного False Negative решения. Хотя, если увеличить размер выборки до 10 миллионов или больше, такие False Negative решения должны появиться. Один миллион, это случайная выборка композиций из огромного числа возможностей. Как только размер выборки намного увеличится, такие сложные композиции, которые алгоритм не может распознать, обязательно появятся. Но, в результате довольно обширного вычислительного эксперимента, было установлено, что доля таких сложных решений не превышает 0.0001 от размера выборки.
В алгоритме есть ограничение по числу случаев применения процедуры Back Tracking, это число равно 1000. (В одном из ответов на комментарии, я об этом подробно писал). Это та граница, когда почти все положительные композиции ( за исключением 0.0001 части выборки) гарантированно комплектуются до полного решения. Если, в качестве граничного значения использовать 2000, то доля False Negative решений значительно уменьшится. Но, в этом случае, просто увеличится время счета, когда программа примет решение, что рассматриваемая композиция является отрицательной. Учитывая, что доля False Negative решений незначительна, и с ростом значения n эта доля уменьшается, было принято компромиссное решение — 1000. Если постановка задачи требует особой точности, этот параметр можно изменить.
Поэтому будет честно, если напишите, что в 99.99% случаев случайных композиций, для произвольного значения n, алгоритм находит решение, либо выносит суждение, что рассматриваемая композиция является отрицательной. Только в одном случае из 10 000 алгоритм может неверно отнести положительную композицию к группе отрицательных.
(А то, будет как в анекдоте про бег на сто метров двух президентов: «Советские журналисты написали, что наш Брежнев прибежал вторым, а их Рейган — предпоследним», хотя было всего два участника).
А теперь о «путанице с детерминированностью». Хочу отметить, что как в остальных ответах на комментарии, так и здесь, я остаюсь в рамках предложенной публикации, и не выхожу на общие рассуждения. (Хотя, это мне нравится, но это отдельный разговор).
Задача называется детерминированной, если при при одном и том же входном значении, на выходе всегда получается один и тот же результат. (Я привел простое и понятное определение. Исправьте меня, если что-то не так. Через Google можно найти много определений, по сути сходящихся к данному.)
Теперь, рассмотрим задачу n-Queens Completion Problem.
— на входе мы получаем случайную композицию из k ферзей, непротиворечиво расставленных на произвольной шахматной доске размера n x n.
— на выходе, мы получаем завершенное решение, если он есть, либо принимается решение о том, что данная композиция не может быть комплектована.
Так вот, каждый раз, запуская задачу на исполнение, мы всегда на выходе получаем разные решения. Исходная композиция из k ферзей остается на местах, а все остальное, что было расставлено до получения полного решения, в разных решениях отличается друг от друга.
В качестве примера, для n=1000, можно формировать случайную композицию из k=377 ферзей, и после этого миллион раз повторно комплектовать только эту композицию. Ни одно решение не будет полностью совпадать, с каким либо из остальных решений.
В этом смысле задача является не детерминированной.
Если, в качестве входных данных, рассмотреть позиции всех ферзей (позиции ферзей из композиции + позиции ферзей, найденных в процессе решения), то получим список из n позиций, который характеризует данное конкретное решение. Список позиций и есть решение, и он всегда будет постоянным для одного и того же решения. Тогда вопрос о детерминированности задачи будет звучать так: " Если на вход подать список позиций, который является решением, то на выходе мы получим этот список как решение". Получается какая то несуразица, хотя все в пределах логики определения детерминированности.
Сравнив эти два варианта, я выбрал первую. (на входе есть композиция — на выходе разные решения)
А теперь, про «про отбрасывание сложных решений».
Смотрите, для n=1000, при решении задачи для одного миллиона случайных композиций, не было ни одного False Negative решения. Хотя, если увеличить размер выборки до 10 миллионов или больше, такие False Negative решения должны появиться. Один миллион, это случайная выборка композиций из огромного числа возможностей. Как только размер выборки намного увеличится, такие сложные композиции, которые алгоритм не может распознать, обязательно появятся. Но, в результате довольно обширного вычислительного эксперимента, было установлено, что доля таких сложных решений не превышает 0.0001 от размера выборки.
В алгоритме есть ограничение по числу случаев применения процедуры Back Tracking, это число равно 1000. (В одном из ответов на комментарии, я об этом подробно писал). Это та граница, когда почти все положительные композиции ( за исключением 0.0001 части выборки) гарантированно комплектуются до полного решения. Если, в качестве граничного значения использовать 2000, то доля False Negative решений значительно уменьшится. Но, в этом случае, просто увеличится время счета, когда программа примет решение, что рассматриваемая композиция является отрицательной. Учитывая, что доля False Negative решений незначительна, и с ростом значения n эта доля уменьшается, было принято компромиссное решение — 1000. Если постановка задачи требует особой точности, этот параметр можно изменить.
Поэтому будет честно, если напишите, что в 99.99% случаев случайных композиций, для произвольного значения n, алгоритм находит решение, либо выносит суждение, что рассматриваемая композиция является отрицательной. Только в одном случае из 10 000 алгоритм может неверно отнести положительную композицию к группе отрицательных.
(А то, будет как в анекдоте про бег на сто метров двух президентов: «Советские журналисты написали, что наш Брежнев прибежал вторым, а их Рейган — предпоследним», хотя было всего два участника).
Sign up to leave a comment.
n-Queens Completion Problem — линейный алгоритм решения