Предыдущая
Наиболее сложными типами графов для алгоритмов группы 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.©
Комментарии (155)
GCU
23.05.2019 10:36«Программа написана для DOS, компилятор BC++ 3.1»
Но зачем это однопоточное ретро в 2019?
Почему бы не рассмотреть решение на OpenCL, например.
Не надо отвечать как прошлый раз в стиле — я уже где-то показывал и кому-то рассказывал — сами должны были это где-то искать и найти.
Большинство пользователей просто прочли статью — если им стало что-то непонятно — задали конкретный вопрос. Они не изучали перечень использованной литературы, в статье его вообще нет (может всё-таки стоит его добавить), и не следят за вашим литературным творчеством.
Статья на Хабре — для широкой общественности, пожалуйста будьте вежливы.
rybvv Автор
23.05.2019 11:12Уж ты! Комменты пошли! И даже кармы чуток вверх подпрыгнула! А вдруг всё-таки продержусь сутки? :)
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%. Короче, алгоритм РАБОТАЕТ! Про графы с иерархической кластеризацией я просто молчу!
Нет, пока я это писал, карму вернули на место. :)GCU
23.05.2019 11:53Watcom С хорошо работает с dos4/gw.
Почему вы сравниваете Borland C для Dos и Watcom C для NT?
Зачем в TSP прямая работа с клавиатурой через bioskey?
Что такое «сортир» и какое он имеет отношение к текущей статье?
В предыдущей статье вы проигнорировали мой вопрос о погрешности. Если вы используете примеры с заранее известным решением, как доказывается что это реальная погрешность в общем случае, а не подогнанная под конечное число эталонных примеров?
GarryC
23.05.2019 12:49Слава Богу, меня не окружают представители
сообщества вполне профессиональных программистов.
а вполне меняемые люди, для которых фразаа вот то, что я сам напишу на чистом C, повторить на «плюсах» не сможет никто
является разновидностью бреда на грани мании величия.
На всякий случай, подскажите, где те, кто разделяют Вашу точку зрения, водятся, чтобы случайно туда не попасть.
P.S. Если у кого то сложилось превратное мнение по поводу возможности диалога с автором, то напомню, что в одном из комментариев к статье о сортировке я дал подробный разбор по поводу «сортировки слиянием», но вменяемого ответа от сабжа так и не получил.
lair
23.05.2019 11:20Судите сами: пока коммивояжёр не посетит все города Земли, ему незачем лететь на Марс — даже одна «лишняя» поездка туда-обратно гарантированно сожрёт любую надежду на улучшение тура на каждой из планет. Аналогично, незачем лететь на Альфу Центавра, пока не закончены все дела в Солнечной системе, незачем лететь в другое звёздное скопление, в другую галактику, т.е. сложность задачи практически линейна по числу узлов!
Она "практически линейна" только если вы докажете, что можно решить задачу за "практически линейное" время для варианта, где длины ребер находятся в одном порядке (например, имеют случайное распределение в диапазоне [0, 1])
алгоритмически задача решена, программа вполне пригодна для практического использования уже сейчас, а результат этот, по большому счёту, никого не интересует — даже институт Клэя
Так какой результат-то у вашей работы? Сделали NP-алгоритм, работающий быстрее существующих? Сделали и доказали P-алгоритм? Что-то еще?
rybvv Автор
23.05.2019 11:26А чего там «доказывать»? Разве не очевидно, что рёбра от любой точки на Земле в другие звёздные системы можно просто выбросить? Или, скажем, путь из Москвы в Малаховку через Хабаровск.
Случайное распределение КАКОЕ? Равномерно случайные графы или, тем более, «матричные» решаются не в пример легче случайных же, но с иерархической кластеризацией. На много порядков легче!lair
23.05.2019 11:34+2А чего там «доказывать»?
Я, вроде, написал уже: что можно решить задачу за "практически линейное" время для варианта, где длины ребер находятся в одном порядке (например, имеют случайное распределение в диапазоне [0, 1]).
Разве не очевидно, что рёбра от любой точки на Земле в другие звёздные системы можно просто выбросить?
Нет, не очевидно.
Случайное распределение КАКОЕ?
Равномерное.
Равномерно случайные графы или, тем более, «матричные» решаются не в пример легче случайных же, но с иерархической кластеризацией.
Не важно, что легче. Важно, что либо решается за "практически линейное время", либо нет.
rybvv Автор
23.05.2019 11:37Так, всё — читайте заметки, разговор окончен — Вы сами сказали, что Вы мне рот затыкаете, да ещё и вопросы при этом задаёте? Перехожу на режим «1 коммент в час», тем более, что мне как раз отлучиться надо на пару часиков.
lair
23.05.2019 11:41+4Так, всё — читайте заметки, разговор окончен
Вот это, FDA847, и есть ответ на вопрос "почему минусуют, а не аргументируют" — потому что на очень простые (и вежливые) вопросы автор статьи отвечать отказывается. Какой смысл в аргументации?
Вы сами сказали, что Вы мне рот затыкаете
Я, заметим, сказал только про минусы к статье.
FDA847
23.05.2019 13:45+1Ну так вот это нормальный диалог, вопросов нет. Неприятно то, что кто-то автора минусует, в результате он оказывается в неравной ситуации, не имея возможности оперативно Вам отвечать. На мой взгляд это просто свинство. Прямых оскорблений тут не было, поэтому таким грязным способом затыкать автору рот просто мерзко.
lair
23.05.2019 13:51+2Неприятно то, что кто-то автора минусует, в результате он оказывается в неравной ситуации, не имея возможности оперативно Вам отвечать.
А что неравного-то? У нас гонка "кто быстрее комментарий напишет"? Автор сам отказался мне отвечать, никакая карма его не останавливала.
Прямых оскорблений тут не было
"Тут" — это где? Я не побоялся и почитал комментарии автора статьи, там достаточно вещей, за которые в других сообществах просто банят. Здесь не банят, здесь минусуют. Это нормально.
Людям (включая меня) неприятно видеть такое поведение, они используют тот инструмент, который им дан платформой. По-моему, все полностью предсказуемо.
FDA847
23.05.2019 13:57-1Людям (включая меня) неприятно видеть такое поведение, они используют тот инструмент, который им дан платформой. По-моему, все полностью предсказуемо.
Это мне напоминает Эксперимент Милгрэма :-)
mayorovp
23.05.2019 13:51+1Нет, это не нормальный диалог. Одна из сторон попросту отказывается отвечать по делу — и эта сторона вовсе не противники автора.
infund
23.05.2019 13:54+3кто-то автора минусует, в результате он оказывается в неравной ситуации, не имея возможности оперативно Вам
непринуждённо выдавая это за милые особенности авторского стиля.отвечатьнахамить,GarryC
23.05.2019 14:38Как автор пишет на своей страничке, в их среде это нормальный тон и у них принято обращаться к коллегам «Мишка» или «Сережка», детский сад какой то.
Он, оказывается, делает нам честь, обращаясь запанибрата с малознакомыми людьми, тем самым приобщая к священному кругу посвященных, а мы ему минусы — неблагодарные…
mwambanatanga
23.05.2019 13:37+1Как сказал один модератор на одном форуме, "забанить нельзя глумиться".
Sirion
23.05.2019 14:58+5Знаете, мне сегодня исполнился 31 год. Автор статьи где-то писал о своём возрасте — то ли "шестьдесят", то ли "шестой десяток". Я с ужасом думаю о том, что, возможно, через 20-30 годиков стану таким же. Что ощущение собственной ненужности и недооценённости толкнёт меня на решательство P=NP и прочих теорем Ферма школьными методами. На последующее выкладывание этих сенсационных работ на захолустные (по меркам масштабов задачи) сайты, и на безобразные срачи с их обитателями, которые юны, глупы, не оказывают мне должного уважения и даже имеют наглость требовать уважения к себе.
Я не верю, что со мной произойдёт эта трансформация. С другой стороны, ребёнком я не верил, что когда-то стану любить котлеты больше мороженого.
Грустно это всё.
GarryC
23.05.2019 18:11+3Присоединяюсь к поздравлениям и не грустите, это не «фатальное свойство белковых тел», мне до 60 осталось чуть более 2 лет, но, надеюсь, никто меня с упомянутым сабжем не спутает.
rybvv Автор
23.05.2019 18:14-5Да как же Вас можно «спутать с упомянутым сабжем»? Сабж с раннего детства привык пользоваться мозгами по назначению! :)
Так этот конкретный человек выражает свое мнение корректно?
А то как же ещё?! Вы считаете иначе? Ну, хорошо, помогите мне: я вот считаю, что Вы лжец и дурак. Как это сформулировать предельно корректно? Сообщите — я постараюсь воспользоваться именно Вашими формулировками. Ну или, в крайнем случае, сообщу, почему это невозможно.
lair
Человек, правящий комментарий, на который ответили, чтобы включить ответ на ответ — это что-то новое на Хабре. Для меня, по крайней мере.
Для меня тоже, лапуль! Но если вы уже нагадили мне в карму до возможности «1 коммент в час» — разве у меня есть выбор? ;)
я не согласен с допустимостью вашего поведения, безотносительно того, что там в правилах написано.
Зашибися! Правил я не нарушаю — Вам это по барабану! Так мне НАСРАТЬ, лапуль, на Ваше восприятие! Даже если бы Вы были владельцем Хабра — потрудитесь ПРОПИСАТЬ это в правилах! ;)
Ну дальше идёт просто словоблудие. Сначала хотел прокомментировать, но комментировать там тупо НЕЧЕГО.
FDA847
Получается, чтобы не нагадили, я также должен был плющить автора?
Вы должны быть в стаде. Ничто иное не прощается. :)lair
23.05.2019 18:59разве у меня есть выбор?
Да, есть.
Правил я не нарушаю — Вам это по барабану!
Ну… да, а что? Правила — они для административной реакции, а я не администрация. Я имею полное право на собственное мнение и собственную реакцию.
Сначала хотел прокомментировать, но комментировать там тупо НЕЧЕГО.
Вот и еще один пример. Это очень удобная позпиция: просто написать "комментировать нечего" вместо того, чтобы, как любит говорить FDA847, аргументировать.
rybvv Автор
23.05.2019 15:00-4То, что вы что-то считаете рабочим стилем, совершенно не означает, что сообщество, в которое вы пришли, с вами согласно.
Да не прячьтесь Вы трусливо за «сообщество»! ОТ СВОЕГО имени можете что-то сказать? Или Вас «сообщество» УПОЛНОМАЧИВАЛО на такие заявления? Нет? Так какого же хрена?!
Это ваше собственное мнение, с которым никто не обязан быть согласным.
Совершенно верно! Это именно МОЁ СОБСТВЕННОЕ МНЕНИЕ! Моё, Рыбинкина Владимира Владимировича! А с ЧЕМ ИМЕННО Вы не согласны? Когда трусливое «сообщество» анонимно гадит в карму, обоссавшись ХОТЬ КАК-ТО аргументировать свои действия — это правильно? Это называется «сообщество»? Это называется «профессионалы»? ВЫ, ЛИЧНО ВЫ с этим согласны? У меня же другой термин — на мой взгляд куда более точный: это БЫДЛО! ;)
Эээ: почему должны? Кому должны?
Да никому ничего не должны! Просто это ИНДИКАТОР профессионализма! Точнее, его отсутствия. ;)
Она «практически линейна» только если вы докажете, что можно решить задачу за «практически линейное» время для варианта, где длины ребер находятся в одном порядке
Вы вообще заметку читали? Там русским языком написано: ДЛЯ ГРАФОВ С ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИЕЙ! И «космический» пример — это пример ИМЕННО ТАКИХ графов! Иак какого же хрена Вы тут зудите про «равномерное.распределение»?! Или Ваша цель загадить ветку словесным поносом?
Нет, не очевидно.
Ну вот видите? Вам ДАЖЕ ЭТО не очевидно! Даже то, что это мгновенно превысит локальную альфу мультиузла! Так О ЧЁМ, простите, с Вами вообще можно «дискутировать»?
Вот это, FDA847, и есть ответ на вопрос «почему минусуют, а не аргументируют» — потому что на очень простые (и вежливые) вопросы автор статьи отвечать отказывается.
:mad: Не надо БРЕХАТЬ, лапуль! Автор русским языком сказал, что ему а) надо уйти и б) что ему УЖЕ фактически перевели карму в режим «1 коммент в час», к чему, по Вашим собственным словам, приложили руку и лично Вы! Так автор лучше потратит это время на разговоры с теми, кто НЕ гадил ему в карму! Тем более, по вопросам, доказывающим, что их автор заметку вообще не читал! Или, как минимум, «смотрел в книгу, видел фигу».
Я, заметим, сказал только про минусы к статье.
… которые НАПРЯМУЮ влияют на карму! Так, может, СНАЧАЛА следовало бы разобраться, а ПОТОМ УЖЕ гадить в карму — не находите? ;)
Автор сам отказался мне отвечать, никакая карма его не останавливала.
Не надо ПИЗДЕТЬ лапуль! Или это провокация на то, чтобы меня забанили?: Так я не боюсь — тогда я, по крайней мере, в Песочницу получу возможность писать! :)
DocJester
Почему вы сравниваете Borland C для Dos и Watcom C для NT?
Я сравниваю компиляторы ДЛЯ ЯЗЫКА СИ! Которому АБСОЛЮТНО по барабану, какая там операционка! Язык «для ОС» — это МАРАЗМ! КЛИНИЧЕСКИЙ маразм!
Зачем в TSP прямая работа с клавиатурой через bioskey?
Господи, да при чём тут TSP?! Работа с клавой, с таймером, с файлами требуется В ПОДАВЛЯЮЩЕМ БОЛЬШИНСТВЕ программ! Так какого же хрена из спи… как это в нормативной лексике… украли?! И на кой мне пользоваться этим говном без КРАЙНЕЙ необходимости?
Что такое «сортир» и какое он имеет отношение к текущей статье?
Посмотрите мои заметки — авось, найдёте. А отношение самое прямое: именно после него мне быдло закомплексованное и стало усиленно гадить в карму.
В предыдущей статье вы проигнорировали мой вопрос о погрешности.
ЧАВО?! Повторите вопрос! Я никогда ничего не «игнорирую»!
Если вы используете примеры с заранее известным решением, как доказывается что это реальная погрешность в общем случае, а не подогнанная под конечное число эталонных примеров?
ДА НИКАК! Я уже писал много раз, что решать задачу коммивояжёра фактически могу лишь я один, поскольку расстояния считаются до целых, то есть вычисляются ПРИБЛИЖЁННО! Лень смотреть, но, по-моему, это сказано в самой первой части этой заметки.
GarryC
Слава Богу, меня не окружают представители сообщества вполне профессиональных программистов. а вполне меняемые люди, для которых фраза «а вот то, что я сам напишу на чистом C, повторить на „плюсах“ не сможет никто
Лапуль, мне глубоко НАСРАТЬ, кто Вам там «окружает»: просто не надо засирать мои ветки — не трону. Даже учить «разновидности сортировки вставками» не пошлю. Заткнитесь, ПОЖАЛУЙСТА!(с)
является разновидностью бреда на грани мании величия».
На всякий случай, подскажите, где те, кто разделяют Вашу точку зрения, водятся, чтобы случайно туда не попасть.
Хабр, лапуль! Валите скорее отседова! :)
P.S. Если у кого то сложилось превратное мнение по поводу возможности диалога с автором, то напомню, что в одном из комментариев к статье о сортировке я дал подробный разбор по поводу «сортировки слиянием», но вменяемого ответа от сабжа так и не получил.
Не надо БРЕХАТЬ, лапуль! ТОЧНУЮ ссылку — В СТУДИЮ! Торжественно обещаю: СНОВА будете ходить с разбитым носом! ;)
Как автор пишет на своей страничке, в их среде это нормальный тон и у них принято обращаться к коллегам «Мишка» или «Сережка», детский сад какой то.
Лапуль, Мишка и Серёжка — это ЛЮДИ! УВАЖАЕМЫЕ люди! Вы же просто быдло, а потому с Вами исключительно на «Вы» ;) И никакого «запанибрата» с Вами И БЫТЬ НЕ МОЖЕТ! ;)
Всё, ПЦ! Карма -11, 1 коммент в час! Быдло, вонючее быдло! Причём ЗНАЮЩЕЕ, кто они! Точнее, ЧТО они. :)
SirionЯ с ужасом думаю о том, что, возможно, через 20-30 годиков стану таким же.
Не волнуйтесь, лапуль — ТАКИМ Вы не станете НИКОГДА! Если Вы УЖЕ СЕЙЧАС готовы жопу лизать титулованным гениям, которые «плюют Вам в рожу», то беспокоиться не о чем. Да, мне 60, вот-вот стукнет 61. Но у меня и Давид Бронштейн были именно моим ДРУГОМ, и Кен Томпсон мне руку пожимал. А закомплексованное быдло я не перевариваю с глубокого детства и редко молчу в их присутствии. Так что не ссыте, лапуль, НЕ ПРОИЗОЙДЁТ с Вами «эта трансформация». ;)
lair
Так уже сказал, и неоднократно.
Ну так какого же хрена прикрываетесь «сообществом»? Вы трус?
С тем, что ваше поведение здесь допустимо.
Да неужели? Увуие правила я нарушил, лапуль? ;)
Опять же, только в принятой вами системе ценностей. Но с чего вы — или кто-то — решил, что она общепринята?
Так я ж сказал: изложите СВОЮ версию! Обоссались? ;)
Да.
А какого же хрена зудите про «равномерное распределение»?
Потому что одна задача сводима к другой с определенными оговорками.
Ха-ха-ха! А ну, шайбу!
Я такого не говорил.
Не говорили. Вы это ДЕЛАЛИ! ;)
Нет, не влияют: «Карма и рейтинг это два совершенно разных показателя, которые абсолютно не связаны между собой».
Я же вижу, лапуль, как падает моя карма с каждой оценкой в мои заметки. ;)
Вам процитировать ваш же комментарий?
А как же! ;)
Дадада, FDA847, никаких «прямых оскорблений», что вы...
Да какие же это «оскорбления», лапуль? Это констатация факта. ;) И затрахался уже повторять: оскорбить невозможно ДАЖЕ ТЕОРЕТИЧЕСКИ — можно лишь оскорбитьСЯ! ;)
lair
23.05.2019 15:16+3ОТ СВОЕГО имени можете что-то сказать?
Так уже сказал, и неоднократно.
А с ЧЕМ ИМЕННО Вы не согласны?
С тем, что ваше поведение здесь допустимо. С тем, что профессионалы "обязаны аргументировать".
Просто это ИНДИКАТОР профессионализма! Точнее, его отсутствия
Опять же, только в принятой вами системе ценностей. Но с чего вы — или кто-то — решил, что она общепринята?
Вы вообще заметку читали?
Да.
И «космический» пример — это пример ИМЕННО ТАКИХ графов! Иак какого же хрена Вы тут зудите про «равномерное.распределение»?
Потому что одна задача сводима к другой с определенными оговорками. И если та задача, к которой сводимо, имеет определенную оценку производительности, у вас никак не получится сделать лучше этой оценки.
фактически перевели карму в режим «1 коммент в час», к чему, по Вашим собственным словам, приложили руку и лично Вы!
Я такого не говорил. Если вы прочитали что-то, чего я не говорил, то это уж точно не мои проблемы.
которые НАПРЯМУЮ влияют на карму!
Нет, не влияют: "Карма и рейтинг это два совершенно разных показателя, которые абсолютно не связаны между собой".
Не надо ПИЗДЕТЬ лапуль!
Вам процитировать ваш же комментарий?
Быдло, вонючее быдло!
Дадада, FDA847, никаких "прямых оскорблений", что вы...
PS.
не следует:
[...]
Оскорблять других пользователей, не следить за эмоциями
Мат, оскорбления, переходы на личности, эвфемизмы, троллинг — хорошие способы быстро и надежно сменить текущий статус аккаунта на ReadOnly.
GCU
23.05.2019 16:10+1Вам не кажется, что заявление о том, что
Я сравниваю компиляторы ДЛЯ ЯЗЫКА СИ! Которому АБСОЛЮТНО по барабану, какая там операционка! Язык «для ОС» — это МАРАЗМ! КЛИНИЧЕСКИЙ маразм!
плохо согласуется с использованием bioskey, который специфичен для DOS и не входит в стандартную библиотеку Си.
Т.е. вы написали зависимый от ОС текст программы для DOS, после чего раскритиковали компилятор Watcom для платформы NT. Это вызывает недоумение.
Раз решение приближённое, то у него должен быть расчёт точности. И опять, непонятно как её считаете. Если точность ничем не ограничена, не может быть вычислена/доказана — то почему это вообще считается решением?
«Сортир» хотя-бы можно проверить, но как проверить TSP для большого графа? — сами же, вроде, написали что никак.
P.S. Зачем так активно убивать учётную запись на ресурсе? «Быдло, тупое быдло!» — сами же призываете минусануть/опустить карму по-глубже. Это уже даже не троллинг, я даже не знаю как это назвать.
Остановитесь! Это должно было быть понятно, при сбросе кармы должно было быть предупреждение, что Вы понимаете что делаете.rybvv Автор
23.05.2019 16:51-4плохо согласуется с использованием bioskey, который специфичен для DOS и не входит в стандартную библиотеку Си.
Нет там ни чего «специфичного для DOS» — это просто НОРМАЛЬНАЯ работа с кольцевым буфером клавиатуры! У меня где-то валялись утилиты для прямой работы с буфером (и даже с «девяткой» по прерываниям), но В ДАННОМ СЛУЧАЕ (в отличие от графики, где стандартные утилиты просто ЖУТКО тормозят) общение с клавой реализовано вполне прилично! Так КАКОГО ЖЕ ХЕРА это «не входит в стандартную библиотеку»?
Т.е. вы написали зависимый от ОС текст программы для DOS, после чего раскритиковали компилятор Watcom для платформы NT. Это вызывает недоумение.
Я?! Да Вы с ума сошли! :) Цитата из моей книги:SINT появился сам собой, «непорочным зачатием», в результате тривиального желания минимизировать время на разработку (и, разумеется, сопровождение) программных модулей, используемых в прикладных задачах самого различного назначения. Уже из самой этой цели понятно, что SINT призван обеспечить максимально возможную унификацию алгоритмов и программ, независимость программного кода от используемых платформ, компиляторов, операционных систем и даже, по возможности, от разрабатываемого конечного продукта.
Раз решение приближённое, то у него должен быть расчёт точности.
А почему Вы МНЕ это говорите? Скажите ОСТАЛЬНЫМ TSP-разработчикам! Какого же хрена я чуть ли не любой их «точный» тур спокойно улучшаю, если просто повысить точность измерения расстояний? ;) Я так и писал: они минимизируют не длину тура, а ошибку округления!
«Сортир» хотя-бы можно проверить, но как проверить TSP для большого графа? — сами же, вроде, написали что никак.
Ну, проверьте хотя бы сортир! Он в миллион раз важнее какого-то сраного комми! :)
P.S. Зачем так активно убивать учётную запись на ресурсе? «Быдло, тупое быдло!» — сами же призываете минусануть/опустить карму по-глубже. Это уже даже не троллинг, я даже не знаю как это назвать.
А что, приплясывать перед этим анонимным говном? Я уже писал модератору несколько дней назад:
Меня ТОШНИТ от необходимости оправдываться, получать право голоса перед сообществом, в котором правят бал полуграмотные визжащие сопляки вроде вчерашнего: Это только вы — говнари, со своим эффектом гусёнка и нулевой обучаемостью, думают иначе. Я уже написал: И если декларируемые цели Хабра совпадают с реальными, то исправить это положение проще простого: достаточно убрать анонимность и обязать авторов «плевков в карму» (да и лайков неплохо бы) письменно обосновывать причину своих действий. А ещё проще (и лучше) вообще убрать к чертям собачьим карму и премодерацию — если есть сообщество, оно без труда САМО справится с теми, кто пытается испохабить ресурс. Но я воспользуюсь ДАЖЕ ЭТОЙ возможностью, если Вы подтверждаете, что и в самом деле я «нынешний», со статусом «полноправный участник», не имею даже тех прав, которые имеет любой только что зарегистрированный новичок. Если это так, то декларируемые цели Хабра НЕ совпадают с реальными! АДНАЗНАЧНА!
Остановитесь! Это должно было быть понятно, при сбросе кармы должно было быть предупреждение, что Вы понимаете что делаете.
Я ПОНИМАЮ, что я делаю! Я свободный человек, и пресмыкаться перед визжащим быдлом не намерен — тем более, что это всего лишь лишит меня возможности говорить на такой помойке, как Хабр. Точнее, на такой помойке, в которую её превратило это анонимно гадящее быдло — сама идея ресурса очень даже неплохая.
Больше кормить не буду.
Ваше право. Я только отвечал…
lairУдивительно, как вы не рассматриваете идею, что карма/рейтинг — это и есть то, как сообщество «само справляется».
У меня просто ОГРОМНЫЙ опыт общения в Инете! А быдло, анонимно гадящее в карму — это что угодно, только не «сообщество»! ;)GCU
23.05.2019 17:02+2Похоже это всё-таки разновидность троллинга :(.
Раз себя так любите, зачем вам Хабр…
lair
23.05.2019 17:11+3если есть сообщество, оно без труда САМО справится с теми, кто пытается испохабить ресурс
Удивительно, как вы не рассматриваете идею, что карма/рейтинг — это и есть то, как сообщество "само справляется".
FDA847
23.05.2019 17:57Вообще это не так. Даже, если человек выразил своё мнение без грубости, но оно не совпадает с мнением большинства, то он уже рискует поплатиться кармой. А в комментариях всё таки должна вестись нормальная дискуссия, а не поддакивание друг другу.
lair
23.05.2019 17:59А в комментариях всё таки должна вестись нормальная дискуссия
Вот только критерии "нормальной дискуссии", да и того, что "должно быть" в комментариях — тоже определяет сообщество.
FDA847
23.05.2019 18:02+1Оскорбления в комментариях должны пресекаться! Это не обсуждается. Но вот если человек выразил своё мнение корректно, и при этом оно не совпадает с мнением большинства, то зачем его гнобить? Ведь когда мнения разные, то и появляется нормальная дискуссия!
lair
23.05.2019 18:14Оскорбления в комментариях должны пресекаться! Это не обсуждается.
Ну вот видите, для вас это "не обсуждается", а какие-то другие люди имеют по этому поводу свое мнение (и даже есть сообщества, где это совершенно нормально).
Но вот если человек выразил своё мнение корректно
Ключевое в этой фразе "если… корректно". Ничего корректного в поведении автора статьи я не вижу.
GarryC
23.05.2019 18:16+1Так этот конкретный человек выражает свое мнение корректно?
Я думаю, ответ очевиден для всех вменяемых людей.
Тогда зачем Вы пишете фразы, которые явным образом не относятся к конкретно обсуждаемому случаю?
Разумеется, лично я за нормальную дискуссию а не за поддакивание, но в данном конкретном случае дискуссии нет, а есть поток не слишком здорового сознания.FDA847
23.05.2019 18:20+2Я писал в том числе и про себя. Здесь я вроде никого не оскорбил, старался вести нормальную дискуссию, но мне также нагадили в карму. Получается, чтобы не нагадили, я также должен был плющить автора?
Refridgerator
24.05.2019 10:06старался вести нормальную дискуссию
И в чём смысл вашей дискуссии, какую идею в рассматриваемой теме вы отстаиваете? Пока я вижу только «плохое сообщество ставит минусы хорошему автору».FDA847
24.05.2019 10:08Конкретно сейчас хочу донести простую вещь — просто так гадить в карму нельзя! Собственно мой самый первый топик этому был посвящён.
Refridgerator
24.05.2019 10:13Здесь у всех есть доля минусов в карме. Если вы хотите стать полноценным членам сообщества — нужно суметь смириться с тем, что все эти минусы заслужены.
FDA847
24.05.2019 10:15Про минусы в карму не согласен. Я никого не оскорбил, а то, что моё мнение не совпадает с мнением большинства не даёт права её уменьшать. Если есть несогласие, то его следует обсуждать в комментариях!
lair
24.05.2019 11:57то, что моё мнение не совпадает с мнением большинства не даёт права её уменьшать
Мне кажется, ваше мнение о карме не совпадает с мнением людей, которые вводили эту механику на Хабре. Право уменьшать карму есть у любого, у кого достаточная собственная карма, и, что важно, причины не важны. Процитирую правила:
По своей сути, изменение кармы это выраженное отношение одного пользователя к другому. Оно всегда субъективно (отражает чувства конкретного пользователя, а не объективную оценку), поэтому оно не может быть «правильным» или «неправильным».
lair
24.05.2019 11:53+1просто так гадить в карму нельзя!
Не "нельзя", а "вам не нравится". Но это не важно, потому что, в моем опыте, на Хабре и не принято минусовать карму просто так. Это всегда происходит как следствие поведения юзера.
Refridgerator
24.05.2019 10:03Но вот если человек выразил своё мнение корректно, и при этом оно не совпадает с мнением большинства
Когда речь идёт о чисто технических или математических вещах, не может быть никакого «мнения», истинность которого зависит от суммы голосов. Факты, цифры, формулы — вот за отсутствие чего автор получил свои минусы.FDA847
24.05.2019 10:05Серьёзно? То есть просто вот так поговорить о теореме Пифагора или происхождении числа Пи нельзя? :-)
Надо всё таки разделять научные статьи, которых на Хабре нет, и научно-популярные, которые изредка присутствуют.Refridgerator
24.05.2019 10:17Можно. Но если вы скажете, что пи=4, а потом будете всерьёз отстаивать это утверждение, несмотря на развёрнутые доказательства его ошибочности в комментариях — ваша карма тоже неуклонно поползёт вниз.
FDA847
24.05.2019 10:19Я про такое говорил? Нет! Тогда на каком основании мне в карму нагадили? Что, смелости признаться не хватает? :-)
Shkaff
24.05.2019 11:29+1Вас не минусовал, но уточню, что написано про карму в правилах хабра:
По своей сути, изменение кармы это выраженное отношение одного пользователя к другому. Оно всегда субъективно (отражает чувства конкретного пользователя, а не объективную оценку), поэтому оно не может быть «правильным» или «неправильным».
А также из кодекса автора:
Я не клянчу карму, я отношусь к изменениям рейтинга спокойно, но вместе с тем стараюсь учесть конструктивную критику и пожелания.
Скорее всего за эти страдания про карму и прилетело, тут не любят нытья по ее поводу…
lair
24.05.2019 11:58Тогда на каком основании мне в карму нагадили? Что, смелости признаться не хватает?
Второе предложение отвечает на первое. Вы косвенно обвиняете неопределенную группу людей в трусости, это неприятно.
M00nL1ght
23.05.2019 19:01+3Ну, проверьте хотя бы сортир! Он в миллион раз важнее какого-то сраного комми! :)
Так проверили уже, но вам:
Господи, ДА СРАЛ Я на Ваши «перемещения и отправления»! Меня интересует утилита сортировки, которая работает быстро и эффективно. Она у меня ЕСТЬ. А онанизмом с подсчётами чего бы то ни было занимайтесь сами — у меня других дел по горло.
— ваши же слова из предыдущей публикации.
Отсюда следует, что как оценивается сложность алгоритма в «O» нотации вы не понимаете. О чем можно дальше разговаривать? А доказательства по типу: «это же очевидно» априори не являются доказательствами. Где формулы, где псведокод для проверки алгоритма? Ведь когда люди пытаются реализовать алгоритм по вашему описанию вы говорите, что они не правильно поняли и написали не верно, так для этого существует псевдокод. Где сколь угодно объективные тесты? Или люди должны верить на словам: «я у себя запустил и оно работает быстро»? Так не работает.
Из всего этого следует, что ваши статьи не имеют технической и какой либо другой ценности, а являются пустой тратой времени для того кто это прочитал (потому что все это выглядит как очередной способ с серьезным видом изобрести «вечный двигатель»), собственно по этому вам и ставят минусы.
Некоторые же пытаются вам аргументировать свои минусы и задавать вопросы, вы начинаете их всячески оскорблять.
Вот вы и получаете, что получаете, тут даже не сколько дело в вашей манере общения (хотя и в ней тоже) сколько в содержании ваших статей и комментариев.FDA847
24.05.2019 01:29Некоторые же пытаются вам аргументировать свои минусы и задавать вопросы, вы начинаете их всячески оскорблять.
А мне кто-нибудь соизволит аргументировать минусы в карму?Refridgerator
24.05.2019 06:47Вы засоряете обсуждение совершенно бессмысленными однотипными комментариями. Минус в карму — это намёк на то, что пора остановиться.
FDA847
24.05.2019 09:08-3То есть кто-то таким образом решает, что другому пора заткнуть рот? Ну тогда я реально соглашусь с автором по поводу местного быдла!
Refridgerator
24.05.2019 09:12Он не решает, он выражает своё мнение. Решение принимает сам автор комментария — продолжать гнуть свою линию или нет.
FDA847
24.05.2019 09:15-3Ничего подобного! Минусующий видит текущую карму и намеренно её уменьшает, не давая тому отвечать! Так что не надо тут оправдываться!
lair
24.05.2019 11:59То есть кто-то таким образом решает, что другому пора заткнуть рот?
Кто-то таким образом говорит: мне неприятно ваше поведение на сайте.
M00nL1ght
24.05.2019 07:58+2Я вам минусы не ставил, поэтому аргументировать ничего не буду. Да и вообще с чего вы взяли, что люди должны это аргументировать? Вот серьезно? С чего?
Они вам это не должны и точка.
Постановка минуса это быстрый способ выразить свое мнение и отношение к материалу общепринятый на всех социальных площадках, и свое мнение и отношение не обязательно аргументировать публично. Ведь на это уже надо потратить время, а у многих нет желания его тратить. Для этого и придуманы системы быстрой оценки в виде плюсов и минусов.
И почему вы по поводу плюсов не возмущаетесь? Следуя вашей логике каждый плюс тоже должен быть аргументирован или что? Ведь минус от плюса ничем не отличается в плане цели выражения отношения. Или вы в других соц сетях тоже просите аргументировать свои плюсы или минусы? Например: поставил лайк под фото в вк — аргументируй! Вы хоть понимаете как это звучит?FDA847
24.05.2019 09:10-2При нормальной дискуссии должны. Но как правильно отметил автор статьи, быдла это не касается. Оно может только втайне гадить и больше ничего!
lair
24.05.2019 12:00Но как правильно отметил автор статьи, быдла это не касается. Оно может только втайне гадить и больше ничего!
… и вы спрашиваете, за что вас минусуют?
rybvv Автор
24.05.2019 09:11-2Ваши статьи, как видите, всё ещё доступны для просмотра.
Для ПРОСМОТРА, но не для НАПИСАНИЯ! Я и обнулил карму лишь потому, что модератор подтвердил, что с кармой менее -30 я не имею ДАЖЕ ТЕОРЕТИЧЕСКОЙ возможности написать заметку! Даже в Песочницу!
Решение принимает сам автор комментария — продолжать гнуть свою линию или нет.
Не «гнуть свою линию», а «прогибаться под быдло», засравшее ветки! А это «две большие разницы»!
M00nL1ght
Вот серьезно? С чего?
АБСОЛЮТНО серьёзно! С того, что в соцсетях антилайки НЕ используются для затыкания ртов, а здесь — ИСПОЛЬЗУЮТСЯ! А потому именно анонимные антилайки без аргументации НЕИЗБЕЖНО приведут к превращению ресурса в помойку! Что и наблюдаем.
FDA847
Да и недовольство стадное! Это как в деревне: затявкала одна шавка — и тут же остальная свора заливается лаем! Причём солидные псы как раз МОЛЧАТ!
Недовольство Вами НАВЕРНЯКА вызвано лишь тем, что Вы пытаетесь защищать меня, «изгоя» и, тем более, тем, что предлагаете трусливому анонимному стаду назваться и даже чего-то там «обосновать», что они В ПРИНЦИПЕ не способны сделать!
malkovsky
Всё, у меня опять осталось 2 минуты на редактирование этого коммента, такшта с ответом придётся подождать (тем более, что мне скоро уходить). Ибо быдло ЕЩЁ ВЧЕРА мне уронило карму до «1 коммент в час», и при этом тут высказывается мнение, что это НЕ ЕСТЬ затыкание рта! А ЧТО ЖЕ ЭТО, ГОСПОДА? ;)FDA847
24.05.2019 09:18-1Именно! Антилайк — это просто выражение недовольства, это нормально. Но некоторым этого мало, они пытаются повысить свою значимость перед «сообществом» и не ленятся залезть в карму и наладить там. Вот это и есть мерзость!
lair
23.05.2019 18:22Человек, правящий комментарий, на который ответили, чтобы включить ответ на ответ — это что-то новое на Хабре. Для меня, по крайней мере.
Ну так какого же хрена прикрываетесь «сообществом»?
А я и не прикрываюсь.
Да неужели?
Ну да. Вы же спросили, с чем я не согласен — так вот, я не согласен с допустимостью вашего поведения, безотносительно того, что там в правилах написано. Это чтобы у вас не было желания сказать "что ж вы правилами прикрываетесь".
Так я ж сказал: изложите СВОЮ версию!
Свою версию чего?
А какого же хрена зудите про «равномерное распределение»?
В следующем предложении написано.
А ну, шайбу!
Шайба. Сначала научитесь нормально задавать вопросы. И нет, "нормально" не по вашим меркам.
Вы это ДЕЛАЛИ!
Тоже нет. Вы либо (более вероятно) говорите о том, чего не знаете, либо (менее вероятно) банально врете.
Я же вижу, лапуль, как падает моя карма с каждой оценкой в мои заметки.
Это, тем не менее, не значит, что карма зависит от оценок. Просто обе этих величины зависят от третьего фактора.
А как же!
Пожалуйста: "разговор окончен".
Да какие же это «оскорбления», лапуль?
Самые обычные. Обычные бытовые оскорбления.
И затрахался уже повторять: оскорбить невозможно ДАЖЕ ТЕОРЕТИЧЕСКИ — можно лишь оскорбитьСЯ
Это ваше личное мнение, которое никто, включая администрацию, разделять не обязан.
rybvv Автор
23.05.2019 19:59-3Да, есть.
И какой же? Покорно ждать отведённого часа и разок ответить, а потом покорно молчать? Нет уж, я предпочитаю редактировать комменты, пока есть возможность! И прошу заметить, это лишь потому, что местное стадо насрало мне в карму уже выше крыши, причём НИ ОДНА СОБАКА за всё это время так и не возразила НИ ПО ОДНОМУ из тезисов, опубликованных во всех трёх заметках! Так это СООБЩЕСТВО или это БЫДЛО? ;)
Я имею полное право на собственное мнение и собственную реакцию.
А у Вас кто-то отнимает это право? Я как раз ПРИВЕТСТВУЮ это право, и НИКОМУ не затыкаю рот, в отличие от местного быдла! Или как там… сообщества. :)
Это очень удобная позиция: просто написать «комментировать нечего» вместо того, чтобы, как любит говорить FDA847, аргументировать.
А что, у Вас там разве ЕСТЬ, что комментировать? Чесслово, не заметил! Не соблаговолите ли сообщить, ЧТО ИМЕННО? Торжественно обещаю не просто прокомментировать — РАЗОБРАТЬ ПО КОСТОЧКАМ! ;)
M00nL1ght
Так проверили уже, но вам:
Да неужели?! Я вот ТРИЖДЫ разобрал даже абсолютно мудацкий пример, который был приготовлен специально для моей «воронки»! Где «проверки»? Или Вы имеете в виду тот кретинизм, когда «реализатор» обозвал МОЕЙ воронкой СВОЁ дерьмо с квадратичной сложностью? Или ещё что-то? ;) И — да ещё раз повторю: СРАЛ Я на Ваши «перемещения и отправления»! Тем более, что даже в Вики чёрным по белому написано: «Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью.» ВРЕМЯ, БЛИН! А не все эти вонючие циферки, которые ровным счётом ни о чём не говорят!
Отсюда следует, что как оценивается сложность алгоритма в «O» нотации вы не понимаете.
Да ничего из этого не «следует»! Я, когда писал заметку про сортир, полагал, что ЛЮБОМУ ДЕБИЛУ должно быть очевидно, что даже по этим идиотским «сравнениям» сложность там В ХУДШЕМ случае логарифмическая, В ЛУЧШЕМ — линейная, а В СРЕДНЕМ — что-то между ними! Но когда распальцованные придурки нашли там квадрат!.. Вот именно: О ЧЁМ можно дальше разговаривать? Какие, в жопу, «формулы»? Какой, в жопу, «псведокод», если вы даже описание простейшего алгоритма НА РУССКОМ ЯЗЫКЕ проссать не в состоянии? И мне АБСОЛЮТНО насрать, верите вы или нет — это ВАШИ проблемы! Алгоритм придуман, описан, программа написана — и на всё это я потратил уже В РАЗЫ меньше времени, чем чтобы вдолбить местному стаду баранов этот алгоритм! А ЕСЛИ «мои статьи не имеют технической и какой либо другой ценности, а являются пустой тратой времени для того кто это прочитал», ТО КАКОГО ХЕРА вы здесь сидите и гадите мне в карму и статьям в комменты? Вам что, заняться больше нечем?
Некоторые же пытаются вам аргументировать свои минусы и задавать вопросы, вы начинаете их всячески оскорблять.
Да неужели?! Кто?! Где?! Когда?! Во всех трёх заметках про комми НИ СЛОВА не было сказано про алгоритмы именно комми! Не заметил? Ну, хорошо: хотя бы в «сортире» — ЧТО? Ну. кроме этого КЛИНИЧЕСКОГО бреда про «разновидность сортироваки вставками»? ЧЕМ Вам не угодило «содержание моих статей и комментариев»? Посмотрите хотя бы сколько там закладок и сколько комментов! Это наверняка В РАЗЫ превышает средние показатели по Хабру! Так что не надо ВРАТЬ, сударь! ;)
infund
Автор явно спутал хабр с солдатским нужником.
А что, разве есть какие-то отличия? ХОТЬ ОДНА СОБАКА за всё это время ХОТЬ ЧТО-НИБУДЬ сказала ПО СУЩЕСТВУ моих заметок? Один поросячий визг — ТИПИЧНЫЙ нужник! ;)lair
23.05.2019 21:51И какой же? Покорно ждать отведённого часа и разок ответить, а потом покорно молчать?
Например.
Нет уж, я предпочитаю редактировать комменты, пока есть возможность!
Если вы предпочитаете, то у вас есть выбор.
НИ ОДНА СОБАКА за всё это время так и не возразила НИ ПО ОДНОМУ из тезисов, опубликованных во всех трёх заметках
ХОТЬ ОДНА СОБАКА за всё это время ХОТЬ ЧТО-НИБУДЬ сказала ПО СУЩЕСТВУ моих заметок?Собакам вообще не свойственно говорить с людьми. А вот хабраюзеров, возражающих вашим тезисам, я видел больше одного. Так что у вас очередной раз избирательное восприятие.
Так это СООБЩЕСТВО или это БЫДЛО? ;)
Я не знаю, какое "это" вы имеете в виду. На Хабре — сообщество. В ваших фантазиях — без понятия.
А что, у Вас там разве ЕСТЬ, что комментировать? Чесслово, не заметил! Не соблаговолите ли сообщить, ЧТО ИМЕННО?
https://habr.com/ru/post/451550/#comment_20189408
Например (но не ограничиваясь), там есть занимательный вопрос, что же конкретно вы считаете результатом вашей работы.
rybvv Автор
23.05.2019 21:56-2Результатом я считаю РАБОТАЮЩУЮ ПРОГРАММУ. Результатом я считаю ЭТОТ ЦИКЛ СТАТЕЙ. Результатом я считаю ГЛАВУ МОЕЙ КНИГИ. Достаточно? Но это был ВОПРОС, а комментировать-то ЧТО? Ваше долбаное «случайное распределение»? Я же русским языком говорил: ГРАФЫ С ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИЕЙ!
Ну и «возражения хабраюзеров — В СТУДИЮ! В пронумерованном и прошнурованном виде. Чтобы два раза не вставать. (с) А я пока ванну приму. :)lair
23.05.2019 22:01Результатом я считаю РАБОТАЮЩУЮ ПРОГРАММУ.
"Работающую программу", которая что? Умеет решать TSP? Умеет решать любую TSP? Умеет точно решать любую TSP? Умеет точно решать любую TSP за неполиномиальное время? За полиномиальное время?
А то результат "работающая программа" я произвожу каждый день по нескольку раз на дню, это настолько скучно, что не заслуживает упоминания.
Но это был ВОПРОС, а комментировать-то ЧТО? Ваше долбаное «случайное распределение»? Я же русским языком говорил: ГРАФЫ С ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИЕЙ!
Да я знаю, что вы говорили. Перечитайте мой комментарий еще раз, он относится к конкретному утверждению. Попробуйте составить на этот комментарий развернутый ответ, даже если вам кажется, что этот комментарий не имеет отношения к теме статьи.
lair
23.05.2019 22:44Ну и «возражения хабраюзеров — В СТУДИЮ!
Одно (свое) я уже привел. Вот вам второе: https://habr.com/ru/post/451550/#comment_20188866 (чтобы вы не агрились на оценочные суждения, читать надо со слов "Если Вы предлагаете какой-то алгоритм").
Ну и вот вам еще, кстати.
Определения:
Мультиузел: инкапсулированная группа узлов.
Мультиребро: инкапсулированная группа рёбер.Что означает слово "инкапсулированная" в этих определениях? Я специально даже поискал, и эти определения нигде, кроме как в этом посте, не встречаются.
rybvv Автор
23.05.2019 23:04-2Я же русским языком сказал: пронумеруйте и прошнуруйте! Я не собираюсь «читать со слов» визги какого-то придурка, называющего меня «троллем», а себя — «профессиональным сообществом». Там нет НИ ОДНОГО возражения — там есть мудацкие рекомендации, как мне надо оформлять мою статью. А с этим я уж как-нибудь САМ разберусь, без сопливых! Хоть один ТЕЗИС моих заметок — оспорен [Y/N]?
А Ваш комментарий не имеет НИ МАЛЕЙШЕГО отношения к теме статьи! Я сказал, что трудоёмкость обработки именно графов с иерархической кластеризацией, считающимися наиболее трудными для обработки, на самом деле практически линейная и проиллюстрировал это на «космическом примере». Так что Ваше «равномерное распределение» здесь просто ни к селу ни к городу!
Да, «программа, которая умеет решать TSP». Нет, не «любую», а симметричную, на плоскости (с округлением до целых или без него), в режиме так называемого CEIL-2D и на шаре в двух режимах: как для графов типа burma14 или gr666, так и для world1904711. Умеет решать точно, умеет решать приближённо, а насчёт полиномиального времени считайте сами — я целое семейство алгоритмов предложил! Кстати, это опять НЕ возражения, а ВОПРОСЫ, причём вопросы, говорящие о том, что заметки мои Вы даже не удосужились прочесть.
Инкапсулированная означает рассматриваемая как единое целое — Вам ДАЖЕ ЭТО нужно объяснять?
Я уже говорил, что в данный момент она как раз решает десятимиллионный граф e10m0. Вот последние данные. Оставлю на ночь — пусть помучает.
14181/16 N=10000000/295 L=2620759265.00 (766/8192) T=64732.5 sec
Нет, не пойдём — мне полминуты осталось на редактирование. И вообще, пошёл я спать!lair
23.05.2019 23:32+2Я не собираюсь
Ожидаемо. Очень удобно отвечать только на то, на что хочется отвечать, а все остальное игнорировать.
Хоть один ТЕЗИС моих заметок — оспорен [Y/N]?
Да.
Я сказал, что трудоёмкость обработки именно графов с иерархической кластеризацией, считающимися наиболее трудными для обработки, на самом деле практически линейная и проиллюстрировал это на «космическом примере».
Понятно. Ну ладно, пойдем еще раз, сначала. Вы согласны, что задача обработки "графа с иерархической кластеризацией" сводима к рекурсивной задаче обработки графов без кластеризации?
Нет, не пойдём
Ну раз не пойдем, значит будет еще одна демонстрация того, что вы отказываетесь обсуждать комментарии "по сути дела".
Да, «программа, которая умеет решать TSP». Нет, не «любую»
А, ну ладно. Какая-то программа, которая умеет решать какой-то класс TSP за неопределенное время. А шуму-то было, Клэевский институт поминали...
Я уже говорил, что в данный момент она как раз решает десятимиллионный граф e10m0. Вот последние данные.
Это и называется — какие-то классы за какое-то время. Скучно.
Инкапсулированная означает рассматриваемая как единое целое — Вам ДАЖЕ ЭТО нужно объяснять?
Конечно, нужно. Потому что это не формальное определение. Любую группу можно рассматривать как единое целое.
M00nL1ght
24.05.2019 00:07+4Какой, в жопу, «псведокод», если вы даже описание простейшего алгоритма НА РУССКОМ ЯЗЫКЕ проссать не в состоянии?
Не в состоянии конечно, ибо это глупо, вы хоть одну научную статью видели без формул и строго доказательства? А все потому, что все что написано на русском языке (как и на любом другом) можно трактовать по разному, собственно вы так и делаете, играете словами в свою защиту, подменяете понятия и термины в зависимости от ситуации. А с помощью формул или псевдокода можно строго определить алгоритм, без возможности трактовать его по разному. Поэтому, во всем мире для доказательства математических и алгоритмических утверждений используются не русский, английский или китайский язык, а формулы и математические символы.
Или Вы имеете в виду тот кретинизм, когда «реализатор» обозвал МОЕЙ воронкой СВОЁ дерьмо с квадратичной сложностью? Или ещё что-то?
Это все туда же, претензия к вам, а не к тому кто попытался реализовать ваш алгоритм. Человек попытался написать код по тому что вы описали сложносочиненными и сложноподчиненными предложениями, что не так уж и легко иногда сделать, учитывая вашу манеру подачи материала. Но вам не нравится. Так может дело не в нем, а в вас? Вы не можете четко донести свою точку зрения? Напишите псевдокод, что бы таких проблем не было.
ВРЕМЯ, БЛИН! А не все эти вонючие циферки, которые ровным счётом ни о чём не говорят!
Вы путаете теплое с мягким. Да, конечно, время является оценкой работы алгоритма, но время (физическое: в секундах, минутах и тд) это всего лишь следствие, а не причина. Потому что в общем случае операции чтения из файла или операции чтения из кэша процессора например, не учитываются при оценки скорости работы алгоритма. Потому что это константы. Быстродействие алгоритма характеризует только вычислительная сложность и ни что другое, только сложность. А вычислительная сложность — это (из вики):понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами.
Время в данном случае условная единица и она одинакова для операции считывания с кэша процессора или если данные придут вам на почтовый ящик и считаются оттуда. На вычислительную сложность алгоритма это ни как не влияет, ни как. Ведь еще раз повторюсь время в оценке быстродействие алгоритма это абстрактность, которая не привязана к устройству.
«O» — нотация общепринятая оценка сложности алгоритма сверху.
Поэтому:
все эти вонючие циферки, которые ровным счётом ни о чём не говорят!
Говорят абсолютно обо всем! И придумано это не на хабре, это придумано учеными и исследователями которые описывают и доказывают свои алгоритмы с помощью формул и псевдокода, а не утверждений типа: «очевидно любому дебилу». И это общепринято во всем мире.
infund
23.05.2019 20:14+6«насрало мне», «абсолютно мудацкий пример», «СРАЛ Я на Ваши», «СВОЁ дерьмо с квадратичной сложностью», «вонючие циферки», «ЛЮБОМУ ДЕБИЛУ должно быть очевидно», «Какие, в жопу, «формулы»?», " НА РУССКОМ ЯЗЫКЕ проссать не в состоянии?", «И мне АБСОЛЮТНО насрать»
Автор явно спутал хабр с солдатским нужником.
malkovsky
24.05.2019 01:14+1Кстати, говорил уже: я НЕ применяю метод ветвей и границ! Чукча не читатель? ;)
Под альфа-границей понимается такая длина тура, для которой оказано, что ниже этой величины даже оптимальный тур быть не может. Бета-граница, напротив, ограничивает длину оптимального тура сверху — хуже уже найденного тура длина тоже быть не может.
Из страницы о методе ветвей и границ на вики
В основе метода ветвей и границ лежит следующая идея: если нижняя граница значений функции на подобласти A дерева поиска больше, чем верхняя граница на какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева)
Также хотелось бы обратить внимание на аналог метода ветвей и границ для антагонистических игр с подозрительно знакомой терминологией — Альфа-бета-отсечение, про которое, кстати, на хабре есть отличная статья
Refridgerator
24.05.2019 06:50rybvv, а помимо задачи коммивояжёра, у вас есть другие идеи для других задач?
rybvv Автор
24.05.2019 08:09Ишь ты! Сутки продержался-таки! И карма за ночь даже чуток подросла, и комменты какие-никакие продолжают появляться… Нет, карму опять тут же вернули взад. :)
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
Да я вообще ни на чём не фокусируюсь — я писал администрации ещё до обретения статуса «полноправного участника»: если пацаньё не наигралось в детстве в погремушки, пусть развлекается со своими кармами, да рейтингами — на здоровье! А вот если это используется для затыкания ртов неугодным — это уже не ресурс, это помойка!
Да, я знаю — у меня ЕСТЬ читатели, и немало людей помогают не дать стаду заткнуть мне рот окончательно. К сожалению, при таких правилах стадо всегда «передавит массой».Refridgerator
24.05.2019 08:52rybvv, затыкание рта неугодным — это когда статьи принудительно отправляются в черновики (а может, и удаляются полностью — не знаю точно). Ваши статьи, как видите, всё ещё доступны для просмотра.
FDA847
24.05.2019 09:12-1Рот затыкается в том числе и отрицательной кармой, не надо тут юлить!
lair
24.05.2019 12:04Как можно видеть на примере этого поста и этой дискуссии, отрицательная карма никак не затыкает рот автора статьи.
FDA847
24.05.2019 12:12Здесь можно только позавидовать стойкости автора! Лучше поучитесь этому у него!
lair
24.05.2019 12:19Поучиться чему, простите? Как выползать из отрицательной кармы?
FDA847
24.05.2019 12:21-3Уметь отстаивать своё СОБСТВЕННОЕ мнение, а не прикрываться мнением «сообщества»!
lair
24.05.2019 13:04Это было бы даже смешно (в конце концов, мало кто заморачивается посмотреть на историю чужих комментариев), но даже в этой дискуссии, обосновывая свои действия, я опираюсь на свое мнение.
FDA847
24.05.2019 13:06Речь не про это была. А про отстаивание мнения автором статьи.
lair
24.05.2019 13:06Ииии? Вы предлагаете мне этому поучиться, значит, вы, видимо, предполагаете, что я этого не умею. Или нет?
FDA847
24.05.2019 13:08+1Да Вы-то тут вообще при чём? Разговор про автора. Он в трёх своих статьях отстаивал свою точку зрения, даже тогда, когда его откровенно гнобили. Не знаю, смогли бы Вы так выстоять, но он в этом плане молодец!
lair
24.05.2019 13:10Да Вы-то тут вообще при чём?
При том, что вы буквально тремя комментариями выше пишете мне "лучше поучитесь этому у него".
он в этом плане молодец!
Не вижу ничего хорошего в (грубом и некорректном) отстаивании ошибочной точки зрения.
FDA847
24.05.2019 13:13Во-первых, так Ленин ещё завещал: «Учиться, учиться и ещё раз учиться!».
Во-вторых, автор только статью выложил, а на него уже накинулись! Никакой брани в комментариях на тот момент ещё даже не было!lair
24.05.2019 13:18Во-первых, так Ленин ещё завещал: «Учиться, учиться и ещё раз учиться!».
Ну то есть вы все-таки считаете, что мне необходимо этому учиться?
Во-вторых, автор только статью выложил, а на него уже накинулись! Никакой брани в комментариях на тот момент ещё даже не было!
Хм. Правда?
Давайте посмотрим, вот первый комментарий (ваш, что характерно), он в 8:09. Вот второй, в 8:16, и он уже с бранью. Так что нет, не получается.
GarryC
24.05.2019 13:21+2Ну Вы знаете, если в статье есть перлы типа
А потому при движении по «воронке» вероятность того, что очередной элемент будет куда-нибудь пристроен без увеличения размера воронки, довольно высока
и на этом обоснование линейности алгоритма автором считается завершенным, то неудивительно, что на такую статью «накидываются»
GarryC
24.05.2019 13:52+1Ну, вообще то, Ленин завещал несколько иное
учиться, учиться и учиться и вырабатывать из себя сознательных социал-демократов, «рабочую интеллигенцию»
или Вы имели в видуво-первых — учиться, во-вторых — учиться и в-третьих — учиться и затем проверять то, чтобы наука у нас не оставалась мёртвой буквой или модной фразой
но в любом случае это несколько не то, чему можно научится у автора обсуждаемых постов и особенно комментариев.
infund
24.05.2019 12:29Чему учиться? Унылой матерщине через слово? Несдержанности в высказываниях, выдаваемой за уникальный авторский стиль?
P.S. Автор всё, рид онли.FDA847
24.05.2019 13:09Таким образом любого можно довести до белого каления. Ничего сложного тут нет, особенно когда толпой на одного накидываются как стая голодных шакалов!
lair
24.05.2019 13:13Вообще-то, автор утверждал, что это его нормальный стиль. У него даже манифест на эту тему есть, основная мысль которого передается следующей фразой: "я считал и считаю, что стиль у меня практически идеальный".
FDA847
24.05.2019 13:14Минусов ему накидали ещё тогда, когда ни одного комментария не было!
Ладно, чего одно и то же обсуждать 10 раз. Предлагаю на этом закончить.lair
24.05.2019 13:15Минусов ему накидали ещё тогда, когда ни одного комментария не было!
А на чем, собственно, основывается это утверждение?
infund
24.05.2019 13:25+1Попробую предположить, что FDA847 импонирует нонконформизм и пассионарность автора. Ход мыслей примерно таков: «Фига себе, автор в обсуждении обложил всех вокруг *уями! Вот это задор, не то, что унылое болото кругом, обсуждают чего-то...» Только эта пассионарность — на самом деле просто вульгарное хамство.
FDA847
24.05.2019 13:28Нет, я просто ненавижу ситуаций, когда все накидываются на одного! По мне это мерзость.
lair
24.05.2019 13:36Что значит "все накидываются на одного"? Человек опубликовал статью на сайте, где любой участник может оставить комментарий, эти самые участники начали оставлять эти самые комментарии — а как, собственно, иначе-то? Один автор, k комментаторов, это нормальная ситуация на Хабре.
M00nL1ght
24.05.2019 13:37Да ни кто на одного не накидывается, люди пытаются узнать и разобраться в том, что написано в статье. А когда ты спрашиваешь вполне конкретный вопрос и просишь пояснить ту или иную вещь, или даже обоснованно даешь автору критику с аргументами, а в ответ прилетают лишь фразочки одна лучше другой в стиле гопника из подворотни, то о чем может быть речь? О каком конструктивном диалоге и отстаивании своего мнения?
M00nL1ght
24.05.2019 13:39вы почитайте историю диалогов с предыдущих его публикаций, там люди вполне нормально задают интересующие их вопросы, а в ответ летит: «быдло, говно и тд».
У автора что синдром туретта в письменном виде?
Sirion
25.05.2019 00:13+2Вы спрашивали, за что вас минусуют в карму. Например, вот за это. Вы обсуждение на хабре пытаетесь переформулировать в терминах дворовой драки. Так и защиту диссертации можно приравнять к коллективному избиению. А анономное рецензирование статьи — к «тёмной».
В общем, нормальные аргументы у вас кончились, но вы на голых эмоциях продолжаете выгораживать автора. Если автор — ваш герой, и вы хотите, чтобы таких на хабре было больше, а не меньше, то ваше желание идёт вразрез с желанием сообщества. Вы прилепляетесь к инородному телу и отторгаетесь иммунитетом вместе с ним.
malkovsky
24.05.2019 09:35Во всех трех статьях вы оперируете понятием «бета-граница», но даете ему хоть какое-то определение только в последней, его я и процитировал. Как, читая ваши заметки, я должен был понять, что под бета-границей подразумевались именно
Я пользуюсь альфа-бета ГРАНИЦАМИ (к тому же, ЛОКАЛЬНЫМИ границами мультиузлов, а не границами всей задачи)
...?
Я также посмотрел "вашу с Ромкой" работу, чтобы попробовать там найти определение, нашел только
An efficiency of an inequality (1) as
criterion of termination of depth first search directly
depends on current tour length (beta-boundary).
что, в общем то, не то же самое, что
Бета-граница, напротив, ограничивает длину оптимального тура сверху — хуже уже найденного тура длина тоже быть не может
Чем именно ваш подход отличается от метода ветвей и границ вы так и не объяснили, а только объявили, что не используете его. Я могу предположить, что вы используете не только этот метод, но это не значит, что вы его не используете.
Если Вы о себе, то похоже.
Я всего лишь процитировал ваши слова из этого комментария.
M00nL1ght
24.05.2019 09:54+1Да хоть килограмм! Я и сам писал такие статьи!
В данном вопросе ваши статьи не котируются от слова совсем, ведь:
Там, где никакие «формулы» нафиг не нужны!
Здесь вообще есть ХОТЬ ОДНА научная статья за всё время существования Хабра? Нет? А какого же хрена до меня докопались?
Вы пишете публикацию в которой вы описываете некий алгоритм и утверждаете, что он является лучшим в своем роде. Такое сильное заявление принято доказывать и не словами «очевидно, дебилы, стадо» и тд., а кодом (специально для вас заменил слово псевдокод на код) и/или формулами и в какой то степени его можно считать как научный труд. Поэтому к вам и докопались, люди хотят доказательство на деле, а не на ваших словах. В ином случае вашу статью можно считать псевдонаучной или вообще развлекательной, чем она и является по моему мнению.
Господи, ну какие вы, в задницу, «профессионалы»? Я лично знаком с превеликим множеством высококлассных программистов — одного из них даже как-то признали лучшим программистом мира!
Да у вас мания величия. Вам бы провериться у специалиста. Наполеоном себя не считаете?
Я НИ РАЗУ В ЖИЗНИ не видел, чтобы хоть один из них рисовал эти поганые «блок-схемы»!
Вы просили пример, того как вы манипулируете словами:
Укажите ХОТЬ ОДНО понятие, ХОТЬ ОДИН термин
Вот он! Говорив про псевдокод я не имел ввиду лишь только блок-схемы (их можно использовать тоже кстати почему нет), или вы не знаете, что такое псевдокод? Напишите код на любом удобном для вас языке и предоставьте его для обсуждения. Я хотел донести до вас мысль, что алгоритм можно представить в виде кода (псевдокода, кода на C, кода на ...). Но вы придрались к слову псевдокод и подменили понятия.
Потому как эти «константы» как раз и отжирают львиную долю времени сортировки! И я писал, что РЕАЛЬНОЕ время работы ХУДШЕГО случая отличалось от времени работы ЛУЧШЕГО менее, чем в два раза!
Да будет вам известно алгоритмы тестируются в равных условиях, алгоритм A и алгоритм B должны тестироваться при одинаковых константах, и в таком тесте константа будет отжирать львиную долю времени сортировки и у алгоритма А и у В. Только такой тест является достоверным для определения скорости работы алгоритма. Поэтому еще раз повторюсь: время в данном случае это условное понятие (не секунды, минуты, ...) и такие константынужноможно сократить. Вы с физикой знакомы? Вы знаете как в физических вычислениях иногда сокращаются единицы измерения? Тут смысл тот же.
Если же вы говорите об уменьшении времени операции чтения например, о том что бы перемещать указатели на данные, а не сами данные и тд. Так это, да будет вам известно, называется оптимизацией кода/железа/… и к вычислительной сложности алгоритма никакого отношения не имеет! Ведь алгоритм:конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
Относится далеко не только к программированию в общем случае, программирование всего лишь средство реализации некоторых задач теории алгоритмов, инструмент если хотите. И алгоритмическая сложность алгоритма к программированию этого алгоритма на языке __ никакого отношения не имеет. Это надо понимать прежде чем пытаться, что то доказывать, вы этого, судя по вашим текстам, не понимаете.
распальцованный быдлокодер, Срули проснулись, гадить в карму, стаду заткнуть мне рот, Вы не пахан в этом стаде, быдло, стадо
У меня тут мысль закралась. Вы случайно не из мест лишения свободы пишете? Жаргон соответсвует. Как вам там интернет удалось провести? Или вы только оттуда вернулись?
lair
24.05.2019 13:03+1Повторяю для особо одарённых
перечень оспоренных тезисов и возражений по нимДа повторяйте что угодно, ничего же не изменится от этого. Пока что вы не можете разобраться даже с одним (моим) возражением.
Какая ещё «рекурсия»?
Обычная такая рекурсия.
Что к чему Вы «сводить» собрались?
Так, кажется, нам нужна система определений для начала. Я так понял из вашей статьи, что вы утверждаете, что есть некий класс графов, который вы называете "графами с иерархической кластеризацией", для которых при числе вершин
Vвычислительная сложность алгоритма находится в классеO(V)("линейная"). Или вы этого не утверждали?
Лапуль, ЕСЛИ симметричная задача решается за полином, ТО ЛЮБАЯ TSP-задача (и вообще NP-задача) ТОЖЕ решается за полином!
Важная часть: если (и еще несколько "если"). В вашем случае "если решается за полином" не показано, поэтому… ну да, если решается. Если.
А я рассматриваю не просто «любую», а ту, которую мне удобно рассматривать в данный момент.
Что означает, что определение "мультиузел"/"мультиребро" бесполезно, потому что не обладает выраженными признаками и характеристиками.
Если Вы утверждаете, что «с помощью формул или псевдокода можно строго определить алгоритм, без возможности трактовать его по разному», то Вы НИКОГДА не программировали ничего сложнее
a=b+c!Знаете, я вот последние несколько дней слушаю очередной курс, и в нем что ни страница, то формулы. И до этого было то же самое.
Псевдокод годится разве что для школьных занятий по информатике
То-то в Стенфордских курсах анализа алгоритмов он используется.
мой опыт показывает, что профессионалы ВСЕГДА обсуждают алгоритмы именно «на русском, английском или китайском языках» и НИКОГДА не обсуждают «формулы и математические символы» — там тупо НЕЧЕГО обсуждать
Вы просили пример подмены — вот он. Ваш оппонент говорит о доказательстве математических и алгоритмических утверждений, а вы говорите об обсуждении алгоритмов. Ну и да, "ваш опыт показывает" — ну да, у вас такой опыт. Я (да и думаю многие здесь) уже заметили, что у вас весьма… уникальный опыт. Совершенно не обязательно, что он здесь приемлем.
И я писал, что РЕАЛЬНОЕ время работы ХУДШЕГО случая отличалось от времени работы ЛУЧШЕГО менее, чем в два раза! А это называется ЛИНЕЙНАЯ трудоёмкость
Нет, не называется. Разница времени работы худшего и лучшего случаев вообще мало что говорит об вычислительной сложности — та вычисляется как функция от входного набора данных.
Refridgerator
24.05.2019 08:31rybvv, я бы вам посоветовал фокусироваться не на минусах, а на плюсах — их вам тоже ставят. Это видно, если посмотреть общее число голосов. Кроме того, на хабре есть люди, у которых доля минусов в карме значительно превышает ваше (например, Mithgol). Не нужно воспринимать минусы как что-то однозначно плохое, а плюсы — как что-то однозначно хорошее. Комментарии людей с резко отрицательной кармой бывает интереснее читать, чем с положительной — особенно, когда дело не касается чисто технических вопросов. Не переживайте так сильно, карма — это просто число, ласкающее наше ЧСВ — а человеку со стороны, читающему хабр, до неё нет никакого дела.
rybvv Автор
24.05.2019 10:58-3Во всех трех статьях вы оперируете понятием «бета-граница», но даете ему хоть какое-то определение только в последней, его я и процитировал.
Да ничего я не «даю»! Понятию тыща лет, оно популярно и часто используется, оно понятно интуитивно, и проводить ликбез здесь я не намерен!
Как, читая ваши заметки, я должен был понять, что под бета-границей подразумевались именно...
ДА НИКАК! Терминология вполне устоявшаяся, удобная, понятная — зачем изобретать велосипед и согласовывать термины? Под альфа-бета границей у меня понимается именно то, что написано! Вы спросили — я ответил. Откуда мне знать, что Вы там поняли, а что не поняли? Это ВАШИ проблемы! У меня на сайте написано открытым текстом:
Ещё одно важное замечание: альфа- и бета-границы можно посчитать не только для графа в целом, но и для любого его мультиузла, причём отдельно для внутреннего тура и для мультирёбер привязки, и каждая такая граница может использоваться для отсечения бесперспективных вариантов, что также снижает общую комбинаторику в неисчислимое множество раз. Так что процедура предварительного вычисления альфа-границы по всему графу может оказаться вообще ненужной, и может быть заменена отвергнутым ранее алгоритмом: тупо считаем все отдельные узлы мультиузлами и пытаемся их перепривязать. При неудаче внешние рёбра рассматриваемого мультиузла становятся внутренними рёбрами более крупного, объединённого мультиузла и исключаются из дальнейшего рассмотрения даже при обсчёте внутреннего канала. Но у меня и так заметка растянулась на ТРИ части! Вы хотите, чтобы их было ТРИДЦАТЬ ТРИ? Так не поможет! Быдлу лишний повод нагадить в карму по каждой части. :)
Чем именно ваш подход отличается от метода ветвей и границ вы так и не объяснили.
О, Господи! Вы мне предлагаете ещё и СРАВНЕНИЕ с «ветвями» провести?! А не жирно ли будет, ребятки? Даже у меня на сайте, где Комми посвящено немало веб-страниц, написано:
Поскольку трудоёмкость получения решения по методу ветвей и границ имеет экспоненциальную сложность, знание принципа его работы способно скорее помешать поиску эффективного метода решения, если таковой существует. К тому же, достаточно просто прикинуть объём хотя бы одной матрицы для графа хотя бы на миллион узлов и время хотя бы на её заполнение.
Я всего лишь процитировал ваши слова из этого комментария.
И там чёрным по белому написано, что «я НЕ применяю МЕТОД ветвей и границ»! :)
M00nL1ght
В данном вопросе ваши статьи не котируются от слова совсем
Да мне плевать, что там у стада, нагадившего мне в карму, «котируется»! Потрудитесь ответить на вопрос: Здесь вообще есть ХОТЬ ОДНА научная статья за всё время существования Хабра? ДА или НЕТ?
специально для вас заменил слово псевдокод на код
Ну, тогда потрудитесь прочесть, что я отвечал тем, кто требовал именно код, а не псевдокод задолго до Вас. :)
Да у вас мания величия. Вам бы провериться у специалиста. Наполеоном себя не считаете?
А вот «медицинская» тема, как и ещё более тупая версия «ржача» много лет используется мною как индикатор быдла! Нет у меня никакой «мании величия». И не было. И не будет. Я просто утверждаю, что ЕСЛИ Вы не способны понять даже алгоритм, написанный на русском языке, никакой «псевдокод» Вам ТЕМ БОЛЕЕ не поможет! АДНАЗНАЧНА! ;)
Вы просили пример, того как вы манипулируете словами:
Просил. Но Вы его так и не привели! Во-первых, Вы сослались на БОЛЕЕ ПОЗДНИЙ текст, чем я просил, ибо Вы утверждали, что это было РАНЕЕ. Вы соврали? ;) Во-вторых, Вы соврали и здесь: я НЕ ПОДМЕНЯЛ псевдокод блок-схемами — я лишь сказал, что и то, и другое есть ГОВНО, и что профессионалы этим говном не пользуются ВООБЩЕ. Шли бы вы со своим долбаным «псевдокодом» куда подальше — если неспособны воспринимать даже русский язык, вам уже НИЧЕГО не поможет!
Да будет вам известно алгоритмы тестируются в равных условиях
Да будет вам известно, что здесь тестировался вообще ОДИН алгоритм, ТА ЖЕ САМАЯ программа, которой на вход подавались массивы как для ЛУЧШЕГО (заведомо линейного), так и для ХУДШЕГО (который проиграл ему лишь сраные десятки процентов). Я потому и говорил (на что стадо баранов истерически визжало и давило на карму, буквально с первого же коммента), что РЕАЛЬНОЕ ФИЗИЧЕСКОЕ время сортировки именно ЛИНЕЙНОЕ! Что бы там ни показывали эти дурацкие циферки! Я доступно излагаю?
У меня тут мысль закралась. Вы случайно не из мест лишения свободы пишете? Жаргон соответсвует. Как вам там интернет удалось провести? Или вы только оттуда вернулись?
Нет, лапуль, у меня просто ОГРОМНЫЙ опыт вытравливания головожопых, и если бы не эти дурацкие «правила», позволяющие анонимно гадящему быдлу ФИЗИЧЕСКИ затыкать рот, я бы преспокойно очистил все свои ветки от визжащего говна за пару-тройку недель, на полном автопилоте, совершенно не напрягаясь.
Refridgerator
Когда речь идёт о чисто технических или математических вещах, не может быть никакого «мнения», истинность которого зависит от суммы голосов. Факты, цифры, формулы — вот за отсутствие чего автор получил свои минусы.
Ха-ха-ха! Вот Вам МЕДИЦИНСКИЙ факт: я утверждаю, что полные перебор НЕ ЕСТЬ синоним дурацкого brute force! Казалось бы, достаточно просто перевод в словаре посмотреть! А теперь почитайте, ЧТО по этому поводу говорило местное стадо и СКОЛЬКО говна она мне за это отвесило в карму.M00nL1ght
24.05.2019 11:40полные перебор НЕ ЕСТЬ синоним дурацкого 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 methode algorithmique qui consiste principalement a essayer toutes les solutions possibles.
И что мы видим? Да то же самое только на другом языке.
Этот термин определен и воспринимается всеми однозначно, конечно вы можете поиграться со словами, но от этого «полный перебор» на русском не перестанет переводиться как «brute force» на английском.
что РЕАЛЬНОЕ ФИЗИЧЕСКОЕ время сортировки именно ЛИНЕЙНОЕ!
Вы делаете утверждение, что время сортировки, а это функция, линейно, а линейность произвольной функции (как свойство функции) тоже надо доказать (сюрприз да?), но что бы это доказать надо сначала эту функцию определить. Вопрос раз: как вы определяете эту функцию? Вопрос два: после того как вы ее определили где доказательства, что она линейна (для доказательства можно использовать любой математический прием которые однозначно это докажет)?
И повторюсь еще раз: «РЕАЛЬНОЕ ФИЗИЧЕСКОЕ время» не используется для оценки вычислительной сложности алгоритма, используется условная единица времени.
И да можете не отвечать на те вопросы, что я задал, они риторические, ибо я заранее знаю что не получу на это ответ. Ведь у вас все это пытались узнать многие в комментариях, но ни один из них не получил внятного, грамотного ответа и по существу, без капслока и фразочек для, как вы это называете, «вытравливания головожопых».
lair
24.05.2019 12:13+1Вот Вам МЕДИЦИНСКИЙ факт: я утверждаю, что полные перебор НЕ ЕСТЬ синоним дурацкого brute force!
Да, факт: вы утверждаете. Однако статья Полный перебор в вики явно говорит нам: "или метод «грубой силы», англ. brute force" и в качестве английского варианта ссылается на Brute-force search.
Так что да, вот факт: вы утверждаете нечто, что не согласуется с общепринятым определением. Заодно это вам пример опровержения вашего тезиса.
valemak
26.05.2019 00:59Жаль, диаграмм/схем нет, темы про графы лучше воспринимаются с изображениями.
FDA847
Прочитал все три статьи. Интересно тема описана. Не понимаю только минусующих. По делу ими написано мало, в основном всё сводится к критике стиля изложения автора. Но можно было бы просто пройти мимо, зачем рейтинг статьи-то уменьшать?
rybvv Автор
Спасибо. Это затыкание рта неугодным. Сначала-то ветки просто ломились от комментов, и карма моя быстренько допрыгала до +13. Но это пока мне советовали «почитать Кнута», да отечески похлопывали по плечу. Ну, а когда я «учителей» поторкал носом — началось. :) Думаю, это реакция на мой «сортир» — самая первая моя заметка на Хабре и самая важная.
FDA847
Знаете как бывает. Есть критика, а есть критиканство. Второе я как раз увидел в прошлых комментариях от минусующих.
rybvv Автор
Знаю. Я 27 лет в Инете. А лайк поставить уже кармы не хватает. :)
FDA847
Ха. Уже -6 и ни одного комментария
rybvv Автор
То ли еще будет, ой-ёй-ёй… :)
DocJester
За что минусы?
Во-первых, за манеру общения. Сообщество реагирует на манеру поведения и не принимает её.
Во-вторых, как минимум, один из последних абзацев, где поднимается вопрос P=NP, заслуживает минуса.
FDA847
А не лучше тогда вопрос про P=NP автору задать? Тогда хоть понятна будет суть недовольства. А тупо ставить минусики за стиль изложения это по-детски как-то совсем!
mayorovp
Так автору уже задавали вопросы, в прошлые разы. Автор на это отреагировал так, что больше вопросов задавать не хочется.
rybvv Автор
Я уже говорил: СТАТЬИ-ТО здесь при чём? И фрагменты из описания своего «идеального стиля общения» цитировал. У меня на Фейсбуке ВСЕ мои ветки открыты ДЛЯ ВСЕХ, в том числе и для комментариев. Но там довольно чисто. Ибо редкий камикадзе осмеливается там гадить. И у меня МНОГО друзей, причём НАСТОЯЩИХ друзей, а не просто «френдов».
А вот насчёт «одного из последних абзацев» можно поподробнее? ЧТО ИМЕННО «заслуживает минуса» и ПОЧЕМУ?
Я уже цитировал, но могу и повторить:
Но вот моя точка зрения на это дело, тоже многократно высказываемая в разных местах: да, стиль своеобразный, но это рабочий стиль! Я заранее предполагаю, что оппонент адекватен, что он меня уважает, что он предполагает, что и я его уважаю, что все тезисы (мои или его) есть соответствующее IMHO, что это не нужно проговаривать на каждый чих. У меня нет ни времени, ни желания долго «обнюхиваться» при знакомстве, делать реверансы и т.п. И собеседнику моему, я полагаю, тоже время дорого. Так зачем же нам фигнёй заниматься, приплясывать друг перед другом — в тыщу раз эффективнее сразу поверить, что перед тобой нормальный, хороший человек, что с ним можно обмениваться эмоциональными, то бишь максимально информативными сообщениями. Господа, ну ведь это же так просто!
sint.wc.lt/about.htm
Ну вот, осталось ещё три плевка в карму, и у меня уже будет один коммент В ЧАС! Нет, не продержусь я сутки… :)
DocJester
Вы приходите в профессиональное сообщество с некоторым набором голословных утверждений, при этом часть Ваших высказываний демонстрирует, что в вопросе Вы некомпетентны (вопрос о равенстве классов P и NP тому пример).
Если Вы предлагаете какой-то алгоритм, который действительно позволяет ускорить решение задачи коммивояжера, то
1) Строго опишите алгоритм формально.
2) Докажите алгоритм (или доказательство корректности — пустой звук?)
3) Конкретно в данном случае, учитывая, что Вы используете теорию графов — строгое математическое определение всего, чем пользуетесь, теоремы и их доказательства.
Впрочем, глупо ждать подобных вещей от тролля.
GarryC
Он не тролль, он «непризнанный гений», это безнадежнее, тролль хотя бы должен понимать, о чем идет речь, для данного сабжа это не обязательно.
FDA847
Профессиональное сообщество не гадит тайно карму и не гнобит авторов. А тут просто в статьях травля какая-то идёт. Прям аж противно!
rybvv Автор
Именно травля! И это есть ИСЧЕРПЫВАЮЩАЯ характеристика «профессионального сообщества»!
Я вижу, уже и Вас травить начали? :)
lair
То, что вы что-то считаете рабочим стилем, совершенно не означает, что сообщество, в которое вы пришли, с вами согласно.
GarryC
Прочитайте 3-4 серьезных статьи действительно по теме, 10-15 летней давности, и Вы там найдете все те подходы и идеи, которые автор выдвигает, как свои. Причем среди авторов статей, посвященных сильно структурированным графам, вы фамилии автора поста не найдете.
особенно ее вторая часть.И в этих работах (действительно серьезных, с подключением математического аппарата) показан возможный выигрыш и четко указаны ограничения, налагаемые на вид исходного графа.
К сожалению, сильно структурированные графы составляют весьма незначительную (хотя и очень важную) часть общей задачи.
Вот поэтому лично мне статьи автора совершенно не представляются интересными, хотя я их и не минусую.
P.S. Мне трудно представить уровень профессионального невежества, необходимого для написания фразы
GCU
Я ожидал, что в статье будут хоть какие-то ссылки по теме.
Автор затрагивает достаточно интересную тему «изобретения» алгоритмов, использует некие эвристики для ускорения решения, но вот с обоснованием решений как-то мутно.
Обычно есть какие-то вполне обоснованные особенности задачи (например какая-нибудь особенная архитектура железа, строгие требования к памяти / времени выполнения, надёжности), которые требуют доработки стандартных решений.
Например — в фургоне с хот-догами стоит старенький 486SX c DOS, продавец путешествует по городу и решает задачу коммивояжёра. Я утрирую, но всё-же — нужны какие-то пусть даже гипотетически условия, для которых изобретение будет оправдано. Без этого статья теряет смысл, объективность и вызывает скорее недоумение (но зачем?)
lair
Потому что весь смысл рейтинга статьи в том, чтобы показывать, сколько людей хочет видеть такую статью (и подобные ей), а сколько — нет. Соответственно, если людям статья не нравится (не важно, за содержимое или за форму), рейтинг будет падать.
rybvv Автор
ЛЮДЕЙ?! Люди АРГУМЕНТИРУЮТ свои решения, а не гадят анонимно! Рейтинг, правда, меня вообще не интересует — он рот не затыкает. А вот карма…
lair
Это ваше собственное мнение, с которым никто не обязан быть согласным.
FDA847
У нас свободная страна, конечно, можно оставаться несогласным. Но гадить считается плохим деянием в любом обществе! Да и профессионалы, которых тут неоднократно упоминали, действительно должны обосновывать своё мнение.
lair
"Гадить" — это "делать плохо", поэтому это бессмысленное утверждение.
Эээ… почему должны? Кому должны?
FDA847
Это мы сейчас уже в область философии уйдём, поэтому предлагаю глубоко не копать. Суть моего тезиса проста. Если ты реально адекватный человек и считаешь себя профессионалом, то либо обоснуй своё мнение и выскажу отрицательную оценку, либо просто помолчи. Тайное сливание кармы мерзко. Это как тайно нагадить соседу перед входной дверью, вместо того, чтобы с ним нормально поговорить.
Конечно, бывают всякие ситуации, и встречаются абсолютные неадекваты. Но авто дайной статьи идёт на диалог, а ему почему-то просто затыкают рот. Мне это с самого начала не понравилось, поэтому я и написал свой первый комментарий.
lair
Это ваше собственное мнение, с которым никто не обязан быть согласным.
В таком случае просто не пользуйтесь ресурсом, где это заложено в правила. Вам здесь мерзко.
Нет, не идет. Он идет на многократное громкое (и неприятное) высказывание своей позиции, которое диалогом никак не является.
saw_tooth
Статья, не художественно-повествовательного характера, которая пытается что-то преподнести в виде новинки, для нормального аргументированного обсуждения, должна обладать равноправием с обоих сторон.
Более того, для признания правоты авторской мысли, которую уже как 3-ю (!!! как будто первых двух было мало) он пытается донести, автору не плохо бы предоставить непротиворечивые доказательства его правоты и всячески способствовать проверке.
А в данном случае мы получаем вот это:
Более того, автор не стыдится манипулировать комментариями свою пользу, использовать полемические уловки: полный спектр апелляций (к авториету, к тошноте, порочный круг и т.п.)
Очевидно, при такой агрессивной политике общения, и совершенно ужасных условиях доказательства его правоты, данную статью можно рассматривать как «вброс говна на вентилятор», приправленный:
— непроверямыми тезисами
— отсутствием логической полноты (корреляция не является причинно-следственной связью, соответственно нужно более гранулярно делать определения и выводы)
— отсутствие обобщенного алгоритма (согласитесь, из текущей стены текста, сложно вычленить какой-либо однозначный алгоритм, что бы на его базе сделать какие либо выводы)
— применение «неудобных технологий» для какой либо проверки (dos есть не у каждого, да и сомневаюсь что именно эта ОС стала той самой «серебренной пулей» в реализации автора. Если решение задачи математически верно, то от среды реализации, при прочих равных, оно не зависит)
и в последнее:
— активно-агрессивный тон, с переходом на личности, при попытке аргументированно критиковать автора.
Лично мне кажется, при таких аспектах, установка отрицательного значения кармы/рейтинга является мерой вынужденной (ногу режут, когда лечить уже не возможно) и нужной, что-бы:
— не травмировать психику людей, которые внезапно могут это прочесть, являясь неподготовленными (да, о плоской земле тоже раньше шутили, а теперь во что это превратилось)
— не культивировать ошибочных мнений и выводов (наличие вывода без фактов и эксперимента, не делает его репрезентативным, но часто это упускают, и получается желтая пресса
— наглядно показать, как НЕ нужно писать статьи, которые претендуют на новшество.
UPD. Самое интересное и не понятное, если автор, всех тут считает дибилами (быдлом), зачем он в очередной раз пишет здесь статью?