Хорошая статья. Раскрыли тему с разных сторон. Думал в конце приведете свое высказывание: "Делай хорошо одно и умей взаимодействовать с другими, не создавая проблем".
Я имею ввиду принципиальное решение, которое позволит передвигаться вперед или назад, при просмотре публикаций большого объема, который сопровождается комментариями гораздо большего объема. Одним из наиболее простых решений я вижу пронумерованные ячейки на полосе скролла, нажал мышкой на нужную пронумерованную ячейку — попал на нужную «остановку».
Я хотел бы обратиться с еще одним предложением, которое, как мне кажется, может заинтересовать членов нашего ХабраСообщества.
Есть несколько интересных (не реализованных) проектов, которые были подготовлены мною для реализации в будущем. Прошло достаточно много времени, и они не реализованы(так и остались на уровне папок, вопросов, идей и сопутствующих материалов). Думаю, я не один такой — у многих есть что предложить.
Я хотел бы опубликовать такие проекты на Хабре, так-как уверен, что в сообществе есть замечательные программисты, которых это заинтересует. Я, со своей стороны, готов помочь таким разработчикам во всем для реализации проекта. Здесь речь идет о добровольных творческих отношениях и это не должно привести к конфликту интересов. Тем более, в зоне внимания членов сообщества.
TimeLine в yotube не нумеруется, а секции на скролле необходимо нумеровать (например, от 1 до 30).
Вообще такое усовершенствование крайне актуально и для MS Word и для Total Commander. Буду рад, если первым эту функцию реализует наш Хабр.
Дорогие программисты портала Хабр, хочу поблагодарить команду, за то, что поддерживаете сайт в тонусе и развиваете его возможности. Хочу обратиться к Вам с предложением.
1. Почти все статьи, публикуемые на Хабре, имеют большой размер, а, вместе с комментариями их длина становится больше. Чтобы вернуться назад, на какую-то позицию в статье, или пройтись вперед, как правило, мышкой передвигается вертикальный ползунок. Можно ли разделить на секции «колею» вертикального ползунка и пронумеровать эти секции? Тогда, нажав на соответствующую секцию, попадем примерно в нужную зону.
1. «Если я правильно ошибаюсь, то данный кусок программы вы недоперепрограммировали».
Начало этой фразы, часто с юмором использовал мой коллега Саша Коган, но в публикации я впервые встретил в этом году на Хабре: Bedal 17 марта 2020 в 14:28
… если я правильно ошибаюсь,
Возможно, в просторах интернета, это использовалось кем-то еще.
Далее, несколько высказываний, которые мне приходилось слышать на обсуждениях проектов:
2. «В вашем коде не хватает адреналина».
3. «Вы ошибаетесь, с точностью до наоборот».
4. Ваш код живет своей отдельной жизнью и не соответствует алгоритму…
— Да, но он работает!
5. Этот код еле дышит и искусственное дыхание не поможет.
В заключение, «чтобы не вставать второй раз», … когда-то в Одессе на юморине мужик нес плакат, на котором было написано; «Будешь сок томатный пить – будешь девушек любить». Думаю, хороший намек программисту о здоровом образе жизни.
От себя, хотел бы привести фразу, которую (к сожалению) поздно осознал:
« Если ты сегодня не жил, то за тебя этот день прожил кто-то другой»
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. Я не вижу пока в этом смысла.
Я ценю, если коллеги пишут комментарии к публикации. Не важно какую, с «положительным» оттенком, или с «отрицательным». Равнодушие хуже всего. Я очень хотел бы, чтобы комментарии прямо или косвенно касались сути и содержания публикации. Ведь Хабр замечателен тем, что здесь можно услышать всестороннее обсуждение и объективную критику. Где еще можно получить такое? Я могу где-то что-то упустить, а коллеги это заметят. В этом и есть направляющая сила.
А теперь о «путанице с детерминированностью». Хочу отметить, что как в остальных ответах на комментарии, так и здесь, я остаюсь в рамках предложенной публикации, и не выхожу на общие рассуждения. (Хотя, это мне нравится, но это отдельный разговор).
Задача называется детерминированной, если при при одном и том же входном значении, на выходе всегда получается один и тот же результат. (Я привел простое и понятное определение. Исправьте меня, если что-то не так. Через Google можно найти много определений, по сути сходящихся к данному.)
— на входе мы получаем случайную композицию из 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 алгоритм может неверно отнести положительную композицию к группе отрицательных.
(А то, будет как в анекдоте про бег на сто метров двух президентов: «Советские журналисты написали, что наш Брежнев прибежал вторым, а их Рейган — предпоследним», хотя было всего два участника).
Вы даете дельный совет, наверное стоило все это разбить на части, и иначе преподнести.
На счет узких мест — да там много разных узких мест. В самом изложении, я как-то на это не акцентировал внимание. Немного коснулся этой темы в предисловии, но это лишь небольшая часть.
Бог с ними, с отрицательными оценками. Люди разные бывают, я на них не обижаюсь. Я предполагаю, что это славные ребята, просто погорячились.
Я жалею только о том, что время потеряно, но не было содержательной дискуссии. Столько нюансов осталось за бортом, а это кому то могло быть полезным на практике.
Давайте вместе выясним, как Вы говорите «истинное положение вещей». (Надеюсь, что Вы внимательно прочитали текст публикации)
1. Все случайные композиции, размера k для произвольной шахматной доски размера n x n, условно можно разделить на два множества:
a) композиции, которые можно комплектовать до полного решения, в статье такие композиции называются «положительными»
b) композиции, которые невозможно комплектовать до полного решения, в статье такие композиции называются «отрицательными»
2. Как определить, является ли композиция положительной или отрицательной?
В предложенном алгоритме, заложено правило: «при формировании ветви поиска решения, на каждом шаге, прежде, чем установить ферзь, проверяется, свободна ли данная ячейка».
3. Это имеет принципиально важное значение. Это означает, что какую бы отрицательную композицию мы не рассматривали, алгоритм все время будет находиться в состоянии счета, пока не остановим.
4. С другой стороны, если алгоритм эффективный, то он должен быть в состоянии комплектовать любую положительную композицию за определенное время. Если мы сможем установить границу, когда любая положительная композиция обязательно комплектуется, то, после этой границы, композиция относится к множеству отрицательных композиций (так как никак не комплектуется).
5 Как установить границу, разделяющую зону, до которой все положительные композиции комплектуются?
Для этого был проведен, достаточно длительный по времени, вычислительный эксперимент:
Приведу текст из статьи с небольшим добавлением:
« Вначале был разработан достаточно быстрый алгоритм формирования массивов решений nQueens Problem для произвольного значения n.
Потом, на основе этой программы были сформированы большие выборки решений для базового списка значений n.
Размеры полученных выборок решений nQueens Problem для различных значений n, соответственно были равны:
Здесь, в скобках указывается список значений 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 оказалось достаточным, чтобы получить эффективное решение.
Заданный Вами вопрос касается сути рассматриваемой проблемы. Если, и далее, что-то будет непонятно, напишите — я на них отвечу. Только, прошу Вас, войти в русло нормальной дискуссии. Не следует использовать фразы: »… упорно не желаете признавать сей прискорбный факт.", "… зациклились на идее «победы»". Я не думаю. что это Ваша обычная манера разговора.
«Дыма без огня не бывает». Раз так среагировали те участники, кто комментировал, значит на то были причины. Жаль, что ни один из участников не задал вопрос, который был бы связан с сутью проблемы или с результатами исследования. Там в самом деле очень много интересного. За полтора года накопилось много чего интересного, и описание полученных результатов примерно в полтора раза больше, чем я выложил на Хабре.
Вы правы в том, что нужно было произвести процедуру селекции и сжатия материала, и подать результаты в сокращенном виде. Наверное, тогда вопросы касались бы теме изложения.
Не совсем так. Среди журналов с открытым доступом, есть такие, где публикация проходит независимое рецензирование. Ниже перечислены некоторые из таких журналов, куда я обращался:
В первых двух отказали, в последнем предстоит рассмотрение. Как писал в предисловии, чтобы публиковать статью в «Discrete Mathematics & Theoretical Computer Science», нужно вначале опубликовать ее в arXiv.org. Что и было сделано.
Я думаю, что платные журналы необоснованно продают результаты труда ученых, за работу и исследования которых оплатили налогоплательщики. Этим вопросом должны заниматься на государственном уровне. Считаю, что информация должна быть в открытом доступе.
Я не нашел публикацию, в которой описывался бы конкретный алгоритм решения поставленной задачи. Есть алгоритмы для поиска списка всех решений n-Queens Problem, есть алгоритмы для быстрого нахождения одного решения для произвольного n. Но алгоритма, который конкретно решал бы задачу n-Queens Completion Problem я не нашел.
Поэтому, об эффективности можно судить по нескольким характеристикам:
— линейная временная сложность алгоритма,
— среднее значение времени решения для любой случайной композиции, при некотором фиксированном значении n ( например, для n=1000, среднее время решения одной случайной композиции равно 0.062157 с.)
— уменьшение числа случаев применения процедуры Back Tracking, при формировании ветви поиска решений.
По поводу изменения названия — возможно, Вы правы. (Такой себе, смягчающий психологический эффект). Но, я написал как есть. Уже поздно что-то менять.
Спасибо!
Вы затронули важный вопрос. С самого начала я планировал выложить исходный код в открытый доступ. Об этом я написал в пункте 7 предисловия:
«7. Я подготовил исходный текст программы, с подробными комментариями, который, надеюсь, в ближайшее время будет опубликован на Хабре. Думаю, что те, кто интересуется решением сложных задач из семейства NP-Complete, найдут для себя что-нибудь интересное.»
Немного задержался с «подробными комментариями». В течение нескольких дней выложу на англоязычном Хабре. Программу генерации случайной композиции для матрицы решения произвольного размера, выставлю на Google-диск (она построена на базе основной программы, нет смысла публиковать ее на Хабре).
На GitHub почему-то «не потянуло», не знаю почему. Следующий проект выложу там.
Я был уверен, что в процессе живого «комментарного» общения кто-то из членов Хабра-Сообщества откликнется на мой просьбу и протестирует алгоритм. Было интересно узнать объективное мнение независимого эксперта. Но не повезло, экспертов в обсуждении не было. После первого комментария:
«Извините, я устал читать. Не покажете место, где кончаются очевидные вещи...»
я понял, что дальше серьезного разговора не будет.
Спасибо!
Почему то, я об этом даже не думал. Это намного проще и лучше воспринимается читателями.
(В последнее время жестко сижу над проектом «Any — SAT», и даже выходя оттуда, остаюсь там). Спасибо!
«Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм»
Странно, Вы уже пишите 7-ой комментарий, так и ни разу не коснувшись самой сути алгоритма. Все вокруг определения понятий детерминированный, недетерминированный,… Судя по комментариям, у меня создается впечатление, что статью до конца Вы так и не прочитали.
В статье достаточно ясно написано, что Back Tracking совершается только на один из трех базовых уровней, если на данном шаге решения, ветвь поиска решения приводит в тупик. Это никак не связано с тем, каким образом формировалась ветвь поиска, начиная с базового уровня. На основе некоторых выделенных правил, на основе генератора случайных чисел (ГСЧ). Не имеет значения, производится возврат на один из базовых уровней в зависимости от уровня решения задачи. Поэтому никакой взаимосвязи между использованием ГСЧ и применением процедуры Back Tracking нет. Думаю, это Вы поняли из самой статьи.
То, что я писал Вам в комментарии, никак не связано с Back Tracking, и я их никак не связывал. Мне показалось, что Вам будет интересно узнать, каким способом используются оставшиеся ресурсы на последнем этапе, когда каждый шаг имеет принципиальное значение. Думаю, мы поняли друг друга.
Спасибо!
Хорошая статья. Раскрыли тему с разных сторон. Думал в конце приведете свое высказывание: "Делай хорошо одно и умей взаимодействовать с другими, не создавая проблем".
Ценю, что вы умеете излагать просто и доходчиво.
Хорошая статья.
Есть несколько интересных (не реализованных) проектов, которые были подготовлены мною для реализации в будущем. Прошло достаточно много времени, и они не реализованы(так и остались на уровне папок, вопросов, идей и сопутствующих материалов). Думаю, я не один такой — у многих есть что предложить.
Я хотел бы опубликовать такие проекты на Хабре, так-как уверен, что в сообществе есть замечательные программисты, которых это заинтересует. Я, со своей стороны, готов помочь таким разработчикам во всем для реализации проекта. Здесь речь идет о добровольных творческих отношениях и это не должно привести к конфликту интересов. Тем более, в зоне внимания членов сообщества.
Вообще такое усовершенствование крайне актуально и для MS Word и для Total Commander. Буду рад, если первым эту функцию реализует наш Хабр.
1. Почти все статьи, публикуемые на Хабре, имеют большой размер, а, вместе с комментариями их длина становится больше. Чтобы вернуться назад, на какую-то позицию в статье, или пройтись вперед, как правило, мышкой передвигается вертикальный ползунок. Можно ли разделить на секции «колею» вертикального ползунка и пронумеровать эти секции? Тогда, нажав на соответствующую секцию, попадем примерно в нужную зону.
Начало этой фразы, часто с юмором использовал мой коллега Саша Коган, но в публикации я впервые встретил в этом году на Хабре:
Bedal 17 марта 2020 в 14:28
… если я правильно ошибаюсь,
Возможно, в просторах интернета, это использовалось кем-то еще.
Далее, несколько высказываний, которые мне приходилось слышать на обсуждениях проектов:
2. «В вашем коде не хватает адреналина».
3. «Вы ошибаетесь, с точностью до наоборот».
4. Ваш код живет своей отдельной жизнью и не соответствует алгоритму…
— Да, но он работает!
5. Этот код еле дышит и искусственное дыхание не поможет.
В заключение, «чтобы не вставать второй раз», … когда-то в Одессе на юморине мужик нес плакат, на котором было написано; «Будешь сок томатный пить – будешь девушек любить». Думаю, хороший намек программисту о здоровом образе жизни.
От себя, хотел бы привести фразу, которую (к сожалению) поздно осознал:
« Если ты сегодня не жил, то за тебя этот день прожил кто-то другой»
Хороший материал. Посмотрел с интересом.
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. Я не вижу пока в этом смысла.
А теперь о «путанице с детерминированностью». Хочу отметить, что как в остальных ответах на комментарии, так и здесь, я остаюсь в рамках предложенной публикации, и не выхожу на общие рассуждения. (Хотя, это мне нравится, но это отдельный разговор).
Задача называется детерминированной, если при при одном и том же входном значении, на выходе всегда получается один и тот же результат. (Я привел простое и понятное определение. Исправьте меня, если что-то не так. Через 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 алгоритм может неверно отнести положительную композицию к группе отрицательных.
(А то, будет как в анекдоте про бег на сто метров двух президентов: «Советские журналисты написали, что наш Брежнев прибежал вторым, а их Рейган — предпоследним», хотя было всего два участника).
Вы даете дельный совет, наверное стоило все это разбить на части, и иначе преподнести.
На счет узких мест — да там много разных узких мест. В самом изложении, я как-то на это не акцентировал внимание. Немного коснулся этой темы в предисловии, но это лишь небольшая часть.
Бог с ними, с отрицательными оценками. Люди разные бывают, я на них не обижаюсь. Я предполагаю, что это славные ребята, просто погорячились.
Я жалею только о том, что время потеряно, но не было содержательной дискуссии. Столько нюансов осталось за бортом, а это кому то могло быть полезным на практике.
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 оказалось достаточным, чтобы получить эффективное решение.
Заданный Вами вопрос касается сути рассматриваемой проблемы. Если, и далее, что-то будет непонятно, напишите — я на них отвечу. Только, прошу Вас, войти в русло нормальной дискуссии. Не следует использовать фразы: »… упорно не желаете признавать сей прискорбный факт.", "… зациклились на идее «победы»". Я не думаю. что это Ваша обычная манера разговора.
«Дыма без огня не бывает». Раз так среагировали те участники, кто комментировал, значит на то были причины. Жаль, что ни один из участников не задал вопрос, который был бы связан с сутью проблемы или с результатами исследования. Там в самом деле очень много интересного. За полтора года накопилось много чего интересного, и описание полученных результатов примерно в полтора раза больше, чем я выложил на Хабре.
Вы правы в том, что нужно было произвести процедуру селекции и сжатия материала, и подать результаты в сокращенном виде. Наверное, тогда вопросы касались бы теме изложения.
— Journal of Artificial Intelligence Research
— SMAI Journal of Computational Mathematics
— Discrete Mathematics & Theoretical Computer Science
В первых двух отказали, в последнем предстоит рассмотрение. Как писал в предисловии, чтобы публиковать статью в «Discrete Mathematics & Theoretical Computer Science», нужно вначале опубликовать ее в arXiv.org. Что и было сделано.
Я думаю, что платные журналы необоснованно продают результаты труда ученых, за работу и исследования которых оплатили налогоплательщики. Этим вопросом должны заниматься на государственном уровне. Считаю, что информация должна быть в открытом доступе.
Поэтому, об эффективности можно судить по нескольким характеристикам:
— линейная временная сложность алгоритма,
— среднее значение времени решения для любой случайной композиции, при некотором фиксированном значении n ( например, для n=1000, среднее время решения одной случайной композиции равно 0.062157 с.)
— уменьшение числа случаев применения процедуры Back Tracking, при формировании ветви поиска решений.
По поводу изменения названия — возможно, Вы правы. (Такой себе, смягчающий психологический эффект). Но, я написал как есть. Уже поздно что-то менять.
Вы затронули важный вопрос. С самого начала я планировал выложить исходный код в открытый доступ. Об этом я написал в пункте 7 предисловия:
«7. Я подготовил исходный текст программы, с подробными комментариями, который, надеюсь, в ближайшее время будет опубликован на Хабре. Думаю, что те, кто интересуется решением сложных задач из семейства NP-Complete, найдут для себя что-нибудь интересное.»
Немного задержался с «подробными комментариями». В течение нескольких дней выложу на англоязычном Хабре. Программу генерации случайной композиции для матрицы решения произвольного размера, выставлю на Google-диск (она построена на базе основной программы, нет смысла публиковать ее на Хабре).
На GitHub почему-то «не потянуло», не знаю почему. Следующий проект выложу там.
Я был уверен, что в процессе живого «комментарного» общения кто-то из членов Хабра-Сообщества откликнется на мой просьбу и протестирует алгоритм. Было интересно узнать объективное мнение независимого эксперта. Но не повезло, экспертов в обсуждении не было. После первого комментария:
«Извините, я устал читать. Не покажете место, где кончаются очевидные вещи...»
я понял, что дальше серьезного разговора не будет.
Почему то, я об этом даже не думал. Это намного проще и лучше воспринимается читателями.
(В последнее время жестко сижу над проектом «Any — SAT», и даже выходя оттуда, остаюсь там). Спасибо!
«Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм»
Странно, Вы уже пишите 7-ой комментарий, так и ни разу не коснувшись самой сути алгоритма. Все вокруг определения понятий детерминированный, недетерминированный,… Судя по комментариям, у меня создается впечатление, что статью до конца Вы так и не прочитали.
В статье достаточно ясно написано, что Back Tracking совершается только на один из трех базовых уровней, если на данном шаге решения, ветвь поиска решения приводит в тупик. Это никак не связано с тем, каким образом формировалась ветвь поиска, начиная с базового уровня. На основе некоторых выделенных правил, на основе генератора случайных чисел (ГСЧ). Не имеет значения, производится возврат на один из базовых уровней в зависимости от уровня решения задачи. Поэтому никакой взаимосвязи между использованием ГСЧ и применением процедуры Back Tracking нет. Думаю, это Вы поняли из самой статьи.
То, что я писал Вам в комментарии, никак не связано с Back Tracking, и я их никак не связывал. Мне показалось, что Вам будет интересно узнать, каким способом используются оставшиеся ресурсы на последнем этапе, когда каждый шаг имеет принципиальное значение. Думаю, мы поняли друг друга.