Как нужно решать задачу коммивояжёра? Часть третья

Начало
Предыдущая

Наиболее сложными типами графов для алгоритмов группы Lin & Kernighan (а, значит, и для нашего тоже) являются те, у которых даже в оптимальном туре встречаются очень большие (относительно средней) длины рёбер. Про один из таких графов (fl3795) мы уже успели «поплакаться в жилетку». Как оказалось, проблема эта настолько серьёзная, что тот самый DIMACS TSP Challenge (Center for Discrete Mathematics and Theoretical Computer Science) содержит целую серию подобных графов, причём размер графов для таких «кластеризованных» узлов ограничивается лишь третью миллиона, в то время, как графы с равномерно распределёнными случайными узлами достигают 10 миллионов. Мы, разумеется, исправили это «упущение» и сгенерили для себя также и «кластеризованные» графы на 1, 3 и 10 миллионов узлов, восстановив «симметрию» с графами равномерно-случайного распределения. Кроме того, мы ввели ещё более сложный тип графов, чем у DIMACS — графы с иерархической кластеризацией узлов (от с111 до c9999999). Так что же, и в самом деле эти графы так уж сложны для поиска оптимального тура? В действительности, дело обстоит чуть ли не с точностью до наоборот!

Предположим, нашему коммивояжёру нужно посетить все города в обитаемой части вселенной. Сложность задачи безмерна? Ничуть не бывало, она смехотворно мала (относительно, конечно) — пусть даже все планеты будут обитаемыми. И не только по сравнению с факториалом возможных туров, но даже по сравнению с общим числом рёбер этого графа! Судите сами: пока коммивояжёр не посетит все города Земли, ему незачем лететь на Марс — даже одна «лишняя» поездка туда-обратно гарантированно сожрёт любую надежду на улучшение тура на каждой из планет. Аналогично, незачем лететь на Альфу Центавра, пока не закончены все дела в Солнечной системе, незачем лететь в другое звёздное скопление, в другую галактику, т.е. сложность задачи практически линейна по числу узлов! Конечно, для разбивки исходного массива узлов «по планетам» придётся рассмотреть все рёбра графа, т.е. задача имеет все-таки квадратичную сложность. Одним словом, независимые группы узлов есть лучшее лекарство от комбинаторного взрыва, и его нужно использовать максимально, вплоть до искусственного создания таких групп.

Внимательный читатель, видимо, уже догадался, что решению TSP могут серьёзно помочь технологии баз данных. Графовых баз данных, разумеется. Они пригодятся и для сведения дерева вариантов к циклическому графу, и для хранения результатов перебора (чтобы избежать повторного счёта) и, что не менее важно, для отсечения бесперспективных веток дерева вариантов, и даже для банального откладывания задачи. Давайте подумаем, что и как нужно в этой базе хранить.

Для дальнейших рассуждений нам потребуется расширенное толкование понятия «граф», как нечто большее, чем просто совокупность узлов и рёбер. Основные концепции этого толкования (мультиузел, мультиребро) и операции над ними (слияние, расщепление и другие) изначально не имели к TSP ни малейшего отношения — они изложены в ряде наших работ по графовым СУБД, и мы не будем на этом останавливаться. По нашему мнению, именно переход к решению задачи коммивояжёра на уровень мультиузлов и есть (единственная!) возможность обеспечить требуемый скачок производительности.

Определения:
Мультиузел: инкапсулированная группа узлов.
Мультиребро: инкапсулированная группа рёбер.

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

Мы не зря вспомнили про базу данных «так поздно», после окончания работы всех предыдущих алгоритмов, когда текущий тур уже неплохо «вылизан». Именно в этот момент количество представляющих интерес для рассмотрения рёбер соизмеримо уже не с квадратом от числа узлов, а с самим этим числом, то есть объём БД многократно снижается. Те рёбра, для которых нам удастся доказать невозможность их вхождения в лучший тур, будут удаляться из рассмотрения. Когда их не останется вообще — задача решена. Пример: предположим, все узлы нашего графа расположены в вершинах правильного многоугольника, а текущий тур проходит по его сторонам. Нам остаётся лишь просмотреть все рёбра графа, и убедиться, что ни одного ребра, дающего надежду на улучшение текущего тура просто нет, т.е. задача решается точно, и даже не просто за полином, а за квадрат! Разумеется, такая «идиллия» в реальных графах почти никогда не встречается, но ЧАСТЬ узлов графа (обычно это одна треть от общего числа узлов) после окончания работы предыдущих алгоритмов связаны текущим туром так, что их оптимальность доказывать не требуется. Одно это уже снижает безумие комбинаторики с N! до (2N/3)! Всё равно много? Ничего, справимся!

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

Под альфа-границей понимается такая длина тура, для которой оказано, что ниже этой величины даже оптимальный тур быть не может. Бета-граница, напротив, ограничивает длину оптимального тура сверху — хуже уже найденного тура длина тоже быть не может. Но если бета-граница ограничивает перебор весьма эффективно и понятно (вспомните правило, что разность длин «старое-новое» должна быть положительной), то зачем нужна альфа-граница в плане ограничения перебора — непонятно. Я тоже долгое время не понимал. Позже попытаюсь подробно проиллюстрировать, а пока поверьте на слово: она нам очень даже пригодится!

Как же мы будем считать альфа-границу? Есть разные способы. Можно, например, найти самое короткое ребро графа и умножить его длину на количество узлов. Можно найти самые короткие рёбра для каждого узла и сложить их длины. Можно найти по два самых коротких ребра для каждого узла (ведь для любого тура у каждого узла имеется по два его ребра) и посчитать их полусумму. Все эти способы, во-первых, требуют просмотра всех рёбер графа и, во-вторых, дают весьма грубую оценку реальной длины тура, которая может в некоторых случаях (для тех же «кластеризованных» графов) превышать рассчитанную подобным образом альфа-границу в десятки, сотни, тысячи, миллионы раз! Впрочем, можно вообще ничего не считать и тупо определить альфа-границу нулём (имея в виду, что мы решаем задачу для рёбер с неотрицательной длиной), и столь же тупо предположить в начале обсчёта, что каждый узел графа является отдельным мультиузлом, а дальнейшая их конфигурация определяется слиянием.

Бросаться сразу в омут каскадной рекурсии нельзя — расчёты вполне могут затянуться в буквальном смысле на тысячелетия. Поэтому делаем так: начинаем обсчёт с самых маленьких мультиузлов, каскадно: вначале обсчитываем все мультиузлы размером в 1 узел, затем 2-3 узла, 4-7, 8-15 и далее по степени двойки. В отличие от работы «среднего» алгоритма, если во время расчёта было найдено улучшение текущего тура, расчёт немедленно прекращается. Точный как бы говорит: «Что вы мне подсунули? Это не оптимальный тур — вот тур короче! Пусть скоростной работает»! Иными словами, ни один из алгоритмов вообще не ищет точного решения — в том числе, и точный, который лишь доказывает оптимальность текущего тура.

Моделирование


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

Итак, какую-то вроде как работающую версию алгоритма я сделал и заготовил для неё две «подлянки» — для графов (burma14 и eil51) подсунул туры, о которых я знаю совершенно точно, что они НЕ оптимальные. И локальные минимумы там более-менее устойчивые — по крайней мере, скоростной алгоритм из них так и не выбрался. Но тут начались сюрпризы уже для меня: программа хладнокровно отмахнулась от сверхмалых графов, впервые дёрнулась на r7 (там 4 пучка рёбер-кандидатов представляли потенциальный интерес) и… не менее хладнокровно отмахнулась и от них! Оказывается, рекурсивную процедуру проверки кандидатов (тогда ещё не написанную) и вызывать-то не требуется: уже сама сборка кандидатов в единый тур показала что решения здесь нет, и быть не может! Забегая вперёд, скажу, что и во всех остальных случаях сборка в тур выполняет роль мощнейшего фильтра: на рекурсию прорываются (в зависимости от конфигурации графа и текущего тура) обычно всего лишь 5-10% кандидатов.

Обрадованный таким «с неба свалившимся» ускорением, да ещё и в самом потенциально опасном месте, я переместил отладку в точку, где рекурсия уж точно понадобится… и тут меня ожидал сюрприз похлеще первого! Я был настолько ошарашен тем, насколько нахально и элегантно программа расправилась с моей «подлянкой» для burma14, что поначалу даже не понял, что произошло! Первый же попавший в новое место отладки вариант показал, что рекурсия тоже не требуется, ибо процедура сборки кандидатов в тур собрала их… точнёхонько в оптимальный! Мало того: эта гнида точно так же, в три прохода, расправилась и с графом eil51, уложив в оптимум и его! Вы представляете моё состояние? Оптимальные решения находит процедура, которая ВААПЩЕ НИЧЕГО НЕ ИЩЕТ! Она просто тупо собирает пучки в единый тур. Нет, это всё более, чем великолепно, конечно, но на чём мне прикажете отлаживаться? Как известно, уже при 66 узлах компьютер величиной с Землю… а у меня самый мелкий граф с устойчивым локальным минимумом остался gr202, да и то на шаре — на плоскости и ваще lin318!

Я кое-что подрихтовал, включил сложное каскадирование по размеру мультиузлов, по глубине рекурсии и по таймеру, так что ни у одного ребра нет теперь шансов уйти в глубокую задумчивость, как бы ему этого ни хотелось. Это дало некоторое замедление на младших каскадах, зато все графы — и «матричные» (u2319 и аналогичные), и равномерно-случайного распределения (fnl4461), и с неприлично большой стартовой бетой (rl11849) и сильно кластеризованные (с11111) считаются относительно равномерно и довольно быстро. Короче говоря, я уже сейчас могу практически гарантировать весьма приличные туры для графов… ну, пока скажем из осторожности, до ста тысяч узлов. Далее там уже идут десятки миллиардов одних только рёбер, так что особых гарантий пока давать не будем.

Прогнал мелкие графы новым алгоритмом «с нуля» — у всех 100% (34 графа) найдено точное решение. Правда, далеко не для всех оно доказано — там расчёты всё-таки весьма громоздкие, так что оптимальность туров доказана пока что лишь для 17 графов, максимальный из которых eil101. Кроме того, gr202 был сброшен (в четыре «пинка») со своего тяжёлого локального минимума в оптимальный тур, у gr229 погрешность упала с 0.26% до 0.01%, у lin318 — с 0.8% до 0.13%, граница минимальной погрешности в 1% переместилась с pcb442 на rbu737 и т.д. Во время тестирования программа нашла улучшения для примерно десятка туров, с которыми не сумел справиться даже случайный поиск (pka379, rat575, u724, rbu737 и ряд других), причём очевидно, что с ростом числа узлов вероятность найти улучшения тура увеличивается.

Первоначально мы промоделировали поиск точного решения путём разбиения графа по туру на три мультиузла и подтвердили работоспособность идеи экспериментально. Попытка увеличения количества анализируемых мультиузлов до пяти (рассматривая как самостоятельные мультиузлы, соединённые исследуемым ребром текущего тура) оказалась крайне неудачной. Конечно, подобрать сразу пять рёбер-кандидатов с суммарной длиной менее пяти удаляемых рёбер тура гораздо труднее, чем группу из трёх рёбер (напомним, что погрешность в длине тура у нас на этом этапе уже весьма невелика), но такой подход, как оказалось, резко увеличивает время генерации пучков рёбер-кандидатов и, самое главное, в десятки раз увеличивает число возможных вариантов сборки получившихся вариантов снова в общий тур, то есть приводит к практически неработоспособному алгоритму. Обратная идея (уменьшение количества рассматриваемых мультиузлов до минимально возможных двух), напротив, оказалась весьма полезной: алгоритм стал проще, компактнее, надёжнее, а скорость его осталась соизмеримой с версией алгоритма на три мультиузла, который отфильтровывал больше комбинаций рёбер-кандидатов (тройки вместо пар), но тратил больше времени на генерацию пучков и комплексную проверку всех возможных вариантов перепривязки. На нём мы и остановились.

Развитие


К сожалению, количество «паразитных» проверок построения замкнутого тура (а это процедура, в общем случае, рекурсивная) при двух рёбрах-кандидатах всё же раздражающе велико. Между тем, мы уже промоделировали буквально все возможные варианты перепривязки мультиузлов… все, кроме одного: версию алгоритма с разбивкой графа на 2.5 мультиузла! Нет, мультиузлов, разумеется, тоже три, как и в первой версии алгоритма, но третий мультиузел на этот раз не является «естественным» мультиузлом графа, образованным по результатам предыдущих расчётов, а всегда состоит лишь из одного узла — того самого, куда «упирается» первое ребро-кандидат. Что это даёт? Скорость! Да больше нас уже ничего и не интересует. За счёт чего?

а) Уже не одно, а два ребра из трёх, которые наверняка не будут присутствовать в гипотетическом новом туре, удаляются сразу. Их длина, как правило, заметно меньше, чем длина ещё не исключённых из рассмотрения межгрупповых рёбер мультиузла, удаляемых в первой версии алгоритма — одно это обычно сокращает объёмы пучков рёбер-кандидатов в разы.

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

в) Исчезает крайне раздражавший, чреватый многократным пересчётом одних и тех же вариантов и даже зацикливанием, алгоритм сборки мультиузлов A и B в общий тур непосредственно через третий мультиузел путём его расщепления (идеологически задача решается как раз наоборот, слиянием мультиузлов, пока весь граф не свяжется в единый мультиузел).

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

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

Лично я свято убеждён, что в каскадированной рекурсии никакой «экспоненты» быть не может, и мне совершенно не хочется менять этот алгоритм на заведомо менее эффективный, «зато» чисто полиномиальный — я практик, и мне всегда были по барабану все эти долбаные «трансвычислительные задачи» и прочие «пределы Бремерманна». Раз уж даже даже для поганых 66 узлов «гипотетический компьютер размером с Землю за период времени, равный общему времени существования Земли» не способен решить задачу, то у нас время пока есть.

Заключение


Задача эта неисчерпаема, как и электрон, и в плане оптимизации там ещё конь не валялся. Из наиболее очевидного:

Программа написана для DOS, компилятор BC++ 3.1, так что ОЗУ здесь можно заказать где-то до полуметра, не более — это где-то в диапазоне 10-15 тысяч узлов, данные для более тяжёлых графов постоянно подкачиваются с диска, и хотя операционка, разумеется, кеширует файловые операции, для больших графов (а в 4 гига ОЗУ, которые сегодня есть на практически любом компе влезают даже стомиллионники!) порядок в производительности практически гарантирован. А то и два.

Неплохо бы вклинить алгоритм проверки принципиальной возможности перепривязки «естественных» мультиузлов — его отсутствие частенько вызывает самые неприятные рекурсивные трепыхания — на длинных рёбрах (когда два или более удалённых мультиузла лихорадочно пытаются отвязаться друг от друга путём перестроения своих внутренних туров, что есть заведомый онанизм). Здесь тоже должен лежать где-то порядок по производительности.

Ну и, конечно, использование БД вариантов, чтобы избежать повторного счёта при каскадном поиске. Желательно не «деревянной» организации БД (так работает, скажем, кэш нашего «Миража» — там невыгодно «кольцевание» дерева), а с ловлей перестановок в порядке замены рёбер (так устроен поиск в дебютном справочнике у того же «Миража»). Здесь я даже не знаю, сколько порядков по скорости лежит, но явно МНОГО!

Остальное ускорение сидит в двух сложных алгоритмах, и мне совершенно неохота этим заниматься. Как-нить в фоновом режиме или даже вообще никак: алгоритмически задача решена, программа вполне пригодна для практического использования уже сейчас, а результат этот, по большому счёту, никого не интересует — даже институт Клэя. Более того: эту задачу выгоднее иметь нерешённой — тогда можно надувать щёки и закатывать глаза: «Ах, задача тысячелетия, ах, 200 лет задаче, ах, миллион»… везде сплошные симулякры. Не говоря уже о потенциальной уязвимости всех систем шифрования с открытым ключом.

Покопался в Инете. Выяснилось, что задача коммивояжёра (точнее, проблема равенства классов P и NP) по-прежнему популярна, «доказательства» представляются десятками, причём сразу по трём направлениям: первая бригада доказывает, что эти классы равны, вторая — что не равны, а третья — что это вообще невозможно доказать. Самое смешное, что все три группы правы. Судите сами: если принять, что полный перебор экспоненциален, то задача за полином не решается — я могу указать графы, для которых переход из неоптимального состояния в оптимальное потребует одновременной замены ОЧЕНЬ большого числа рёбер — ста, тысячи, миллиона… если же полный перебор полиномиален, то и доказывать нечего: P=NP. Если дыра в постулатах, то и доказать ничего нельзя: дыра именно в постулатах. Вот там она и сидит!

В общем, есть желание у молодых здоровых программеров поковыряться в этой изрядно надоевшей мне задаче — обращайтесь. С вас «справка о состоятельности» — макет программы с диалогом, графикой и возможностью заказа ОЗУ многими метрами. Язык программирования может быть любой, при условии, что это язык C.©
Поделиться публикацией

Комментарии 158

    –8
    Прочитал все три статьи. Интересно тема описана. Не понимаю только минусующих. По делу ими написано мало, в основном всё сводится к критике стиля изложения автора. Но можно было бы просто пройти мимо, зачем рейтинг статьи-то уменьшать?
      –8
      Спасибо. Это затыкание рта неугодным. Сначала-то ветки просто ломились от комментов, и карма моя быстренько допрыгала до +13. Но это пока мне советовали «почитать Кнута», да отечески похлопывали по плечу. Ну, а когда я «учителей» поторкал носом — началось. :) Думаю, это реакция на мой «сортир» — самая первая моя заметка на Хабре и самая важная.

      Вон, и по другим веткам гадить начали: с утра в одной было -12 — стало -14, в другой долго державшийся -41 сменился на -42. И, естественно, всё молча. Быдло-с… :) Причём, как выяснилось, если карму сбросить до -31, я уже ФИЗИЧЕСКИ не смогу ничего писать — ни в Recovery Mode, ни даже в Песочницу! Инфа точная, вчера модератор подтвердил, потому-то я и обнулил карму (тоже была -42). Интересно, сутки продержусь? :)

      Пока это писал, стало уже -15, -43 и -5, и карма -4. И, разумеется, ни одного коммента. Быдло-с…
        –6
        Знаете как бывает. Есть критика, а есть критиканство. Второе я как раз увидел в прошлых комментариях от минусующих.
          –5
          Знаю. Я 27 лет в Инете. А лайк поставить уже кармы не хватает. :)
          –7
          Ха. Уже -6 и ни одного комментария
            +3
            То ли еще будет, ой-ёй-ёй… :)
          +7
          За что минусы?
          Во-первых, за манеру общения. Сообщество реагирует на манеру поведения и не принимает её.
          Во-вторых, как минимум, один из последних абзацев, где поднимается вопрос P=NP, заслуживает минуса.
            –2
            А не лучше тогда вопрос про P=NP автору задать? Тогда хоть понятна будет суть недовольства. А тупо ставить минусики за стиль изложения это по-детски как-то совсем!
              +6

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

              –5
              Я уже говорил: СТАТЬИ-ТО здесь при чём? И фрагменты из описания своего «идеального стиля общения» цитировал. У меня на Фейсбуке ВСЕ мои ветки открыты ДЛЯ ВСЕХ, в том числе и для комментариев. Но там довольно чисто. Ибо редкий камикадзе осмеливается там гадить. И у меня МНОГО друзей, причём НАСТОЯЩИХ друзей, а не просто «френдов».

              А вот насчёт «одного из последних абзацев» можно поподробнее? ЧТО ИМЕННО «заслуживает минуса» и ПОЧЕМУ?

              Я уже цитировал, но могу и повторить:
              Но вот моя точка зрения на это дело, тоже многократно высказываемая в разных местах: да, стиль своеобразный, но это рабочий стиль! Я заранее предполагаю, что оппонент адекватен, что он меня уважает, что он предполагает, что и я его уважаю, что все тезисы (мои или его) есть соответствующее IMHO, что это не нужно проговаривать на каждый чих. У меня нет ни времени, ни желания долго «обнюхиваться» при знакомстве, делать реверансы и т.п. И собеседнику моему, я полагаю, тоже время дорого. Так зачем же нам фигнёй заниматься, приплясывать друг перед другом — в тыщу раз эффективнее сразу поверить, что перед тобой нормальный, хороший человек, что с ним можно обмениваться эмоциональными, то бишь максимально информативными сообщениями. Господа, ну ведь это же так просто!
              sint.wc.lt/about.htm

              Ну вот, осталось ещё три плевка в карму, и у меня уже будет один коммент В ЧАС! Нет, не продержусь я сутки… :)
                +7
                Вы приходите в профессиональное сообщество с некоторым набором голословных утверждений, при этом часть Ваших высказываний демонстрирует, что в вопросе Вы некомпетентны (вопрос о равенстве классов P и NP тому пример).
                Если Вы предлагаете какой-то алгоритм, который действительно позволяет ускорить решение задачи коммивояжера, то
                1) Строго опишите алгоритм формально.
                2) Докажите алгоритм (или доказательство корректности — пустой звук?)
                3) Конкретно в данном случае, учитывая, что Вы используете теорию графов — строгое математическое определение всего, чем пользуетесь, теоремы и их доказательства.
                Впрочем, глупо ждать подобных вещей от тролля.
                  +7
                  Он не тролль, он «непризнанный гений», это безнадежнее, тролль хотя бы должен понимать, о чем идет речь, для данного сабжа это не обязательно.
                    –6
                    Профессиональное сообщество не гадит тайно карму и не гнобит авторов. А тут просто в статьях травля какая-то идёт. Прям аж противно!
                      –3
                      Именно травля! И это есть ИСЧЕРПЫВАЮЩАЯ характеристика «профессионального сообщества»!

                      Я вижу, уже и Вас травить начали? :)
                    +2
                    стиль своеобразный, но это рабочий стиль

                    То, что вы что-то считаете рабочим стилем, совершенно не означает, что сообщество, в которое вы пришли, с вами согласно.

                  +11
                  Прочитайте 3-4 серьезных статьи действительно по теме, 10-15 летней давности, и Вы там найдете все те подходы и идеи, которые автор выдвигает, как свои. Причем среди авторов статей, посвященных сильно структурированным графам, вы фамилии автора поста не найдете.
                  И в этих работах (действительно серьезных, с подключением математического аппарата) показан возможный выигрыш и четко указаны ограничения, налагаемые на вид исходного графа.
                  К сожалению, сильно структурированные графы составляют весьма незначительную (хотя и очень важную) часть общей задачи.
                  Вот поэтому лично мне статьи автора совершенно не представляются интересными, хотя я их и не минусую.

                  P.S. Мне трудно представить уровень профессионального невежества, необходимого для написания фразы
                  что я на чистом C повторю ЛЮБЫЕ действия, написанные на «плюсах», а вот то, что я сам напишу на чистом C, повторить на «плюсах» не сможет никто!
                  особенно ее вторая часть.
                    +1
                    Я ожидал, что в статье будут хоть какие-то ссылки по теме.
                    Автор затрагивает достаточно интересную тему «изобретения» алгоритмов, использует некие эвристики для ускорения решения, но вот с обоснованием решений как-то мутно.

                    Обычно есть какие-то вполне обоснованные особенности задачи (например какая-нибудь особенная архитектура железа, строгие требования к памяти / времени выполнения, надёжности), которые требуют доработки стандартных решений.
                    Например — в фургоне с хот-догами стоит старенький 486SX c DOS, продавец путешествует по городу и решает задачу коммивояжёра. Я утрирую, но всё-же — нужны какие-то пусть даже гипотетически условия, для которых изобретение будет оправдано. Без этого статья теряет смысл, объективность и вызывает скорее недоумение (но зачем?)
                    +4
                    Но можно было бы просто пройти мимо, зачем рейтинг статьи-то уменьшать?

                    Потому что весь смысл рейтинга статьи в том, чтобы показывать, сколько людей хочет видеть такую статью (и подобные ей), а сколько — нет. Соответственно, если людям статья не нравится (не важно, за содержимое или за форму), рейтинг будет падать.

                      –3
                      ЛЮДЕЙ?! Люди АРГУМЕНТИРУЮТ свои решения, а не гадят анонимно! Рейтинг, правда, меня вообще не интересует — он рот не затыкает. А вот карма…
                        +4
                        Люди АРГУМЕНТИРУЮТ свои решения, а не гадят анонимно!

                        Это ваше собственное мнение, с которым никто не обязан быть согласным.

                          –7
                          У нас свободная страна, конечно, можно оставаться несогласным. Но гадить считается плохим деянием в любом обществе! Да и профессионалы, которых тут неоднократно упоминали, действительно должны обосновывать своё мнение.
                            +3
                            Но гадить считается плохим деянием в любом обществе!

                            "Гадить" — это "делать плохо", поэтому это бессмысленное утверждение.


                            Да и профессионалы, которых тут неоднократно упоминали, действительно должны обосновывать своё мнение.

                            Эээ… почему должны? Кому должны?

                              –3
                              Это мы сейчас уже в область философии уйдём, поэтому предлагаю глубоко не копать. Суть моего тезиса проста. Если ты реально адекватный человек и считаешь себя профессионалом, то либо обоснуй своё мнение и выскажу отрицательную оценку, либо просто помолчи. Тайное сливание кармы мерзко. Это как тайно нагадить соседу перед входной дверью, вместо того, чтобы с ним нормально поговорить.
                              Конечно, бывают всякие ситуации, и встречаются абсолютные неадекваты. Но авто дайной статьи идёт на диалог, а ему почему-то просто затыкают рот. Мне это с самого начала не понравилось, поэтому я и написал свой первый комментарий.
                                +2
                                Если ты реально адекватный человек и считаешь себя профессионалом, то либо обоснуй своё мнение и выскажу отрицательную оценку, либо просто помолчи.

                                Это ваше собственное мнение, с которым никто не обязан быть согласным.


                                Тайное сливание кармы мерзко.

                                В таком случае просто не пользуйтесь ресурсом, где это заложено в правила. Вам здесь мерзко.


                                Но авто дайной статьи идёт на диалог, а ему почему-то просто затыкают рот.

                                Нет, не идет. Он идет на многократное громкое (и неприятное) высказывание своей позиции, которое диалогом никак не является.

                              +17
                              Статья, не художественно-повествовательного характера, которая пытается что-то преподнести в виде новинки, для нормального аргументированного обсуждения, должна обладать равноправием с обоих сторон.
                              Более того, для признания правоты авторской мысли, которую уже как 3-ю (!!! как будто первых двух было мало) он пытается донести, автору не плохо бы предоставить непротиворечивые доказательства его правоты и всячески способствовать проверке.
                              А в данном случае мы получаем вот это:
                              image
                              Более того, автор не стыдится манипулировать комментариями свою пользу, использовать полемические уловки: полный спектр апелляций (к авториету, к тошноте, порочный круг и т.п.)
                              Очевидно, при такой агрессивной политике общения, и совершенно ужасных условиях доказательства его правоты, данную статью можно рассматривать как «вброс говна на вентилятор», приправленный:
                              — непроверямыми тезисами
                              — отсутствием логической полноты (корреляция не является причинно-следственной связью, соответственно нужно более гранулярно делать определения и выводы)
                              — отсутствие обобщенного алгоритма (согласитесь, из текущей стены текста, сложно вычленить какой-либо однозначный алгоритм, что бы на его базе сделать какие либо выводы)
                              — применение «неудобных технологий» для какой либо проверки (dos есть не у каждого, да и сомневаюсь что именно эта ОС стала той самой «серебренной пулей» в реализации автора. Если решение задачи математически верно, то от среды реализации, при прочих равных, оно не зависит)
                              и в последнее:
                              — активно-агрессивный тон, с переходом на личности, при попытке аргументированно критиковать автора.

                              Лично мне кажется, при таких аспектах, установка отрицательного значения кармы/рейтинга является мерой вынужденной (ногу режут, когда лечить уже не возможно) и нужной, что-бы:
                              — не травмировать психику людей, которые внезапно могут это прочесть, являясь неподготовленными (да, о плоской земле тоже раньше шутили, а теперь во что это превратилось)
                              — не культивировать ошибочных мнений и выводов (наличие вывода без фактов и эксперимента, не делает его репрезентативным, но часто это упускают, и получается желтая пресса
                              — наглядно показать, как НЕ нужно писать статьи, которые претендуют на новшество.

                              UPD. Самое интересное и не понятное, если автор, всех тут считает дибилами (быдлом), зачем он в очередной раз пишет здесь статью?
                      +2
                      «Программа написана для DOS, компилятор BC++ 3.1»
                      Но зачем это однопоточное ретро в 2019?
                      Почему бы не рассмотреть решение на OpenCL, например.

                      Не надо отвечать как прошлый раз в стиле — я уже где-то показывал и кому-то рассказывал — сами должны были это где-то искать и найти.
                      Большинство пользователей просто прочли статью — если им стало что-то непонятно — задали конкретный вопрос. Они не изучали перечень использованной литературы, в статье его вообще нет (может всё-таки стоит его добавить), и не следят за вашим литературным творчеством.
                      Статья на Хабре — для широкой общественности, пожалуйста будьте вежливы.
                        –6
                        Уж ты! Комменты пошли! И даже кармы чуток вверх подпрыгнула! А вдруг всё-таки продержусь сутки? :)

                        mayorovp
                        Так автору уже задавали вопросы, в прошлые разы. Автор на это отреагировал так, что больше вопросов задавать не хочется.
                        Да неужели?! Я тыщу раз проговаривал открытым текстом, что могу разобрать ЛЮБОЙ вопрос с ЛЮБОЙ степенью детализации! Где «вопросы»? Огласите весь список, пжалста! ;) Вот, скажем, снова нарисовавшийся здесь GarryC — он разве вопросы задавал? Нет, он нёс голословную ахинею, что моя «воронка» является «разновидностью сортировки вставками и имеет квадратичную сложность в худшем случае». Ну и, естественно, получил по носу! Как и два «реализатора» моего алгоритма, один из которых И В САМОМ ДЕЛЕ умудрился доиграться до квадрата! И это «профессиональное сообщество»?! Ещё много лет назад я писал про таких «профессионалов»: Для «подтверждения» своих «мыслей» они тычут пальцем в мегатонные доки, которые они якобы изучили (или хотя бы читали). Например, в трёхтомник Кнута. Однако в последнее время (видимо, нарвавшись пару раз на тех, кто этого самого Кнута все-таки читал) предпочитают ссылаться на некие абстрактные «учебники» или там «документацию». Профессионал же не позволяет себе подобного НИКОГДА — он просто не умеет этого делать.

                        DocJester
                        Вы приходите в профессиональное сообщество с некоторым набором голословных утверждений, при этом часть Ваших высказываний демонстрирует, что в вопросе Вы некомпетентны (вопрос о равенстве классов P и NP тому пример).
                        А вот врать — нехорошо! Это ИМЕННО ВЫ здесь голословно утверждаете о моей некомпетентности, так и не ответив на прямой мой вопрос: «ЧТО ИМЕННО «заслуживает минуса» и ПОЧЕМУ»? Шайбу, господин «профессионал»! ;)

                        Господи, да ничего я вам не «предлагаю»! Я описал алгоритм СОРТИРОВКИ, простой и эффективный — так местные «профессионалы» ДАЖЕ В НЕГО врубиться до сих пор не могут! Куда вам до «комми» — там и в самом деле сложно! Вон какое было паломничество на мою страничку tsptest — и чего? Сказали хоть слово? Нет, ибо сказать тупо НЕЧЕГО! ;) А метать бисер перед вами я не собираюсь! У моих заметок ЕСТЬ читатели, у меня ЕСТЬ собеседники на Хабре, и оформлять свои заметки я буду так, как ИМЕННО Я считаю нужным и правильным!

                        Так как насчёт «некоторых абзацев»? Ответ будет или «как всегда»? ;)

                        GarryC
                        Он не тролль, он «непризнанный гений», это безнадежнее, тролль хотя бы должен понимать, о чем идет речь, для данного сабжа это не обязательно.
                        Что, сударь, битый нос покоя не даёт? Как там с «разновидностью сортировки вставками»? :)

                        Прочитайте 3-4 серьезных статьи действительно по теме, 10-15 летней давности, и Вы там найдете все те подходы и идеи, которые автор выдвигает, как свои.
                        Вы ещё и брехливы, к тому же. ПЕРЕЧИСЛИТЕ «все те подходы и идеи, которые автор выдвигает, как свои»! Не можете? Кто бы сомневался! И при чём тут «сильно структурированные графы»? Что это вообще такое и какое отношение это имеет к задаче коммивояжёра?

                        Вот поэтому лично мне статьи автора совершенно не представляются интересными, хотя я их и не минусую.
                        Да-да, тут уже немало отметившихся «это не я»? А КТО ЖЕ минусует? Быдло анонимное, которое даже вякнуть ничего не может? :)

                        Мне трудно представить уровень профессионального невежества, необходимого для написания фразы что я на чистом C повторю ЛЮБЫЕ действия, написанные на «плюсах», а вот то, что я сам напишу на чистом C, повторить на «плюсах» не сможет никто!
                        Да не берите в голову! Эти слова я говорил много лет назад, в сообществе вполне профессиональных программистов. Учите лучше «разновидности сортировки вставками». :)

                        GCU
                        Но зачем это однопоточное ретро в 2019?
                        А мне нравится! Старый, добротный компилятор, все его глюки давно известны… Вот сейчас в SINT загоняю свой сортир, так когда компилируется BC — всё прекрасно: читаю системный счётчик (0x46C) — всё прекрасно читается, часики тикают. Включаю WATCOM для NT — эксепшн выскакивает! Лезу в Инет — все пишут, что НЕЛЬЗЯ читать BIOS под NT! Уроды! Ну хотя бы метод дайте, чтобы счётчик тиков виден был! Или клаву нормальную, тыщу лет назад реализованную в bioskey! Все возможности спёрли — работай, программист!

                        И я вежливый — я всегда собеседника по умолчанию уважаю! Ну, а уж дальше — как получится. :)

                        Какие Вам нужны «обоснования решений»? Спрашивайте — отвечу. Я вот БЕЗ ПОНЯТИЯ, что там может быть непонятного! Особенно в «сортире».

                        Ну вот у меня прям ща на моём двухъядернике 2.8 ГГц гоняется десятимиллионник e10m0 — ПОСЛЕДНИЙ, у кого известна best-known и для которого я ещё не уложил бету в единицы процентов. Сейчас у него… вот прям в данный момент… 2622048914/2253088162*100-100=16.376% погрешности. Поди плохо? ;) А у меня на сайте пока что висит 49.8%. Раньше висело 71%. Короче, алгоритм РАБОТАЕТ! Про графы с иерархической кластеризацией я просто молчу!

                        Нет, пока я это писал, карму вернули на место. :)
                          +6
                          А КТО ЖЕ минусует?

                          Ну вот я, например.

                            +1
                            Watcom С хорошо работает с dos4/gw.
                            Почему вы сравниваете Borland C для Dos и Watcom C для NT?
                            Зачем в TSP прямая работа с клавиатурой через bioskey?
                            Что такое «сортир» и какое он имеет отношение к текущей статье?

                            В предыдущей статье вы проигнорировали мой вопрос о погрешности. Если вы используете примеры с заранее известным решением, как доказывается что это реальная погрешность в общем случае, а не подогнанная под конечное число эталонных примеров?
                              +9
                              Слава Богу, меня не окружают представители
                              сообщества вполне профессиональных программистов.
                              а вполне меняемые люди, для которых фраза
                              а вот то, что я сам напишу на чистом C, повторить на «плюсах» не сможет никто
                              является разновидностью бреда на грани мании величия.

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

                              P.S. Если у кого то сложилось превратное мнение по поводу возможности диалога с автором, то напомню, что в одном из комментариев к статье о сортировке я дал подробный разбор по поводу «сортировки слиянием», но вменяемого ответа от сабжа так и не получил.
                              +4
                              Судите сами: пока коммивояжёр не посетит все города Земли, ему незачем лететь на Марс — даже одна «лишняя» поездка туда-обратно гарантированно сожрёт любую надежду на улучшение тура на каждой из планет. Аналогично, незачем лететь на Альфу Центавра, пока не закончены все дела в Солнечной системе, незачем лететь в другое звёздное скопление, в другую галактику, т.е. сложность задачи практически линейна по числу узлов!

                              Она "практически линейна" только если вы докажете, что можно решить задачу за "практически линейное" время для варианта, где длины ребер находятся в одном порядке (например, имеют случайное распределение в диапазоне [0, 1])


                              алгоритмически задача решена, программа вполне пригодна для практического использования уже сейчас, а результат этот, по большому счёту, никого не интересует — даже институт Клэя

                              Так какой результат-то у вашей работы? Сделали NP-алгоритм, работающий быстрее существующих? Сделали и доказали P-алгоритм? Что-то еще?

                                –1
                                А чего там «доказывать»? Разве не очевидно, что рёбра от любой точки на Земле в другие звёздные системы можно просто выбросить? Или, скажем, путь из Москвы в Малаховку через Хабаровск.

                                Случайное распределение КАКОЕ? Равномерно случайные графы или, тем более, «матричные» решаются не в пример легче случайных же, но с иерархической кластеризацией. На много порядков легче!

                                Ну, всё — карма -10, разговоры заканчиваются. :)
                                  +4
                                  А чего там «доказывать»?

                                  Я, вроде, написал уже: что можно решить задачу за "практически линейное" время для варианта, где длины ребер находятся в одном порядке (например, имеют случайное распределение в диапазоне [0, 1]).


                                  Разве не очевидно, что рёбра от любой точки на Земле в другие звёздные системы можно просто выбросить?

                                  Нет, не очевидно.


                                  Случайное распределение КАКОЕ?

                                  Равномерное.


                                  Равномерно случайные графы или, тем более, «матричные» решаются не в пример легче случайных же, но с иерархической кластеризацией.

                                  Не важно, что легче. Важно, что либо решается за "практически линейное время", либо нет.

                                    –1
                                    Так, всё — читайте заметки, разговор окончен — Вы сами сказали, что Вы мне рот затыкаете, да ещё и вопросы при этом задаёте? Перехожу на режим «1 коммент в час», тем более, что мне как раз отлучиться надо на пару часиков.
                                      +8
                                      Так, всё — читайте заметки, разговор окончен

                                      Вот это, FDA847, и есть ответ на вопрос "почему минусуют, а не аргументируют" — потому что на очень простые (и вежливые) вопросы автор статьи отвечать отказывается. Какой смысл в аргументации?


                                      Вы сами сказали, что Вы мне рот затыкаете

                                      Я, заметим, сказал только про минусы к статье.

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

                                          А что неравного-то? У нас гонка "кто быстрее комментарий напишет"? Автор сам отказался мне отвечать, никакая карма его не останавливала.


                                          Прямых оскорблений тут не было

                                          "Тут" — это где? Я не побоялся и почитал комментарии автора статьи, там достаточно вещей, за которые в других сообществах просто банят. Здесь не банят, здесь минусуют. Это нормально.


                                          Людям (включая меня) неприятно видеть такое поведение, они используют тот инструмент, который им дан платформой. По-моему, все полностью предсказуемо.

                                            –4
                                            Людям (включая меня) неприятно видеть такое поведение, они используют тот инструмент, который им дан платформой. По-моему, все полностью предсказуемо.

                                            Это мне напоминает Эксперимент Милгрэма :-)
                                              +2

                                              Это вопрос ваших ассоциаций (и внимательности к деталям).

                                                +4

                                                Не вижу ничего общего.

                                              +3

                                              Нет, это не нормальный диалог. Одна из сторон попросту отказывается отвечать по делу — и эта сторона вовсе не противники автора.

                                                +6
                                                кто-то автора минусует, в результате он оказывается в неравной ситуации, не имея возможности оперативно Вам отвечать нахамить,
                                                непринуждённо выдавая это за милые особенности авторского стиля.
                                                  +5
                                                  Как автор пишет на своей страничке, в их среде это нормальный тон и у них принято обращаться к коллегам «Мишка» или «Сережка», детский сад какой то.
                                                  Он, оказывается, делает нам честь, обращаясь запанибрата с малознакомыми людьми, тем самым приобщая к священному кругу посвященных, а мы ему минусы — неблагодарные…
                                      +4

                                      Как сказал один модератор на одном форуме, "забанить нельзя глумиться".

                                        +1

                                        Великолепно, в мемориз.

                                        +9

                                        Знаете, мне сегодня исполнился 31 год. Автор статьи где-то писал о своём возрасте — то ли "шестьдесят", то ли "шестой десяток". Я с ужасом думаю о том, что, возможно, через 20-30 годиков стану таким же. Что ощущение собственной ненужности и недооценённости толкнёт меня на решательство P=NP и прочих теорем Ферма школьными методами. На последующее выкладывание этих сенсационных работ на захолустные (по меркам масштабов задачи) сайты, и на безобразные срачи с их обитателями, которые юны, глупы, не оказывают мне должного уважения и даже имеют наглость требовать уважения к себе.


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


                                        Грустно это всё.

                                          +3
                                          Поздравляю с днём рождения!
                                            +7
                                            Присоединяюсь к поздравлениям и не грустите, это не «фатальное свойство белковых тел», мне до 60 осталось чуть более 2 лет, но, надеюсь, никто меня с упомянутым сабжем не спутает.
                                              –7
                                              Да как же Вас можно «спутать с упомянутым сабжем»? Сабж с раннего детства привык пользоваться мозгами по назначению! :)

                                              Так этот конкретный человек выражает свое мнение корректно?
                                              А то как же ещё?! Вы считаете иначе? Ну, хорошо, помогите мне: я вот считаю, что Вы лжец и дурак. Как это сформулировать предельно корректно? Сообщите — я постараюсь воспользоваться именно Вашими формулировками. Ну или, в крайнем случае, сообщу, почему это невозможно.

                                              lair
                                              Человек, правящий комментарий, на который ответили, чтобы включить ответ на ответ — это что-то новое на Хабре. Для меня, по крайней мере.
                                              Для меня тоже, лапуль! Но если вы уже нагадили мне в карму до возможности «1 коммент в час» — разве у меня есть выбор? ;)

                                              я не согласен с допустимостью вашего поведения, безотносительно того, что там в правилах написано.
                                              Зашибися! Правил я не нарушаю — Вам это по барабану! Так мне НАСРАТЬ, лапуль, на Ваше восприятие! Даже если бы Вы были владельцем Хабра — потрудитесь ПРОПИСАТЬ это в правилах! ;)

                                              Ну дальше идёт просто словоблудие. Сначала хотел прокомментировать, но комментировать там тупо НЕЧЕГО.

                                              FDA847
                                              Получается, чтобы не нагадили, я также должен был плющить автора?
                                              Вы должны быть в стаде. Ничто иное не прощается. :)
                                                +1
                                                разве у меня есть выбор?

                                                Да, есть.


                                                Правил я не нарушаю — Вам это по барабану!

                                                Ну… да, а что? Правила — они для административной реакции, а я не администрация. Я имею полное право на собственное мнение и собственную реакцию.


                                                Сначала хотел прокомментировать, но комментировать там тупо НЕЧЕГО.

                                                Вот и еще один пример. Это очень удобная позпиция: просто написать "комментировать нечего" вместо того, чтобы, как любит говорить FDA847, аргументировать.

                                                +2

                                                Вы дали мне некоторое успокоение, спасибо)

                                              –4
                                              lair
                                              Да, есть.
                                              И какой же? Покорно ждать отведённого часа и разок ответить, а потом покорно молчать? Нет уж, я предпочитаю редактировать комменты, пока есть возможность! И прошу заметить, это лишь потому, что местное стадо насрало мне в карму уже выше крыши, причём НИ ОДНА СОБАКА за всё это время так и не возразила НИ ПО ОДНОМУ из тезисов, опубликованных во всех трёх заметках! Так это СООБЩЕСТВО или это БЫДЛО? ;)

                                              Я имею полное право на собственное мнение и собственную реакцию.
                                              А у Вас кто-то отнимает это право? Я как раз ПРИВЕТСТВУЮ это право, и НИКОМУ не затыкаю рот, в отличие от местного быдла! Или как там… сообщества. :)

                                              Это очень удобная позиция: просто написать «комментировать нечего» вместо того, чтобы, как любит говорить FDA847, аргументировать.
                                              А что, у Вас там разве ЕСТЬ, что комментировать? Чесслово, не заметил! Не соблаговолите ли сообщить, ЧТО ИМЕННО? Торжественно обещаю не просто прокомментировать — РАЗОБРАТЬ ПО КОСТОЧКАМ! ;)

                                              M00nL1ght
                                              Так проверили уже, но вам:
                                              Да неужели?! Я вот ТРИЖДЫ разобрал даже абсолютно мудацкий пример, который был приготовлен специально для моей «воронки»! Где «проверки»? Или Вы имеете в виду тот кретинизм, когда «реализатор» обозвал МОЕЙ воронкой СВОЁ дерьмо с квадратичной сложностью? Или ещё что-то? ;) И — да ещё раз повторю: СРАЛ Я на Ваши «перемещения и отправления»! Тем более, что даже в Вики чёрным по белому написано: «Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью.» ВРЕМЯ, БЛИН! А не все эти вонючие циферки, которые ровным счётом ни о чём не говорят!

                                              Отсюда следует, что как оценивается сложность алгоритма в «O» нотации вы не понимаете.
                                              Да ничего из этого не «следует»! Я, когда писал заметку про сортир, полагал, что ЛЮБОМУ ДЕБИЛУ должно быть очевидно, что даже по этим идиотским «сравнениям» сложность там В ХУДШЕМ случае логарифмическая, В ЛУЧШЕМ — линейная, а В СРЕДНЕМ — что-то между ними! Но когда распальцованные придурки нашли там квадрат!.. Вот именно: О ЧЁМ можно дальше разговаривать? Какие, в жопу, «формулы»? Какой, в жопу, «псведокод», если вы даже описание простейшего алгоритма НА РУССКОМ ЯЗЫКЕ проссать не в состоянии? И мне АБСОЛЮТНО насрать, верите вы или нет — это ВАШИ проблемы! Алгоритм придуман, описан, программа написана — и на всё это я потратил уже В РАЗЫ меньше времени, чем чтобы вдолбить местному стаду баранов этот алгоритм! А ЕСЛИ «мои статьи не имеют технической и какой либо другой ценности, а являются пустой тратой времени для того кто это прочитал», ТО КАКОГО ХЕРА вы здесь сидите и гадите мне в карму и статьям в комменты? Вам что, заняться больше нечем?

                                              Некоторые же пытаются вам аргументировать свои минусы и задавать вопросы, вы начинаете их всячески оскорблять.
                                              Да неужели?! Кто?! Где?! Когда?! Во всех трёх заметках про комми НИ СЛОВА не было сказано про алгоритмы именно комми! Не заметил? Ну, хорошо: хотя бы в «сортире» — ЧТО? Ну. кроме этого КЛИНИЧЕСКОГО бреда про «разновидность сортироваки вставками»? ЧЕМ Вам не угодило «содержание моих статей и комментариев»? Посмотрите хотя бы сколько там закладок и сколько комментов! Это наверняка В РАЗЫ превышает средние показатели по Хабру! Так что не надо ВРАТЬ, сударь! ;)

                                              infund
                                              Автор явно спутал хабр с солдатским нужником.
                                              А что, разве есть какие-то отличия? ХОТЬ ОДНА СОБАКА за всё это время ХОТЬ ЧТО-НИБУДЬ сказала ПО СУЩЕСТВУ моих заметок? Один поросячий визг — ТИПИЧНЫЙ нужник! ;)
                                                +3
                                                И какой же? Покорно ждать отведённого часа и разок ответить, а потом покорно молчать?

                                                Например.


                                                Нет уж, я предпочитаю редактировать комменты, пока есть возможность!

                                                Если вы предпочитаете, то у вас есть выбор.


                                                НИ ОДНА СОБАКА за всё это время так и не возразила НИ ПО ОДНОМУ из тезисов, опубликованных во всех трёх заметках
                                                ХОТЬ ОДНА СОБАКА за всё это время ХОТЬ ЧТО-НИБУДЬ сказала ПО СУЩЕСТВУ моих заметок?

                                                Собакам вообще не свойственно говорить с людьми. А вот хабраюзеров, возражающих вашим тезисам, я видел больше одного. Так что у вас очередной раз избирательное восприятие.


                                                Так это СООБЩЕСТВО или это БЫДЛО? ;)

                                                Я не знаю, какое "это" вы имеете в виду. На Хабре — сообщество. В ваших фантазиях — без понятия.


                                                А что, у Вас там разве ЕСТЬ, что комментировать? Чесслово, не заметил! Не соблаговолите ли сообщить, ЧТО ИМЕННО?

                                                https://habr.com/ru/post/451550/#comment_20189408


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

                                                  –3
                                                  Результатом я считаю РАБОТАЮЩУЮ ПРОГРАММУ. Результатом я считаю ЭТОТ ЦИКЛ СТАТЕЙ. Результатом я считаю ГЛАВУ МОЕЙ КНИГИ. Достаточно? Но это был ВОПРОС, а комментировать-то ЧТО? Ваше долбаное «случайное распределение»? Я же русским языком говорил: ГРАФЫ С ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИЕЙ!

                                                  Ну и «возражения хабраюзеров — В СТУДИЮ! В пронумерованном и прошнурованном виде. Чтобы два раза не вставать. (с) А я пока ванну приму. :)
                                                    +2
                                                    Результатом я считаю РАБОТАЮЩУЮ ПРОГРАММУ.

                                                    "Работающую программу", которая что? Умеет решать TSP? Умеет решать любую TSP? Умеет точно решать любую TSP? Умеет точно решать любую TSP за неполиномиальное время? За полиномиальное время?


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


                                                    Но это был ВОПРОС, а комментировать-то ЧТО? Ваше долбаное «случайное распределение»? Я же русским языком говорил: ГРАФЫ С ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИЕЙ!

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

                                                      +1
                                                      Ну и «возражения хабраюзеров — В СТУДИЮ!

                                                      Одно (свое) я уже привел. Вот вам второе: https://habr.com/ru/post/451550/#comment_20188866 (чтобы вы не агрились на оценочные суждения, читать надо со слов "Если Вы предлагаете какой-то алгоритм").


                                                      Ну и вот вам еще, кстати.


                                                      Определения:
                                                      Мультиузел: инкапсулированная группа узлов.
                                                      Мультиребро: инкапсулированная группа рёбер.

                                                      Что означает слово "инкапсулированная" в этих определениях? Я специально даже поискал, и эти определения нигде, кроме как в этом посте, не встречаются.

                                                        –3
                                                        Я же русским языком сказал: пронумеруйте и прошнуруйте! Я не собираюсь «читать со слов» визги какого-то придурка, называющего меня «троллем», а себя — «профессиональным сообществом». Там нет НИ ОДНОГО возражения — там есть мудацкие рекомендации, как мне надо оформлять мою статью. А с этим я уж как-нибудь САМ разберусь, без сопливых! Хоть один ТЕЗИС моих заметок — оспорен [Y/N]?

                                                        А Ваш комментарий не имеет НИ МАЛЕЙШЕГО отношения к теме статьи! Я сказал, что трудоёмкость обработки именно графов с иерархической кластеризацией, считающимися наиболее трудными для обработки, на самом деле практически линейная и проиллюстрировал это на «космическом примере». Так что Ваше «равномерное распределение» здесь просто ни к селу ни к городу!

                                                        Да, «программа, которая умеет решать TSP». Нет, не «любую», а симметричную, на плоскости (с округлением до целых или без него), в режиме так называемого CEIL-2D и на шаре в двух режимах: как для графов типа burma14 или gr666, так и для world1904711. Умеет решать точно, умеет решать приближённо, а насчёт полиномиального времени считайте сами — я целое семейство алгоритмов предложил! Кстати, это опять НЕ возражения, а ВОПРОСЫ, причём вопросы, говорящие о том, что заметки мои Вы даже не удосужились прочесть.

                                                        Инкапсулированная означает рассматриваемая как единое целое — Вам ДАЖЕ ЭТО нужно объяснять?

                                                        Я уже говорил, что в данный момент она как раз решает десятимиллионный граф e10m0. Вот последние данные. Оставлю на ночь — пусть помучает.
                                                        14181/16 N=10000000/295 L=2620759265.00 (766/8192) T=64732.5 sec

                                                        Нет, не пойдём — мне полминуты осталось на редактирование. И вообще, пошёл я спать!
                                                          +6
                                                          Я не собираюсь

                                                          Ожидаемо. Очень удобно отвечать только на то, на что хочется отвечать, а все остальное игнорировать.


                                                          Хоть один ТЕЗИС моих заметок — оспорен [Y/N]?

                                                          Да.


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

                                                          Понятно. Ну ладно, пойдем еще раз, сначала. Вы согласны, что задача обработки "графа с иерархической кластеризацией" сводима к рекурсивной задаче обработки графов без кластеризации?


                                                          Нет, не пойдём

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


                                                          Да, «программа, которая умеет решать TSP». Нет, не «любую»

                                                          А, ну ладно. Какая-то программа, которая умеет решать какой-то класс TSP за неопределенное время. А шуму-то было, Клэевский институт поминали...


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

                                                          Это и называется — какие-то классы за какое-то время. Скучно.


                                                          Инкапсулированная означает рассматриваемая как единое целое — Вам ДАЖЕ ЭТО нужно объяснять?

                                                          Конечно, нужно. Потому что это не формальное определение. Любую группу можно рассматривать как единое целое.

                                                    +8
                                                    Какой, в жопу, «псведокод», если вы даже описание простейшего алгоритма НА РУССКОМ ЯЗЫКЕ проссать не в состоянии?


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

                                                    Или Вы имеете в виду тот кретинизм, когда «реализатор» обозвал МОЕЙ воронкой СВОЁ дерьмо с квадратичной сложностью? Или ещё что-то?


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

                                                    ВРЕМЯ, БЛИН! А не все эти вонючие циферки, которые ровным счётом ни о чём не говорят!


                                                    Вы путаете теплое с мягким. Да, конечно, время является оценкой работы алгоритма, но время (физическое: в секундах, минутах и тд) это всего лишь следствие, а не причина. Потому что в общем случае операции чтения из файла или операции чтения из кэша процессора например, не учитываются при оценки скорости работы алгоритма. Потому что это константы. Быстродействие алгоритма характеризует только вычислительная сложность и ни что другое, только сложность. А вычислительная сложность — это (из вики):
                                                    понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами.
                                                    Время в данном случае условная единица и она одинакова для операции считывания с кэша процессора или если данные придут вам на почтовый ящик и считаются оттуда. На вычислительную сложность алгоритма это ни как не влияет, ни как. Ведь еще раз повторюсь время в оценке быстродействие алгоритма это абстрактность, которая не привязана к устройству.

                                                    «O» — нотация общепринятая оценка сложности алгоритма сверху.

                                                    Поэтому:

                                                    все эти вонючие циферки, которые ровным счётом ни о чём не говорят!


                                                    Говорят абсолютно обо всем! И придумано это не на хабре, это придумано учеными и исследователями которые описывают и доказывают свои алгоритмы с помощью формул и псевдокода, а не утверждений типа: «очевидно любому дебилу». И это общепринято во всем мире.
                                                    +9
                                                    «насрало мне», «абсолютно мудацкий пример», «СРАЛ Я на Ваши», «СВОЁ дерьмо с квадратичной сложностью», «вонючие циферки», «ЛЮБОМУ ДЕБИЛУ должно быть очевидно», «Какие, в жопу, «формулы»?», " НА РУССКОМ ЯЗЫКЕ проссать не в состоянии?", «И мне АБСОЛЮТНО насрать»


                                                    Автор явно спутал хабр с солдатским нужником.
                                                      +2
                                                      Кстати, говорил уже: я НЕ применяю метод ветвей и границ! Чукча не читатель? ;)

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

                                                      Из страницы о методе ветвей и границ на вики
                                                      В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти A дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева)

                                                      Также хотелось бы обратить внимание на аналог метода ветвей и границ для антагонистических игр с подозрительно знакомой терминологией — Альфа-бета-отсечение, про которое, кстати, на хабре есть отличная статья
                                                        +1
                                                        rybvv, а помимо задачи коммивояжёра, у вас есть другие идеи для других задач?
                                                          –4
                                                          Ишь ты! Сутки продержался-таки! И карма за ночь даже чуток подросла, и комменты какие-никакие продолжают появляться… Нет, карму опять тут же вернули взад. :)

                                                          FDA847
                                                          А мне кто-нибудь соизволит аргументировать минусы в карму?
                                                          Я могу. Вы имеете наглость не соглашаться с мнением стада и Вы не пахан в этом стаде. Это не прощается — стадо таких уничтожает.

                                                          lair
                                                          Ожидаемо. Очень удобно отвечать только на то, на что хочется отвечать, а все остальное игнорировать.
                                                          Повторяю для особо одарённых: там НЕ НА ЧТО отвечать! Там НЕЧЕГО комментировать! Там НЕТ возражений!

                                                          Да.
                                                          Да?! Ну, тогда перечень оспоренных тезисов и возражений по ним — В СТУДИЮ, господин лжец! ;)

                                                          Вы согласны, что задача обработки «графа с иерархической кластеризацией» сводима к рекурсивной задаче обработки графов без кластеризации?
                                                          Вы что, сдурели?! Какая ещё «рекурсия»? Графы с иерархической кластеризаций я привёл потому, что они прекрасно иллюстрируют понятие «мультиузел», но и в любых других графах техника обработки точно такая же! Что к чему Вы «сводить» собрались?

                                                          Какая-то программа, которая умеет решать какой-то класс TSP за неопределенное время. А шуму-то было, Клэевский институт поминали...
                                                          Лапуль, ЕСЛИ симметричная задача решается за полином, ТО ЛЮБАЯ TSP-задача (и вообще NP-задача) ТОЖЕ решается за полином! ;)

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

                                                          M00nL1ght
                                                          Не в состоянии конечно, ибо это глупо, вы хоть одну научную статью видели без формул и строго доказательства?
                                                          Да хоть килограмм! Я и сам писал такие статьи! Там, где никакие «формулы» нафиг не нужны! Например, в нашей с Ромкой работе «Software for solving of TSP». Ха-ха-ха! Ой, мамочки! Есть-таки там «формула»! Есть! Вот она:
                                                          It is obvious that the sum of lengths of new edges for all contours is less than the similar sum of deleted edges, i.e.
                                                          1+2+3+… +k > 1’+2’+3’+… +k’ (1)
                                                          Thus, there always exists at least one contour for which edges rightly similar inequality and at least one order of its detour when this inequality is correct on each step of detour. Differently, from any current tour it is always possible to create the best tour at keeping of benefit on each step of replacement of old edges on new ones. Therefore, the search of the best tour consists in revealing of contours and of continuously profitable order of detour of contours and also of nodes in each of them. Unlike [5] our algorithm do not stop until exact solution.

                                                          И, наконец, какое отношение имеет это усиленно гадившее мне в карму стадо по кличке «сообщество разработчиков» к научным статьям? Здесь вообще есть ХОТЬ ОДНА научная статья за всё время существования Хабра? Нет? А какого же хрена до меня докопались? Может, «дело было не в бобине»? ;)

                                                          вы играете словами в свою защиту, подменяете понятия и термины в зависимости от ситуации.
                                                          Укажите ХОТЬ ОДНО понятие, ХОТЬ ОДИН термин, который я «подменил в зависимости от ситуации», господин лжец! Это как раз присутствующий здесь GarryC подменял мою «воронку» своей поганой «разновидностью сортировки вставками»!

                                                          А с помощью формул или псевдокода можно строго определить алгоритм, без возможности трактовать его по разному.
                                                          :lol: Господи, ну какие вы, в задницу, «профессионалы»? Я лично знаком с превеликим множеством высококлассных программистов — одного из них даже как-то признали лучшим программистом мира! — и я НИ РАЗУ В ЖИЗНИ не видел, чтобы хоть один из них что-то писал на псевдокоде! Я НИ РАЗУ В ЖИЗНИ не видел, чтобы хоть один из них рисовал эти поганые «блок-схемы»! Псевдокод годится разве что для школьных занятий по информатике — да и то лишь для того, чтобы привить детям отвращение к программированию! Если Вы утверждаете, что «с помощью формул или псевдокода можно строго определить алгоритм, без возможности трактовать его по разному», то Вы НИКОГДА не программировали ничего сложнее a=b+c! У нас бывали ситуации с «Миражом», когда мы (АВТОРЫ как алгоритмов, так и кода!) смотрим на код (на код, а не на псевдокод!) как баран на новые ворота: «Это что за хрень тут написана?! Что она вообще делает»?! И только потом вспоминали: «Ах, это когда В ПРЕРЫВАНИИ случится определённая ситуация, понадобится результат работы этого куска кода»! А про программирование, управляемое данными слышали когда-нибудь? Что Вы вообще можете увидеть в этом сраном псевдокоде «без возможности трактовать его по разному»?

                                                          Поэтому, во всем мире для доказательства математических и алгоритмических утверждений используются не русский, английский или китайский язык, а формулы и математические символы.
                                                          Лапуль, мой опыт показывает, что профессионалы ВСЕГДА обсуждают алгоритмы именно «на русском, английском или китайском языках» и НИКОГДА не обсуждают «формулы и математические символы» — там тупо НЕЧЕГО обсуждать!

                                                          Это все туда же, претензия к вам, а не к тому кто попытался реализовать ваш алгоритм.
                                                          Человек попытался ОПУСТИТЬ мой алгоритм, выдавая свой полуграмотный бред за мою «воронку» и утверждая, что Квик «в 10 раз быстрее»! И лишь когда я его извозил носом по его говну, заткнулся (надеюсь). Нормальные люди сначала СПРАШИВАЮТ, а ПОТОМ УЖЕ пытаются реализовать!

                                                          написать код по тому что вы описали сложносочиненными и сложноподчиненными предложениями
                                                          … проще простого! Если, конечно, Вы программист, а не распальцованный быдлокодер.

                                                          Вы путаете теплое с мягким. Да, конечно, время является оценкой работы алгоритма, но время (физическое: в секундах, минутах и тд) это всего лишь следствие, а не причина. Потому что в общем случае операции чтения из файла или операции чтения из кэша процессора например, не учитываются при оценки скорости работы алгоритма. Потому что это константы.
                                                          Это как раз Вы «путаете тёплое с мягким»! Потому как эти «константы» как раз и отжирают львиную долю времени сортировки! И я писал, что РЕАЛЬНОЕ время работы ХУДШЕГО случая отличалось от времени работы ЛУЧШЕГО менее, чем в два раза! А это называется ЛИНЕЙНАЯ трудоёмкость — что бы там эти вонючие цифири ни показывали! Конечных пользователей интересует именно «время физическое: в секундах, минутах и тд», а не рассуждения этих долбаных «теоретиков» о своих долбаных «циферках» — они НИЧЕГО не «характеризуют»! Что я и демонстрировал в этих ветках, неоднократно отсортировав специально изготовленные для моей «воронки» (и, к тому же, совершенно идиотские) массивы строк объёмом ДО МИЛЛИАРДА элементов и более! Какие ещё нужны доказательства стаду баранов, обосравших мою «воронку» и мой «комми» своими антилайками с головы до пят? И мне глубоко насрать, что там «общепринято во всем мире», если на практике сортирует, в основном, Квик, у которого трудоёмкость худшего случая как раз квадрат. Даже если обращать внимание на эти поганые цифири.

                                                          malkovsky
                                                          Чукча не читатель?
                                                          Если Вы о себе, то похоже. Я пользуюсь альфа-бета ГРАНИЦАМИ (к тому же, ЛОКАЛЬНЫМИ границами мультиузлов, а не границами всей задачи), но я не пользуюсь МЕТОДОМ ветвей и границ! Потому как он а) экспоненциальный и б) СТРРРРРАШНО ресурсоёмкий! И никакого «дерева поиска» у меня нет — даже в случае использования БД для хранения вариантов! А свою «отличную статью на хабре про альфа-бета-отсечение» засуньте, плиз, куда подальше — я об этом писал ещё в прошлом тысячелетии (про Миража)
                                                          И теоретически ты интересен. Мы ведь до Шеннона придумали алгоритм перебора, только потом о нем прочитали. Юра еще долго смеялся, узнав, что минимакс впоследствии был заменен негомаксом. Затем мы получили теоретически предельную по альфа-бета скорость, потом и ее превзошли… И нет у тебя уже ни альфа ни бета, что противоречит всем учебникам.

                                                          Refridgerator
                                                          rybvv, а помимо задачи коммивояжёра, у вас есть другие идеи для других задач?
                                                          Да хоть килограмм! Я же алгоритмист! Но мне моего «Синдбада» по гроб жизни хватит — это не какой-то сраный Комми — это Задача! Именно для Синдбада, кстати, и был написан этот сортир.

                                                          Вы засоряете обсуждение совершенно бессмысленными однотипными комментариями.
                                                          :lol: Ну уж если кто тут и «засоряет обсуждение», то никак не он! ;) Вон, только что в соседней ветке говнюк по кличке MarazmDed развизжался про меня, любимого:
                                                          При всем общем маразме, бездоказательных голословных утверждениях и полном идиотизме автора — несет он редкостный бред — подход «модерировать тех, кого вроде бы и не за что, а надо» — глубоко ущербный. и далее про «чебурнет». Вот скажите: КАКОМУ ДЕБИЛУ непонятно, что подход этот «глубоко ущербный»? И что, это разве повод засирать мои ветки словесным поносом?

                                                          О! Срули проснулись — опять гадить в карму стали…

                                                          Refridgerator
                                                          Да я вообще ни на чём не фокусируюсь — я писал администрации ещё до обретения статуса «полноправного участника»: если пацаньё не наигралось в детстве в погремушки, пусть развлекается со своими кармами, да рейтингами — на здоровье! А вот если это используется для затыкания ртов неугодным — это уже не ресурс, это помойка!

                                                          Да, я знаю — у меня ЕСТЬ читатели, и немало людей помогают не дать стаду заткнуть мне рот окончательно. К сожалению, при таких правилах стадо всегда «передавит массой».
                                                            +2
                                                            rybvv, затыкание рта неугодным — это когда статьи принудительно отправляются в черновики (а может, и удаляются полностью — не знаю точно). Ваши статьи, как видите, всё ещё доступны для просмотра.
                                                              –7
                                                              Рот затыкается в том числе и отрицательной кармой, не надо тут юлить!
                                                                +3

                                                                Как можно видеть на примере этого поста и этой дискуссии, отрицательная карма никак не затыкает рот автора статьи.

                                                                  –2
                                                                  Здесь можно только позавидовать стойкости автора! Лучше поучитесь этому у него!
                                                                    +1

                                                                    Поучиться чему, простите? Как выползать из отрицательной кармы?

                                                                      –4
                                                                      Уметь отстаивать своё СОБСТВЕННОЕ мнение, а не прикрываться мнением «сообщества»!
                                                                        +1

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

                                                                          0
                                                                          Речь не про это была. А про отстаивание мнения автором статьи.
                                                                            +2

                                                                            Ииии? Вы предлагаете мне этому поучиться, значит, вы, видимо, предполагаете, что я этого не умею. Или нет?

                                                                              +1
                                                                              Да Вы-то тут вообще при чём? Разговор про автора. Он в трёх своих статьях отстаивал свою точку зрения, даже тогда, когда его откровенно гнобили. Не знаю, смогли бы Вы так выстоять, но он в этом плане молодец!
                                                                                +2
                                                                                Да Вы-то тут вообще при чём?

                                                                                При том, что вы буквально тремя комментариями выше пишете мне "лучше поучитесь этому у него".


                                                                                он в этом плане молодец!

                                                                                Не вижу ничего хорошего в (грубом и некорректном) отстаивании ошибочной точки зрения.

                                                                                  –2
                                                                                  Во-первых, так Ленин ещё завещал: «Учиться, учиться и ещё раз учиться!».

                                                                                  Во-вторых, автор только статью выложил, а на него уже накинулись! Никакой брани в комментариях на тот момент ещё даже не было!
                                                                                    +2
                                                                                    Во-первых, так Ленин ещё завещал: «Учиться, учиться и ещё раз учиться!».

                                                                                    Ну то есть вы все-таки считаете, что мне необходимо этому учиться?


                                                                                    Во-вторых, автор только статью выложил, а на него уже накинулись! Никакой брани в комментариях на тот момент ещё даже не было!

                                                                                    Хм. Правда?


                                                                                    Давайте посмотрим, вот первый комментарий (ваш, что характерно), он в 8:09. Вот второй, в 8:16, и он уже с бранью. Так что нет, не получается.

                                                                                      +5
                                                                                      Ну Вы знаете, если в статье есть перлы типа
                                                                                      А потому при движении по «воронке» вероятность того, что очередной элемент будет куда-нибудь пристроен без увеличения размера воронки, довольно высока
                                                                                      и на этом обоснование линейности алгоритма автором считается завершенным, то неудивительно, что на такую статью «накидываются»
                                                                                        +5
                                                                                        Ну, вообще то, Ленин завещал несколько иное
                                                                                        учиться, учиться и учиться и вырабатывать из себя сознательных социал-демократов, «рабочую интеллигенцию»
                                                                                        или Вы имели в виду
                                                                                        во-первых — учиться, во-вторых — учиться и в-третьих — учиться и затем проверять то, чтобы наука у нас не оставалась мёртвой буквой или модной фразой
                                                                                        но в любом случае это несколько не то, чему можно научится у автора обсуждаемых постов и особенно комментариев.
                                                                          +3
                                                                          Чему учиться? Унылой матерщине через слово? Несдержанности в высказываниях, выдаваемой за уникальный авторский стиль?
                                                                          P.S. Автор всё, рид онли.
                                                                            +3
                                                                            Автор всё, рид онли.

                                                                            И это, заметим, совсем не из-за минусов в карму.

                                                                              –2
                                                                              Таким образом любого можно довести до белого каления. Ничего сложного тут нет, особенно когда толпой на одного накидываются как стая голодных шакалов!
                                                                                +2

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

                                                                                  0
                                                                                  Минусов ему накидали ещё тогда, когда ни одного комментария не было!
                                                                                  Ладно, чего одно и то же обсуждать 10 раз. Предлагаю на этом закончить.
                                                                                    +1
                                                                                    Минусов ему накидали ещё тогда, когда ни одного комментария не было!

                                                                                    А на чем, собственно, основывается это утверждение?

                                                                                      +3
                                                                                      Попробую предположить, что FDA847 импонирует нонконформизм и пассионарность автора. Ход мыслей примерно таков: «Фига себе, автор в обсуждении обложил всех вокруг *уями! Вот это задор, не то, что унылое болото кругом, обсуждают чего-то...» Только эта пассионарность — на самом деле просто вульгарное хамство.
                                                                                        –2
                                                                                        Нет, я просто ненавижу ситуаций, когда все накидываются на одного! По мне это мерзость.
                                                                                          +2

                                                                                          Что значит "все накидываются на одного"? Человек опубликовал статью на сайте, где любой участник может оставить комментарий, эти самые участники начали оставлять эти самые комментарии — а как, собственно, иначе-то? Один автор, k комментаторов, это нормальная ситуация на Хабре.

                                                                                            +5
                                                                                            Да ни кто на одного не накидывается, люди пытаются узнать и разобраться в том, что написано в статье. А когда ты спрашиваешь вполне конкретный вопрос и просишь пояснить ту или иную вещь, или даже обоснованно даешь автору критику с аргументами, а в ответ прилетают лишь фразочки одна лучше другой в стиле гопника из подворотни, то о чем может быть речь? О каком конструктивном диалоге и отстаивании своего мнения?
                                                                                              +3
                                                                                              вы почитайте историю диалогов с предыдущих его публикаций, там люди вполне нормально задают интересующие их вопросы, а в ответ летит: «быдло, говно и тд».
                                                                                              У автора что синдром туретта в письменном виде?
                                                                                      +4
                                                                                      Вы спрашивали, за что вас минусуют в карму. Например, вот за это. Вы обсуждение на хабре пытаетесь переформулировать в терминах дворовой драки. Так и защиту диссертации можно приравнять к коллективному избиению. А анономное рецензирование статьи — к «тёмной».

                                                                                      В общем, нормальные аргументы у вас кончились, но вы на голых эмоциях продолжаете выгораживать автора. Если автор — ваш герой, и вы хотите, чтобы таких на хабре было больше, а не меньше, то ваше желание идёт вразрез с желанием сообщества. Вы прилепляетесь к инородному телу и отторгаетесь иммунитетом вместе с ним.
                                                                            +1
                                                                            Во всех трех статьях вы оперируете понятием «бета-граница», но даете ему хоть какое-то определение только в последней, его я и процитировал. Как, читая ваши заметки, я должен был понять, что под бета-границей подразумевались именно
                                                                            Я пользуюсь альфа-бета ГРАНИЦАМИ (к тому же, ЛОКАЛЬНЫМИ границами мультиузлов, а не границами всей задачи)

                                                                            ...?
                                                                            Я также посмотрел "вашу с Ромкой" работу, чтобы попробовать там найти определение, нашел только
                                                                            An efficiency of an inequality (1) as
                                                                            criterion of termination of depth first search directly
                                                                            depends on current tour length (beta-boundary).

                                                                            что, в общем то, не то же самое, что
                                                                            Бета-граница, напротив, ограничивает длину оптимального тура сверху — хуже уже найденного тура длина тоже быть не может

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

                                                                            Я всего лишь процитировал ваши слова из этого комментария.
                                                                              +2
                                                                              Да хоть килограмм! Я и сам писал такие статьи!

                                                                              В данном вопросе ваши статьи не котируются от слова совсем, ведь:
                                                                              Там, где никакие «формулы» нафиг не нужны!

                                                                              Здесь вообще есть ХОТЬ ОДНА научная статья за всё время существования Хабра? Нет? А какого же хрена до меня докопались?

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

                                                                              Господи, ну какие вы, в задницу, «профессионалы»? Я лично знаком с превеликим множеством высококлассных программистов — одного из них даже как-то признали лучшим программистом мира!

                                                                              Да у вас мания величия. Вам бы провериться у специалиста. Наполеоном себя не считаете?

                                                                              Я НИ РАЗУ В ЖИЗНИ не видел, чтобы хоть один из них рисовал эти поганые «блок-схемы»!


                                                                              Вы просили пример, того как вы манипулируете словами:

                                                                              Укажите ХОТЬ ОДНО понятие, ХОТЬ ОДИН термин


                                                                              Вот он! Говорив про псевдокод я не имел ввиду лишь только блок-схемы (их можно использовать тоже кстати почему нет), или вы не знаете, что такое псевдокод? Напишите код на любом удобном для вас языке и предоставьте его для обсуждения. Я хотел донести до вас мысль, что алгоритм можно представить в виде кода (псевдокода, кода на C, кода на ...). Но вы придрались к слову псевдокод и подменили понятия.

                                                                              Потому как эти «константы» как раз и отжирают львиную долю времени сортировки! И я писал, что РЕАЛЬНОЕ время работы ХУДШЕГО случая отличалось от времени работы ЛУЧШЕГО менее, чем в два раза!


                                                                              Да будет вам известно алгоритмы тестируются в равных условиях, алгоритм A и алгоритм B должны тестироваться при одинаковых константах, и в таком тесте константа будет отжирать львиную долю времени сортировки и у алгоритма А и у В. Только такой тест является достоверным для определения скорости работы алгоритма. Поэтому еще раз повторюсь: время в данном случае это условное понятие (не секунды, минуты, ...) и такие константы нужно можно сократить. Вы с физикой знакомы? Вы знаете как в физических вычислениях иногда сокращаются единицы измерения? Тут смысл тот же.

                                                                              Если же вы говорите об уменьшении времени операции чтения например, о том что бы перемещать указатели на данные, а не сами данные и тд. Так это, да будет вам известно, называется оптимизацией кода/железа/… и к вычислительной сложности алгоритма никакого отношения не имеет! Ведь алгоритм:
                                                                              конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
                                                                              Относится далеко не только к программированию в общем случае, программирование всего лишь средство реализации некоторых задач теории алгоритмов, инструмент если хотите. И алгоритмическая сложность алгоритма к программированию этого алгоритма на языке __ никакого отношения не имеет. Это надо понимать прежде чем пытаться, что то доказывать, вы этого, судя по вашим текстам, не понимаете.

                                                                              распальцованный быдлокодер, Срули проснулись, гадить в карму, стаду заткнуть мне рот, Вы не пахан в этом стаде, быдло, стадо

                                                                              У меня тут мысль закралась. Вы случайно не из мест лишения свободы пишете? Жаргон соответсвует. Как вам там интернет удалось провести? Или вы только оттуда вернулись?
                                                                                +2
                                                                                Повторяю для особо одарённых
                                                                                перечень оспоренных тезисов и возражений по ним

                                                                                Да повторяйте что угодно, ничего же не изменится от этого. Пока что вы не можете разобраться даже с одним (моим) возражением.


                                                                                Какая ещё «рекурсия»?

                                                                                Обычная такая рекурсия.


                                                                                Что к чему Вы «сводить» собрались?

                                                                                Так, кажется, нам нужна система определений для начала. Я так понял из вашей статьи, что вы утверждаете, что есть некий класс графов, который вы называете "графами с иерархической кластеризацией", для которых при числе вершин V вычислительная сложность алгоритма находится в классе O(V) ("линейная"). Или вы этого не утверждали?


                                                                                Лапуль, ЕСЛИ симметричная задача решается за полином, ТО ЛЮБАЯ TSP-задача (и вообще NP-задача) ТОЖЕ решается за полином!

                                                                                Важная часть: если (и еще несколько "если"). В вашем случае "если решается за полином" не показано, поэтому… ну да, если решается. Если.


                                                                                А я рассматриваю не просто «любую», а ту, которую мне удобно рассматривать в данный момент.

                                                                                Что означает, что определение "мультиузел"/"мультиребро" бесполезно, потому что не обладает выраженными признаками и характеристиками.


                                                                                Если Вы утверждаете, что «с помощью формул или псевдокода можно строго определить алгоритм, без возможности трактовать его по разному», то Вы НИКОГДА не программировали ничего сложнее a=b+c!

                                                                                Знаете, я вот последние несколько дней слушаю очередной курс, и в нем что ни страница, то формулы. И до этого было то же самое.


                                                                                Псевдокод годится разве что для школьных занятий по информатике

                                                                                То-то в Стенфордских курсах анализа алгоритмов он используется.


                                                                                мой опыт показывает, что профессионалы ВСЕГДА обсуждают алгоритмы именно «на русском, английском или китайском языках» и НИКОГДА не обсуждают «формулы и математические символы» — там тупо НЕЧЕГО обсуждать

                                                                                Вы просили пример подмены — вот он. Ваш оппонент говорит о доказательстве математических и алгоритмических утверждений, а вы говорите об обсуждении алгоритмов. Ну и да, "ваш опыт показывает" — ну да, у вас такой опыт. Я (да и думаю многие здесь) уже заметили, что у вас весьма… уникальный опыт. Совершенно не обязательно, что он здесь приемлем.


                                                                                И я писал, что РЕАЛЬНОЕ время работы ХУДШЕГО случая отличалось от времени работы ЛУЧШЕГО менее, чем в два раза! А это называется ЛИНЕЙНАЯ трудоёмкость

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

                                                                                +1
                                                                                rybvv, я бы вам посоветовал фокусироваться не на минусах, а на плюсах — их вам тоже ставят. Это видно, если посмотреть общее число голосов. Кроме того, на хабре есть люди, у которых доля минусов в карме значительно превышает ваше (например, Mithgol). Не нужно воспринимать минусы как что-то однозначно плохое, а плюсы — как что-то однозначно хорошее. Комментарии людей с резко отрицательной кармой бывает интереснее читать, чем с положительной — особенно, когда дело не касается чисто технических вопросов. Не переживайте так сильно, карма — это просто число, ласкающее наше ЧСВ — а человеку со стороны, читающему хабр, до неё нет никакого дела.
                                                                                  –6
                                                                                  malkovsky
                                                                                  Во всех трех статьях вы оперируете понятием «бета-граница», но даете ему хоть какое-то определение только в последней, его я и процитировал.
                                                                                  Да ничего я не «даю»! Понятию тыща лет, оно популярно и часто используется, оно понятно интуитивно, и проводить ликбез здесь я не намерен!

                                                                                  Как, читая ваши заметки, я должен был понять, что под бета-границей подразумевались именно...
                                                                                  ДА НИКАК! Терминология вполне устоявшаяся, удобная, понятная — зачем изобретать велосипед и согласовывать термины? Под альфа-бета границей у меня понимается именно то, что написано! Вы спросили — я ответил. Откуда мне знать, что Вы там поняли, а что не поняли? Это ВАШИ проблемы! У меня на сайте написано открытым текстом:
                                                                                  Ещё одно важное замечание: альфа- и бета-границы можно посчитать не только для графа в целом, но и для любого его мультиузла, причём отдельно для внутреннего тура и для мультирёбер привязки, и каждая такая граница может использоваться для отсечения бесперспективных вариантов, что также снижает общую комбинаторику в неисчислимое множество раз. Так что процедура предварительного вычисления альфа-границы по всему графу может оказаться вообще ненужной, и может быть заменена отвергнутым ранее алгоритмом: тупо считаем все отдельные узлы мультиузлами и пытаемся их перепривязать. При неудаче внешние рёбра рассматриваемого мультиузла становятся внутренними рёбрами более крупного, объединённого мультиузла и исключаются из дальнейшего рассмотрения даже при обсчёте внутреннего канала. Но у меня и так заметка растянулась на ТРИ части! Вы хотите, чтобы их было ТРИДЦАТЬ ТРИ? Так не поможет! Быдлу лишний повод нагадить в карму по каждой части. :)

                                                                                  Чем именно ваш подход отличается от метода ветвей и границ вы так и не объяснили.
                                                                                  О, Господи! Вы мне предлагаете ещё и СРАВНЕНИЕ с «ветвями» провести?! А не жирно ли будет, ребятки? Даже у меня на сайте, где Комми посвящено немало веб-страниц, написано:
                                                                                  Поскольку трудоёмкость получения решения по методу ветвей и границ имеет экспоненциальную сложность, знание принципа его работы способно скорее помешать поиску эффективного метода решения, если таковой существует. К тому же, достаточно просто прикинуть объём хотя бы одной матрицы для графа хотя бы на миллион узлов и время хотя бы на её заполнение.

                                                                                  Я всего лишь процитировал ваши слова из этого комментария.
                                                                                  И там чёрным по белому написано, что «я НЕ применяю МЕТОД ветвей и границ»! :)

                                                                                  M00nL1ght

                                                                                  В данном вопросе ваши статьи не котируются от слова совсем
                                                                                  Да мне плевать, что там у стада, нагадившего мне в карму, «котируется»! Потрудитесь ответить на вопрос: Здесь вообще есть ХОТЬ ОДНА научная статья за всё время существования Хабра? ДА или НЕТ?

                                                                                  специально для вас заменил слово псевдокод на код
                                                                                  Ну, тогда потрудитесь прочесть, что я отвечал тем, кто требовал именно код, а не псевдокод задолго до Вас. :)

                                                                                  Да у вас мания величия. Вам бы провериться у специалиста. Наполеоном себя не считаете?
                                                                                  А вот «медицинская» тема, как и ещё более тупая версия «ржача» много лет используется мною как индикатор быдла! Нет у меня никакой «мании величия». И не было. И не будет. Я просто утверждаю, что ЕСЛИ Вы не способны понять даже алгоритм, написанный на русском языке, никакой «псевдокод» Вам ТЕМ БОЛЕЕ не поможет! АДНАЗНАЧНА! ;)

                                                                                  Вы просили пример, того как вы манипулируете словами:
                                                                                  Просил. Но Вы его так и не привели! Во-первых, Вы сослались на БОЛЕЕ ПОЗДНИЙ текст, чем я просил, ибо Вы утверждали, что это было РАНЕЕ. Вы соврали? ;) Во-вторых, Вы соврали и здесь: я НЕ ПОДМЕНЯЛ псевдокод блок-схемами — я лишь сказал, что и то, и другое есть ГОВНО, и что профессионалы этим говном не пользуются ВООБЩЕ. Шли бы вы со своим долбаным «псевдокодом» куда подальше — если неспособны воспринимать даже русский язык, вам уже НИЧЕГО не поможет!

                                                                                  Да будет вам известно алгоритмы тестируются в равных условиях
                                                                                  Да будет вам известно, что здесь тестировался вообще ОДИН алгоритм, ТА ЖЕ САМАЯ программа, которой на вход подавались массивы как для ЛУЧШЕГО (заведомо линейного), так и для ХУДШЕГО (который проиграл ему лишь сраные десятки процентов). Я потому и говорил (на что стадо баранов истерически визжало и давило на карму, буквально с первого же коммента), что РЕАЛЬНОЕ ФИЗИЧЕСКОЕ время сортировки именно ЛИНЕЙНОЕ! Что бы там ни показывали эти дурацкие циферки! Я доступно излагаю?

                                                                                  У меня тут мысль закралась. Вы случайно не из мест лишения свободы пишете? Жаргон соответсвует. Как вам там интернет удалось провести? Или вы только оттуда вернулись?
                                                                                  Нет, лапуль, у меня просто ОГРОМНЫЙ опыт вытравливания головожопых, и если бы не эти дурацкие «правила», позволяющие анонимно гадящему быдлу ФИЗИЧЕСКИ затыкать рот, я бы преспокойно очистил все свои ветки от визжащего говна за пару-тройку недель, на полном автопилоте, совершенно не напрягаясь.

                                                                                  Refridgerator
                                                                                  Когда речь идёт о чисто технических или математических вещах, не может быть никакого «мнения», истинность которого зависит от суммы голосов. Факты, цифры, формулы — вот за отсутствие чего автор получил свои минусы.
                                                                                  Ха-ха-ха! Вот Вам МЕДИЦИНСКИЙ факт: я утверждаю, что полные перебор НЕ ЕСТЬ синоним дурацкого brute force! Казалось бы, достаточно просто перевод в словаре посмотреть! А теперь почитайте, ЧТО по этому поводу говорило местное стадо и СКОЛЬКО говна она мне за это отвесило в карму.
                                                                                    +2
                                                                                    полные перебор НЕ ЕСТЬ синоним дурацкого brute force!

                                                                                    Открываем вики и видим:
                                                                                    на русском:
                                                                                    Полный перебор — Метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов

                                                                                    на английском:
                                                                                    In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.


                                                                                    exhaustive = исчерпывающий
                                                                                    поиска решения исчерпыванием всевозможных вариантов = consists of systematically enumerating all possible candidates for the solution

                                                                                    Для интереса откроем на французском:

                                                                                    La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles.


                                                                                    И что мы видим? Да то же самое только на другом языке.

                                                                                    Этот термин определен и воспринимается всеми однозначно, конечно вы можете поиграться со словами, но от этого «полный перебор» на русском не перестанет переводиться как «brute force» на английском.

                                                                                    что РЕАЛЬНОЕ ФИЗИЧЕСКОЕ время сортировки именно ЛИНЕЙНОЕ!


                                                                                    Вы делаете утверждение, что время сортировки, а это функция, линейно, а линейность произвольной функции (как свойство функции) тоже надо доказать (сюрприз да?), но что бы это доказать надо сначала эту функцию определить. Вопрос раз: как вы определяете эту функцию? Вопрос два: после того как вы ее определили где доказательства, что она линейна (для доказательства можно использовать любой математический прием которые однозначно это докажет)?
                                                                                    И повторюсь еще раз: «РЕАЛЬНОЕ ФИЗИЧЕСКОЕ время» не используется для оценки вычислительной сложности алгоритма, используется условная единица времени.

                                                                                    И да можете не отвечать на те вопросы, что я задал, они риторические, ибо я заранее знаю что не получу на это ответ. Ведь у вас все это пытались узнать многие в комментариях, но ни один из них не получил внятного, грамотного ответа и по существу, без капслока и фразочек для, как вы это называете, «вытравливания головожопых».
                                                                                      +3
                                                                                      Вот Вам МЕДИЦИНСКИЙ факт: я утверждаю, что полные перебор НЕ ЕСТЬ синоним дурацкого brute force!

                                                                                      Да, факт: вы утверждаете. Однако статья Полный перебор в вики явно говорит нам: "или метод «грубой силы», англ. brute force" и в качестве английского варианта ссылается на Brute-force search.


                                                                                      Так что да, вот факт: вы утверждаете нечто, что не согласуется с общепринятым определением. Заодно это вам пример опровержения вашего тезиса.

                                                                                        +1

                                                                                        Ну так что, rybvv, раз вы снова не в read-only, соблаговолите, может быть, объяснить разницу между вашим утверждением и, гм, общепринятой терминологией?

                                                                                          +1
                                                                                          Не соблаговолит он, не царское это дело.
                                                                                            +1

                                                                                            Справедливости ради, соблаговолил, и это достаточно… забавно.


                                                                                            (ну то есть нет)

                                                                                      –2
                                                                                      Жаль, диаграмм/схем нет, темы про графы лучше воспринимаются с изображениями.
                                                                                        +1
                                                                                        Посмотрим на список рёбер с точки зрения локальных интересов каждого узла. Он, конечно, «хотел бы» обладать двумя самыми короткими рёбрами из этого списка. Если при этом не возникает конфликтов, т.е. каждый из желаемых соседей также «предпочитает» иметь своим партнёром по туру именно этот узел — задача решена, оптимальный тур найден: длина тура совпадает с альфа-границей, список интересных рёбер пуст, дальнейший перебор не имеет смысла, улучшить оценку невозможно.

                                                                                        Это не так. Вместо одного большого тура может получиться набор маленьких циклов.

                                                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                        Самое читаемое