• Тополиный пух, AMA #20, июль
    +1
    Спасибо Boomburum, я подумаю над этим.
  • Тополиный пух, AMA #20, июль
    +1
    Я имею ввиду принципиальное решение, которое позволит передвигаться вперед или назад, при просмотре публикаций большого объема, который сопровождается комментариями гораздо большего объема. Одним из наиболее простых решений я вижу пронумерованные ячейки на полосе скролла, нажал мышкой на нужную пронумерованную ячейку — попал на нужную «остановку».
  • Тополиный пух, AMA #20, июль
    +1
    Я хотел бы обратиться с еще одним предложением, которое, как мне кажется, может заинтересовать членов нашего ХабраСообщества.

    Есть несколько интересных (не реализованных) проектов, которые были подготовлены мною для реализации в будущем. Прошло достаточно много времени, и они не реализованы(так и остались на уровне папок, вопросов, идей и сопутствующих материалов). Думаю, я не один такой — у многих есть что предложить.
    Я хотел бы опубликовать такие проекты на Хабре, так-как уверен, что в сообществе есть замечательные программисты, которых это заинтересует. Я, со своей стороны, готов помочь таким разработчикам во всем для реализации проекта. Здесь речь идет о добровольных творческих отношениях и это не должно привести к конфликту интересов. Тем более, в зоне внимания членов сообщества.
  • Тополиный пух, AMA #20, июль
    +1
    TimeLine в yotube не нумеруется, а секции на скролле необходимо нумеровать (например, от 1 до 30).
    Вообще такое усовершенствование крайне актуально и для MS Word и для Total Commander. Буду рад, если первым эту функцию реализует наш Хабр.
  • Тополиный пух, AMA #20, июль
    +2
    Дорогие программисты портала Хабр, хочу поблагодарить команду, за то, что поддерживаете сайт в тонусе и развиваете его возможности. Хочу обратиться к Вам с предложением.

    1. Почти все статьи, публикуемые на Хабре, имеют большой размер, а, вместе с комментариями их длина становится больше. Чтобы вернуться назад, на какую-то позицию в статье, или пройтись вперед, как правило, мышкой передвигается вертикальный ползунок. Можно ли разделить на секции «колею» вертикального ползунка и пронумеровать эти секции? Тогда, нажав на соответствующую секцию, попадем примерно в нужную зону.
  • Начинаем веселье и объявляем конкурс хабрамемов
    +1
    1. «Если я правильно ошибаюсь, то данный кусок программы вы недоперепрограммировали».

    Начало этой фразы, часто с юмором использовал мой коллега Саша Коган, но в публикации я впервые встретил в этом году на Хабре:
    Bedal 17 марта 2020 в 14:28
    … если я правильно ошибаюсь,

    Возможно, в просторах интернета, это использовалось кем-то еще.

    Далее, несколько высказываний, которые мне приходилось слышать на обсуждениях проектов:

    2. «В вашем коде не хватает адреналина».

    3. «Вы ошибаетесь, с точностью до наоборот».

    4. Ваш код живет своей отдельной жизнью и не соответствует алгоритму…
    — Да, но он работает!

    5. Этот код еле дышит и искусственное дыхание не поможет.

    В заключение, «чтобы не вставать второй раз», … когда-то в Одессе на юморине мужик нес плакат, на котором было написано; «Будешь сок томатный пить – будешь девушек любить». Думаю, хороший намек программисту о здоровом образе жизни.

    От себя, хотел бы привести фразу, которую (к сожалению) поздно осознал:

    « Если ты сегодня не жил, то за тебя этот день прожил кто-то другой»
  • 10 интересных репозиториев на GitHub, полезных любому разработчику
    +1
    Спасибо автору за проделанную работу!
  • Давайте быстрокодить как профессионалы
    +1
    Спасибо за публикацию!
    Хороший материал. Посмотрел с интересом.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Вы согласитесь с тем, что:

    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. Я не вижу пока в этом смысла.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Я ценю, если коллеги пишут комментарии к публикации. Не важно какую, с «положительным» оттенком, или с «отрицательным». Равнодушие хуже всего. Я очень хотел бы, чтобы комментарии прямо или косвенно касались сути и содержания публикации. Ведь Хабр замечателен тем, что здесь можно услышать всестороннее обсуждение и объективную критику. Где еще можно получить такое? Я могу где-то что-то упустить, а коллеги это заметят. В этом и есть направляющая сила.

    А теперь о «путанице с детерминированностью». Хочу отметить, что как в остальных ответах на комментарии, так и здесь, я остаюсь в рамках предложенной публикации, и не выхожу на общие рассуждения. (Хотя, это мне нравится, но это отдельный разговор).

    Задача называется детерминированной, если при при одном и том же входном значении, на выходе всегда получается один и тот же результат. (Я привел простое и понятное определение. Исправьте меня, если что-то не так. Через 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 алгоритм может неверно отнести положительную композицию к группе отрицательных.
    (А то, будет как в анекдоте про бег на сто метров двух президентов: «Советские журналисты написали, что наш Брежнев прибежал вторым, а их Рейган — предпоследним», хотя было всего два участника).

  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Спасибо за поддержку!

    Вы даете дельный совет, наверное стоило все это разбить на части, и иначе преподнести.

    На счет узких мест — да там много разных узких мест. В самом изложении, я как-то на это не акцентировал внимание. Немного коснулся этой темы в предисловии, но это лишь небольшая часть.

    Бог с ними, с отрицательными оценками. Люди разные бывают, я на них не обижаюсь. Я предполагаю, что это славные ребята, просто погорячились.

    Я жалею только о том, что время потеряно, но не было содержательной дискуссии. Столько нюансов осталось за бортом, а это кому то могло быть полезным на практике.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Давайте вместе выясним, как Вы говорите «истинное положение вещей». (Надеюсь, что Вы внимательно прочитали текст публикации)

    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 оказалось достаточным, чтобы получить эффективное решение.

    Заданный Вами вопрос касается сути рассматриваемой проблемы. Если, и далее, что-то будет непонятно, напишите — я на них отвечу. Только, прошу Вас, войти в русло нормальной дискуссии. Не следует использовать фразы: »… упорно не желаете признавать сей прискорбный факт.", "… зациклились на идее «победы»". Я не думаю. что это Ваша обычная манера разговора.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Спасибо за совет!

    «Дыма без огня не бывает». Раз так среагировали те участники, кто комментировал, значит на то были причины. Жаль, что ни один из участников не задал вопрос, который был бы связан с сутью проблемы или с результатами исследования. Там в самом деле очень много интересного. За полтора года накопилось много чего интересного, и описание полученных результатов примерно в полтора раза больше, чем я выложил на Хабре.

    Вы правы в том, что нужно было произвести процедуру селекции и сжатия материала, и подать результаты в сокращенном виде. Наверное, тогда вопросы касались бы теме изложения.
  • n-Queens Completion Problem — линейный алгоритм решения
    +1
    Не совсем так. Среди журналов с открытым доступом, есть такие, где публикация проходит независимое рецензирование. Ниже перечислены некоторые из таких журналов, куда я обращался:

    — Journal of Artificial Intelligence Research

    — SMAI Journal of Computational Mathematics

    — Discrete Mathematics & Theoretical Computer Science

    В первых двух отказали, в последнем предстоит рассмотрение. Как писал в предисловии, чтобы публиковать статью в «Discrete Mathematics & Theoretical Computer Science», нужно вначале опубликовать ее в arXiv.org. Что и было сделано.

    Я думаю, что платные журналы необоснованно продают результаты труда ученых, за работу и исследования которых оплатили налогоплательщики. Этим вопросом должны заниматься на государственном уровне. Считаю, что информация должна быть в открытом доступе.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Я не нашел публикацию, в которой описывался бы конкретный алгоритм решения поставленной задачи. Есть алгоритмы для поиска списка всех решений n-Queens Problem, есть алгоритмы для быстрого нахождения одного решения для произвольного n. Но алгоритма, который конкретно решал бы задачу n-Queens Completion Problem я не нашел.

    Поэтому, об эффективности можно судить по нескольким характеристикам:

    — линейная временная сложность алгоритма,

    — среднее значение времени решения для любой случайной композиции, при некотором фиксированном значении n ( например, для n=1000, среднее время решения одной случайной композиции равно 0.062157 с.)

    — уменьшение числа случаев применения процедуры Back Tracking, при формировании ветви поиска решений.

    По поводу изменения названия — возможно, Вы правы. (Такой себе, смягчающий психологический эффект). Но, я написал как есть. Уже поздно что-то менять.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Спасибо!
    Вы затронули важный вопрос. С самого начала я планировал выложить исходный код в открытый доступ. Об этом я написал в пункте 7 предисловия:

    «7. Я подготовил исходный текст программы, с подробными комментариями, который, надеюсь, в ближайшее время будет опубликован на Хабре. Думаю, что те, кто интересуется решением сложных задач из семейства NP-Complete, найдут для себя что-нибудь интересное.»

    Немного задержался с «подробными комментариями». В течение нескольких дней выложу на англоязычном Хабре. Программу генерации случайной композиции для матрицы решения произвольного размера, выставлю на Google-диск (она построена на базе основной программы, нет смысла публиковать ее на Хабре).
    На GitHub почему-то «не потянуло», не знаю почему. Следующий проект выложу там.

    Я был уверен, что в процессе живого «комментарного» общения кто-то из членов Хабра-Сообщества откликнется на мой просьбу и протестирует алгоритм. Было интересно узнать объективное мнение независимого эксперта. Но не повезло, экспертов в обсуждении не было. После первого комментария:

    «Извините, я устал читать. Не покажете место, где кончаются очевидные вещи...»

    я понял, что дальше серьезного разговора не будет.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Спасибо!
    Почему то, я об этом даже не думал. Это намного проще и лучше воспринимается читателями.
    (В последнее время жестко сижу над проектом «Any — SAT», и даже выходя оттуда, остаюсь там). Спасибо!
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Комент:

    «Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм»

    Странно, Вы уже пишите 7-ой комментарий, так и ни разу не коснувшись самой сути алгоритма. Все вокруг определения понятий детерминированный, недетерминированный,… Судя по комментариям, у меня создается впечатление, что статью до конца Вы так и не прочитали.

    В статье достаточно ясно написано, что Back Tracking совершается только на один из трех базовых уровней, если на данном шаге решения, ветвь поиска решения приводит в тупик. Это никак не связано с тем, каким образом формировалась ветвь поиска, начиная с базового уровня. На основе некоторых выделенных правил, на основе генератора случайных чисел (ГСЧ). Не имеет значения, производится возврат на один из базовых уровней в зависимости от уровня решения задачи. Поэтому никакой взаимосвязи между использованием ГСЧ и применением процедуры Back Tracking нет. Думаю, это Вы поняли из самой статьи.
    То, что я писал Вам в комментарии, никак не связано с Back Tracking, и я их никак не связывал. Мне показалось, что Вам будет интересно узнать, каким способом используются оставшиеся ресурсы на последнем этапе, когда каждый шаг имеет принципиальное значение. Думаю, мы поняли друг друга.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Хочу, чуточку забегая вперед, ответить на комментарий нашего коллеги. с ником
    primetalk
    Коммент:

    t = n^0.781568*10^(-3.628927)

    1. Где здесь «время комплектации растет линейно, с увеличением значения n»?
    2. Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?


    Здесь ошибки нет. В тексте публикации об этом сказано в одном месте:

    «В полученной зависимости линейный коэффициент (0.781568) меньше единицы, что приводит к тому, что с ростом значения n, линия регрессии и диагональ квадранта расходятся.»

    и подробно объяснено чуть дальше по курсу:

    «Такое поведение алгоритма, на первый взгляд кажется ошибочным, так как нет объективных причин, почему при малых значениях n алгоритм будет считать медленнее, чем при больших значениях. Однако, здесь ошибки нет, и это является объективным свойством данного алгоритма. Связано это с тем, что данный алгоритм является композицией из трех алгоритмов, которые работают с разной скоростью. Причем, количество строк, обрабатываемых каждым из этих алгоритмов, изменяется с ростом значения n. Именно по этой причине растет время счета на начальном интервале значений n=(10, 20, 30, 40), так как все расчеты на этом маленьком участке проводятся только на основе пятого блока процедур, который работает очень эффективно, но не так быстро, как первый блок процедур. Таким образом, учитывая, что время счета, необходимое для расположения ферзя на одной строке, уменьшается с увеличением размера шахматной доски, временную сложность данного алгоритма можно назвать убывающей – линейной»

    Я не хотел на этом акцентировать внимание. И так разговоры только о том, что это невозможно. Вместо того, чтобы просто взять и проверить, все комментарии свелись к общипыванию ромашки – верю не верю.
    А Вам, спасибо за настырность! Ценю таких.
  • n-Queens Completion Problem — линейный алгоритм решения
    –1
    Коммент-1

    «Ваш комменёарий показывает только то, что вы не понимаете смысл термина «детерминированный алгоритм». Единственным критерием детерминированности алгоритма является то, что он всегда возвращает один и тот же результат на одних и тех же входных данных. И это всё!

    Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»

    Коммент-2

    «Ваше понимание «детерминированности» очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.»

    Я хотел бы ответить на оба комментария, они близки по смыслу. Надеюсь коллеги не обидятся. Для этого, прошу вначале внимательно прочитать мой ответ на комментарий, приведенный выше (Комментарий – О недетерминированном поиске)

    Думаю, что очевидный термин «детерминированный алгоритм» мы все понимаем одинаково, поэтому не стоит на это терять время. Кстати, я нигде не сравнивал детерминированность самой задачи с процедурой Back Tracking, это разные вещи. Не знаю, почему это привязываете ко мне. Здесь интересно другое. Вы пишите:

    «Перебор с возвратом (который вы называете Back Tracking) абсолютно детерминирован, если выбор следующей ветви производится не случайным образом.»

    Я думаю, что Вы здесь имели в виду не «выбор следующей ветви», а продолжение формирования ветви с заданного уровня. Ветвь мы не выбираем, а формируем ветвь на каждом шаге поиска решения.

    В предложенном алгоритме, на последнем, самом ответственном этапе формирования ветви поиска решения возникает ситуация, когда:

    — в списке строк, ранжированных по определенному критерию приоритета, встречаются две или более строки с одинаковым приоритетом. В этом случае, выбор индекса строки производится случайным образом,

    — среди свободных позиций, в отобранной строке, встречаются две или более позиции, с одинаковым приоритетом. В этом случае, выбор индекса свободной позиции в отобранной строке так же производится случайным образом.
    Я решил привести это, так как Ваш комментарий предполагает, что Вы понимаете о чем идет речь.
  • n-Queens Completion Problem — линейный алгоритм решения
    –2
    Коммент:
    «Вопросы выше связаны с неправильным названием статьи. Тема «n-Queens Completion Problem» предполагает именно строгое математическое решение, без ложно-негативных и прочих недетерминированных. Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?»

    Я снова хочу сказать, что n-Queens Completion Problem и другие проблемы подобного рода невозможно решить на основе строгих математических методов. Они могут быть решены на основе алгоритмической математики с применением Computational Simulation. Об этом, в ответах на комментарии, я уже писал несколько раз. В статье есть раздел «Замечание», и там есть «Философское замечание» с примером, который достаточно нагляден, и позволит ответить на поставленный вопрос. Будет правильно, если, все таки, Вы посмотрите хотя бы этот раздел.

    Коммент:
    «Тема «линейный алгоритм решения» предполагает решение ранее указанной задачи (n-Queens Completion Problem) за линейное время. Но что мы видим в реальности?»

    В реальности, данный алгоритм имеет линейную временную сложность. Размер выборки случайных композиций, которые были сформированы для определения времени решения n-Queens Completion Problem для n=1000, был равен одному миллиону. Это была своего рода контрольная точка. Для остальных значений n, из базового списка значений, размер выборки составлял 100 000 или меньше. Во всех случаях распределение времени решения для различных значений n является унимодальным, с длинным правым хвостом. Думаю, что объективное свойство именно данной задачи, а не алгоритма. Какой бы ни был замечательный алгоритм решения данной задачи, всегда будут «неудобные» композиции, которые потребуют большего времени для комплектации. Так вот, в статье я использовал среднее значение выборки времени решения для каждого значения n, и на его основе был построен график и были сделаны соответствующие выводы. Если в качестве основной характеристики времени счета использовать: модальное значение, медианное значение, минимальное значение, максимальное значение или усредненное значение из ограниченного интервала в единицах стандартного отклонения, то во всех случаях (подчеркиваю, во всех случаях) временная сложность алгоритма оказывается линейной. Я выбрал среднее значение как наиболее «содержательную» характеристику времени счета. Еще раз хочу ответить на Ваш вопрос – это то, что мы видим в реальности.

    Коммент:
    «Проблема в общем случае за линейное время не решается. Есть набор эвристик, которые в среднем дают хороший результат, но в частных случаях уводят время в полиномиальное, а то и в экспоненциальное. Собственно противоречие между заявлением про «линейное время» и заявленной темой (n-Queens Completion Problem) и составляют суть комментариев выше (от тех, кто решил возразить).»

    Я, в общем случае, проблему решения задач из семейства NP-Complete нигде в публикации не рассматривал. Всюду речь идет только об одной конкретной задаче: n-Queens Completion. Я не могу говорить за все задачи из этого семейства, но конкретно про n-Queens Completion я утверждаю, что предложенный алгоритм решает данную задачу за линейное время. Причем, на всем диапазоне значений n от 7 до 100 миллионов. Это же легко проверить, я уже полдня объясняю это уважаемым коллегам. Зачем выдумывать что-то с потолка, если можно потратить 10-15 минут и убедиться в этом.

    Как можно утверждать, что алгоритм «в частных случаях уводят время в полиномиальное, а то и в экспоненциальное». Откуда это следует? Как я писал выше, какой бы показатель распределения времени счета вы не выбрали, вы получите график, который показывает, что временная сложность является линейной. Ваше высказывание эквивалентно утверждению, что данные в таблице 2 неверные. Хотя, возможно, Вы что-то другое имели ввиду.

    Коммент:
    «Хотя вообще, автор проделал большой труд и убил очень много времени. Поэтому он молодец. Но всё же пока что его результат неидеален. Идеал — это линейное время во всех случаях.»

    Спасибо, что сказали доброе слово в мой адрес. Хоть кто-то, сознательный об этом подумал.
    Я не знаю, как выглядит идеальный алгоритм, поэтому использую термин эффективный. Хотя, ни тот не другой не имеют объективной единицы измерения, и при сравнении двух алгоритмов, решающих одну и ту же задачу, все сводится к временной сложности, сложности по требуемой памяти и т.д.
    Если, Вы считаете, что «Идеал — это линейное время во всех случаях.», то я хочу снова подтвердить, что здесь линейное время во всех случаях, хотя это я еще не считаю идеалом.
  • n-Queens Completion Problem — линейный алгоритм решения
    –2
    С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно

    Вопрос:

    «Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.»

    Я хочу попросить Вас, все таки, не спешить и вникнуть в суть того, что сказано. Фраза «С помощью строгих математических методов» — означает, только то, что проблема решается только на основе определений, формулировке лемм и доказательстве теорем. Без применения методов алгоритмической математики и компьютерного моделирования. А каком «полиномиальном времени» строгих математических методов Вы говорите.

    «прямым перебором или обычным backtracking'ом»

    — Back Tracking является неотъемлемым компонентом прямого перебора, для поиска всех решений. Поэтому, здесь «или» не уместна. Когда Вы ищите все возможные решения, то постоянно «заходите» в тот или иной тупик, и вынуждены возвращаться назад на один шаг назад (если опять тупик — то на два или более шагов назад). Для этого Вы должны запомнить все основные параметры нескольких последовательных уровней, чтобы можно было восстановить исходное состояние на данном уровне. Попробуйте, это все очень интересно.
  • n-Queens Completion Problem — линейный алгоритм решения
    –3
    Вопрос: ««Единственный алгоритм нахождения точного решения 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.
  • n-Queens Completion Problem — линейный алгоритм решения
    –1
    Вопрос:
    «А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом
    Перебор же »

    — Я в самом деле не встречал публикаций, в которых приводится детерминированный алгоритм решения какой-либо из NP-полных задач в широком диапазоне изменчивости основного параметра задачи. Мне реально это интересно, поэтому, если Вы знаете такую публикацию, выложите ссылку.

    Решить задачу детерминировано, означает последовательно формировать ветвь поиска решения от начала до конца, нигде не «спотыкаясь». Это означает получить решение задачи, и ни разу не использовать процедуру Back Tracking, так как идете «верной дорогой». Можете Вы привести какой либо алгоритм решения одной из задач семейства NP-Complete, в которой бы не использовалась процедура Back Tracking?
    Думаю, что не удастся. Мы выполняем Back Tracking и возвращаемся назад, чтобы с какой-то позиции снова продолжать строить ветвь поиска решения, надеясь, что «на этот раз повезет» и дойдем до цели. Если есть Back Tracking, значит есть неопределенность в том, что выбирать. Чем меньше число случаев использования процедуры Back Tracking, тем более эффективным является алгоритм.

    Я целенаправленно занимался этим вопросом, после того, как был разработан алгоритм решения n-Queens Completion Problem. Это заняло слишком много времени, но, в итоге удалось изменить алгоритм таким образом, что на достаточно широком интервале значений n, в 50% случаях процедура Back Tracking ни разу не используется при формировании полного решения.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Вопрос: «Т.е. программа работает, но в конечном итоге, формального доказательства не будет и, очевидно никакого «прорыва» — просто качественный алгорим, который работает на подмножестве параметров.»

    — ценю Ваш юмор, только давайте подойдем к вопросу серьезно. Выше я уже писал, что на основе строгого математического подхода, данную задачу и другие аналогичные задачи решить невозможно. Я утверждаю, что задачи такого класса, с большой вероятностью могут быть решены на основе алгоритмической математики с использованием Computational Simulation. Поэтому формального доказательства, в данной задаче, и других подобных задачах быть не может. Я не ставил перед собой цель строго математически доказать P=NP или P ≠ NP. Возьму на себя смелость нагло утверждать, что строго математически это никто не докажет, и что самое интересное, в этом нет никакого смысла. Нужно просто брать конкретную задачу из множества NP-Complete и «конкретно» ее решать. То, что одну из задач из этого семейства удалось решить, пока говорит только о том, что это возможно. И не более того.

    Я не люблю и не использую слова «революция», «прорыв» или что-то подобное. Оно здесь не к месту. Считаю полезным концентрироваться на задаче, и если удастся – жить внутри задачи. «Там изнутри все видно».

    Не знаю, как относиться к Вашим словам, про «просто качественный алгоритм, который работает на подмножестве параметров.». Воспринимаю как намек на положительную оценку. А если серьезно, то давайте подумаем. В интернет публикации n-Queens bibliography — 342 references приводятся ссылки на 342 статьи, которые прямо или косвенно, относятся к тематике n-Queens Problem. Можете найти хотя бы одну публикацию, в которой использовался такой огромный объем результатов вычислительных экспериментов. Ведь я рассматривал диапазон значений размера шахматной доски от 7 до 100 миллионов. Причем, там, где это было приемлемо по времени, размер сформированной выборки составлял один миллион. Это только для одного конкретного значения n. Прежде чем вынести полученные результаты на обсуждение, алгоритм многократно тестировался. Не будет ошибкой, если я скажу, что за полтора года алгоритм тестировался несколько десятков миллионов раз.

    « Про дядю Вову»

    В России только «один дядя Вова», думал Вы про него. Раскрыл – оказалось совсем другое.
    Не может быть и речи о том, что «информацию сжимал». Я готов предоставить любому члену нашего Хабра-Сообщества исходный текст программы (на Матлабе) для всевозможного прогона. Об этом я писал в предисловии к статье. Это важная и сильная составляющая Хабра-Сообщества, когда члены сообщества могут свободно проверить те или иные алгоритмы и открыто высказать свое мнение.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Вопрос: «Скорость выполнения алгоритма на конкретном компьютере не имеет отношения к линейному/нелинейному времени.»

    — нигде в тексте нет и не может быть намека на то, что временная сложность алгоритма зависит от вычислительного устройства. Так же, выбор языка программирования не будет влиять на временную сложность. Не могу понять, откуда у Вас такая ассоциация.
    Характеристики вычислительного устройства, обычно приводятся в публикациях, чтобы читатель мог оценить время выполнения тех или иных решений.

    Вопрос: «…Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде»
    Скриптовый язык Матлаба, это почти тот же псевдокод. В ближайшее время, исходный код с подробными комментариями, будет опубликован на Хабре. Это даст возможность проверить.
    Изначально, я ставил цель оценить временную сложность на основе вычислительных экспериментов. Что, в принципе и было сделано.

    Вопрос: «n-Queens Completion problem является классической не детерминированной задачей. это утверждение противоречит формулировке задачи, данной в разделе «1. Введение». Там задача сформулирована детерминировано, как и положено задачам класса NP.»

    Вы затронули сложный и важный вопрос, поэтому давайте рассмотрим его чуть подробнее. Располагая ферзь в ячейку ( i, j ) матрицы решения n x n, мы, после этого, полностью исключаем строку i и столбец j. Кроме этого, мы исключаем все ячейки матрицы решения, которые расположены вдоль левой и правой диагоналей матрицы, проходящих через ячейку ( i, j ). Все действия здесь детерминированные. Но, мы не ведем учет состояния каждой ячейки матрицы решения. Ведь, даже для n=106 пришлось бы держать массив n=1012, и каждый раз проводить диагональные исключения, чтобы по ходу знать статус каждой ячейки. А как быть, если n будет равно сто миллионам? Это путь неэффективный, и нереальный для больших n. Получается, что в процессе решения задачи, мы не знаем статус ячеек в оставшихся свободных строках. Выбирая строку для расположения ферзя, мы должны:

    — проверить все ячейки этой строки,

    — выделить индексы свободных ячеек,

    — выбрать одну из этих ячеек, так, чтобы не ошибиться.

    То, что каждый раз необходимо определить статус ячейки (он неопределенный, пока это не установим) делает недетерминированным решение задачи. Хотя, изначальные действия детерминированные. Именно это имеется ввиду в тексте статьи.

    Вопрос: «False Negative решения… В детерминированном алгоритме решения NP-полных задач таких решений быть не может».

    False Negative решения появляются тогда, когда некое «изначально верное решение» алгоритм « считает» ошибочным. Это не связано с формулировкой задачи, это свойство алгоритма ошибаться. Чем лучше алгоритм, тем меньше False Negative решений.
    В задаче n-Queens Completion встречаются композиции, для которых очень сложно найти решение. Если программа 1000 раз выполняет процедуру Back Tracking и не может комплектовать данную композицию, то дальнейший поиск прекращается. Принимается решение, что данная композиция отрицательная, хотя изначально известно, что данная композиция может быть комплектована. Это компромисс затрат времени счета и эффективности работы алгоритма.

    А что касается «детерминированном алгоритме решения NP-полных задач», то я не знаю детерминированных алгоритмов решения NP-полных задач. Буду рад, если сообщите об этом.
  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Вопрос: « Автор заявляет о революции — о наличии линейного решения для NP-полной задачи.»

    О революции нигде в тексте нет и намека. Это другая материя. А то, что временная сложность алгоритма линейная – так это правда. Это же легко проверить. Я в предисловии к статье писал, если у Вас есть возможность запустить программу на Матлабе, то напишите мне (в предисловии есть мой e-mail). Я вышлю Вам программу (алгоритм) для тестирования. Это не займет у Вас много времени, программа работает очень быстро.

    «Такое заявление требует убедительных доказательств, …»

    Корректно сформулированные вычислительные задачи можно решить на основе строгих математических методов (на основе определений, формулировке лемм и доказательстве теорем), либо с помощью алгоритмической математики на основе Computational Simulation. С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно. Об этом в конце статьи есть «философское замечание». Я тоже хотел строго математически, но заблуждался, причем долго. Подобного рода задачи можно решить только на основе алгоритмической математики. Что в принципе и было сделано (правда, для этого потребовалось слишком много времени).

    А теперь, по поводу «убедительных доказательств…». Есть алгоритмическое решение данной задачи. Я уверен, что Вы серьезный человек, поэтому предлагаю Вам проверить работу алгоритма. Это совсем не сложно, и даст вам возможность обоснованно оценить работу алгоритма и сделать выводы.

    «…то была бы опровергнута гипотеза P ≠ NP»

    У страха глаза велики – я тоже «боялся», до определенной поры. Не надо демонизировать. Все гораздо сложнее и интереснее. Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики. В каждом случае будет свой подход, хотя, что-то общее в алгоритме решения будет их объединять. Утверждать, что после решения n-Queens Completion Problem, все остальные задачи из множества NP-Complete сразу завалятся, будет неверно. Я не говорю об полиномиальном сведении решения одной сложной задачи к решению другой задачи. Я имею ввиду разработку эффективного алгоритма для решения конкретной задачи.
  • n-Queens Completion Problem — линейный алгоритм решения
    +1
    Статья в самом деле большая. Для тех, кто пытался решать подобные задачи, наверное статья представит интерес. Для других, кто хочет кратко — достаточно посмотреть только Выводы (в конце статьи).
    Проблема, которая рассматривается в публикации, принципиально важная и достаточно сложная. Мне показалось, что будет правильным привести подробное изложение результатов исследования, без «темных» мест.

    Вопрос:… может ли он найти все возможные расстановки ферзей на доске?

    Все возможные расстановки ферзей на доске означает все полные решения 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 — говорит об эффективности данного алгоритма. Но ничего абсолютно совершенного нет. Я буду рад, если Вы или кто-то другой честно и обоснованно покажет слабые стороны данного алгоритма. Ведь цель нашего общения — в обмене информацией и развитии.
  • Опыт поступления в магистратуру в Германии (детальный разбор)
    +3
    Спасибо Илья, за хорошо проделанную работу!

    Подробно, аккуратно, доходчиво,…
    Ценю ваше уважительное отношение к читателям. Это мне понравилось.
    Буду рад помочь вам корректно ставить сложные задачи в области Искусственного интеллекта, и искать пути их решения. Если сочтете интересным, пишите. (ericgrig@gmail.com)
  • Эпическая миссия DeepMind по решению сложнейшей проблемы науки
    0
    Спасибо за содержательный комментарий к тому, что я написал. Особенно за ссылки, с удовольствием прочитаю. Если есть еще материалы, перешлите мне на ericgrig@gmail.com

    1. Это интересная, сложная, и трудно разрешимая задача. Больше 20 лет исследований (различные команды + большие вычислительные мощности) не привели к эффективному решению. Может формулировка задачи на другом уровне абстракции и использование новых идей позволит достичь успеха.

    2. Задача мне интересна не только на позновательном уровне. Так получилось, что в ближайшие год-полтора мне придется уделить ей часть своего времени.

    3. Я прицепил слово «безбашный» в кавычках к задаче, подразумевая, что задача достаточно сложная и до сих пор не имеет завершенного решения. Если данная публикация мотивирует амбициозных членов ХабраСообщества к ее решению, так это похвально.
  • Эпическая миссия DeepMind по решению сложнейшей проблемы науки
    0
    Мне нравится Демис Хассабис как одаренный человек, который не боится ставить и решать сложные задачи. И слава богу, что у него хватает рвения идти вперед. Кто мешал другим замечательным командам с хорошим финансированием, делать нечто подобное или лучше? Поэтому я отношусь к команде Хассабиса с уважением — я ценю их труд.

    В нашем ХабраСообществе много рассудительных людей, которые с пониманием отнесутся к данной научно-познавательной публикации. Думаю, ее цель — создать побудительные мотивы к «безбашным» задачам у молодых амбициозных хаброчитателей. Таких у нас много…

    Реально мне хотелось бы узнать больше информации об исследованиях по предсказанию структуры белков. Интересная задача — «за душу берет». Надеюсь, Вячеслав когда нибудь об этом напишет более подробно.
  • Как случайность может помочь математикам
    0
    Спасибо Вячеславу, что затронул интересную тему. Очень интересную.

    Как-то так получилось, что за последние два года достаточно много времени было посвящено мною именно этой тематике. По собственному опыту могу сказать следующее:

    1. Как правило, речь идет об очень большой группе недетерминированных задач, связанных с отбором в огромном пространстве состояния в условиях ограничений. Как вы понимаете, речь идет о задачах из множества NP в различных модификациях.

    2. Решение таких задач будет крайне неэффективным, без использования метода случайного отбора при формировании ветви поиска решения.

    3. Использование только случайного отбора (и больше ничего), не приведет к эффективному решению задачи. Процент правильных решений будет незначительным, и с увеличением ключевых параметров задачи, доля правильных решений быстро сведется к нулю.

    4. Для решения задачи, наряду со случайным (безусловным) отбором, необходимо включить в алгоритм процедуру отбора, основанную на каком-то правиле (условный отбор).

    5. Не все модели случайного отбора являются одинаковыми, между ними есть различия.
  • Алкоголь и математик(а)
    +1
    Читая коментарии, убеждаюсь, что члены Хабро-Сообщества — интересные и содержательные люди. Это радует.
    … почему то, в сязи с рассматриваемой тематикой вспомнил фразу Жванецкого: «Хорошая алкоголь, в малых дозах — полезна в неограниченном количестве».
    Меня отец учил ухаживать за виноградником, учил простому ремеслу виноделия… потом я интересовался этим более серьезно, делал вина, ставил эксперименты,… У меня сформировалось устойчивое мнение о вине, и оно состоит в следующем:
    — если вино натуральное, сделано по стандартной технологии, без всяких добавок, то это продукт питания. Такое вино полезно пить в умеренных дозах, если нет противопоказаний.
    — если вино создано с нарушением стандартной технологии и со всякими добавками — то это алкоголь. Такую жидкость можно пить, но это не полезно.
  • Алан Кей рекомендует почитать старые и забытые, но важные книги по программированию
    0
    Эти гниги написаны талантливыми людьми. Их приятно читать. Каждый извлечет для себя что то полезное. Иногда помогает «вправить» мозги. Спасибо автору за подборку!
  • Осваиваем компьютерное зрение — 8 основных шагов
    0
    Спасибо автору за хорошую подборку материалов.
  • А вот я «настоящий»
    +2
    Спасибо автору за искреннее изложение своей линии жизни.
    Высоко ценю ваше отношение к студентам, к родным… У вас хорошая внутренняя мотивация.
    Желаю вам здоровья и успехов на этом пути.
  • Спокойствие спокойствию рознь
    0
    Спасибо за публикацию!

    С удовольствием просмотрел. Ценю, ваше умение хорошо абстрагироваться и находить
    прозрачные решения. У вас хороший потенциал для решения более сложных задач.

    Желаю успехов!
  • Эффективная генерация числа в заданном интервале
    0
    Спасибо!

    Замечательная статья. Прочитал с удовольствием.
    Вопрос, который меня интересует, состоит в следующем:

    1. Если выполнить генерацию случайных, равномерно-распределенных целых чисел на некотором интервале [ n1, n2 ], то окажется, что часть чисел из этого интервала повторяется два или более раза, а некоторых чисел в этой сгенерированной выборке вообще нет. Это плохо, но это факт. Что можете сказать по результатам работы вашего алгоритма – доля повторов и отсутствующих чисел увеличивается или уменьшается в сравнении с другими алгоритмами?

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

    2. Я присоединяюсь к коллегам из хабра-сообщества, и хочу попросить, чтобы на графиках по каждой оси указывали название переменной и единицу измерения. Это не сложно. Тогда нам легче будет понять друг друга.
  • Доступное объяснение гипотезы Римана
    0
    Спасибо!
    Замечательное по стилю изложение. Звучит как песня.

    По сути проблемы. У меня было несколько попыток решение данной задачи. Результаты были никакие и задача откладывалась на следующий раз. (Это как «гантели для мозгов», чтобы «извилины не закисли»). Но, что интересно, критически оценивая свою любительскую работу, я пришел к важному выводу:

    1.Данную задачу и ряд других интересных задач, невозможно решить на основе стандартного математического подхода, т.е. на основе формулировки лемм, доказательства теорем и т.д.

    2.Данную задачу с большой вероятностью удастся решить на основе алгоритмической математики, т.е. решение не будет представлено в виде формулы, а будет представлено в виде алгоритма вычисления конкретной позиции следующего простого числа в последовательном списке натуральных чисел. Некоторым аналогом такого подхода может служить динамический ряд, когда на основе предисстории значений производится прогноз следующего значения.

    3.Хорошие алгоритмические решения дадут интервал (n_min, n_max) в котором должен находиться следующее простое число. Лучшим будет тот алгоритм, у которого значение
    n_max — n_min будет минимальным.
  • Путь к кнопке “бабло” по дороге из граблей
    +1
    Вначале хочу пожелать успехов всей команде в реализации и продвижении проекта.
    1.Думаю, что идея «торгуй на бирже так же, как тот крутой парень» достаточно жизнеспособна и найдет поддержку среди определенной категории трейдеров. Во всяком случае, образ Уоррена Буфета и действия большого числа подражателей может служить тому подтверждением.

    Если я правильно понимаю, то основная бизнес составляющая проекта – это предоставление услуги по демонстрации торговых действий некого успешного трейдера на выбранной вами бирже. Вы предполагаете, что успешный трейдер будет служить образом для подражания для ваших клиентов. В связи с этим есть несколько вопросов:

    -образ какого количества успешных трейдеров (экспертов) вы можете предложить своим клиентам для подражания?

    -на основе какой экспертной оценки вы подбираете этих успешных трейдеров?

    — как быть в том случае, если клиента интересует некая валютная пара (ХХХ, USD), но ни один из демонстрируемых экспертов в данный момент этим не занимается?

    -может ли быть такая ситуация, что действия экспертов будут быстрыми и клиенты не успеют копировать их действия?

    -есть много бирж, а на этих биржах торгуют достаточное количество успешных трейдеров. Будет ли у клиентов возможность «заказать» конкретного трейдера из заданной биржи (в хорошем смысле этого слова)?

    2.Тема, которой вы занимаетесь, мне интересна и близка. Только в той части, что касается прогноза цен произвольной валютной пары на один или более шагов вперед. (Возможно, это будет звучать не скромно, но нам удалось достичь очень высокой точности прогноза для различных валютных пар. Для каждой валютной пары проводился анализ поминутных суточных данных за три года. Это легко проверить). Сейчас все это находится на стадии разработки интернет проекта «prediction as a service».
    Хочу предложить членам команды принять участие в данном проекте. Ваш проект и данный проект взаимно дополняют друг друга. Если конечная цель – заработать деньги, то еще не известно из какого проекта Вы больше заработаете.

    3. Также, я хотел бы предложить совместно разработать эффективный алгоритм формирования торговой стратегии. Это интересная задача, и это именно то, что вы хотите предложить своим клиентам. (напишите мне (ericgrig@gmail.com). Уверен, что наше сотрудничество будет взаимно полезным).