Решение задачи коммивояжера с помощью метода ветвей и границ

Здравствуй, Хабр! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию, предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:



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

Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.

Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.

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

Алгоритм состоит из двух этапов:


Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)
Второй (основной) этап

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

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

2. Теперь наше множество S разбиваем на множества — содержащие ребро с максимальным штрафом(Sw) и не содержащие это ребро(Sw/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества Sw/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества Sw примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для Sw равна сумме оценки затрат для S и r(h,k), где r(h,k) — сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.

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

Небольшая оптимизация — подключаем эвристику

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей — Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Теперь, собственно, об ошибках в той публикации


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

Доказательство


Вернемся к картинке в начале поста:


А вот решение с исправленным алгоритмом:



Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать

График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:

График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.

Попробовать с подробным решением можно тут.
данные измерений были получены по 100 случайным матрицам. не слишком хорошее число, но общее представление обеспечивает.
Исходники на GitHub (обновлены).
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

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

    0
    Я заметил этот факт некоторое время назад :)
    Вот пост, рассказывающий, как я обошел эту проблему
    habrahabr.ru/post/229597/
      +3
      upd. а не пробовали на большом графе? не 15х15. Разделение на 2n на каждом шаге может привести к очень большому числу одновременно просматриваемых ветвей
      плюс на большом графе вероятность попадания в «плохую ситуацию», описанную Вами в контр-примере в начале поста, уменьшается.

      и я, честно, не понимаю формулировки «неправильный ответ». В любом случае это алгоритм приближенного решения, а не точного. Понятно, что на небольших задачах возможно его улучшение. Вопрос в сходимости приближенного алгоритма к точному ответу на больших задач, где точное решение за адекватное время невозможно.
        –2
        Дело в том, что задача коммивояжера заключается именно в поиске самого выгодного маршрута. поэтому необходимо сохранять предыдущие шаги (или матрицу затрат), и при необходимости, «изучать» все потенциальные решения на предыдущих шагах. конечно это затратно в плане памяти, и в случае большой матрицы дерево может очень сильно разрастись… Но зато получается правильный ответ к задаче: самый выгодный маршрут
          +1
          Ну при таком подходе лучший вариант — честный перебор. Честный перебор — экспоненциальное время. Потому задача NP-тяжелая.
          Экспоненциальное время на достаточно больших задачах настолько большое, что не вычислимо на современных мощностях за адекватное время(хотя бы десяток лет)
          Отсюда приходит идея как минимум сокращения вариантов перебора — ввод различных эвристик и т.д.
          Это автоматически перечеркивает гарантию нахождения точного решения, ибо не все варианты перебора просмотрены.

          Точное решение находится либо потому что повезло, либо размер задачи невелик.
            +1
            и вопрос тут далеко не в памяти. первостепенное значение — время.
              –2
              по каким показателям вы сравнивали полный перебор и метод ветвей и границ?
              по времени — очень сильно проигрывает, так как задача в большинстве случаях может быть решена за линейное от размерности матрицы, или с небольшими лишними ответвлениями,
              по памяти — либо немного выигрывает метод ветвей и границ, так как для листьев надо хранить только историю взятых или не взятых ребер, либо проигрывает если хранить все матрицы (чтобы сэкономить время)
              upd: если вы считаете что самое важное — время, то лучше метод ветвей и границ, чем полный перебор
                +3
                Задача коммивояжера до данного момента не имеет решения, которое бы хотя бы за полиномиальное, не то что линейное, время находили бы решение, гарантированно отстоящее не более чем на некое эпсилон от оптимального.

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

                А серьезно — просто попробуйте запуститься на графе всяко побольше, чем 15х15.
                  –1
                  1) оценка полиномиальное/линейное/экспоненциальное и т.д. «ставится» в случае самых наихудших условий, я упомянул что такое «линейное время» возможно в конкретных случаях, когда решение находится без возврата назад (т.е. не самых худших). и это ярко прослеживается на графике ( к сведению генерировались числа от 0 до 99)
                  2) исследования с большой матрицей проводил, именно поэтому там стоит галочка на то чтобы выводить дерево или нет. так как при очень больших размерах браузер попросту тормозил.
                    +1
                    А как вы узнаете, что нашли действительно самое оптимальное решение за «линейное время»?
                      0
                      для отдельного случая взятого с потолка — можем по построенному дереву пройтись еще раз на наличие лишних ответвлений и сделать соответствующий вывод… либо мы можем сделать, то что сделал я: берем несколько случайных матриц, ищем для них решение нашей задачи, измеряем потраченное время. на основе этой статистики мы можем найти вероятность того, что случайное дерево окажется одним из тех, для которого решения будет занимать «линейное или близкое к этому время». тут еще надо не забывать что диапазон допустимых значений в матрице затрат, тоже будет влиять на эту вероятность.
                      +1
                      Уважаемый webmasterx, а разве оценка сложности qsort o(n*log(n)) — это худший случай?
                      Худшее время qsort'a — квадрат…
                        0
                        и просто, чтобы Вы понимали масштабы. Алгоритм, приведенный мной в посте, на который Вы ссылались, реализованный на c++11, с многопоточностью на 64 ядра для просчета ветвей, сохраненных из предыдущих итераций, на графе 500х500 работал 9.5 часов. И это лишь при раздвоении на каждой итерации и с ограничением на число сохраненных ветвей.
                          0
                          зачем вы говорите о масштабах? речь идет именно о решении задачи коммивояжера, а не о получении равного (и правильного) или близкого (но неправильного) к равному правильного ответа к задачи Коммивояжера. Если речь бы шла именно о минимизации затрат времени и отсутствовала необходимость в 100% правильности ответа, то вы можете и обойтись делением на два подмножества. но это уже не было бы решением задачи коммивояжёра (во всех случаях, в конкретных ответы могли бы совпасть)
                            0
                            Единственное ныне существующее точное решение коммивояжера — полный перебор.
                            Увы, но это так.
                            Полный перебор — это пара десятков строчек кода, никому не интересных, потому что алгоритм очевиден.

                            Но только Ваш алгоритм не дает гарантированно верное решение.
                          0
                          Да, но это же не значит, что в таком случае следует пользоваться пузырьковой сортировкой? В конце концов, она дает тот же результат при том же наихудшем времени O(n^2).
                            +1
                            Таки да, однако алгоритм, приведенный автором, далеко не линеен, как он утверждает, а экспоненциален.
                            И несмотря на его утверждения, точного решения он тоже не гарантирует.

                            Скорее, вопрос в том, имеет ли смысл рассматривать большее число ветвей на каждом шаге. Эта идея сильно увеличивает время вычислений, однако на больших графах вероятность того, что такой подход что-то сильно улучшит, невысока, ибо проблема, которую решает данное изменение алгоритма, маловероятна и эта вероятность падает с увеличением размера графа. Возможно, стоит рассматривать большее число ветвей не глобально и всегда, а лишь на неких локальных итерациях. Однако, непонятно, как понимать, на каких.
                              0
                              Я гарантирую 100% правильное решение, иначе бы не стал писать это как решение задачи коммивояжера.
                              повторяюсь: я не утверждаю что алгоритм линеен, я утверждаю что он существенно быстрее полного перебора. возьмем к примеру мой график: даже отбросив последние значения (посчитав их ошибочными), и взяв за самое большее затраченное время 0.075с как время полного перебора, то самое наименьшее пусть будет 0.06с, что в несколько раз меньше максимального. а вероятность того, что матрица решится за время приблизительно в половину от максимального, достаточно высока, чтобы применять этот вместо полного перебора.
                              Насчет дальнейших возможных оптимизаций, которые вы предложили: они не будут гарантировать 100% правильное решения, но могут сэкономить время, но это совершенно другой разговор
                                0
                                Уважаемый webmasterx, графики пузырьковой сортировки и qsorta на массивах длиной по 10-15 элементов тоже будут одинаковы. На массивах по паре миллионов элементов — нет.
                                и Ваш алгоритм не альтернатива полному перебору — он не гарантирует оптимальное решение
                                  0
                                  приведите, пожалуйста, строгое математическое доказательство корректности в таком случае.
                                    0
                                    метода ветвей и границ? Вы можете с легкостью найти его в оригинале: A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems, стр. 497-520.
                                      0
                                      а что есть n в количестве разделяемых ветвей (2n)?
                                        0
                                        добавил: n — кол-во элементов с максимальным штрафом
                                        0
                                        Небольшая оптимизация — подключаем эвристику

                                        Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (hi,ki) или нет, и вешаем двух и более детей — Sw(hi,ki) и Sw/o(hi,ki). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

                                        как минимум эта эвристика может увести Вас от оптимального решения.
                                          0
                                          что вы подразумеваете под оптимальным?
                                          лучше идти в глубину, стремясь к решению, чем в ширину, рассматривая менее вероятные ветви. (так как со спуском вниз уменьшаются значения в матрице затрат, а значит может меньше прибавится штрафа к минимальной границе, чем по сравнению с более высокими значениями)
                                            0
                                            только вот в менее вероятных ветвях может быть и есть самое выгодное решение. (вероятность этого мала, но она не нулевая)
                                              0
                                              пожалуй, в своем следующем посте я проведу приближенные исследования этой самой вероятности
                                0
                                Худшее время qsort'a — квадрат…
                                Немного оффтопик: нетрудно модифицировать qsort таким образом, чтобы и в худшем случае он работал за O(n log n). Идея проста: вы ограничиваете глубину дерева сортировки некой величиной порядка log n и при достижении указанной глубины переключаетесь на другой алгоритм, который имеет время работы в худшем случае O(n log n) (на его роль обычно выбирают heap sort, т.к. он не требует дополнительной памяти). Подобный прием называется Introsort и используется, например, в libstdc++ (с ограничителем глубины равным 2*log2 n).
                                  0
                                  Можно и без heapsort. Достаточно на каждом шагу искать медиану массива за линейное время (такие алгоритмы существуют). Правда, скорость работы уменьшится примерно в 10 раз, зато будет гарантированное O(n log n).
                                    0
                                    Можно, но это непрактичный способ в отличии от вышеприведенного. Фишка в том, что если выбрать ограничитель глубины достаточно большим, то в большинстве случаев у вас до heapsort'а дело вообще не дойдет, сортировка закончится раньше. То есть, грубо говоря, в среднем случае ваша сортировка — тот же самый quicksort + очень небольшой оверхед на проверку глубины, а переключение идет лишь тогда, когда у quicksort'а дела пошли неважно.

                                    К слову, алгоритм нахождения i-ой порядковой статистики (в том числе и медианы) можно затюнинговать похожим образом, используя вначале quickselect (который в среднем очень быстр, но в худшем случае работает за O(n2)) и переключаясь на алгоритм, ищущий за гарантированное линейное время, если quickselect работает слишком долго.
                    +1
                    Я попробовал ваш алгоритм:
                    5x5
                    Время:1.1067810058594.
                    Что-то как-то лучше уж полный перебор.
                      0
                      данная матрица затрат — как раз таки яркий и лаконичный пример когда происходит полный перебор.
                      но если взять матрицу из примера 3 — то она решается за гораздо меньшее время. потому что в отличии от полного перебора были отсеяны наименее вероятные множества решений
                        +2
                        Я что-то путаю, или полный перебор графа из 5 вершин это 24 варианта? Как это может считаться дольше секунды?
                          0
                          вы не правы. 5! = 120
                          а вот насчет расчетов дольше секунды: боюсь тут вы правы, где-то я допустил ошибку, но я её не вижу. даже если выводить только те листья, по которым прошелся алгоритм. архив с уменьшим деревом
                            +1
                            Всё-таки маршруты зациклены, поэтому 24. Хотя, как вы заметили, сути это не меняет.
                      0
                      Обновил пост.
                      Исправлена ошибка в результате которой задача решалась с более чем (n-1)! вариантов.
                      Также добавил скриншот для сравнения с полным перебором.
                        0
                        Суть поста от этого не поменялась.
                        Что с корректностью?
                        Что с вероятностью пропустить «точное решение» в «менее вероятных ветвях»?
                          0
                          корректность осталась.
                          вероятность 0.
                          была допущена логическая ошибка при изменении неправильного алогритма, которая не бросалась сразу в глаза не смотря на свою очевидность
                            0
                            Вопрос был, где обещанное Вами доказательство того, что алгоритм в 100% случаях дает правильное и точное решение задачи коммивояжера?
                            И где доказательство того, что вероятность озвученного выше события = 0?
                              0
                              с этим вопросом не ко мне, а к создателям алгоритма. и найти его в интернете на русском языке тоже можно. Внимательный человек конечно задастся вопросом: если так, то почему я и demist допустили ошибки? Отвечу, алгоритм не был написан исключительно для решения задачи комивояжера, и поэтому его описание достаточно расплывчатое для меня, чтобы прочитать даже переведенный вариант.
                              Могу вам «на пальцах» объяснить почему решение правильное и точное. но не гарантирую что смогу убедить вас.
                                0
                                Если Вы прочитаете комментарии выше, то заметите, что я постоянно говорю об одном — алгоритм не гарантирует точное решение. Он гарантирует в некоторой степени неплохое решение, не более того.

                                Единственный алгоритм, дающий точное решение — полный перебор.

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

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

                                    Если Вы все же откидываете некие варианты, то и точное решение Вы также можете и «откинуть»
                                      0
                                      1)подскажите пожалуйста страницу и абзац где говорится что МВиГ не всегда решается правильно?
                                      2) МВиГ — это и есть полный перебор всех возможных вариантов с отсеиванием явно не оптимальных решений. Для задачи Коммивояжера не существует алгоритмов сложность которых отличается от полного перебора. ( по крайней мере я не встречал не слышал о таком алгоритме)
                                      3) конечно можно. но МВиГ отбрасывает очевидно неоптимальные решения. В этом и заключается вся прелесть алгоритма
                                        0
                                        Я бы посоветовал Вам внимательно прочесть все, что там написано. Внимательно и с пониманием. Тогда Вы получите ответы на все Ваши вопросы.

                                        Вы сами писали выше, что описание МВиГ выглядело для Вас «расплывчатым».
                                        По ссылке неплохое объяснение, как это работает.

                                        Еще, для ознакомления с темой, рекомендую вот это.

                                        Это хотя бы для начала.
                                          0
                                          Я бы вам рекомендовал почитать более внимательно тот текст. тогда вы поймете что вы не правы.

                                          Расплывчатым для меня является само описание которое применимо не только к задаче коммивояжера.

                                          Предложенная вами ссылка опять не доказывает, ваше утверждение о том, что решение не всегда оптимальное.
                                            0
                                            Запустите ваш алгоритм на большом графе.
                                            Потом чуть-чуть измените параметры эвристики, которая отвечает за движение в глубину.
                                            Ой! А решение-то поменялось… У задачи же не могут быть два точных решения, но почему-то разные по стоимости…

                                            Не верите теории — проверяйте на практике.

                                            Граф 15х15 — не аргумент, слишком мало вариантов. Берите минимум 500х500

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

                                                Ладно, черт с ней, с теорией. Давайте что попроще, практика.

                                                Просто проведите тесты на большом графе. Поиграйте с эвристиками, Вы все увидите сами.

                                                Ну никто в мире, никто, не проверяет алгоритмы для NP-трудных задач на таких маленьких размерностях. У Вас лишь несколько сотен вариантов перебора, это несерьезно.
                                                  0
                                                  а что для вас сложного с теорией? с каким эвристиками вы предлагаете поиграть? и проверяют прежде всего теоретический материал, а потом уже на компьютерах.
                                                  Итак, судя по всему вы признаете что у вас нет доказтельств того, что МВиГ для поиска гамильтоного цикла решает задачу?
                                                    0
                                                    Постойте, постойте. Вроде бы Вы убеждаете меня, что все работает, а я, наоборот, утверждаю, что МВиГ не всегда верно работает. Давайте хоть с постановкой задачи определимся…
                                                      0
                                                      задача озвучена в наших постах — поиск гамильтоного цикла. и способ решения также указан — с помощью метода ветвей и границ
                                                        0
                                                        Отлично. Вот я говорю Вам, что МВиГ, как и любой эвристический алгоритм, не гарантирует нахождение точного решения.

                                                        Дабы не вникать в потоки теории ввиду явной разницы в математической подготовке, я предлагаю Вам взять Ваш собственный алгоритм и запустить его на большом графе(500 вершин как минимум), а потом вспомнить, что Вы сами ввели в алгоритм эвристику.
                                                        Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух и более детей — Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.


                                                        И немного поменять ее. И Вы сами увидите, что результат работы программы поменялся. Т.е. входные данные одни и те же, а результаты разные! Значит, что-то не так с алгоритмом.

                                                        Я же не говорю возьмите то, а скачайте то. Просто возьмите Ваш собственный алгоритм и потестируйте его.
                                                          0
                                                          upd. кстати абзац про эвристику в Вашем посте был дословно скопирован из моего поста, было бы неплохо это указывать, но это так, ремарка.
                                                            0
                                                            не знаю как для вас, но для меня назвать это «эвристикой» было слишком громко. от того, что мы стараемся углубиться или расшириться может увеличиться только время и может измениться маршрут. но не его конечная стоимость.
                                                            Для таких тестов как вы хотите у меня попросту не хватит оперативной памяти. Но и смысла я в них не вижу. с ними можно будет только найти баг в коде

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

                                                              Про оперативку.
                                                              Дело в используемом языкe. На С++ я обсчитывал графы по 1000 вершин на ноутбуке с 8Гб оперативной памяти. 500 вершин — за глаза хватало 4Гб.
                                                              Попробуйте язык без сборщика мусора, если это в Ваших силах, конечно, и оперативки будет хватать.
                                                                0
                                                                постойте, я не понял, что портит алгоритм? Эвристика? в нашем случае или вообще?

                                                                И ответьте на вопрос: признаете ли вы, что метод ветвей и границ для поиска гамильтонова цикла всегда дает точный ответ?

                                                                Про оперативку. По правильному алгоритму у вас может не хватить 8Гб для 1000 вершин.
                                                                  0
                                                                  Эвристические алгоритмы в общем случае уже не всегда гарантируют точный ответ.

                                                                  Грамотно написанный МВиГ без эвристик дает верный ответ, только тогда он не сильно отличается от полного перебора.

                                                                  МВиГ c эвристиками не дает гарантированного верного ответа.

                                                                  Поверьте, на С++ в 8Гб можно засунуть гораздо больше, чем в php ;)
                                                                    0
                                                                    Не будем говорить про общие случаи.

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

                                                                    С вот этой эвристикой, которая у вас написана, МВиГ тоже дает гарантированный верный ответ. Это очевидно. Вам объяснить?

                                                                    Я не спорю по поводу мощи С++.

                                                                      0
                                                                      Да, дело в этой эвристике.

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

                                                                      На маленьких графах такого не случается. А на больших — редко, но метко.
                                                                      Пути решения различны, я в одном из своих постов предлагал хранить неплохие ветки в памяти подольше, чтобы иметь возможность к ним «откатываться»
                                                                        0
                                                                        Извините, но какая задача озвучена в наших постах? Поиск Гамильтонова цикла. А это значит что найденный путь должен быть минимальным. Не важно как он ищется и как долго. Любой другой ответ — это не решение задачи.

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

                                                                        Напоминаю, эвристика о том, чтобы при равных минимальных границах выбирать то ребро, размерность матрицы которого меньше.

                                                                          0
                                                                          Я лишь предлагал алгоритм приближенного решения задачи. Потому что при больших размерностях получить точный ответ нельзя — надо ждать столетия вычислений.

                                                                          Ваш алгоритм, к сожалению, тоже экспоненциален, так что на больших данных ждать его придется очень долго.

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

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

                                                                              Говорю же, не лезьте в теорию, у нас разные уровни подготовки.
                                                                              0
                                                                              Так что, как это ни грустно признавать, Ваш алгоритм не строго корректен и экспоненциален.

                                                                              Так что Вы сделали то, что никому не нужно.

                                                                              Людям нужна либо строгая корректность(минимальный процент людей, в основном, из науки + у них обычно не слишком большая размерность, кластера за пару недель справляются) либо время работы(95% заинтересованных лиц — им нужен достаточно точный ответ, однако размерности данных зашкаливают).

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

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

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

                                                                                Это было нужно мне.

                                                                                Речь не шла о реальном применении, и что делать в связи с тормознутостью компьютеров, для больших матриц.
                                                                                  0
                                                                                  Понятно. Да, это отличная задача для мотивации разобраться с алгоритмами работы с матрицами, памятью и т.д. Я сам когда-то с этого же приблизительно начинал. Тогда вопрос снят.

                                                                                  Поймите, я Вас не критикую, я пытаюсь указать на моменты, которые Вы не заметили.

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

                                                                                  Так что нельзя говорить, что он 100% корректен — бывают случаи, когда может «не получиться»

                                                                                    0
                                                                                    Ответов может быть несколько, да. И такое бывает.

                                                                                    Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
                                                                                      0
                                                                                      А какие моменты я не заметил? (с момента обновления поста).

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

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

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

                                                                                      Я же исправил ваш алгоритм! Он выбирает всегда с самой наименьшой стоимостью ветку ( вот в чем у вас была ошибка). и всегда самую глубокую
                                                                                        0
                                                                                        Мой алгоритм не нуждался в исправлениях, у него другие цели.

                                                                                        Он работает на огромных данных за адекватное время и не упирается в оперативку.

                                                                                        Ваш же алгоритм будет работать столько, что до Пекина пешком можно успеть… Раз 200
                                                                                          0
                                                                                          Поймите же, наконец, что алгоритм с экспоненцальной сложностью не интересен — уже есть такой же по сложности — полный перебор.

                                                                                          Точного решения NP-трудных задач за хотя бы полиномиальное время на текущий момент не существует в природе.

                                                                                          А за нахождение такого алгоритма даже существует специальная премия с нехилым денежным бонусом.

                                                                                          Ваши графики ничего не говорят о сложности — слишком маленькие данные. Это как знаете, в окрестности 0 и x, x^2, x^4 и т.д. тоже почти одно и то же, на первый взгляд.
                                                                                          А x на отрезке [0,1] так вообще самый «большой». А вот потом все ровно наоборот.
                                                                                            0
                                                                                            Вообще-то нуждался. Прочитайте свою постановку задачи. И скажите, удовлетворяет ли ваш алгоритм этой задаче
                                                                                              0
                                                                                              задача стояла конкретно для одного графа.
                                                                                              понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
                                                                                              в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.


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

                                                                                                То есть, если бы никто вам в комментарии не написал, то так бы никто не узнал что ни один из алгоритмов не дает правильного ответа?
                                                                                                  0
                                                                                                  Поверьте, компании готовы платить огромные деньги за то, чтобы получить хотя бы приближенные решения. Потому что на тех объемах данных, что у них есть, точное решение посчитать невозможно. В посте приведены алгоритмы, различные существующие. Ремарка про один граф относится к подбору констант, это всегда определяется данными и только ими. Нельзя их угадать заранее для любого графа.
                                                                                                  0
                                                                                                  Так что, подытожу.

                                                                                                  Рекомендую Вам прочитать Кормена(главы про основы вычислительной сложности), книжку-методичку от MIT по алгоритмам приближенного решения NP-тяжелых задач(к сожалению, она так и не вышла, валяется в сети в виде презентации), и пересесть на более подходящий для таких целей язык(раз уж он Вас ограничивает), потому что на маленьких размерностях Вы никогда не увидите ничего интересного.
                                                                                                    0
                                                                                                    Ради примера — приближенный МВиГ на данных одной крупной компании дал ответ только спустя 8 дней 23 часа 47 минут на кластере из 512 Intel XEON и 4000 Gb оперативки.
                                                                                                      0
                                                                                                      зачем вы мне советуете какие-то книги? причем тут сложность? Вы помните о чем был разговор?
                                                                                                      1)Вы признаете что с помощью вашего алгоритма не всегда можно найти правильное решение?
                                                                                                      2) Вы признаете что предоставленный мною алгоритм позволяет найти правильное решение (с эвристикой и без)?
                                                                                                      и на маленьких размерностях можно увидеть (вы похоже не знаете, но к какому закону ближе та или иная кривая можно судить и по всего нескольким точкам)
                                                                                                        0
                                                                                                        Простите за нескромный вопрос, но какое у Вас образование?
                                                                                                        Возможно, в разных сферах разные базовые понятия…

                                                                                                        1) Я никогда и не отрицал этого, я утверждал лишь про приближенные решения

                                                                                                        2) Без эвристики — да, будет найдено верное решение. С эвристикой — нет, не всегда.

                                                                                                        По поводу нескольких точек — Вы не правы. Прошу ссылку подтверждающую Ваши слова.
                                                                                                          0
                                                                                                          2) объясните, почему вы до сих пор так думаете?
                                                                                                            0
                                                                                                            Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
                                                                                                              0
                                                                                                              не понимаю. где сломалось? Почему его нельзя выбирать? Посмотрите на пример в посте. если я вас правильно понял, то как раз тот случай, когда продолжать дальше по первой ветви неправильно

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

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