Немного истории. В 2001 году была решена задача на 15112 узлов, при этом процессорное время в пересчёте на 500 MHz Alpha processor составило более 22 лет, в 2004 был найден оптимальный тур для графа на 24978 узлов (88 лет), в 2005 — для 33810 узлов (15 лет), в 2006 — для 85900 узлов (136 лет). На этом пока всё и закончилось. Мало того: ни одно из известных на сегодняшний момент решений, строго говоря, нельзя считать таковым, поскольку расстояния между узлами округляются до целых, т.е. вычисляются приближённо. Так, для графа eil101 ошибка определения длины best-known тура составляет около 2%, ho14473 — 1%, lrb744710 — почти 6% и т.д. О каком же «точном» решении можно говорить при таких страшных ошибках в определении длины тура? Ещё более эффектный пример — World TSP на 1904711 узлов, если заданные GEO-координаты считать EUC-координатами, т.е. выполнить расчёт не на «глобусе», а на «карте мира». В этом случае ошибка округления составит более 10000%!
Разумеется, это «мелкое жульничество» отнюдь не случайно, поскольку позволяет сократить время вычислений, и не просто сократить, а сократить в НЕВООБРАЗИМОЕ число раз! Ведь при расчёте тура длины L любое найденное решение в диапазоне (L-1, L-0.5) уменьшает длину тура сразу на целую единицу, а при поиске этого решения исключается из рассмотрения ещё одна бездна вариантов в диапазоне (L-0.5, L). Кроме того, число таких «точных» решений растёт с увеличением числа узлов графа. Например, для графа wi29 точное решение лишь одно, а для eil51 их не менее трёх. Для графа lrb744710, при средней длине ребра best-known тура менее 2.2 (!), число «точных» решений наверняка составляет многие миллиарды. Одним словом, поиск действительно точных решений задач для таких графов потребовал бы уже не десятилетий, а многих тысячелетий процессорного времени.
Постановка задачи
- Задачу коммивояжёра будем решать именно в виде поиска Гамильтоновых циклов (замкнутый маршрут, включающий ровно по одному разу каждую вершину графа), для которых там якобы что-то «доказано», и именно полным перебором, который якобы «экспоненциален». Понятно, что ветви с границами экспоненциальны, но у меня вопрос, господа математики: кто посмеет отвергнуть гипотезу, что может существовать и полиномиальный алгоритм, который будет отсекать заведомо бесперспективные варианты ещё лучше, чем ветви с границами? Например, так хорошо отсекать, что количество туров-кандидатов после отсечения будет полиномиально по отношению к числу узлов графа? Есть такие?
- Алгоритм должен уметь находить как точные, так и «жульническо-точные» решения, поскольку буквально все существующие TSP-задачи считают длину ребра с округлением до целых — нам придётся продемонстрировать, что мы умеем их решать и в таком режиме тоже. Скорость и качество работы алгоритма не должны сколько-нибудь заметно зависеть от точности вычислений.
- Алгоритм должен работать на обычной персоналке и позволять при этом обсчитывать очень большие графы, с миллионами узлов. В настоящее время разработанный софт позволяет обсчитывать графы размером примерно до 100 миллионов узлов (чуть больше), наибольший из реально решавшихся им тестовых графов имеет 123456789 узлов.
- Поскольку TSP-задачи обычно многодневные, должна быть предусмотрена возможность отложить расчёт в любой момент с тем, чтобы возобновить его с момента откладывания в любое время.
- Несмотря на то, что подавляющее большинство существующих TSP-графов заданы, как точки на плоскости или на шаре, использовать их геометрические особенности мы принципиально не хотим. Это противоречит постановке задачи и, по сути, является таким же жульничеством, как и округление. Конечно, для реальных практических задач можно и нужно использовать все возможности, но нас интересует не разработка конкретного приложения, а решение задачи в общем виде. Поэтому мы не будем использовать, например, такой очевидный (и весьма эффективный) метод разбиения исходного графа на подзадачи путём группировки узлов по близости их координат. Одним словом, алгоритму должно быть безразлично, считается ли длина по координатам узлов, задана ли она таблично, выполняется или нет так называемое «неравенство треугольника». Так что решать задачу коммивояжёра мы будем именно переборными методами, в то время, как Keld Helsgaun, автор самого лучшего на данный момент метода, которым найдена львиная доля существующих best-known решений, признаётся, что 5 из 6 эвристик его алгоритма как раз геометрические.
Из всего многообразия алгоритмов мы будем рассматривать лишь те, которые основаны на модификации текущего тура, т.е. наш подход очень напоминает классический Lin-Kernighan-Johnson метод, как и его разновидность LKH. Однако есть важнейшее отличие: мы используем его для поиска не только приближённого, но и точного решения. Весь инструментарий для этого уже имеется, осталось только выбросить «мутации» и все остальные «ideas from tabu search and evolutionary computing», заменив их (хотя бы) каскадной рекурсией. Ведь любая ускоряющая эвристика на этом этапе лишь переводит задачу из разряда точных в приближённые! Оно нам надо?
Для детальной проверки всех концепций нашего подхода проведём масштабный эксперимент: решим заново все известные задачи, решённые и не решённые на данный момент, включив сюда и задачи из DIMACS TSP Challenge, и куда более трудные для обработки графы с иерархической кластеризацией собственного изготовления, и равномерно-случайные, и все остальные. В итоге получился набор из 395 задач коммивояжёра для графов от 3 до 123456789 узлов.
Скоростной алгоритм
Алгоритм минимально возможной модификации тура путем замены двух рёбер (2-opt) элементарен (из тура удаляются два ребра, затем полученные цепочки вновь соединяются в тур противоположными концами), но очень эффективен — это главная «рабочая лошадка» при скоростной модификации тура — именно на него падает основная доля падения бета-границы: до 90% и более. Другие алгоритмы атомарной модификации (например, «двойной мост», который меняет рёбра по схеме 4-opt), слишком дороги и практически не используются как почти бесполезные.
Итак, перед нами граф, для которого мы должны найти оптимальный тур. О самом графе и текущем туре мы не знаем пока ничего: возможно, тур уже оптимальный (такие «чудеса» иногда встречаются — например, у графа pr2392 узлы заботливо заданы именно в такой последовательности, что, соединяя на старте рёбрами первый со вторым, второй с третьим,… последний с первым мы как раз и получаем оптимальный тур). Возможно, погрешность составляет сотые доли процента (если, например, мы попытаемся улучшить best-known решение для графа w1904711), возможно — многие тысячи процентов (скажем, погрешность для того же w1904711 на старте составляет более 50000%) — алгоритму об этом ничего не известно. Поэтому он «предполагает худшее», и главная задача скоростного алгоритма — «уронить» бета-границу как можно быстрее и как можно ниже. При этом крайне желательно рассматривать не все рёбра графа (которых всё у того же w1904711 несколько триллионов), а лишь весьма небольшую их часть, но именно ту, которая позволить уменьшить бета-границу. Напомним, что о рёбрах у нас тоже нет никакой информации — они даже могут быть заданы таблично. Так есть ли хоть какие-то критерии для выбора «нужных» рёбер? Такие критерии есть!
На старте, при загрузке исходных данных, считаем длину текущего тура и, поделив её на число узлов графа, получаем среднюю длину ребра. Таким образом, каждое рассматриваемое ребро тура может быть меньше, больше, много больше этой самой текущей средней длины. Именно эта информация и управляет перебором: чем длиннее ребро, тем внимательнее оно рассматривается: при увеличении длины ребра на каждые 5% (реально у нас чуть больше — на 1/16) глубина рассмотрения (то есть количество рёбер тура, начиная с текущего, с которыми проверяется возможность атомарных изменений тура) удваивается. Короткие же рёбра (у нас это рёбра средней длины и менее) рассматриваются лишь на минимальную глубину, которая определяется текущей итерацией (этап поиска решения каким-либо алгоритмом для всех рёбер тура), и вообще может быть нулевой. Фактически, это и есть разбиение исходного графа на подзадачи, но разбиение динамическое, по факту принадлежности элементов группы одному участку текущего тура.
Что это даёт? Очень многое! При таком подходе короткие рёбра на младших итерациях почти не рассматриваются, т.е. алгоритм не отвлекается на «мелочь», и смотрит лишь те варианты, которые могут дать серьёзное уменьшение бета-границы. С каждым найденным решением средняя длина ребра уменьшается, поэтому некоторые рёбра, считавшиеся ранее «короткими» переходят в разряд «длинных» и вовлекаются в перебор. Напротив, переход к следующей итерации никак не зависит от длины тура, и определяется отношением количества найденных за время итерации решений к числу узлов графа. Смысл очевиден: незачем «звать на помощь старших», пока дела идут хорошо. Более того, если отношение совсем уж велико (десятки процентов), значит, тур удалось хорошо «взлохматить», и есть смысл вернуть управление младшим (более скоростным) итерациям, поскольку вероятность их успешной работы весьма высока.
Вообще говоря, реально существующий скоростной алгоритм работает примерно в 10-100 раз быстрее, чем только что описанный, поскольку при поиске решения имеется множество технических нюансов. Перечислим важнейшие:
Львиную долю производительности обеспечивает так называемый «добор». После окончания каждой итерации, если при этом было найдено хотя бы одно решение, она повторяется, но только для новых рёбер, появившихся именно на этой итерации. Таких рёбер обычно совсем немного, но они ещё не рассматривались, и вероятность новых решений среди них довольно высока. В результате «добор» выполняется во много раз быстрее, а его эффективность нередко даже превышает эффективность основной итерации. Таким образом, каждая итерация снижает бета-границу приблизительно вдвое сильнее, и почти всё её снижение (90% и более) приходится на 2-3 самых младших итерации, что заметно ускоряет прохождение и всех остальных итераций. Программно «добор», разумеется, реализован в рамках одной итерации, которая заканчивается не после рассмотрения всех рёбер тура, а после того, как все они, включая вновь появившиеся, получат статус «рассмотрен».
Введено понятие «минимальной базовой глубины» (у нас она составляет 64 ребра) — это означает, что скоростной алгоритм не имеет права закончить работу даже при полной неудаче с поиском решений, пока все рёбра не будут рассмотрены на эту минимальную глубину. Такой подход практически гарантирует, что скоростной алгоритм не передаст следующему обработчику тур с погрешностью в сотни и тысячи процентов. Для графов с большими погрешностями стартового тура эта минимальная глубина может расти «естественным образом» (если итерациям будет удаваться находить достаточно много улучшений тура) — мне доводилось наблюдать и глубину 1024, и даже 8192 (больше не видел ни разу), но это уже для графов-«миллионников». В любом случае, даже такая глубина пренебрежимо мала по сравнению с количеством узлов графа, поэтому время работы скоростного алгоритма растёт практически линейно по числу узлов, что и подтверждает эксперимент.
Введено понятие «абсолютного ребра». Если для какого-либо ребра глубина расчёта составит половину узлов графа или более, ребро обсчитывается полностью, на всю глубину, и помечается как «абсолютное», которое уже не будет рассматриваться ни на одной их последующих итераций скоростного поиска. Для некоторых типов графов эта техника позволяет уменьшить время поиска решения в разы.
При сверхмалой глубине расчёта текущего ребра (до 16) смотрим только «разворот цепочки», далее подключаются некоторые скоростные версии из серии 3-opt, а на глубине 64 (минимальная обязательная глубина) более «тяжёлые» атомарные алгоритмы. Это сокращает время работы скоростного алгоритма примерно вдвое.
При обработка «сверхдлинных» рёбер (с длиной, превышающей среднюю в 8 и более раз) решение на изменение тура принимается лишь при уменьшении длины именно этого ребра, причём не менее, чем на 1%. Это не только сокращает время поиска на данной итерации, минимизируя «мышиную возню» на длинных рёбрах, но и нередко заметно сбрасывает бета-границу, ускоряя, таким образом, и прохождение всех остальных итераций.
Есть множество других нюансов реализации: ограничение на разницу в глубине расчёта длинных и коротких рёбер, инкрементирование длины ребра при выборе глубины, чтобы избежать неприятных наводок, вызванных округлением до целых (иногда это ускоряет расчёт в десятки раз!), технология изменения базовой глубины расчёта между итерациями и т.п.
Эксперимент показал, что скоростной алгоритм (который рассматривает, как правило, далеко не все рёбра — иногда намного меньше 1%) даёт вполне удовлетворительные результаты, пригодные даже для практического применения. Бета-граница с любой величины (обычно это 3-5 тысяч процентов погрешности) падает до 10-20%, редко выше, часто ниже. Эффективность работы алгоритма для сверхбольших графов и вообще не с чем сравнивать: ни одна известная нам программа не в состоянии даже начать расчет уже при сотнях тысяч узлов (по крайней мере, на обычном PC). Иными словами, мы не считаем нужным далее улучшать скоростной алгоритм. В конце концов, есть возможность использовать любой понравившийся эвристический алгоритм, а его результат «скормить» нашему в качестве входных данных. Что мы и делали при расчете решения без округления, подставляя в качестве исходного «оптимальный» тур из TSPLIB. Даже в этом случае основная доля найденных решений приходится тоже на скоростной алгоритм.
Ну и хватит, пожалуй. Похоже, тут тоже получится 3-4 заметки, а как их писать, когда мне столько нагадили в карму, что я могу публиковать не более одной заметки в неделю в этом несчастном «Recovery Mode»? О-хо-хо…
Комментарии (56)
igormich88
13.05.2019 13:47А как в общем случае связаны длина ребра и связанный с ним выигрыш? Ну то есть можно же построить граф где выигрыш обратно пропорционален длине ребра.
PS я не специалист по теории графов.
m1n7
13.05.2019 13:54-3а как их писать, когда мне столько нагадили в карму
А зачем вообще их писать? Тут же только СТАДО БАРАНОВ и «УЧИТЕЛЯ», какой смысл метать бисер перед свиньями?
sbnur
13.05.2019 14:06-1Как писал, мой знакомый поэт:
А жизнь прошла, как иностранка,
Которую никто не знал...
GCU
13.05.2019 14:21Непонятно — как считается погрешность?
Откуда могут взяться тысячи процентов, если можно просто минимальное остовное дерево обойти два раза…
rybvv Автор
13.05.2019 14:28-1О быдло ломанулось! Уже и ветка имеет -14, и карма -18, и в рейти нге на полторы сотни вниз скакнул! И всё молча, всё анонимно! Стадо трусливое… Как же меня тошнит от этой помойки!
Поскольку у меня теперь [пока ещё] «1 коммент в час», отвечать буду «оптом».
igormich88
А как в общем случае связаны длина ребра и связанный с ним выигрыш?
Никак не связаны. Представьте граф в миллион узлов компактной группой, и далеко-далеко от неё находится последний узел, для которого, возможно, никакого выигрыша вообще нет. А что там «можно же построить », я вообще не понял. :)
GCU
Непонятно — как считается погрешность?
Это для «геометрических» графов. Я уже давал иллюстрацию: представьте, что все расстояния лучшего тура составляют 1 см, а все рёбра, туда не входящие, имеют длину от одного до сотни… парсеков. Так что ЛЮБОЙ тур, кроме оптимального, будет иметь многие миллиарды процентов погрешности.
Откуда могут взяться тысячи процентов, если можно просто минимальное остовное дерево обойти два раза…
m1n7
Зачем писать? Первую заметку (сортир) я написал именно для серьёзного разговора, полагая, что я действительно пришёл в «сообщество разработчиков». Вторую (про ИИ) я написал «для приглашения», поскольку здешние правила с премодерацией… ну, я об этом уже писал, и даже в этой ветке. Две статьи про OSM тоже серьёзные — я их написал тоже «для разработчиков», с которыми поначалу был довольно интересный разговор, но быстро утух. А цикл заметок про комми — специально для трусливого быдла, которое способно только анонимно гадить в карму, да пальцы гнуть — делать что-либо оно не в состоянии. Что и наблюдаем. :)
GarryC
Лапуль, я уже говорил, что за все мои 27 лет пребывания в Сети, у меня НИКОГДА не было ника, кроме rybvv, что означает Рыбинкин Владимир Владимирович, так что свои дурацкие ДОМЫСЛЫ (в т.ч. про «ингкогнито»), засуньте, плиз, туде же, куда и свои «советы». ;) А комментарий Ваш предназначен для засирания ветки словесным поносом, ибо по теме ветки, как и в случае алгоритма сортировки, Вы ничего сказать НЕ СПОСОБНЫ. ;) Кстати, говорил уже: я НЕ применяю метод ветвей и границ! Чукча не читатель? ;)
Sirion
Да нет у меня никакого «апломба»! И не было никогда! Что там может «прощать» стадо, которое МОЛЧА гадит в карму? Вот ЗА ЧТО набросились на эту заметку? НА КОЙ Вам «код»? Что Вы с ним делать будете? Здесь АЛГОРИТМ описан! Шевельните извилиной, «разработчики», хреновы! ;)
sbnur
А как я писал одному «знакомому поэту»:
Утратили способности любить,
Тщеславие надеясь утолить
В бряцанье злата, в самовосхваленьях,
И в бесконечных поисках того,
Кто вас ещё ничтожнее и гаже
Вам предстоит свой смертный встретить час.
Вы жалки, вы смешны… но тьфу на вас!
Умрите ж под Москвой, скулящие уроды!
Ваш вид отвратен мне, но, к счастью, y природы
В достатке самых сладостных утех
И ласки женщины, и детский смех,
И запахи лугов, журчанье родника,
И дождь, и солнце, небо, облака,
И в шелесте листвы, пронизанной лучами
Светила заходящего, и в птичьем гомоне,
В сиянии снегов, в божественных аккордах
Ушедших гениев полно очарованья
Искусство, знание, надежные друзья…
Всё, без чего представить жизнь нельзя.
Как много нам дано добра и света!
Спасибо тебе, жизнь, за всё за это!
Sirion
13.05.2019 14:34-1Вы правда думаете, что дело в анонимности? Так я вам в лицо скажу:
1. Вы хамло.
2. Вы сильно переоцениваете свою квалификацию (точнее, сильно недооцениваете квалификацию всех остальных).
Товарищи быдло, выходите из сумрака, присоединяйтесь)
GCU
13.05.2019 14:41Я не понимаю каким образом ребро в «несколько парсеков» окажется в минимальном остовном дереве.
Возможно речь идёт об ориентированных графах, где «стоимость» использования рёбер для перехода AB и BA различна (или вообще перехода назад нет), или вершины нельзя посещать несколько раз…
Но тогда приведённые примеры графов реально сбивают с толку, они же «геометрические».
Chuvi
13.05.2019 14:56+2Вот он я, поставивший один из минусов. Первопричина спора мне не известна, но ваш тон в первом абзаце поста вызвал желание поставить посту минус и закрыть его.
igormich88
13.05.2019 15:13Если связи нет то почему ваш алгоритм основывается на оценке ребер по их длине?
А как именно построить я не знаю, но предполагаю что имея алгоритм можно найти граф на котором он будет работать не эффективно, например долго обрабатывать длинные ребра не получая от этого существенного выигрыша.
OvO
13.05.2019 14:53+1Хотя автор груб, не допускает возражений и иногда бездоказателен в своих утверждениях нельзя не отметить что его статьи весьма яркие и заставляют задуматься. И прежде чем лишать человека возможности их писать, может, стоит задуматься, насколько страшны ваши обиды?
Sirion
13.05.2019 15:02-1О чём конкретно вы задумались после этой статьи? Расскажите.
GCU
13.05.2019 15:07+1Правда, что такой статьи достаточно чтобы стать полноправным пользователем Хабра? :)
OvO
14.05.2019 00:26+1Позвольте избавить вас от заурядных объяснений и оставить мои мысли при мне. Как мне показалось, автор очень ревностно относится к своему делу и кому-то может не понравиться статья или комментарий, но совсем лишать человека слова, в данном случае, незалуженно.
Sirion
14.05.2019 01:24+1У меня нет возможности вам это не позволить. Однако, на мой взгляд, ваше молчание в ответ на мой вопрос обесценивает вашу точку зрения и придаёт больший вес нулевой гипотезе.
Если автору важно донести до широких масс свои мысли, ему следует освоить правила поведения в обществе. Разумеется, есть определённая ступень гениальности, после которой её обладателю простят всё, даже если он будет плевать собеседнику в рожу. Такой, знаете, гипертрофированный доктор Хаус. Но автору до этой ступени очень и очень далеко. Его опусы в лучшем случае вызывают любопытство, а его манеры таковы, как будто, простите за быдло-аналогию, его никогда в жизни не били по лицу.OvO
14.05.2019 15:02+1Это ваше мнение, я не хочу вступать в долгую полемику на тему статьи, в которой вы разбираетесь лучше меня.
Я, как читатель, призываю не затыкать рот авторам, которые пишут противоречивые статьи вызывающие любопытство, даже если они грубы. Кроме того, если вы уже готовы простить гению всё, то проигнорировать грубость взрослого человека, который рассказывает о своей многолетней работе(?), не должно составить труда.Sirion
14.05.2019 16:01Я услышал ваш призыв, но, пожалуй, всё же проигнорирую его, как вы игнорируете мои аргументы. Повторюсь, я не вижу здесь содержания, из-за которого стоило бы прощать форму. Если это итог многолетней работы, это поднимает вопрос о качестве работы.
Позволять каждому, простите, балаболу сыпать широковещательными оскорблениями на моём любимом ресурсе я не настроен. Как и большинство тех, кто обладает правом голоса. Вам как читателю придётся с этим смириться.OvO
14.05.2019 17:26Строго говоряб я не пытаюсь убедить лично вас, Вы — меньшинство этого большинства, хоть и говорите от его имени. А случайный пользователь может и согласится, что пока автор остается в рамках правил ресурса, не стоит затыкать ему рот.
michael_vostrikov
14.05.2019 17:32Так не остается он в рамках правил ресурса, и просьбы их соблюдать игнорирует, потому и ставят минусы.
Sirion
14.05.2019 18:42Вопрос даже не в правилах. Кармическая система кокрастыке и нужна для того, чтобы модерировать тех, кого по правилам вроде бы и не за что, а надо.
wataru
14.05.2019 17:51Я поддержу michael_vostrikov тут. Я тоже считаю что автор не вписывается в рамки данного ресурса.
Sirion
14.05.2019 18:39По крайней мере, я аргументирую своё мнение. Чего нельзя сказать о вас. Вы считаете, что право высказаться должно быть вообще у каждого, независимо от? Тогда хабр превратится в помойку
ещё большую, чем сейчас. Вы считаете, что у данного конкретного автора есть какие-то особые достоинства, оправдывающие его недостатки? Тогда ответьте на мой исходный вопрос: о чём эта статья заставила вас задуматься?OvO
14.05.2019 19:30-1Мое мнение вполне очевидно, каждый может ошибаться, каждый имеет право проявлять эмоции. Есть разные типы людей — кто-то более эмоционально стабилен, а кто-то менее. Кто-то, например, считает, что кроме правил есть еще известные только ему понятия. У всех есть свои тараканы в голове.
Если говорить объективно про данного автора, то у него есть 6 статей за месяц, половина из которых оценена положительно с сотнями комментариев. Значит может, умеет возбуждать аудиторию, нравиться ей. Но не сегодня. Сегодня 41 пользователь(это если судить по минусам в статье, на самом деле меньше) лишили остальных этого контента. Это большинство ресурса? Нет. Статья нарушала правила ресурса? Неочевидно, я не нашел, но ходят слухи, что было. Автор может писать статьи, которые нравятся людям? Уже нет. Уменьшение контента ведет к уменьшению аудитории и потере популярности ресурса, что, в свою очередь, превратит его в помойку.Sirion
14.05.2019 19:56Это работает не так. Позвольте ответить вам анекдотом.
Заголовок спойлераСтарый шотландец жалуется близкому другу:
— Я, Джон МакМорран, построил два хороших крепких моста через реку. Вся
деревня теперь ходит по этим мостам и радуется. Но никто, никто не
называет меня «Джон Строитель Мостов»!
— Я, Джон МакМорран, когда на нашу деревню напали ночью подлые
англичане, первым выскочил из дома и убил двенадцать врагов, получив при
этом только две царапины. Но никто, никто не называет меня «Джон Храбрый
Воин»!
— Я, Джон МакМорран, искустный кузнец. Я сковал столько мечей, что даже
наши внуки не будут испытывать в них недостатка. Но никто, никто не
наывает меня «Джон Кователь Мечей».
— Но стоило мне ОДИН РАЗ трахнуть овцу…Zenitchik
14.05.2019 20:06Уменьшение контента ведет к уменьшению аудитории и потере популярности ресурса, что, в свою очередь, превратит его в помойку.
А вот тут скорее наоборот. Сейчас в погоне зарекламными деньгамипопулярностью Хабр превращают в помойку. Тогда как в интересах находящихся здесь специалистов — превратить его в более элитарную площадку.
michael_vostrikov
14.05.2019 22:02+3Это большинство ресурса? Нет.
Вы подменяете понятия. На Хабре нет правила, что каждый должен проголосовать за статью. Большинство не будет ставить минус либо потому что им эта тема вообще неинтересна, и они статью не читали, либо потому что видят, что минусов уже достаточно. Я например не ставил. В итоге заинтересованных в теме и согласных с минусами большинство. Потому что те, кто заинтересован и не согласен, ставят плюс.
Статья нарушала правила ресурса? Неочевидно, я не нашел, но ходят слухи, что было.
На Хабре можно писать не только статьи, но и комментарии. И соответственно другие могут эти комментарии читать, как и статьи. На качество ресурса влияют обе составляющие. Почему вы только статьи рассматриваете? Комментарии нарушают правила ресурса, этому есть подтверждение от администрации.
В статьях тоже нет ничего, что составляет ценность. В таких статьях пишут доказательства с использованием логики и математики, приводят сравнения с существующими методами, а также код или хотя бы псевдокод. Здесь этого нет. Насколько было бы меньше флуда, если бы автор привел в статье код своей сортировки? Флуд это полезные комментарии, они ведут к увеличению популярности ресурса? Нет.
Уменьшение контента ведет к уменьшению аудитории и потере популярности ресурса
Это некорректное обобщение. Уменьшение качественного контента ведет к уменьшению аудитории и потере популярности ресурса, уменьшение некачественного контента ведет к увеличению (или как минимум к сохранению) аудитории и приобретению популярности ресурса.
Сегодня 41 пользователь лишили остальных этого контента
Автор может писать статьи, которые нравятся людям? Уже нет.Зато другого не лишили. Другие авторы могут писать статьи, которые нравятся людям? Да. Значит причины для сохранения популярности ресурса остаются. Авторы могут предполагать, что к их статьям не будет комментариев в подобном стиле? Это положительно влияет на их желание писать статьи? Ответ выбирайте сами.
Ресурсу не нужны любые авторы, нужны те, которые как минимум не влияют на него отрицательно.
OvO
14.05.2019 23:14+1Извините, но я кратко. Статья мне не понравилась, 42 минус мой. 41 это верхняя оценка количества отрицательных отзывов автору исходя из предположения, что за каждым минусом автору следовал минус статье. Я считаю, что неудачная статья — не повод затыкать рот, за ней вполне могли следовать и удачные, тем более что таковые уже были.
По поводу популярности — Reddit на ~75% состоит из флуда, котиков и эротики, но я не за котиков, я за баланс.michael_vostrikov
14.05.2019 23:56+1А что конкретно является поводом затыкать рот? Например, неоднократное нарушение правил ресурса является? Это не риторический вопрос, ответьте пожалуйста, да или нет?
И почему вы решили, что статья является таким поводом? Поводом является общение автора в комментариях. А статью, как я понимаю, просто заминусовали, потому что нормальные статьи на такие темы пишутся по-другому.
И я повторю вопрос, который вы проигнорировали, но тем не менее повторили аргумент, с которым он связан. Почему вы рассматриваете только статьи? И почему вы думаете, что такие статьи не могут написать другие авторы, которые общаются соблюдая правила ресурса?
OvO
15.05.2019 00:48А что конкретно является поводом затыкать рот
Грубое нарушение правил ресурса — да.
Поводом является общение автора в комментариях.
А что с комментариями? Эмоционально, грубо, но ничего криминального.
Почему вы рассматриваете только статьи?
Не уловил суть вопроса, но я рассматриваю все интересное и доктор сказал, что это нормально.
И почему вы думаете, что такие статьи не могут написать другие авторы,
Конечно, такие статьи могут написать и другие авторы, могут, могут, но… не пишут.michael_vostrikov
15.05.2019 09:13+1Грубое нарушение правил ресурса — да.
В таком случае ваше определение грубого и негрубого нарушения, пожалуйста. И пояснение, почему в правилах вообще должны быть ограничения, которые можно нарушать негрубо без применения каких-либо мер.
А что с комментариями?
Я же уже сказал — они нарушают правила ресурса, причем этому есть подтверждение от администрации.
грубо
Это достаточная характеристика, чтобы люди не захотели общаться. Нет, вариант просто не общаться с автором в его статьях не подходит, он навязывает такой стиль общения и в других статьях. А также это достаточная причина, чтобы снизить популярность и привлекательность ресурса, тем более для незарегистрированных пользователей.
Не уловил суть вопроса
Почему вы считаете, что причины "статья не нарушала правила ресурса" и "за ней вполне могли следовать и удачные" стоит рассматривать как повод не ограничивать автора в общении, а причины "комментарии нарушали правила ресурса" и "за ними вполне могли следовать комментарии в том же стиле" не стоит рассматривать как повод ограничить?
Конечно, такие статьи могут написать и другие авторы, могут, могут, но… не пишут.
Доказательства, пожалуйста. На какие конкретно темы другие авторы не пишут статьи, которые нравятся людям?
OvO
15.05.2019 23:27Нет, вариант просто не общаться с автором в его статьях не подходит, он навязывает...
Вы сейчас тоже пытаетесь навязать свой стиль и мне, допустим, не понравились ваши многочисленные вопросы и ваши попытки найти логические ошибки в моих ответах. Я мог бы тыкать стрелочки, возмущаться, воспитывать и пытаться отстоять свою точку зрения, но я могу поступить проще и вы не сможете мне в этом помешать — я могу не читать ваши комментарии и не отвечать на них. Ничего личного, просто для примера, смотрите, как хорошо я это умею:michael_vostrikov
16.05.2019 00:09+1я могу не читать ваши комментарии и не отвечать на них
Вот в той части предложения, которую вы скрыли за многоточием, и есть объяснение, почему это не работает. Я открываю статью другого автора, читаю комментарии, и чтобы определить "этот комментарий написан в стиле, который мне не нравится, и мне не надо его читать" мне надо его сначала прочитать. На Хабре нет возможности скрывать комментарии конкретного пользователя.
А незарегистрированные пользователи вообще не в курсе, кого игнорировать, а кого нет. Почитают, и не будут регистрироваться, и другим скажут что там ругань в комментариях, и другие тоже не будут регистрироваться. Вот это прямо ведет "к уменьшению аудитории и потере популярности ресурса".
и мне, допустим, не понравились ваши многочисленные вопросы и ваши попытки найти логические ошибки в моих ответах
Многочисленные вопросы и указание на логические ошибки не имеют общеизвестного негативного смысла и не нарушают правила ресурса. Выражения автора имеют и нарушают. Возможно вам пофиг на ресурс, а мне и другим нет. Я хочу читать информацию про программирование, а не ругательные слова. Вы можете поставить мне минус в карму по личной неприязни, а не по объективным причинам, это ваш выбор и вопрос вашей совести. Кто-то другой поставит мне плюс, и если таких будет больше, ваш минус ничего не будет значить. А если меньше, значит я сделаю вывод, что я действительно всем надоел своими вопросами, и не буду их задавать, если хочу продолжать иметь возможность оставлять комментарии.
Я мог бы тыкать стрелочки, возмущаться, воспитывать и пытаться отстоять свою точку зрения
Почему вы решили, что ограничением на комментирование автора кто-то воспитывает или пытается отстоять свою точку зрения? Ему ограничили комментирование, чтобы он не ругался в комментариях. Потому что просьбы словами он игнорировал. Всё.
Если что, лично я ему минус в карму не ставил. Я не ставлю минусы тем, с кем спорю.
GarryC
13.05.2019 15:59Да Господь с Вами, какие обиды? Здесь идет речь о том, что человек не вполне компетентен в нашей (надеюсь) предметной области (посмотрите хотя бы его ответы на комментарий в статье о сортировке — он реально не понимает разницы между методом слияния и методов вставки) и пытается скрыть свои недостатки под густым слоем апломба, плавно переходящего в хамство. Меня лично его высказывания обидеть не способны, «обидеть может равный».
rybvv Автор
13.05.2019 16:57-2:lol: Воистину, «не имей сто рублей, а имей наглую рожу». Говорил, носом возил, что в моей «воронке» НЕТ И БЛИЗКО никакой «вставки», не говоря уже про «квадратичную сложность» — вроде, заткнулся, но проходит время, и оно опять всплывает… Так что про «компетенцию» уж чья бы корова мычала! Включая тех двоих «реализаторов», которые изуродовали мой алгоритм (один даже до квадрата!) и продолжали нагло утверждать, что это МОЙ алгоритм! И говорил уже тыщу раз обидеть В ПРИНЦИПЕ невозможно — можно лишь обидетьСЯ!
Ну что, по теме ЭТОЙ заметки ХОТЬ КТО-НИБУДЬ, ХОТЬ ЧТО-НИБУДЬ — скажет? Кто там вякал-то про «квалификацию»? А ну, поворотись-ка, сынку! Экий смешной какой!(с)
Ух ты, как ломанулись-то на мой tsptest смотреть! Я ща глянул — там данные немного устарели. Я давно уже комми не гонял, но кое-что там изменилось. Если интересно — сохраните страницу, через пару часиков обновлю — посмотрите динамику. Так что же минусов-то накидали, если с таким интересом ломанулись? Тем более, ни одна собака ни слова против алгоритма так и не осмелилась вякнуть. Думаю, так и не осмелится.
GarryC
О! Про вставки и квадратичную сложность заткнулись, наконец? :lol: ЧТО, НЕТ???!!! И что за херню Вы тут выкопали? С КАКОГО ХРЕНА «сортировке слиянием данные должны быть доступны с самого начала работы алгоритма»? В «воронку» данные поступают именно ПОСЛЕДОВАТЕЛЬНО, и никакого «дополнительного массива организовать» не требуется (автор НЕ описывал такой вариант — не надо ВРАТЬ!), и никакой «сортировки вставками» НЕ ТРЕБУЕТСЯ! По крайней мере, МОЕМУ алгоритму! А что там у полуграмотных идиотов — то мне по барабану. Моя воронка спокойно отсортировала МИЛЛИАРД строк, причём именно того исходного массива, который указал «критик», и который сам сумел отсортировать сраные 32К тех же строк.GarryC
13.05.2019 17:11+1Какое тонкое наблюдение насчет того что иметь, а что нет…
Не для Вас (это безнадежно), но для тех читателей, что хотят разобраться в методах сортировки.
Сортировка слиянием применяется для данных, расположенных в памяти, причем эти данные должны быть доступны с самого начала работы алгоритма, и именно за счет данного обстоятельства (и использования дополнительной памяти O(n)) удается снизить сложность до O(n*ln(n)).
В том случае, когда очередные элементы данных поступают последовательно и нет возможности организовать дополнительный массив (а именно такой вариант описывал автор изначального текста, особенно напирая на ограничения по памяти), применяют сортировку вставками и у нее сложность O(n*n).
Ну а то теме этой заметки сказать особо и нечего — никто не обязан давать доказательства невозможности существования алгоритма, сводящего задачу к полиномиальной, наоборот, бремя доказательства верности алгоритма и его свойств лежит на авторе алгоритма, лично я подобных доказательств не увидел (доказательства в стиле «мамой клянусь, да» в инженерной среде не принимаются.
Когда нормальные доказательства будут, тогда и поговорим. Для уяснения способа построения подобных работ рекомендую обратится к книге Кнута, там есть множество примеров доказательства правильности и свойств алгоритмов.wataru
13.05.2019 18:16+1В том случае, когда очередные элементы данных поступают последовательно и нет возможности организовать дополнительный массив (а именно такой вариант описывал автор изначального текста, особенно напирая на ограничения по памяти), применяют сортировку вставками и у нее сложность O(n*n).
Вообще говоря, сортировка кучей не потребует памяти больше чем ровно один массив и будет работать за O(n log n).
Хотя я, скорее всего, не понимаю контекста. Какое-то очень странное ограничение — получать элементы по одному, но в конце выдать их все отсортированными в списке.
michael_vostrikov
13.05.2019 18:30+3Моя воронка спокойно отсортировала МИЛЛИАРД строк, причём именно того исходного массива, который указал «критик», и который сам сумел отсортировать 32К тех же строк.
Один из «реализаторов» отсортировал максимально жалкие 32768 строк, в воронка — МИЛЛИАРД таких же строк, то есть в 32768 раз больше, чем эти несчастные 32768!Почему вы продолжаете это повторять в разных комментариях? Вы думаете, в другие алгоритмы сортировки нельзя поставить произвольное количество элементов? Или что, какой вывод-то?
Вот, пожалуйста.
// 11, 12, 13, 14 timSort 1073741824 elements compareElements() calls: 6140460645
На 32 миллиона сравнений меньше, чем у вас с несколькими воронками (6172582694), и на 21 миллиард меньше, чем с одной (28021925721). Дальше что?
Вы даже не смогли прочитать и понять окружающий текст, хотя причина, по которой я сделал только до 32768 элементов там указана явно: "вы слишком преувеличиваете линейность".
Восемь цифр для определения динамики вполне достаточно — уже по ним явно видно, что никакой линейности нет. Это значит, что про линейную сложность в худшем и среднем случае вы наврали, и никакой миллиард этого не исправит.
Akon32
13.05.2019 23:07может, стоит задуматься, насколько страшны ваши обиды?
Задуматься? Но зачем? Обиды комментаторов — это проблемы автора.
Имхо, в статье про сортировки есть что-то полезное, но любые попытки что-либо уточнить разбиваются о закостенелость автора и утопают в его стиле общения… В итоге доля полезной информации стремится к нулю, а срачи процветают.
rybvv Автор
13.05.2019 15:29-6Что, час прошёл, что ли? Ну, ловите снова «оптовый» ответ:
Chuvi
Я про то и говорю! Форма и содержание, данные и информация, смысл и значение… Я так и писал насчёт своего «тона»:
Стиль мой не ругал только ленивый. Особенно часто это делают мои друзья, которые бывают иногда весьма убедительны. Тем не менее, я считал и считаю, что стиль у меня практически идеальный. Здесь я приведу небольшую справку для тех, кто меня ещё не знает, в виде аргументов той и другой стороны. Речь идёт, разумеется, только о форме общения — содержание достаточно неплохо описывается пушкинским: «Для власти, для ливреи не гнуть ни помыслов, ни совести, ни шеи». А по форме претензии ко мне такие:
…
Убедительно? Убедительно. Да я и сам прекрасно знаю, что «встречают по одёжке». Но вот моя точка зрения на это дело, тоже многократно высказываемая в разных местах: да, стиль своеобразный, но это рабочий стиль! Я заранее предполагаю, что оппонент адекватен, что он меня уважает, что он предполагает, что и я его уважаю, что все тезисы (мои или его) есть соответствующее IMHO, что это не нужно проговаривать на каждый чих. У меня нет ни времени, ни желания долго «обнюхиваться» при знакомстве, делать реверансы и т.п. И собеседнику моему, я полагаю, тоже время дорого. Так зачем же нам фигнёй заниматься, приплясывать друг перед другом — в тыщу раз эффективнее сразу поверить, что перед тобой нормальный, хороший человек, что с ним можно обмениваться эмоциональными, то бишь максимально информативными сообщениями. Господа, ну ведь это же так просто!
…
Да, мои слова часто «выглядят именно наездом или наскоком». Для тех, кто закомплексован, кто ищет эти наскоки, кто не в состоянии поверить собеседнику, кто боится быть им обманутым… да и хрен бы с ними! Следовательно, этот мой стиль не только рабочий, но и фильтрующий всяких закомплексованных! Не говоря уже про штатных троллей. Они с этим стилем не уживаются, он не сдаёт территорию хаму и мерзавцу — он её защищает. А если мы будем себя уважать только на собственной кухне, отдав все публичные площадки хамам и подлецам, то за что, нам, собственно, себя уважать?
GCU
Правда, что такой статьи достаточно чтобы стать полноправным пользователем Хабра?
И не такой достаточно! Правда, никаких «полноправных пользователей Хабра» при ТАКИХ правилах нет, И БЫТЬ НЕ МОЖЕТ!
igormich88
Если связи нет то почему ваш алгоритм основывается на оценке ребер по их длине?
А на чём же ещё основываться? Ведь никакой другой информации ВООБЩЕ НЕТ! :)
А я предполагаю, что НЕЛЬЗЯ «найти граф на котором он будет работать не эффективно, например долго обрабатывать длинные ребра не получая от этого существенного выигрыша». Алгоритм — вот он, в заметке! Ищите граф! :) Для ориентировки — вот все мои тестовые графы, которые обсчитывались этим алгоритмом — на любой вкус!
sint.wc.lt/tsptest.htm
third112
13.05.2019 17:48+4Ведь любая ускоряющая эвристика на этом этапе лишь переводит задачу из разряда точных в приближённые! Оно нам надо?
Отсюда понял, что предлагается строго доказанный, а не эвристический алгоритм. Но где? Точное описание алгоритма и его доказательство? Их нет.
Есть множество других нюансов реализации: [...] и т.п.
Все нюансы даже не перечислены.
время работы скоростного алгоритма растёт практически линейно по числу узлов, что и подтверждает эксперимент.
Теоретической оценки сложности нет. Значит, несмотря на заявление выше, эвристика. Но экспериментальная оценка требует воспроизводимости. Как я могу воспроизвести и проверить, если нет описания алгоритма и листинга программы? Никак, что грубо противоречит экспериментальному подходу.
При этом:
Для графов с большими погрешностями стартового тура эта минимальная глубина может расти «естественным образом» (если итерациям будет удаваться находить достаточно много улучшений тура) — мне доводилось наблюдать и глубину 1024, и даже 8192 (больше не видел ни разу), но это уже для графов-«миллионников».
Если автор не видел — это не значит, что такого не существует.
В итоге получился набор из 395 задач коммивояжёра для графов от 3 до 123456789 узлов.
395 задач лишь малая часть возможных задач, бывают алгоритмы, которые правильно работают на некоторых графах и терпят крах на других.
ни одна известная нам программа не в состоянии даже начать расчет уже при сотнях тысяч узлов (по крайней мере, на обычном PC)
М.б. автор знает не все программы? В статье упоминаются некоторые. В таком случае принято указывать ссылки на источник. Если, нпр., источник — солидный научный журнал и ссылка на обзор по задаче коммивояжёра, то снялись бы сомнения в том, что автор данной статьи не упомянул важные решения.
Про «своеобразную форму» изложения достаточно сказали комментаторы выше, поэтому повторять не буду.
В свете сказанного вынужден заключить, что данный текст не может быть назван научной статьей, т.к. нарушает основные принципы научного метода.
valemak
13.05.2019 23:05Жаль, что продолжения не будет. Думаю, те, кто горячо полемизировал с автором, тоже испытывают определённое сожаление.
buriy
15.05.2019 17:55+3Этот автор никогда не признает свою неправоту даже в мелочах, он всегда начинает хамить в ответ, когда ему нечего сказать в свою защиту. Поэтому практически полезной дискуссии не получается. А про все свои достижения и рассуждения, тут и там пестрящие ошибками и недосказанностями, заставляющими представить его в более выгодном свете, он уже по многу раз рассказал. Так что я с удовольствием переворачиваю эту страницу.
mwambanatanga
14.05.2019 05:59+1один человек осмелился сказать, что у него интеллект есть
Не могу заставить себя испытывать сожаление по отношению к автору таких слов.
slavap
14.05.2019 09:38+1Для тех кто пропустил предыдущие «серии»:
«Сортировка» или «Последний раз о задаче коммивояжера»
Заставить работать машину клиента!
Еще раз о программировании FOREX
Алгоритмы решения NP-трудных задач
Всегда в ветках «трэш, угар и противоестественное поведение» :-) Финал очевиден — бан.GCU
14.05.2019 10:42Боже мой — автор страдает этим не первый десяток лет! За это время можно было бы и наглядно оформить описания алгоритмов с картинками вместо словесных, нарисовать красивые графики :)
Но самый главный алгоритм — как пользоваться сетевым этикетом, чтобы не банили и сливали карму автор не осилил. Это печально на самом деле.
rybvv Автор
16.05.2019 21:29-2Меня тут «хирургически» вырезали из «саморегулирующегося сообщества», но я сюда посматривал и даже кое на что отвечал «в стол». Забавно было видеть, как падала оценка последней заметки даже после моего бана, и как продолжали плодиться комменты там же и тогда же. Не оправдывайтесь, господа, не получится! ;)
Накопившиеся ответы, как обычно при таких правилах с задержками комментов, даю оптом. Сначала по теме ветки:
third112
Отсюда понял, что предлагается строго доказанный, а не эвристический алгоритм.
А что там «доказывать», если ПОЛНЫЙ перебор ВСЕХ вариантов?
Все нюансы даже не перечислены.
И что? Это же нюансы! Это же нюансы СКОРОСТНОГО алгоритма, ПЕРВОГО из всей группы! Кого интересует линейная часть сброса беты? ВАЖНЕЙШИЕ — перечислены, и этого УЖЕ достаточно для эффективнейшей его работы. Тут от обилия АЛГОРИТМОВ глаза разбегаются, а им НЮАНСЫ подавай, да ещё ВСЕ, да ещё С ИЛЛЮСТРАЦИЯМИ, панимаш! И это «сообщество РАЗРАБОТЧИКОВ»?
Теоретической оценки сложности нет.
А что тут «оценивать»? На мелких графах (до нескольких сотен узлов), очевидно, рассматриваются ВСЕ рёбра, то есть там сложность квадратичная. Больше квадрата сложность быть не может, поскольку рассмотренные на полную глубину рёбра получают статус «абсолютных» и больше не рассматриваются вообще. Ну, а для остальных графов скоростной заканчивает работу обычно на глубине 128 или даже 64, и никогда ещё не было случая, чтобы глубина была больше 8192. Что же это (при миллионах узлов), если не линейная сложность?
Как это «нет описания алгоритма»? А то что же ещё в заметке? :) А вот «листинг программы» — это отдельная песня. Не дам! И что Вы хотите проверять? Ну вот, скажем, у меня давным-давно валяется на сайте какая-то версия sint.wc.lt/tsp.zip — что-то никто пока её особо не проверял! Вот, подсунул ей прямо сейчас граф d15112 — вот её листинг:
Travelling salesman problem, V 9.02, 04.11.2015
Author: Vladimir Rybinkin
Start: N=15112 L=112310765.00 T=0.0 sec
3375/32 N=15112/15 L=6813306.00 (1553.0 [1024])T=14.0 sec
2/16 N=15112/5 L=4094139.00 (261.0 [16])T=28.0 sec
…
Fast: N=15112 L=1743371.00 T=168.9 sec
Как видите, скоростной сбросил бету с 112310765/1573084*100-100=7039.5% до 1743371/1573084*100-100=10.825% погрешности. Неплохо! А последняя версия на том же графе… ща посмотрю…
Travelling salesman problem, V 10.04, 24.04.18
Author: Vladimir Rybinkin
Start: N=15112 L=112310765.00 T=0.0 sec
1211/1 N=15112/0 L=7158231.00 (1175/512) T=14.1 sec
426/2 N=15112/0 L=4326759.00 (788/1024) T=28.2 sec
…
Fast: N=15112 L=1694289.00 T=345.5 sec
…
Medium: N=15112 L=1659661.00 T=3348.1 sec
Как видим, скоростной здесь отработал заметно дольше, но «солиднее», сбросив бету до 7.705%, а дважды отработавший за ним «средний» (с зачисткой скоростным) уронил её уже до 5.504% (на что потребовался уже час времени). В общем, я считаю, что эта спарка алгоритмов работает практически идеально, и улучшать что-либо в них я просто НЕ ХОЧУ! Точный — другое дело, там в плане оптимизации ещё конь нее валялся!
Если автор не видел — это не значит, что такого не существует.
Да, но автор включил в список тестовых графов ВСЕ, которые вообще ему известны, и дополнил доброй половиной СВОИХ! И те самые 8192 встретились как раз на МОИХ графах — если я правильно помню, на графе r12345678. К тому же, это было давно, и я не уверен, что нынешняя версия скоростного доберётся до этих значений даже на нём. Даже уверен, что не доберётся!
395 задач лишь малая часть возможных задач, бывают алгоритмы, которые правильно работают на некоторых графах и терпят крах на других.
Ха-ха-ха! Прочитайте предыдущий мой ответ или посмотрите на список — найдёте там ХОТЬ ОДИН известный TSP-граф, которого бы не было у меня?
М.б. автор знает не все программы?
М.б. Но Конкорд автор знает, и с его автором даже когда-то переписывался. А Вы — знаете? :)
В таком случае принято указывать ссылки на источник.
Какие «ссылки», Господи?! Какая «научная статья»?! Это я так, для лёгкого чтения, «подразнить гусей». :) Уже после того шабаша, который устроили у меня в «сортире», я окончательно потерял интерес к этой помойке под названием «сообщество разработчиков». Правда, парочку интересных людей всё же нашёл. Разговариваем…
Ну, ловите ещё пару примеров работы скоростного последней версией (запускаю «с нуля»):
Граф rl11849
Fast: N=11849 L=1027321.00 T=93.8 sec
Скоростной за полторы минуты сбросил бету с
86621277 (9281.8%) до 1027321 (11.27%)
Medium: N=11849 L=989437.00 T=1673.8 sec
Средний за полчаса понизил её до 989437 (7.16%)
Что ещё взять… ну, monalisa, допустим, на 100000 узлов:
Погрешность на старте: 991784778/5757191*100-100=17126.9%
Fast: N=100000 L=5978911.00 T=13071.6 sec
Работал почти 4 часа. Почему так долго? Да потому, что получалось хорошо! Доскакал до глубины 512 (в принципе, ему разрешено прерывать расчёт уже при глубине 64) и уронил бету до 5978911 (3.851%)!
Мало? Ну, могу вообще «убить наповал» каким-нибудь графом-миллионником с иерархической кластеризаций! Вот, например, этим: c5555555. Там best-known вообще никто не знает, так что погрешность оценить нельзя. А вот падение бета-границы — можно! Даю фрагменты листинга (первая цифирь — число найденных решений на итерации, через слеш — глубина):
Travelling salesman problem, V 10.04, 24.04.18
Author: Vladimir Rybinkin
Start: N=5555555 L=594668211265.00 T=0.0 sec
136461/1 N=5555555/0 L=583739307335.00 (158579/32) T=14.1 sec
264994/1 N=5555555/0 L=573517605103.00 (375599/64) T=28.1 sec
521090/1 N=5555555/2 L=553550416429.00 (32268/0) T=56.3 sec
1026711/1 N=5555555/6 L=514591353030.00 (6688/0) T=112.5 sec
1890740/1 N=5555555/0 L=450932029775.00 (180258/64) T=211.0 sec
4294105/1 N=5555555/0 L=291723244978.00 (126508/64) T=506.4 sec
8092313/1 N=5555555/0 L=99922586620.00 (178820/64) T=1012.7 sec
1544975/1 N=5555555/0 L=58804697995.00 (8832/2) T=2011.8 sec
2720335/1 N=5555555/0 L=25530051294.00 (14361/512) T=5006.4 sec
3261655/1 N=5555555/4 L=12885871750.00 (1572/0) T=10000.1 sec
4133319/1 N=5555555/0 L=5599650766.00 (78081/16384) T=20025.8 sec
1725605/1 N=5555555/0 L=608997688.00 (1056/4096) T=50012.7 sec
3053/2 N=5555555/26 L=252879469.00 (7656/262144) T=71171.2 sec
А вот здесь почти 20 часов отработал не просто скоростной алгоритм, а скоростной на глубине 1! И сделал он на этой глубине 14 каскадов! Почему? По той самой причине: получалось хорошо! За это время он сбросил бета-границу с 594668211265 до 252935853, то есть в 2351 раз! А на этой глубине он рёбра тура длиной менее средней не смотрит вообще! Мало? Плохо? Нет? А какого же на мою заметку набросились всем скопом? А почему на мой сайт целое паломничество заявилось, особенно на страницу tsptest? Риторический вопрос… :)
А, меня разбанили-таки. :) Ладно, пущай ещё посчитает. В данный момент снова работает глубина 1:
263639/1 N=5555555/6 L=208939653.00 (792/8192) T=80261.6 sec
О, блин, у меня уже один комментарий В ДЕНЬ! Ну, тогда всё вываливаю сюда! :)
Теперь по сортиру:
wataru
Вообще говоря, сортировка кучей не потребует памяти больше чем ровно один массив и будет работать за O(n log n).
Вообще говоря, сортировка воронкой требует памяти 6*n БАЙТ, и работает за O(n log n) В ХУДШЕМ случае.
Какое-то очень странное ограничение — получать элементы по одному, но в конце выдать их все отсортированными в списке.
Ничего странного: сортируется входной поток данных, и первичная сортировка совмещена с процессом загрузки данных в ОЗУ. А чтение из файла и запись в файл намного выгоднее выполнять именно ПОСЛЕДОВАТЕЛЬНО.
GCU
Боже мой — автор страдает этим не первый десяток лет! За это время можно было бы и наглядно оформить описания алгоритмов с картинками вместо словесных, нарисовать красивые графики
А зачем? Я пришёл поговорить с разработчиками! А они и без «весёлых картинок» прекрасно всё понимают. А остальному «сообществу» бесполезно — я ведь давал ссылку на свой сайт с подробной анимашкой с иллюстрацией работы «воронки». Ну и как — помогло? Да, кстати: автор ничем не «страдает». ;)
michael_vostrikov
Вы думаете, в другие алгоритмы сортировки нельзя поставить произвольное количество элементов?
Да ничего я не «думаю»! Я просто констатирую факт: Вы смогли отсортировать лишь сраных 32К строк ВАШЕГО ЖЕ тестового массива. А в слиянии списков «слева направо» и вообще доигрались до квадрата. Я же говорил: НЕ СМЕТЬ называть ВАШЕ дерьмо МОЕЙ воронкой!
На 32 миллиона сравнений меньше, чем у вас с несколькими воронками (6172582694), и на 21 миллиард меньше, чем с одной (28021925721). Дальше что?
Да ничего! Во-первых, timSort «ОСНОВАН на том, что сортируемые массивы данных часто содержат в себе упорядоченные подмассивы». Воронка же прекрасно сортирует ЛЮБЫЕ данные! В том числе, и этот Ваш массив, который Вы готовили специально для неё. Во-вторых, у меня было недостаточно ОЗУ, и сортировка миллиарда строк потребовала слияния СЕМИ промежуточных файлов. А timSort (кстати, про Квик Вы вообще заткнулись?) в таких условиях вообще работать-то будет? В-третьих, как я уже говорил, все эти цифири роли практически не играют — РЕАЛЬНОЕ время работы воронки в несколько списков и в один список отличается весьма незначительно, и все эти «миллиарды» значения не имеют. От слова «совсем». Ну, подрочит она немного мелкими массивами в ОЗУ — какая разница? Основное время всё равно отжирают ФАЙЛОВЫЕ операции!
В статьях тоже нет ничего, что составляет ценность.
Для Вас — несомненно! Так отошли бы в сторонку, что ли…
Насколько было бы меньше флуда, если бы автор привел в статье код своей сортировки?
ЩАЗ! Если господа «разработчики» не в состоянии прорубить даже алгоритм, который я придумал и запрограммировал, потратив на это куда меньше времени, чем на попытки вдолбить его вам, то до кода вам ещё расти и расти! Да пальцы не гнуть при этом, да учителей из себя не корчить.
Зато другого не лишили. Другие авторы могут писать статьи, которые нравятся людям?
Другие — могут, а мне низзя? И кто же определяет, что там «нравится людям»? Вы? Это сообщество разработчиков или театр какой? Вот, открываю «лучшие публикации» — ни в одной нет более сотни комментов! Да и больше полусотни кот наплакал! Окрываю свои — любая просто ломится от комментов! И закладок у каждой дофига, и подписчиков у меня уже 20 штук. Так что же это за «люди» такие? И какие именно авторы «нужны ресурсу»? Тоже Вы определяете? И почему же вы ИМЕННО У МЕНЯ в ветках срёте, господа? Там, «в лучших публикациях» вам сказать нечего? И кто же вы тогда? Прям заинтриговали! :)
И почему вы решили, что статья является таким поводом? Поводом является общение автора в комментариях.
Да неужели? Так почему гадите именно в статьи а не в те самые «комментарии»? Статья-то ЧЕМ провинилась? И какие такие «нормальные статьи на такие темы пишутся по-другому»? Здесь на Хабре БЫЛИ статьи именно на эту тему! Уж не они ли «эталон»? :)
И почему вы думаете, что такие статьи не могут написать другие авторы, которые общаются соблюдая правила ресурса?
В зеркало посмотрите. Ну или в свои 10 статей. :)
Это достаточная характеристика, чтобы люди не захотели общаться.
Ути-пути! Сударь, не Вы ли 22 апреля 2019 в 08:46 написали: «Разговор окончен»? На что я в тот же день в 14:02 написал: «Вот за это спасибо»! А в 15:41: «Сударь, попрощались ведь уже!» А 23 апреля в 18:45 я писал: «Любопытная закономерность: эта ветка набрала почти 4 сотни комментов — в основном тех, где размахивали руками и топали ногами. А сейчас ветка как будто вымерла, и разговор поддерживает тот единственный, с кем мы уже попрощались». А в 23:13: «Ну и как, долго Вы ещё <прощаться> будете?» А 24 апреля в 07:42: «Нет, я заметил, что Вы уже попрощались тыщу лет назад, но никак не уйдёте». А в 15:00: «Сударь, Вы сколько раз собираетесь <разговор действительно оканчивать>? Вы свалите, наконец, отседова или так и будете зудеть точнёхонько по моему описанию, что <никуда она, нафиг, не денется>? Так, может, „дело было не в бобине“? ;)
А незарегистрированные пользователи вообще не в курсе, кого игнорировать, а кого нет.
От Вас справки не получили, что ли? А Вам не приходило в голову, что и незарегистрированные пользователи в состоянии пользоваться СОБСТВЕННЫМИ мозгами по назначению? ;)
Возможно вам пофиг на ресурс, а мне и другим нет.
Это как раз МНЕ не пофиг на ресурс! И потому я уже неоднократно писал администрации: поменяйте вы эти идиотские правила! Они НЕИЗБЕЖНО ведут к превращению ресурса в помойку!
Я хочу читать информацию про программирование, а не ругательные слова.
Так ЧИТАЙТЕ информацию про программирование! В первой же моей заметке (которую вчера модератор убрал, наконец, из Песочницы) не было НИ ОДНОГО ругательного слова, и было ЧИСТЕЙШЕЕ программирование, пока банда идиотов не стала плести клиническую ахинею про „разновидность сортировки вставками“, да не стала представлять свою клиническую „реализацию“ моего алгоритма! ЧИТАЙТЕ информацию про программирование, а не ПИШИТЕ про него — какой Вы, в баню, „программист“? И будет тогда всем полное ЩАСТЬЕ! :)
Я не ставлю минусы тем, с кем спорю.
Лапуль, чтобы СПОРИТЬ со мной, надо хоть какую-то квалификацию в программировании иметь! Вам же я русским языком писал 22 апреля 2019 в 23:42: Ну это уже что-то! Ладно, Вам жирный плюс за мужской ответ. Но как программист — уж извините — Вы меня не интересуете. От слова <совсем>.
CoolCmd
Что характерно, на Хоботе его заблокировали за хамство.
На Хоботе, милок, я был одним из четырёх кандидатов в модераторы рубрики „программирование“! Правда, я сразу отказался (да меня бы никто и не взял), но тем не менее. Но это было в те времена, когда ресурс ещё не угробило визжащее быдло, и там ещё водились программисты. И я до сих пор горжусь, что был, по-видимому, единственным, кому была посвящена „персональная“ ветка, в которую приходило целое созвездие программистов ВЫСОЧАЙШЕЙ квалификации! На Хабре-то есть хоть один такого уровня? Пальцем покажите! Ну и, раз уж „Для тех кто пропустил предыдущие серии“, включите уж и эту:
В. Рыбинкину — человеку и ассемблеру...
Форум ixbt был уничтожен в районе 2003-2005 годов, умирал долго и мучительно (потому как правила там не чета здешним). Хабр, как я теперь понимаю, был убит ещё до рождения: при таких правилах здесь может быть ТОЛЬКО помойка! Без вариантов!
buriy
Этот автор никогда не признает свою неправоту даже в мелочах, он всегда начинает хамить в ответ, когда ему нечего сказать в свою защиту.
Ещё один „вечно прощающийся“? :) Я же говорил, лапуль, что даже самые мои непримиримые оппоненты много раз публично подтверждали, что я вменяем. А ещё я много раз говорил открытым текстом, что я отвечаю ЗА ВСЕ свои слова, и что я могу разобрать ЛЮБОЙ вопрос с ЛЮБОЙ степенью сложности.
Поэтому практически полезной дискуссии не получается.
Ну так отойдите в сторонку, сударь! Какая может быть „полезная дискуссия“ с тем, кто в голубом глазу утверждал, что „БД представить как граф — вообще не проблема, адаптер пишется в 10 строчек (если есть интроспекция в каком-либо виде)“ или что „brute force и полный перебор — это полные синонимы“? ;)
А про все свои достижения и рассуждения, тут и там пестрящие ошибками и недосказанностями, заставляющими представить его в более выгодном свете, он уже по многу раз рассказал.
Вы ещё и лживы, к тому же.
Так что я с удовольствием переворачиваю эту страницу.
Ха-ха-ха! Запомните этот твит!(с)
Sirion
Если автору важно донести до широких масс свои мысли, ему следует освоить правила поведения в обществе.
Это вы, что ли, „общество“? Автору 60 лет, из которых 27 лет он провёл в Инете, и он ПРЕКРАСНО знает правила поведения в обществе. Я же лично Вам писал: Ну, ПРОДЕМОНСТРИРУЙТЕ свою <квалификацию>! Молчите? То-то же: До сих пор НИКТО из вас, лихорадочно гадивших мне в карму, не произнёс НИ СЛОВА по существу моей заметки! И вы — »общество"? О таких, как вы, я писал: Да, я хочу быть услышанным и понятым. Но отнюдь не «кем бы то ни было». Люди мне важны, быдло — нет: любая реакция быдла не может меня ни «окрылить» ни, наоборот, «заставить опустить руки». Я согласен с фразой Ходорковского: «Есть люди, чьё мнение мне радикально безразлично».
Разумеется, есть определённая ступень гениальности, после которой её обладателю простят всё, даже если он будет плевать собеседнику в рожу.
Даже «разумеется»? Быдло-то простит — куда оно, нафиг, денется? А вот люди — никогда! Никому! Ни гению, ни супергению. Вот Вы и сами подтвердили, какое вы «общество»! ;) Значит, мне просто статуса не хватает? А если вдруг чудо — если институт Клэя признает моё решение ЗК решением, я могу «плевать Вам в рожу», и Вы будете покорно утираться? Такие у Вас «правила поведения в обществе»? Помните классику?
Душу — Господу,
Сердце — Женщине,
Долг — Отечеству,
Честь — НИКОМУ!
Впрочем, кому я это говорю?..
Повторюсь, я не вижу здесь содержания, из-за которого стоило бы прощать форму.
Информация ПОЛНОСТЬЮ определяется ПРИЁМНИКОМ! И если Вы «не видите здесь содержания», то это ВАШИ проблемы! Я услышал: «позволять каждому балаболу сыпать широковещательными оскорблениями» Вы не настроены. А титулованным гениям Вы «простите всё, даже если они „будут плевать собеседнику в рожу“. А если судить по Вашей карме и рейтингу, то именно Вы, и такие как Вы, и превратили этот ресурс в помойку.
О, блин! И третью часть опубликовать кармы не хватает! Опять в Песочницу, что ли, писать? :)michael_vostrikov
16.05.2019 23:47Спрячу под спойлер, пожалуй, чтобы никому не мешало.
Скрытый текстВы смогли отсортировать лишь сраных 32К строк ВАШЕГО ЖЕ тестового массива.
Вы глаза-то разуйте. Ваш миллиард тоже нормально сортирует. Повторяю, для того, что я хотел показать было достаточно 32768. Разговора кто больше отсортирует там не было.
Во-первых, timSort «ОСНОВАН на том, что сортируемые массивы данных часто содержат в себе упорядоченные подмассивы». Воронка же прекрасно сортирует ЛЮБЫЕ данные!
И timSort прекрасно сортирует любые данные. А отсортированные быстрее, чем другие алгоритмы. Фраза "ОСНОВАН на том", которую вы почему-то запихали в цитату, это ваши выдумки, такой цитаты нет нигде в интернете. Нет, фраза "Основная идея алгоритма в том, что в реальном мире..." ни разу не означает, что неотсортированные данные он сортирует плохо. А то, что "сортируемые массивы данных часто содержат в себе упорядоченные подмассивы" написано и в вашей статье.
А timSort в таких условиях вообще работать-то будет?
Это не вы ли там писали, что дескать в современных компьютерах ресурсов дофига? Что, уже отказываетесь от своих слов, когда это против вас сработало? Сейчас даже в ноутбуки по 16 Гб оперативной памяти ставят. А в серверах, где в современном мире и происходит основная обработка данных, вообще десятки и сотни гигабайт. И я вам уже показывал код, как любую сортировку можно использовать с ограничением O(1) оперативной памяти.
кстати, про Квик Вы вообще заткнулись?
Если вас это так беспокоит, что вы продолжаете говорить об этом в другой статье, то я поясню. Я взял первый попавшийся алгоритм, чтобы было на чем сравнивать. Конкретные цифры мы в конце концов от вас узнали, они лучше QuickSort, но хуже MergeSort и TimSort. Про QuickSort говорить нет смысла, есть более быстрые алгоритмы. И ваш к ним не относится.
В том числе, и этот Ваш массив, который Вы готовили специально для неё.
Я готовил для одной воронки, потому что вы настаивали, что надо основываться на вашем описании в статье. Что вы теперь увиливаете? С одной воронкой получаются те цифры, которые указал я. Вы сами потом цифры с одной воронкой показали, они точно такие же. Если вы меняете число воронок, то и я другой пример приведу. Такая же последовательность, только не из 4 цифр, а из 40, то есть [11, ..., 50]. Ваш алгоритм на нем даже QuickSort проигрывает, хоть с одной воронкой, хоть с 64. Хотя по вашим словам возрастающие последовательности он должен хорошо сортировать.
РЕАЛЬНОЕ время работы воронки в несколько списков и в один список отличается весьма незначительно, и все эти «миллиарды» значения не имеют.
Это не вы ли там писали, что дескать строки в 3 килобайта при сравнениях подтормаживают? Что, уже отказываетесь от своих слов? Сколько там займет 21 миллиард сравнений таких строк? А ведь для сравнения их еще сначала надо прочитать в оперативную память из временных файлов. А это 21 миллиард обращений к диску.
Так отошли бы в сторонку, что ли…
Вы продолжаете меня упоминать в разных комментах, жалуетесь всем, что я дескать мало строк отсортировал, поэтому я ответил. А то, что вы процитировали, я писал вообще не вам.
Другие — могут, а мне низзя?
Другие могут писать то, что нравится людям. И вы можете писать то, что нравится людям. А вы вместо этого пишете то, что не нравится людям. Конкретно ругань и оскорбления. Именно поэтому вас забанили.
И кто же определяет, что там «нравится людям»?
Люди и определяют.
Окрываю свои — любая просто ломится от комментов!
Да-да, половина из них это и есть тот флуд, про который я сказал. Они бесполезны. Другая половина это ваша ругань, за которую вас и забанили.
потратив на это куда меньше времени, чем на попытки вдолбить его вам
Вы походу не понимаете, поэтому я про это отдельно скажу. Не надо никому ничего вдалбливать, надо показать конкретный работающий код. Он работает независимо от того, понял его кто-то или нет. Кому надо, сам скопирует, запустит, и будет разбираться, кому не надо, пройдет мимо. Времени это требует еще меньше, просто текст скопировать и вставить. Один раз. И всё. Но вы вместо этого решили зачем-то его вдалбливать.
И какие такие «нормальные статьи на такие темы пишутся по-другому»?
Описание таких статей написано после процитированного вами предложения "В статьях тоже нет ничего, что составляет ценность". Но вы как обычно только фразы из контекста выдергиваете.
Сударь, не Вы ли 22 апреля 2019 в 08:46 написали: «Разговор окончен»?
Если вас это так беспокоит, что вы продолжаете говорить об этом в другой статье, то я поясню. В первый раз я прощаться не собирался, я хотел вас спровоцировать, чтобы вы рассказали детали алгоритма. Потому что на обычные просьбы вы не реагировали. Во второй раз я сказал "разговор действительно окончен", и потом лично вам я больше ничего не писал. Я написал в той статье еще 2 комментария, в одном русским языком написано "Отвечу сам себе", потому что это уточнение моего собственного комментария, потому что ваша программа работала в DOSBox почти сутки, и я написал результаты когда она закончила работу, в другом русским языком написано "Я пишу это не вам, а другим читателям". На всякий случай повторю, потому что вы с первого раза не понимаете — с вами я в той статье больше не разговаривал. Потом я обнаружил, что вы продолжаете меня упоминать в разговорах с другими пользователями, и написал пояснение. Прекратите писать про меня, зачем вам сдались мои сообщения, пишите по теме статьи.
Вы свалите, наконец, отседова
Хренасе заявление. Хабр это не ваша собственность. Может лучше вы свалите с Хабра?
Вам же я русским языком писал 22 апреля 2019 в 23:42: как программист — уж извините — Вы меня не интересуете. От слова <совсем>.
И что с того, что вы писали? Мне ваше мнение по барабану. Я вас тоже считаю некомпетентным в программировании.
GarryC
Поскольку я, похоже, именно тот, кто осмелился заявить о наличии у меня интеллекта, позволю дать Вам совет — оставьте тон «Я Д'Артанян, а Вы все ....» и с кармой у Вас станет намного лучше.
Ну а по теме — боюсь, что на любой алгоритм, кроме переборного, удастся сконструировать пример, на котором оптимальный результат данным алгоритмом найден не будет. Но это не моя тема, так что могу и ошибаться, это из общих соображений.
rybvv Автор
Сударь, Вас я НЕ уважаю, и «советы» Ваши (тем более, на Ваши же дурацкие ДОМЫСЛЫ про меня) оставьте лучше при себе. ПО ТЕМЕ можете что-то сообщить? Нет? Только в карму гадить? Вы разве не заметили, что у меня именно ПЕРЕБОРНЫЙ алгоритм? Даже ПОЛНОпереборный? Или вообще заметку не читали?
P.S. Да, именно Вы осмелились заявить, что у Вас интеллект есть. Но на следующий же мой вопрос: «Ах, так Вы ЗНАЕТЕ, что это такое?» Вы трусливо промолчали. ЧТД! ;)
GarryC
Ну что же, я не строил никаких домыслов, более того, я совершенно точно уверен, что Ваша фамилия не Д'Артаньян, так что мой комментарий вовсе не был предназначен для вскрытия Вашего инкогнито.
Тем не менее, мой совет в данный момент имеет 2 плюса, Ваша реакция имеет два минуса (причем ни один из них не принадлежит мне), можете продолжать в том же духе, «мыши плакали, кололись, но продолжали жрать кактус».
А по теме (обычно я читаю заметки, к которым пишу комментарий, и в Вашем случае не отступил от своего правила, хотя соблазн был велик) — Вы упорно продолжаете путать метод полного перебора и метод исчерпывания, для чего применяете «метод ветвей и границ» к задачам, для которых его применимость не доказана.
P.S. Пытаться дать определение интеллекта собеседнику, его лишенному (согласно его же заявлениям) контр-продуктивно.
Sirion
Я вот сейчас мысленно перебираю запомнившихся мне хабраавторов и не могу припомнить никого, кому при всех прочих его достоинствах читатели простили бы апломб, подобный вашему. Сам стиль изложения может убить сколь угодно интересное содержание. А содержания в данном посте особо и нет. Громкие слова и всё. Дайте код, дайте бенчмарки. Иначе фричество это.