Хочу, чуточку забегая вперед, ответить на комментарий нашего коллеги. с ником
primetalk
Коммент:
t = n^0.781568*10^(-3.628927)
1. Где здесь «время комплектации растет линейно, с увеличением значения n»?
2. Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
Здесь ошибки нет. В тексте публикации об этом сказано в одном месте:
«В полученной зависимости линейный коэффициент (0.781568) меньше единицы, что приводит к тому, что с ростом значения n, линия регрессии и диагональ квадранта расходятся.»
и подробно объяснено чуть дальше по курсу:
«Такое поведение алгоритма, на первый взгляд кажется ошибочным, так как нет объективных причин, почему при малых значениях n алгоритм будет считать медленнее, чем при больших значениях. Однако, здесь ошибки нет, и это является объективным свойством данного алгоритма. Связано это с тем, что данный алгоритм является композицией из трех алгоритмов, которые работают с разной скоростью. Причем, количество строк, обрабатываемых каждым из этих алгоритмов, изменяется с ростом значения n. Именно по этой причине растет время счета на начальном интервале значений n=(10, 20, 30, 40), так как все расчеты на этом маленьком участке проводятся только на основе пятого блока процедур, который работает очень эффективно, но не так быстро, как первый блок процедур. Таким образом, учитывая, что время счета, необходимое для расположения ферзя на одной строке, уменьшается с увеличением размера шахматной доски, временную сложность данного алгоритма можно назвать убывающей – линейной»
Я не хотел на этом акцентировать внимание. И так разговоры только о том, что это невозможно. Вместо того, чтобы просто взять и проверить, все комментарии свелись к общипыванию ромашки – верю не верю.
А Вам, спасибо за настырность! Ценю таких.
«Ваш комменёарий показывает только то, что вы не понимаете смысл термина «детерминированный алгоритм». Единственным критерием детерминированности алгоритма является то, что он всегда возвращает один и тот же результат на одних и тех же входных данных. И это всё!
Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Коммент-2
«Ваше понимание «детерминированности» очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.»
Я хотел бы ответить на оба комментария, они близки по смыслу. Надеюсь коллеги не обидятся. Для этого, прошу вначале внимательно прочитать мой ответ на комментарий, приведенный выше (Комментарий – О недетерминированном поиске)
Думаю, что очевидный термин «детерминированный алгоритм» мы все понимаем одинаково, поэтому не стоит на это терять время. Кстати, я нигде не сравнивал детерминированность самой задачи с процедурой Back Tracking, это разные вещи. Не знаю, почему это привязываете ко мне. Здесь интересно другое. Вы пишите:
«Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Я думаю, что Вы здесь имели в виду не «выбор следующей ветви», а продолжение формирования ветви с заданного уровня. Ветвь мы не выбираем, а формируем ветвь на каждом шаге поиска решения.
В предложенном алгоритме, на последнем, самом ответственном этапе формирования ветви поиска решения возникает ситуация, когда:
— в списке строк, ранжированных по определенному критерию приоритета, встречаются две или более строки с одинаковым приоритетом. В этом случае, выбор индекса строки производится случайным образом,
— среди свободных позиций, в отобранной строке, встречаются две или более позиции, с одинаковым приоритетом. В этом случае, выбор индекса свободной позиции в отобранной строке так же производится случайным образом.
Я решил привести это, так как Ваш комментарий предполагает, что Вы понимаете о чем идет речь.
Коммент:
«Вопросы выше связаны с неправильным названием статьи. Тема «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 и другие задачи подобного рода решить невозможно
Вопрос:
«Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.»
Я хочу попросить Вас, все таки, не спешить и вникнуть в суть того, что сказано. Фраза «С помощью строгих математических методов» — означает, только то, что проблема решается только на основе определений, формулировке лемм и доказательстве теорем. Без применения методов алгоритмической математики и компьютерного моделирования. А каком «полиномиальном времени» строгих математических методов Вы говорите.
«прямым перебором или обычным backtracking'ом»
— Back Tracking является неотъемлемым компонентом прямого перебора, для поиска всех решений. Поэтому, здесь «или» не уместна. Когда Вы ищите все возможные решения, то постоянно «заходите» в тот или иной тупик, и вынуждены возвращаться назад на один шаг назад (если опять тупик — то на два или более шагов назад). Для этого Вы должны запомнить все основные параметры нескольких последовательных уровней, чтобы можно было восстановить исходное состояние на данном уровне. Попробуйте, это все очень интересно.
Вопрос: ««Единственный алгоритм нахождения точного решения 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-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом
Перебор же »
— Я в самом деле не встречал публикаций, в которых приводится детерминированный алгоритм решения какой-либо из NP-полных задач в широком диапазоне изменчивости основного параметра задачи. Мне реально это интересно, поэтому, если Вы знаете такую публикацию, выложите ссылку.
Решить задачу детерминировано, означает последовательно формировать ветвь поиска решения от начала до конца, нигде не «спотыкаясь». Это означает получить решение задачи, и ни разу не использовать процедуру Back Tracking, так как идете «верной дорогой». Можете Вы привести какой либо алгоритм решения одной из задач семейства NP-Complete, в которой бы не использовалась процедура Back Tracking?
Думаю, что не удастся. Мы выполняем Back Tracking и возвращаемся назад, чтобы с какой-то позиции снова продолжать строить ветвь поиска решения, надеясь, что «на этот раз повезет» и дойдем до цели. Если есть Back Tracking, значит есть неопределенность в том, что выбирать. Чем меньше число случаев использования процедуры Back Tracking, тем более эффективным является алгоритм.
Я целенаправленно занимался этим вопросом, после того, как был разработан алгоритм решения n-Queens Completion Problem. Это заняло слишком много времени, но, в итоге удалось изменить алгоритм таким образом, что на достаточно широком интервале значений n, в 50% случаях процедура Back Tracking ни разу не используется при формировании полного решения.
Вопрос: «Т.е. программа работает, но в конечном итоге, формального доказательства не будет и, очевидно никакого «прорыва» — просто качественный алгорим, который работает на подмножестве параметров.»
— ценю Ваш юмор, только давайте подойдем к вопросу серьезно. Выше я уже писал, что на основе строгого математического подхода, данную задачу и другие аналогичные задачи решить невозможно. Я утверждаю, что задачи такого класса, с большой вероятностью могут быть решены на основе алгоритмической математики с использованием Computational Simulation. Поэтому формального доказательства, в данной задаче, и других подобных задачах быть не может. Я не ставил перед собой цель строго математически доказать P=NP или P ≠ NP. Возьму на себя смелость нагло утверждать, что строго математически это никто не докажет, и что самое интересное, в этом нет никакого смысла. Нужно просто брать конкретную задачу из множества NP-Complete и «конкретно» ее решать. То, что одну из задач из этого семейства удалось решить, пока говорит только о том, что это возможно. И не более того.
Я не люблю и не использую слова «революция», «прорыв» или что-то подобное. Оно здесь не к месту. Считаю полезным концентрироваться на задаче, и если удастся – жить внутри задачи. «Там изнутри все видно».
Не знаю, как относиться к Вашим словам, про «просто качественный алгоритм, который работает на подмножестве параметров.». Воспринимаю как намек на положительную оценку. А если серьезно, то давайте подумаем. В интернет публикации n-Queens bibliography — 342 references приводятся ссылки на 342 статьи, которые прямо или косвенно, относятся к тематике n-Queens Problem. Можете найти хотя бы одну публикацию, в которой использовался такой огромный объем результатов вычислительных экспериментов. Ведь я рассматривал диапазон значений размера шахматной доски от 7 до 100 миллионов. Причем, там, где это было приемлемо по времени, размер сформированной выборки составлял один миллион. Это только для одного конкретного значения n. Прежде чем вынести полученные результаты на обсуждение, алгоритм многократно тестировался. Не будет ошибкой, если я скажу, что за полтора года алгоритм тестировался несколько десятков миллионов раз.
« Про дядю Вову»
В России только «один дядя Вова», думал Вы про него. Раскрыл – оказалось совсем другое.
Не может быть и речи о том, что «информацию сжимал». Я готов предоставить любому члену нашего Хабра-Сообщества исходный текст программы (на Матлабе) для всевозможного прогона. Об этом я писал в предисловии к статье. Это важная и сильная составляющая Хабра-Сообщества, когда члены сообщества могут свободно проверить те или иные алгоритмы и открыто высказать свое мнение.
Вопрос: «Скорость выполнения алгоритма на конкретном компьютере не имеет отношения к линейному/нелинейному времени.»
— нигде в тексте нет и не может быть намека на то, что временная сложность алгоритма зависит от вычислительного устройства. Так же, выбор языка программирования не будет влиять на временную сложность. Не могу понять, откуда у Вас такая ассоциация.
Характеристики вычислительного устройства, обычно приводятся в публикациях, чтобы читатель мог оценить время выполнения тех или иных решений.
Вопрос: «…Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде»
Скриптовый язык Матлаба, это почти тот же псевдокод. В ближайшее время, исходный код с подробными комментариями, будет опубликован на Хабре. Это даст возможность проверить.
Изначально, я ставил цель оценить временную сложность на основе вычислительных экспериментов. Что, в принципе и было сделано.
Вопрос: «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-полной задачи.»
О революции нигде в тексте нет и намека. Это другая материя. А то, что временная сложность алгоритма линейная – так это правда. Это же легко проверить. Я в предисловии к статье писал, если у Вас есть возможность запустить программу на Матлабе, то напишите мне (в предисловии есть мой e-mail). Я вышлю Вам программу (алгоритм) для тестирования. Это не займет у Вас много времени, программа работает очень быстро.
«Такое заявление требует убедительных доказательств, …»
Корректно сформулированные вычислительные задачи можно решить на основе строгих математических методов (на основе определений, формулировке лемм и доказательстве теорем), либо с помощью алгоритмической математики на основе Computational Simulation. С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно. Об этом в конце статьи есть «философское замечание». Я тоже хотел строго математически, но заблуждался, причем долго. Подобного рода задачи можно решить только на основе алгоритмической математики. Что в принципе и было сделано (правда, для этого потребовалось слишком много времени).
А теперь, по поводу «убедительных доказательств…». Есть алгоритмическое решение данной задачи. Я уверен, что Вы серьезный человек, поэтому предлагаю Вам проверить работу алгоритма. Это совсем не сложно, и даст вам возможность обоснованно оценить работу алгоритма и сделать выводы.
«…то была бы опровергнута гипотеза P ≠ NP»
У страха глаза велики – я тоже «боялся», до определенной поры. Не надо демонизировать. Все гораздо сложнее и интереснее. Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики. В каждом случае будет свой подход, хотя, что-то общее в алгоритме решения будет их объединять. Утверждать, что после решения n-Queens Completion Problem, все остальные задачи из множества NP-Complete сразу завалятся, будет неверно. Я не говорю об полиномиальном сведении решения одной сложной задачи к решению другой задачи. Я имею ввиду разработку эффективного алгоритма для решения конкретной задачи.
Статья в самом деле большая. Для тех, кто пытался решать подобные задачи, наверное статья представит интерес. Для других, кто хочет кратко — достаточно посмотреть только Выводы (в конце статьи).
Проблема, которая рассматривается в публикации, принципиально важная и достаточно сложная. Мне показалось, что будет правильным привести подробное изложение результатов исследования, без «темных» мест.
Вопрос:… может ли он найти все возможные расстановки ферзей на доске?
Все возможные расстановки ферзей на доске означает все полные решения 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 — говорит об эффективности данного алгоритма. Но ничего абсолютно совершенного нет. Я буду рад, если Вы или кто-то другой честно и обоснованно покажет слабые стороны данного алгоритма. Ведь цель нашего общения — в обмене информацией и развитии.
Подробно, аккуратно, доходчиво,…
Ценю ваше уважительное отношение к читателям. Это мне понравилось.
Буду рад помочь вам корректно ставить сложные задачи в области Искусственного интеллекта, и искать пути их решения. Если сочтете интересным, пишите. (ericgrig@gmail.com)
Спасибо за содержательный комментарий к тому, что я написал. Особенно за ссылки, с удовольствием прочитаю. Если есть еще материалы, перешлите мне на ericgrig@gmail.com
1. Это интересная, сложная, и трудно разрешимая задача. Больше 20 лет исследований (различные команды + большие вычислительные мощности) не привели к эффективному решению. Может формулировка задачи на другом уровне абстракции и использование новых идей позволит достичь успеха.
2. Задача мне интересна не только на позновательном уровне. Так получилось, что в ближайшие год-полтора мне придется уделить ей часть своего времени.
3. Я прицепил слово «безбашный» в кавычках к задаче, подразумевая, что задача достаточно сложная и до сих пор не имеет завершенного решения. Если данная публикация мотивирует амбициозных членов ХабраСообщества к ее решению, так это похвально.
Мне нравится Демис Хассабис как одаренный человек, который не боится ставить и решать сложные задачи. И слава богу, что у него хватает рвения идти вперед. Кто мешал другим замечательным командам с хорошим финансированием, делать нечто подобное или лучше? Поэтому я отношусь к команде Хассабиса с уважением — я ценю их труд.
В нашем ХабраСообществе много рассудительных людей, которые с пониманием отнесутся к данной научно-познавательной публикации. Думаю, ее цель — создать побудительные мотивы к «безбашным» задачам у молодых амбициозных хаброчитателей. Таких у нас много…
Реально мне хотелось бы узнать больше информации об исследованиях по предсказанию структуры белков. Интересная задача — «за душу берет». Надеюсь, Вячеслав когда нибудь об этом напишет более подробно.
Спасибо Вячеславу, что затронул интересную тему. Очень интересную.
Как-то так получилось, что за последние два года достаточно много времени было посвящено мною именно этой тематике. По собственному опыту могу сказать следующее:
1. Как правило, речь идет об очень большой группе недетерминированных задач, связанных с отбором в огромном пространстве состояния в условиях ограничений. Как вы понимаете, речь идет о задачах из множества NP в различных модификациях.
2. Решение таких задач будет крайне неэффективным, без использования метода случайного отбора при формировании ветви поиска решения.
3. Использование только случайного отбора (и больше ничего), не приведет к эффективному решению задачи. Процент правильных решений будет незначительным, и с увеличением ключевых параметров задачи, доля правильных решений быстро сведется к нулю.
4. Для решения задачи, наряду со случайным (безусловным) отбором, необходимо включить в алгоритм процедуру отбора, основанную на каком-то правиле (условный отбор).
5. Не все модели случайного отбора являются одинаковыми, между ними есть различия.
Читая коментарии, убеждаюсь, что члены Хабро-Сообщества — интересные и содержательные люди. Это радует.
… почему то, в сязи с рассматриваемой тематикой вспомнил фразу Жванецкого: «Хорошая алкоголь, в малых дозах — полезна в неограниченном количестве».
Меня отец учил ухаживать за виноградником, учил простому ремеслу виноделия… потом я интересовался этим более серьезно, делал вина, ставил эксперименты,… У меня сформировалось устойчивое мнение о вине, и оно состоит в следующем:
— если вино натуральное, сделано по стандартной технологии, без всяких добавок, то это продукт питания. Такое вино полезно пить в умеренных дозах, если нет противопоказаний.
— если вино создано с нарушением стандартной технологии и со всякими добавками — то это алкоголь. Такую жидкость можно пить, но это не полезно.
Эти гниги написаны талантливыми людьми. Их приятно читать. Каждый извлечет для себя что то полезное. Иногда помогает «вправить» мозги. Спасибо автору за подборку!
Спасибо автору за искреннее изложение своей линии жизни.
Высоко ценю ваше отношение к студентам, к родным… У вас хорошая внутренняя мотивация.
Желаю вам здоровья и успехов на этом пути.
С удовольствием просмотрел. Ценю, ваше умение хорошо абстрагироваться и находить
прозрачные решения. У вас хороший потенциал для решения более сложных задач.
Замечательная статья. Прочитал с удовольствием.
Вопрос, который меня интересует, состоит в следующем:
1. Если выполнить генерацию случайных, равномерно-распределенных целых чисел на некотором интервале [ n1, n2 ], то окажется, что часть чисел из этого интервала повторяется два или более раза, а некоторых чисел в этой сгенерированной выборке вообще нет. Это плохо, но это факт. Что можете сказать по результатам работы вашего алгоритма – доля повторов и отсутствующих чисел увеличивается или уменьшается в сравнении с другими алгоритмами?
Хочу отметить, что вы предлагаете хороший, более совершенный алгоритм, который может служить замечательным инструментом для работы.
2. Я присоединяюсь к коллегам из хабра-сообщества, и хочу попросить, чтобы на графиках по каждой оси указывали название переменной и единицу измерения. Это не сложно. Тогда нам легче будет понять друг друга.
primetalk
Коммент:
t = n^0.781568*10^(-3.628927)
1. Где здесь «время комплектации растет линейно, с увеличением значения n»?
2. Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
Здесь ошибки нет. В тексте публикации об этом сказано в одном месте:
«В полученной зависимости линейный коэффициент (0.781568) меньше единицы, что приводит к тому, что с ростом значения n, линия регрессии и диагональ квадранта расходятся.»
и подробно объяснено чуть дальше по курсу:
«Такое поведение алгоритма, на первый взгляд кажется ошибочным, так как нет объективных причин, почему при малых значениях n алгоритм будет считать медленнее, чем при больших значениях. Однако, здесь ошибки нет, и это является объективным свойством данного алгоритма. Связано это с тем, что данный алгоритм является композицией из трех алгоритмов, которые работают с разной скоростью. Причем, количество строк, обрабатываемых каждым из этих алгоритмов, изменяется с ростом значения n. Именно по этой причине растет время счета на начальном интервале значений n=(10, 20, 30, 40), так как все расчеты на этом маленьком участке проводятся только на основе пятого блока процедур, который работает очень эффективно, но не так быстро, как первый блок процедур. Таким образом, учитывая, что время счета, необходимое для расположения ферзя на одной строке, уменьшается с увеличением размера шахматной доски, временную сложность данного алгоритма можно назвать убывающей – линейной»
Я не хотел на этом акцентировать внимание. И так разговоры только о том, что это невозможно. Вместо того, чтобы просто взять и проверить, все комментарии свелись к общипыванию ромашки – верю не верю.
А Вам, спасибо за настырность! Ценю таких.
«Ваш комменёарий показывает только то, что вы не понимаете смысл термина «детерминированный алгоритм». Единственным критерием детерминированности алгоритма является то, что он всегда возвращает один и тот же результат на одних и тех же входных данных. И это всё!
Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Коммент-2
«Ваше понимание «детерминированности» очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.»
Я хотел бы ответить на оба комментария, они близки по смыслу. Надеюсь коллеги не обидятся. Для этого, прошу вначале внимательно прочитать мой ответ на комментарий, приведенный выше (Комментарий – О недетерминированном поиске)
Думаю, что очевидный термин «детерминированный алгоритм» мы все понимаем одинаково, поэтому не стоит на это терять время. Кстати, я нигде не сравнивал детерминированность самой задачи с процедурой Back Tracking, это разные вещи. Не знаю, почему это привязываете ко мне. Здесь интересно другое. Вы пишите:
«Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»
Я думаю, что Вы здесь имели в виду не «выбор следующей ветви», а продолжение формирования ветви с заданного уровня. Ветвь мы не выбираем, а формируем ветвь на каждом шаге поиска решения.
В предложенном алгоритме, на последнем, самом ответственном этапе формирования ветви поиска решения возникает ситуация, когда:
— в списке строк, ранжированных по определенному критерию приоритета, встречаются две или более строки с одинаковым приоритетом. В этом случае, выбор индекса строки производится случайным образом,
— среди свободных позиций, в отобранной строке, встречаются две или более позиции, с одинаковым приоритетом. В этом случае, выбор индекса свободной позиции в отобранной строке так же производится случайным образом.
Я решил привести это, так как Ваш комментарий предполагает, что Вы понимаете о чем идет речь.
«Вопросы выше связаны с неправильным названием статьи. Тема «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 неверные. Хотя, возможно, Вы что-то другое имели ввиду.
Коммент:
«Хотя вообще, автор проделал большой труд и убил очень много времени. Поэтому он молодец. Но всё же пока что его результат неидеален. Идеал — это линейное время во всех случаях.»
Спасибо, что сказали доброе слово в мой адрес. Хоть кто-то, сознательный об этом подумал.
Я не знаю, как выглядит идеальный алгоритм, поэтому использую термин эффективный. Хотя, ни тот не другой не имеют объективной единицы измерения, и при сравнении двух алгоритмов, решающих одну и ту же задачу, все сводится к временной сложности, сложности по требуемой памяти и т.д.
Если, Вы считаете, что «Идеал — это линейное время во всех случаях.», то я хочу снова подтвердить, что здесь линейное время во всех случаях, хотя это я еще не считаю идеалом.
Вопрос:
«Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.»
Я хочу попросить Вас, все таки, не спешить и вникнуть в суть того, что сказано. Фраза «С помощью строгих математических методов» — означает, только то, что проблема решается только на основе определений, формулировке лемм и доказательстве теорем. Без применения методов алгоритмической математики и компьютерного моделирования. А каком «полиномиальном времени» строгих математических методов Вы говорите.
«прямым перебором или обычным backtracking'ом»
— Back Tracking является неотъемлемым компонентом прямого перебора, для поиска всех решений. Поэтому, здесь «или» не уместна. Когда Вы ищите все возможные решения, то постоянно «заходите» в тот или иной тупик, и вынуждены возвращаться назад на один шаг назад (если опять тупик — то на два или более шагов назад). Для этого Вы должны запомнить все основные параметры нескольких последовательных уровней, чтобы можно было восстановить исходное состояние на данном уровне. Попробуйте, это все очень интересно.
Мне кажется, что Вы хотели написать что-то очень интересное, но оно не так вышло. Вот смотрите, одна из задач из множества NP-Complete (n-Queens Completion Problem). Пусть размер стороны шахматной доски n=100. Число способов выбора в произвольном порядке 100 строк для расположения ферзя равно 100!.. Когда мы выбираем строку, то среди оставшихся свободных позиций, мы должны выбрать одну позицию, чтобы расположить там ферзь. Среднее число всех возможных вариантов выбора произвольной свободной позиции во всех строках равно 10124 (это значение получено на основе 100 000 вычислительных экспериментов). Итого, пространство перебора всех возможных вариантов составляет 100! * 10124. Представим себе, что на шахматной доске 100 х 100 правильно расставлена композиция из 27 ферзей. Вы полагаете, что для комплектации данной композиции до полного решения мне нужен «полный перебор всех возможных вариантов»? Этого категорически делать не надо. Наоборот, цель будет состоять в том, чтобы максимально избегать этого. Нужно найти правила, которые позволят «лавировать» в этом огромном пространстве выбора и достичь своей цели. Нужно «стараться знать», что выбирать на каждом шаге, чтобы не ошибиться и дойти до цели.
«…иначе задача не является NP-полной»
Вы грамотный специалист, советую посмотреть определение NP-Complete задач. Необходимость полного перебора всех возможных вариантов никак не связано с тем, относится ли задача к множеству NP-Complete.
«А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом
Перебор же »
— Я в самом деле не встречал публикаций, в которых приводится детерминированный алгоритм решения какой-либо из NP-полных задач в широком диапазоне изменчивости основного параметра задачи. Мне реально это интересно, поэтому, если Вы знаете такую публикацию, выложите ссылку.
Решить задачу детерминировано, означает последовательно формировать ветвь поиска решения от начала до конца, нигде не «спотыкаясь». Это означает получить решение задачи, и ни разу не использовать процедуру Back Tracking, так как идете «верной дорогой». Можете Вы привести какой либо алгоритм решения одной из задач семейства NP-Complete, в которой бы не использовалась процедура Back Tracking?
Думаю, что не удастся. Мы выполняем Back Tracking и возвращаемся назад, чтобы с какой-то позиции снова продолжать строить ветвь поиска решения, надеясь, что «на этот раз повезет» и дойдем до цели. Если есть Back Tracking, значит есть неопределенность в том, что выбирать. Чем меньше число случаев использования процедуры Back Tracking, тем более эффективным является алгоритм.
Я целенаправленно занимался этим вопросом, после того, как был разработан алгоритм решения n-Queens Completion Problem. Это заняло слишком много времени, но, в итоге удалось изменить алгоритм таким образом, что на достаточно широком интервале значений n, в 50% случаях процедура Back Tracking ни разу не используется при формировании полного решения.
— ценю Ваш юмор, только давайте подойдем к вопросу серьезно. Выше я уже писал, что на основе строгого математического подхода, данную задачу и другие аналогичные задачи решить невозможно. Я утверждаю, что задачи такого класса, с большой вероятностью могут быть решены на основе алгоритмической математики с использованием Computational Simulation. Поэтому формального доказательства, в данной задаче, и других подобных задачах быть не может. Я не ставил перед собой цель строго математически доказать P=NP или P ≠ NP. Возьму на себя смелость нагло утверждать, что строго математически это никто не докажет, и что самое интересное, в этом нет никакого смысла. Нужно просто брать конкретную задачу из множества NP-Complete и «конкретно» ее решать. То, что одну из задач из этого семейства удалось решить, пока говорит только о том, что это возможно. И не более того.
Я не люблю и не использую слова «революция», «прорыв» или что-то подобное. Оно здесь не к месту. Считаю полезным концентрироваться на задаче, и если удастся – жить внутри задачи. «Там изнутри все видно».
Не знаю, как относиться к Вашим словам, про «просто качественный алгоритм, который работает на подмножестве параметров.». Воспринимаю как намек на положительную оценку. А если серьезно, то давайте подумаем. В интернет публикации n-Queens bibliography — 342 references приводятся ссылки на 342 статьи, которые прямо или косвенно, относятся к тематике n-Queens Problem. Можете найти хотя бы одну публикацию, в которой использовался такой огромный объем результатов вычислительных экспериментов. Ведь я рассматривал диапазон значений размера шахматной доски от 7 до 100 миллионов. Причем, там, где это было приемлемо по времени, размер сформированной выборки составлял один миллион. Это только для одного конкретного значения n. Прежде чем вынести полученные результаты на обсуждение, алгоритм многократно тестировался. Не будет ошибкой, если я скажу, что за полтора года алгоритм тестировался несколько десятков миллионов раз.
« Про дядю Вову»
В России только «один дядя Вова», думал Вы про него. Раскрыл – оказалось совсем другое.
Не может быть и речи о том, что «информацию сжимал». Я готов предоставить любому члену нашего Хабра-Сообщества исходный текст программы (на Матлабе) для всевозможного прогона. Об этом я писал в предисловии к статье. Это важная и сильная составляющая Хабра-Сообщества, когда члены сообщества могут свободно проверить те или иные алгоритмы и открыто высказать свое мнение.
— нигде в тексте нет и не может быть намека на то, что временная сложность алгоритма зависит от вычислительного устройства. Так же, выбор языка программирования не будет влиять на временную сложность. Не могу понять, откуда у Вас такая ассоциация.
Характеристики вычислительного устройства, обычно приводятся в публикациях, чтобы читатель мог оценить время выполнения тех или иных решений.
Вопрос: «…Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде»
Скриптовый язык Матлаба, это почти тот же псевдокод. В ближайшее время, исходный код с подробными комментариями, будет опубликован на Хабре. Это даст возможность проверить.
Изначально, я ставил цель оценить временную сложность на основе вычислительных экспериментов. Что, в принципе и было сделано.
Вопрос: «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-полных задач. Буду рад, если сообщите об этом.
О революции нигде в тексте нет и намека. Это другая материя. А то, что временная сложность алгоритма линейная – так это правда. Это же легко проверить. Я в предисловии к статье писал, если у Вас есть возможность запустить программу на Матлабе, то напишите мне (в предисловии есть мой e-mail). Я вышлю Вам программу (алгоритм) для тестирования. Это не займет у Вас много времени, программа работает очень быстро.
«Такое заявление требует убедительных доказательств, …»
Корректно сформулированные вычислительные задачи можно решить на основе строгих математических методов (на основе определений, формулировке лемм и доказательстве теорем), либо с помощью алгоритмической математики на основе Computational Simulation. С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно. Об этом в конце статьи есть «философское замечание». Я тоже хотел строго математически, но заблуждался, причем долго. Подобного рода задачи можно решить только на основе алгоритмической математики. Что в принципе и было сделано (правда, для этого потребовалось слишком много времени).
А теперь, по поводу «убедительных доказательств…». Есть алгоритмическое решение данной задачи. Я уверен, что Вы серьезный человек, поэтому предлагаю Вам проверить работу алгоритма. Это совсем не сложно, и даст вам возможность обоснованно оценить работу алгоритма и сделать выводы.
«…то была бы опровергнута гипотеза P ≠ NP»
У страха глаза велики – я тоже «боялся», до определенной поры. Не надо демонизировать. Все гораздо сложнее и интереснее. Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики. В каждом случае будет свой подход, хотя, что-то общее в алгоритме решения будет их объединять. Утверждать, что после решения n-Queens Completion Problem, все остальные задачи из множества NP-Complete сразу завалятся, будет неверно. Я не говорю об полиномиальном сведении решения одной сложной задачи к решению другой задачи. Я имею ввиду разработку эффективного алгоритма для решения конкретной задачи.
Проблема, которая рассматривается в публикации, принципиально важная и достаточно сложная. Мне показалось, что будет правильным привести подробное изложение результатов исследования, без «темных» мест.
Вопрос:… может ли он найти все возможные расстановки ферзей на доске?
Все возможные расстановки ферзей на доске означает все полные решения 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 — говорит об эффективности данного алгоритма. Но ничего абсолютно совершенного нет. Я буду рад, если Вы или кто-то другой честно и обоснованно покажет слабые стороны данного алгоритма. Ведь цель нашего общения — в обмене информацией и развитии.
Подробно, аккуратно, доходчиво,…
Ценю ваше уважительное отношение к читателям. Это мне понравилось.
Буду рад помочь вам корректно ставить сложные задачи в области Искусственного интеллекта, и искать пути их решения. Если сочтете интересным, пишите. (ericgrig@gmail.com)
1. Это интересная, сложная, и трудно разрешимая задача. Больше 20 лет исследований (различные команды + большие вычислительные мощности) не привели к эффективному решению. Может формулировка задачи на другом уровне абстракции и использование новых идей позволит достичь успеха.
2. Задача мне интересна не только на позновательном уровне. Так получилось, что в ближайшие год-полтора мне придется уделить ей часть своего времени.
3. Я прицепил слово «безбашный» в кавычках к задаче, подразумевая, что задача достаточно сложная и до сих пор не имеет завершенного решения. Если данная публикация мотивирует амбициозных членов ХабраСообщества к ее решению, так это похвально.
В нашем ХабраСообществе много рассудительных людей, которые с пониманием отнесутся к данной научно-познавательной публикации. Думаю, ее цель — создать побудительные мотивы к «безбашным» задачам у молодых амбициозных хаброчитателей. Таких у нас много…
Реально мне хотелось бы узнать больше информации об исследованиях по предсказанию структуры белков. Интересная задача — «за душу берет». Надеюсь, Вячеслав когда нибудь об этом напишет более подробно.
Как-то так получилось, что за последние два года достаточно много времени было посвящено мною именно этой тематике. По собственному опыту могу сказать следующее:
1. Как правило, речь идет об очень большой группе недетерминированных задач, связанных с отбором в огромном пространстве состояния в условиях ограничений. Как вы понимаете, речь идет о задачах из множества NP в различных модификациях.
2. Решение таких задач будет крайне неэффективным, без использования метода случайного отбора при формировании ветви поиска решения.
3. Использование только случайного отбора (и больше ничего), не приведет к эффективному решению задачи. Процент правильных решений будет незначительным, и с увеличением ключевых параметров задачи, доля правильных решений быстро сведется к нулю.
4. Для решения задачи, наряду со случайным (безусловным) отбором, необходимо включить в алгоритм процедуру отбора, основанную на каком-то правиле (условный отбор).
5. Не все модели случайного отбора являются одинаковыми, между ними есть различия.
… почему то, в сязи с рассматриваемой тематикой вспомнил фразу Жванецкого: «Хорошая алкоголь, в малых дозах — полезна в неограниченном количестве».
Меня отец учил ухаживать за виноградником, учил простому ремеслу виноделия… потом я интересовался этим более серьезно, делал вина, ставил эксперименты,… У меня сформировалось устойчивое мнение о вине, и оно состоит в следующем:
— если вино натуральное, сделано по стандартной технологии, без всяких добавок, то это продукт питания. Такое вино полезно пить в умеренных дозах, если нет противопоказаний.
— если вино создано с нарушением стандартной технологии и со всякими добавками — то это алкоголь. Такую жидкость можно пить, но это не полезно.
Высоко ценю ваше отношение к студентам, к родным… У вас хорошая внутренняя мотивация.
Желаю вам здоровья и успехов на этом пути.
С удовольствием просмотрел. Ценю, ваше умение хорошо абстрагироваться и находить
прозрачные решения. У вас хороший потенциал для решения более сложных задач.
Желаю успехов!
Замечательная статья. Прочитал с удовольствием.
Вопрос, который меня интересует, состоит в следующем:
1. Если выполнить генерацию случайных, равномерно-распределенных целых чисел на некотором интервале [ n1, n2 ], то окажется, что часть чисел из этого интервала повторяется два или более раза, а некоторых чисел в этой сгенерированной выборке вообще нет. Это плохо, но это факт. Что можете сказать по результатам работы вашего алгоритма – доля повторов и отсутствующих чисел увеличивается или уменьшается в сравнении с другими алгоритмами?
Хочу отметить, что вы предлагаете хороший, более совершенный алгоритм, который может служить замечательным инструментом для работы.
2. Я присоединяюсь к коллегам из хабра-сообщества, и хочу попросить, чтобы на графиках по каждой оси указывали название переменной и единицу измерения. Это не сложно. Тогда нам легче будет понять друг друга.