Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 82
Я заметил этот факт некоторое время назад :)
Вот пост, рассказывающий, как я обошел эту проблему
habrahabr.ru/post/229597/
Вот пост, рассказывающий, как я обошел эту проблему
habrahabr.ru/post/229597/
upd. а не пробовали на большом графе? не 15х15. Разделение на 2n на каждом шаге может привести к очень большому числу одновременно просматриваемых ветвей
плюс на большом графе вероятность попадания в «плохую ситуацию», описанную Вами в контр-примере в начале поста, уменьшается.
и я, честно, не понимаю формулировки «неправильный ответ». В любом случае это алгоритм приближенного решения, а не точного. Понятно, что на небольших задачах возможно его улучшение. Вопрос в сходимости приближенного алгоритма к точному ответу на больших задач, где точное решение за адекватное время невозможно.
плюс на большом графе вероятность попадания в «плохую ситуацию», описанную Вами в контр-примере в начале поста, уменьшается.
и я, честно, не понимаю формулировки «неправильный ответ». В любом случае это алгоритм приближенного решения, а не точного. Понятно, что на небольших задачах возможно его улучшение. Вопрос в сходимости приближенного алгоритма к точному ответу на больших задач, где точное решение за адекватное время невозможно.
Дело в том, что задача коммивояжера заключается именно в поиске самого выгодного маршрута. поэтому необходимо сохранять предыдущие шаги (или матрицу затрат), и при необходимости, «изучать» все потенциальные решения на предыдущих шагах. конечно это затратно в плане памяти, и в случае большой матрицы дерево может очень сильно разрастись… Но зато получается правильный ответ к задаче: самый выгодный маршрут
Ну при таком подходе лучший вариант — честный перебор. Честный перебор — экспоненциальное время. Потому задача NP-тяжелая.
Экспоненциальное время на достаточно больших задачах настолько большое, что не вычислимо на современных мощностях за адекватное время(хотя бы десяток лет)
Отсюда приходит идея как минимум сокращения вариантов перебора — ввод различных эвристик и т.д.
Это автоматически перечеркивает гарантию нахождения точного решения, ибо не все варианты перебора просмотрены.
Точное решение находится либо потому что повезло, либо размер задачи невелик.
Экспоненциальное время на достаточно больших задачах настолько большое, что не вычислимо на современных мощностях за адекватное время(хотя бы десяток лет)
Отсюда приходит идея как минимум сокращения вариантов перебора — ввод различных эвристик и т.д.
Это автоматически перечеркивает гарантию нахождения точного решения, ибо не все варианты перебора просмотрены.
Точное решение находится либо потому что повезло, либо размер задачи невелик.
и вопрос тут далеко не в памяти. первостепенное значение — время.
по каким показателям вы сравнивали полный перебор и метод ветвей и границ?
по времени — очень сильно проигрывает, так как задача в большинстве случаях может быть решена за линейное от размерности матрицы, или с небольшими лишними ответвлениями,
по памяти — либо немного выигрывает метод ветвей и границ, так как для листьев надо хранить только историю взятых или не взятых ребер, либо проигрывает если хранить все матрицы (чтобы сэкономить время)
upd: если вы считаете что самое важное — время, то лучше метод ветвей и границ, чем полный перебор
по времени — очень сильно проигрывает, так как задача в большинстве случаях может быть решена за линейное от размерности матрицы, или с небольшими лишними ответвлениями,
по памяти — либо немного выигрывает метод ветвей и границ, так как для листьев надо хранить только историю взятых или не взятых ребер, либо проигрывает если хранить все матрицы (чтобы сэкономить время)
upd: если вы считаете что самое важное — время, то лучше метод ветвей и границ, чем полный перебор
Задача коммивояжера до данного момента не имеет решения, которое бы хотя бы за полиномиальное, не то что линейное, время находили бы решение, гарантированно отстоящее не более чем на некое эпсилон от оптимального.
Так что либо вы не понимаете алгоритмической сложности задачи, либо уже завтра утром о Вас узнает весь мир.
А серьезно — просто попробуйте запуститься на графе всяко побольше, чем 15х15.
Так что либо вы не понимаете алгоритмической сложности задачи, либо уже завтра утром о Вас узнает весь мир.
А серьезно — просто попробуйте запуститься на графе всяко побольше, чем 15х15.
1) оценка полиномиальное/линейное/экспоненциальное и т.д. «ставится» в случае самых наихудших условий, я упомянул что такое «линейное время» возможно в конкретных случаях, когда решение находится без возврата назад (т.е. не самых худших). и это ярко прослеживается на графике ( к сведению генерировались числа от 0 до 99)
2) исследования с большой матрицей проводил, именно поэтому там стоит галочка на то чтобы выводить дерево или нет. так как при очень больших размерах браузер попросту тормозил.
2) исследования с большой матрицей проводил, именно поэтому там стоит галочка на то чтобы выводить дерево или нет. так как при очень больших размерах браузер попросту тормозил.
А как вы узнаете, что нашли действительно самое оптимальное решение за «линейное время»?
для отдельного случая взятого с потолка — можем по построенному дереву пройтись еще раз на наличие лишних ответвлений и сделать соответствующий вывод… либо мы можем сделать, то что сделал я: берем несколько случайных матриц, ищем для них решение нашей задачи, измеряем потраченное время. на основе этой статистики мы можем найти вероятность того, что случайное дерево окажется одним из тех, для которого решения будет занимать «линейное или близкое к этому время». тут еще надо не забывать что диапазон допустимых значений в матрице затрат, тоже будет влиять на эту вероятность.
Уважаемый webmasterx, а разве оценка сложности qsort o(n*log(n)) — это худший случай?
Худшее время qsort'a — квадрат…
Худшее время qsort'a — квадрат…
и просто, чтобы Вы понимали масштабы. Алгоритм, приведенный мной в посте, на который Вы ссылались, реализованный на c++11, с многопоточностью на 64 ядра для просчета ветвей, сохраненных из предыдущих итераций, на графе 500х500 работал 9.5 часов. И это лишь при раздвоении на каждой итерации и с ограничением на число сохраненных ветвей.
зачем вы говорите о масштабах? речь идет именно о решении задачи коммивояжера, а не о получении равного (и правильного) или близкого (но неправильного) к равному правильного ответа к задачи Коммивояжера. Если речь бы шла именно о минимизации затрат времени и отсутствовала необходимость в 100% правильности ответа, то вы можете и обойтись делением на два подмножества. но это уже не было бы решением задачи коммивояжёра (во всех случаях, в конкретных ответы могли бы совпасть)
Да, но это же не значит, что в таком случае следует пользоваться пузырьковой сортировкой? В конце концов, она дает тот же результат при том же наихудшем времени O(n^2).
Таки да, однако алгоритм, приведенный автором, далеко не линеен, как он утверждает, а экспоненциален.
И несмотря на его утверждения, точного решения он тоже не гарантирует.
Скорее, вопрос в том, имеет ли смысл рассматривать большее число ветвей на каждом шаге. Эта идея сильно увеличивает время вычислений, однако на больших графах вероятность того, что такой подход что-то сильно улучшит, невысока, ибо проблема, которую решает данное изменение алгоритма, маловероятна и эта вероятность падает с увеличением размера графа. Возможно, стоит рассматривать большее число ветвей не глобально и всегда, а лишь на неких локальных итерациях. Однако, непонятно, как понимать, на каких.
И несмотря на его утверждения, точного решения он тоже не гарантирует.
Скорее, вопрос в том, имеет ли смысл рассматривать большее число ветвей на каждом шаге. Эта идея сильно увеличивает время вычислений, однако на больших графах вероятность того, что такой подход что-то сильно улучшит, невысока, ибо проблема, которую решает данное изменение алгоритма, маловероятна и эта вероятность падает с увеличением размера графа. Возможно, стоит рассматривать большее число ветвей не глобально и всегда, а лишь на неких локальных итерациях. Однако, непонятно, как понимать, на каких.
Я гарантирую 100% правильное решение, иначе бы не стал писать это как решение задачи коммивояжера.
повторяюсь: я не утверждаю что алгоритм линеен, я утверждаю что он существенно быстрее полного перебора. возьмем к примеру мой график: даже отбросив последние значения (посчитав их ошибочными), и взяв за самое большее затраченное время 0.075с как время полного перебора, то самое наименьшее пусть будет 0.06с, что в несколько раз меньше максимального. а вероятность того, что матрица решится за время приблизительно в половину от максимального, достаточно высока, чтобы применять этот вместо полного перебора.
Насчет дальнейших возможных оптимизаций, которые вы предложили: они не будут гарантировать 100% правильное решения, но могут сэкономить время, но это совершенно другой разговор
повторяюсь: я не утверждаю что алгоритм линеен, я утверждаю что он существенно быстрее полного перебора. возьмем к примеру мой график: даже отбросив последние значения (посчитав их ошибочными), и взяв за самое большее затраченное время 0.075с как время полного перебора, то самое наименьшее пусть будет 0.06с, что в несколько раз меньше максимального. а вероятность того, что матрица решится за время приблизительно в половину от максимального, достаточно высока, чтобы применять этот вместо полного перебора.
Насчет дальнейших возможных оптимизаций, которые вы предложили: они не будут гарантировать 100% правильное решения, но могут сэкономить время, но это совершенно другой разговор
Уважаемый webmasterx, графики пузырьковой сортировки и qsorta на массивах длиной по 10-15 элементов тоже будут одинаковы. На массивах по паре миллионов элементов — нет.
и Ваш алгоритм не альтернатива полному перебору — он не гарантирует оптимальное решение
и Ваш алгоритм не альтернатива полному перебору — он не гарантирует оптимальное решение
приведите, пожалуйста, строгое математическое доказательство корректности в таком случае.
метода ветвей и границ? Вы можете с легкостью найти его в оригинале: A. H. Land and A. G. Doig. An automatic method of solving discrete programming problems, стр. 497-520.
а что есть n в количестве разделяемых ветвей (2n)?
Небольшая оптимизация — подключаем эвристику
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (hi,ki) или нет, и вешаем двух и более детей — Sw(hi,ki) и Sw/o(hi,ki). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
как минимум эта эвристика может увести Вас от оптимального решения.
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (hi,ki) или нет, и вешаем двух и более детей — Sw(hi,ki) и Sw/o(hi,ki). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
как минимум эта эвристика может увести Вас от оптимального решения.
что вы подразумеваете под оптимальным?
лучше идти в глубину, стремясь к решению, чем в ширину, рассматривая менее вероятные ветви. (так как со спуском вниз уменьшаются значения в матрице затрат, а значит может меньше прибавится штрафа к минимальной границе, чем по сравнению с более высокими значениями)
лучше идти в глубину, стремясь к решению, чем в ширину, рассматривая менее вероятные ветви. (так как со спуском вниз уменьшаются значения в матрице затрат, а значит может меньше прибавится штрафа к минимальной границе, чем по сравнению с более высокими значениями)
Худшее время qsort'a — квадрат…Немного оффтопик: нетрудно модифицировать qsort таким образом, чтобы и в худшем случае он работал за O(n log n). Идея проста: вы ограничиваете глубину дерева сортировки некой величиной порядка log n и при достижении указанной глубины переключаетесь на другой алгоритм, который имеет время работы в худшем случае O(n log n) (на его роль обычно выбирают heap sort, т.к. он не требует дополнительной памяти). Подобный прием называется Introsort и используется, например, в libstdc++ (с ограничителем глубины равным 2*log2 n).
Можно и без heapsort. Достаточно на каждом шагу искать медиану массива за линейное время (такие алгоритмы существуют). Правда, скорость работы уменьшится примерно в 10 раз, зато будет гарантированное O(n log n).
Можно, но это непрактичный способ в отличии от вышеприведенного. Фишка в том, что если выбрать ограничитель глубины достаточно большим, то в большинстве случаев у вас до heapsort'а дело вообще не дойдет, сортировка закончится раньше. То есть, грубо говоря, в среднем случае ваша сортировка — тот же самый quicksort + очень небольшой оверхед на проверку глубины, а переключение идет лишь тогда, когда у quicksort'а дела пошли неважно.
К слову, алгоритм нахождения i-ой порядковой статистики (в том числе и медианы) можно затюнинговать похожим образом, используя вначале quickselect (который в среднем очень быстр, но в худшем случае работает за O(n2)) и переключаясь на алгоритм, ищущий за гарантированное линейное время, если quickselect работает слишком долго.
К слову, алгоритм нахождения i-ой порядковой статистики (в том числе и медианы) можно затюнинговать похожим образом, используя вначале quickselect (который в среднем очень быстр, но в худшем случае работает за O(n2)) и переключаясь на алгоритм, ищущий за гарантированное линейное время, если quickselect работает слишком долго.
Я попробовал ваш алгоритм:
Время:1.1067810058594.
Что-то как-то лучше уж полный перебор.
Время:1.1067810058594.
Что-то как-то лучше уж полный перебор.
данная матрица затрат — как раз таки яркий и лаконичный пример когда происходит полный перебор.
но если взять матрицу из примера 3 — то она решается за гораздо меньшее время. потому что в отличии от полного перебора были отсеяны наименее вероятные множества решений
но если взять матрицу из примера 3 — то она решается за гораздо меньшее время. потому что в отличии от полного перебора были отсеяны наименее вероятные множества решений
Я что-то путаю, или полный перебор графа из 5 вершин это 24 варианта? Как это может считаться дольше секунды?
вы не правы. 5! = 120
а вот насчет расчетов дольше секунды: боюсь тут вы правы, где-то я допустил ошибку, но я её не вижу. даже если выводить только те листья, по которым прошелся алгоритм. архив с уменьшим деревом
а вот насчет расчетов дольше секунды: боюсь тут вы правы, где-то я допустил ошибку, но я её не вижу. даже если выводить только те листья, по которым прошелся алгоритм. архив с уменьшим деревом
Обновил пост.
Исправлена ошибка в результате которой задача решалась с более чем (n-1)! вариантов.
Также добавил скриншот для сравнения с полным перебором.
Исправлена ошибка в результате которой задача решалась с более чем (n-1)! вариантов.
Также добавил скриншот для сравнения с полным перебором.
Суть поста от этого не поменялась.
Что с корректностью?
Что с вероятностью пропустить «точное решение» в «менее вероятных ветвях»?
Что с корректностью?
Что с вероятностью пропустить «точное решение» в «менее вероятных ветвях»?
корректность осталась.
вероятность 0.
была допущена логическая ошибка при изменении неправильного алогритма, которая не бросалась сразу в глаза не смотря на свою очевидность
вероятность 0.
была допущена логическая ошибка при изменении неправильного алогритма, которая не бросалась сразу в глаза не смотря на свою очевидность
Вопрос был, где обещанное Вами доказательство того, что алгоритм в 100% случаях дает правильное и точное решение задачи коммивояжера?
И где доказательство того, что вероятность озвученного выше события = 0?
И где доказательство того, что вероятность озвученного выше события = 0?
с этим вопросом не ко мне, а к создателям алгоритма. и найти его в интернете на русском языке тоже можно. Внимательный человек конечно задастся вопросом: если так, то почему я и demist допустили ошибки? Отвечу, алгоритм не был написан исключительно для решения задачи комивояжера, и поэтому его описание достаточно расплывчатое для меня, чтобы прочитать даже переведенный вариант.
Могу вам «на пальцах» объяснить почему решение правильное и точное. но не гарантирую что смогу убедить вас.
Могу вам «на пальцах» объяснить почему решение правильное и точное. но не гарантирую что смогу убедить вас.
Если Вы прочитаете комментарии выше, то заметите, что я постоянно говорю об одном — алгоритм не гарантирует точное решение. Он гарантирует в некоторой степени неплохое решение, не более того.
Единственный алгоритм, дающий точное решение — полный перебор.
Более того, современные алгоритмы, использующие комбинации эволюционных алгоритмов и алгоритмов муравьиной колонии, превосходят метод ветвей и границ по качеству решения.
Единственный алгоритм, дающий точное решение — полный перебор.
Более того, современные алгоритмы, использующие комбинации эволюционных алгоритмов и алгоритмов муравьиной колонии, превосходят метод ветвей и границ по качеству решения.
Почему алгоритм не гарантирует правильного решения? Ссылочку, будьте добры на опровержение.
вот
Если Вы реализуете алгоритм МВиГ так, чтобы в худшем случае пересмотреть все варианты — да, у Вас будет гарантированно точное решение, однако алгоритм выродится в полный перебор, а значит и сложность будет иметь экспоненциальную. Так что такой вариант алгоритма МВиГ можно рассматривать лишь как по-другому записанный полный перебор.
Если Вы все же откидываете некие варианты, то и точное решение Вы также можете и «откинуть»
Если Вы реализуете алгоритм МВиГ так, чтобы в худшем случае пересмотреть все варианты — да, у Вас будет гарантированно точное решение, однако алгоритм выродится в полный перебор, а значит и сложность будет иметь экспоненциальную. Так что такой вариант алгоритма МВиГ можно рассматривать лишь как по-другому записанный полный перебор.
Если Вы все же откидываете некие варианты, то и точное решение Вы также можете и «откинуть»
1)подскажите пожалуйста страницу и абзац где говорится что МВиГ не всегда решается правильно?
2) МВиГ — это и есть полный перебор всех возможных вариантов с отсеиванием явно не оптимальных решений. Для задачи Коммивояжера не существует алгоритмов сложность которых отличается от полного перебора. ( по крайней мере я не встречал не слышал о таком алгоритме)
3) конечно можно. но МВиГ отбрасывает очевидно неоптимальные решения. В этом и заключается вся прелесть алгоритма
2) МВиГ — это и есть полный перебор всех возможных вариантов с отсеиванием явно не оптимальных решений. Для задачи Коммивояжера не существует алгоритмов сложность которых отличается от полного перебора. ( по крайней мере я не встречал не слышал о таком алгоритме)
3) конечно можно. но МВиГ отбрасывает очевидно неоптимальные решения. В этом и заключается вся прелесть алгоритма
Я бы посоветовал Вам внимательно прочесть все, что там написано. Внимательно и с пониманием. Тогда Вы получите ответы на все Ваши вопросы.
Вы сами писали выше, что описание МВиГ выглядело для Вас «расплывчатым».
По ссылке неплохое объяснение, как это работает.
Еще, для ознакомления с темой, рекомендую вот это.
Это хотя бы для начала.
Вы сами писали выше, что описание МВиГ выглядело для Вас «расплывчатым».
По ссылке неплохое объяснение, как это работает.
Еще, для ознакомления с темой, рекомендую вот это.
Это хотя бы для начала.
Я бы вам рекомендовал почитать более внимательно тот текст. тогда вы поймете что вы не правы.
Расплывчатым для меня является само описание которое применимо не только к задаче коммивояжера.
Предложенная вами ссылка опять не доказывает, ваше утверждение о том, что решение не всегда оптимальное.
Расплывчатым для меня является само описание которое применимо не только к задаче коммивояжера.
Предложенная вами ссылка опять не доказывает, ваше утверждение о том, что решение не всегда оптимальное.
Запустите ваш алгоритм на большом графе.
Потом чуть-чуть измените параметры эвристики, которая отвечает за движение в глубину.
Ой! А решение-то поменялось… У задачи же не могут быть два точных решения, но почему-то разные по стоимости…
Не верите теории — проверяйте на практике.
Граф 15х15 — не аргумент, слишком мало вариантов. Берите минимум 500х500
Практика не подтверждает теории, а вот опровергать может.
Потом чуть-чуть измените параметры эвристики, которая отвечает за движение в глубину.
Ой! А решение-то поменялось… У задачи же не могут быть два точных решения, но почему-то разные по стоимости…
Не верите теории — проверяйте на практике.
Граф 15х15 — не аргумент, слишком мало вариантов. Берите минимум 500х500
Практика не подтверждает теории, а вот опровергать может.
уточню, не может быть два правильных решения с разной стоимостью. предоставьте скриншот доказательства. если вы его на самом деле придумали, то могу вам с радостью сообщить — вы не понимаете сути алгоритма
Да, пора менять работу… Занимаюсь этой темой четвертый год уже :)
Ладно, черт с ней, с теорией. Давайте что попроще, практика.
Просто проведите тесты на большом графе. Поиграйте с эвристиками, Вы все увидите сами.
Ну никто в мире, никто, не проверяет алгоритмы для NP-трудных задач на таких маленьких размерностях. У Вас лишь несколько сотен вариантов перебора, это несерьезно.
Ладно, черт с ней, с теорией. Давайте что попроще, практика.
Просто проведите тесты на большом графе. Поиграйте с эвристиками, Вы все увидите сами.
Ну никто в мире, никто, не проверяет алгоритмы для NP-трудных задач на таких маленьких размерностях. У Вас лишь несколько сотен вариантов перебора, это несерьезно.
а что для вас сложного с теорией? с каким эвристиками вы предлагаете поиграть? и проверяют прежде всего теоретический материал, а потом уже на компьютерах.
Итак, судя по всему вы признаете что у вас нет доказтельств того, что МВиГ для поиска гамильтоного цикла решает задачу?
Итак, судя по всему вы признаете что у вас нет доказтельств того, что МВиГ для поиска гамильтоного цикла решает задачу?
Постойте, постойте. Вроде бы Вы убеждаете меня, что все работает, а я, наоборот, утверждаю, что МВиГ не всегда верно работает. Давайте хоть с постановкой задачи определимся…
задача озвучена в наших постах — поиск гамильтоного цикла. и способ решения также указан — с помощью метода ветвей и границ
Отлично. Вот я говорю Вам, что МВиГ, как и любой эвристический алгоритм, не гарантирует нахождение точного решения.
Дабы не вникать в потоки теории ввиду явной разницы в математической подготовке, я предлагаю Вам взять Ваш собственный алгоритм и запустить его на большом графе(500 вершин как минимум), а потом вспомнить, что Вы сами ввели в алгоритм эвристику.
И немного поменять ее. И Вы сами увидите, что результат работы программы поменялся. Т.е. входные данные одни и те же, а результаты разные! Значит, что-то не так с алгоритмом.
Я же не говорю возьмите то, а скачайте то. Просто возьмите Ваш собственный алгоритм и потестируйте его.
Дабы не вникать в потоки теории ввиду явной разницы в математической подготовке, я предлагаю Вам взять Ваш собственный алгоритм и запустить его на большом графе(500 вершин как минимум), а потом вспомнить, что Вы сами ввели в алгоритм эвристику.
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух и более детей — Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
И немного поменять ее. И Вы сами увидите, что результат работы программы поменялся. Т.е. входные данные одни и те же, а результаты разные! Значит, что-то не так с алгоритмом.
Я же не говорю возьмите то, а скачайте то. Просто возьмите Ваш собственный алгоритм и потестируйте его.
upd. кстати абзац про эвристику в Вашем посте был дословно скопирован из моего поста, было бы неплохо это указывать, но это так, ремарка.
не знаю как для вас, но для меня назвать это «эвристикой» было слишком громко. от того, что мы стараемся углубиться или расшириться может увеличиться только время и может измениться маршрут. но не его конечная стоимость.
Для таких тестов как вы хотите у меня попросту не хватит оперативной памяти. Но и смысла я в них не вижу. с ними можно будет только найти баг в коде
Про то что за основу был взят ваш алгоритм, я хорошо намекнул в заголовке спойлера, мне понравилось как он написан.
Для таких тестов как вы хотите у меня попросту не хватит оперативной памяти. Но и смысла я в них не вижу. с ними можно будет только найти баг в коде
Про то что за основу был взят ваш алгоритм, я хорошо намекнул в заголовке спойлера, мне понравилось как он написан.
Эвристичность тут в том, что желание двигаться в глубину — это наше желание, разработчиков, чтобы получить ответ. Это требование наше, а не задачи. Требование задачи — минимальный путь, только и всего. Это все и портит, грубо говоря, мы вносим в алгоритм то, что ему может помешать.
Про оперативку.
Дело в используемом языкe. На С++ я обсчитывал графы по 1000 вершин на ноутбуке с 8Гб оперативной памяти. 500 вершин — за глаза хватало 4Гб.
Попробуйте язык без сборщика мусора, если это в Ваших силах, конечно, и оперативки будет хватать.
Про оперативку.
Дело в используемом языкe. На С++ я обсчитывал графы по 1000 вершин на ноутбуке с 8Гб оперативной памяти. 500 вершин — за глаза хватало 4Гб.
Попробуйте язык без сборщика мусора, если это в Ваших силах, конечно, и оперативки будет хватать.
постойте, я не понял, что портит алгоритм? Эвристика? в нашем случае или вообще?
И ответьте на вопрос: признаете ли вы, что метод ветвей и границ для поиска гамильтонова цикла всегда дает точный ответ?
Про оперативку. По правильному алгоритму у вас может не хватить 8Гб для 1000 вершин.
И ответьте на вопрос: признаете ли вы, что метод ветвей и границ для поиска гамильтонова цикла всегда дает точный ответ?
Про оперативку. По правильному алгоритму у вас может не хватить 8Гб для 1000 вершин.
Эвристические алгоритмы в общем случае уже не всегда гарантируют точный ответ.
Грамотно написанный МВиГ без эвристик дает верный ответ, только тогда он не сильно отличается от полного перебора.
МВиГ c эвристиками не дает гарантированного верного ответа.
Поверьте, на С++ в 8Гб можно засунуть гораздо больше, чем в php ;)
Грамотно написанный МВиГ без эвристик дает верный ответ, только тогда он не сильно отличается от полного перебора.
МВиГ c эвристиками не дает гарантированного верного ответа.
Поверьте, на С++ в 8Гб можно засунуть гораздо больше, чем в php ;)
Не будем говорить про общие случаи.
Вы все время говорите про эвристики во множественном числе, не знаю какие вы имеете в виду.
С вот этой эвристикой, которая у вас написана, МВиГ тоже дает гарантированный верный ответ. Это очевидно. Вам объяснить?
Я не спорю по поводу мощи С++.
Вы все время говорите про эвристики во множественном числе, не знаю какие вы имеете в виду.
С вот этой эвристикой, которая у вас написана, МВиГ тоже дает гарантированный верный ответ. Это очевидно. Вам объяснить?
Я не спорю по поводу мощи С++.
Да, дело в этой эвристике.
Проблема в том, что на больших, очень больших графах разница в штрафах между ветвями становится очень маленькой, и подобная эвристика может «увести» алгоритм в ветку, которая кажется чуть-чуть совсем хуже, но зато путь на 1 ребро больше.
На маленьких графах такого не случается. А на больших — редко, но метко.
Пути решения различны, я в одном из своих постов предлагал хранить неплохие ветки в памяти подольше, чтобы иметь возможность к ним «откатываться»
Проблема в том, что на больших, очень больших графах разница в штрафах между ветвями становится очень маленькой, и подобная эвристика может «увести» алгоритм в ветку, которая кажется чуть-чуть совсем хуже, но зато путь на 1 ребро больше.
На маленьких графах такого не случается. А на больших — редко, но метко.
Пути решения различны, я в одном из своих постов предлагал хранить неплохие ветки в памяти подольше, чтобы иметь возможность к ним «откатываться»
Извините, но какая задача озвучена в наших постах? Поиск Гамильтонова цикла. А это значит что найденный путь должен быть минимальным. Не важно как он ищется и как долго. Любой другой ответ — это не решение задачи.
Вы как раз таки предлагать по-быстрому выдать ответ вместо того, чтобы решать задачу. А это совершенно другой разговор.
Напоминаю, эвристика о том, чтобы при равных минимальных границах выбирать то ребро, размерность матрицы которого меньше.
Вы как раз таки предлагать по-быстрому выдать ответ вместо того, чтобы решать задачу. А это совершенно другой разговор.
Напоминаю, эвристика о том, чтобы при равных минимальных границах выбирать то ребро, размерность матрицы которого меньше.
Я лишь предлагал алгоритм приближенного решения задачи. Потому что при больших размерностях получить точный ответ нельзя — надо ждать столетия вычислений.
Ваш алгоритм, к сожалению, тоже экспоненциален, так что на больших данных ждать его придется очень долго.
И, к сожалению, он теряет свойство корректности. Потому что даже при равных минимальных границах выбор пути в котором размерность меньше, не означает, что оптимальное решение не может лежать в другом пути.
Ваш алгоритм, к сожалению, тоже экспоненциален, так что на больших данных ждать его придется очень долго.
И, к сожалению, он теряет свойство корректности. Потому что даже при равных минимальных границах выбор пути в котором размерность меньше, не означает, что оптимальное решение не может лежать в другом пути.
можно. но долго. но это будет ответ к задаче, а не приближенное решение ( неизвестно еще к тому же насколько)
Вы сами поняли, что написали в последнем абзаце? Я скажу вывод, который из него можно сделать: если мы нашли ответ со стоимостью Х, и если, есть возможные решения минимальная стоимость которых не меньше Х, то это не означает, что мы нашли самое оптимальное решение.
Вам не кажется что здесь есть противоречие?
Вы сами поняли, что написали в последнем абзаце? Я скажу вывод, который из него можно сделать: если мы нашли ответ со стоимостью Х, и если, есть возможные решения минимальная стоимость которых не меньше Х, то это не означает, что мы нашли самое оптимальное решение.
Вам не кажется что здесь есть противоречие?
Так что, как это ни грустно признавать, Ваш алгоритм не строго корректен и экспоненциален.
Так что Вы сделали то, что никому не нужно.
Людям нужна либо строгая корректность(минимальный процент людей, в основном, из науки + у них обычно не слишком большая размерность, кластера за пару недель справляются) либо время работы(95% заинтересованных лиц — им нужен достаточно точный ответ, однако размерности данных зашкаливают).
Типичный пример — задача составления расписаний. Алгоритмы там те же, что и коммивояжер. Только коммивояжер не слишком интересен практически, а вот расписания интересны.
Реальная задача — расписание в РЖД. Представляете, сколько там станций и сколько составов? Алгоритм с экспоненциальной сложностью даст ответ, в лучшем случае, в следующем тысячелетии.
Так что Вы сделали то, что никому не нужно.
Людям нужна либо строгая корректность(минимальный процент людей, в основном, из науки + у них обычно не слишком большая размерность, кластера за пару недель справляются) либо время работы(95% заинтересованных лиц — им нужен достаточно точный ответ, однако размерности данных зашкаливают).
Типичный пример — задача составления расписаний. Алгоритмы там те же, что и коммивояжер. Только коммивояжер не слишком интересен практически, а вот расписания интересны.
Реальная задача — расписание в РЖД. Представляете, сколько там станций и сколько составов? Алгоритм с экспоненциальной сложностью даст ответ, в лучшем случае, в следующем тысячелетии.
ответов может быть несколько. вам это кажется странным?
алгоритм не корректен с точки зрения теоретического описания или то, что при реализации на практике он не будет выдавать точный ответ?
Это было нужно мне.
Речь не шла о реальном применении, и что делать в связи с тормознутостью компьютеров, для больших матриц.
алгоритм не корректен с точки зрения теоретического описания или то, что при реализации на практике он не будет выдавать точный ответ?
Это было нужно мне.
Речь не шла о реальном применении, и что делать в связи с тормознутостью компьютеров, для больших матриц.
Понятно. Да, это отличная задача для мотивации разобраться с алгоритмами работы с матрицами, памятью и т.д. Я сам когда-то с этого же приблизительно начинал. Тогда вопрос снят.
Поймите, я Вас не критикую, я пытаюсь указать на моменты, которые Вы не заметили.
К сожалению, вот этот случай, когда стоимости равны, может «увести» алгоритм в ветку, в которой на следующих шагах все гораздо хуже, чем если бы мы пошли в другую равную. Такая ситуация уникальна и возникает редко. Но в огромных графах даже почти нулевая вероятность может проявиться — и тогда Ваш алгоритм даст сильно неверный ответ.
Так что нельзя говорить, что он 100% корректен — бывают случаи, когда может «не получиться»
Поймите, я Вас не критикую, я пытаюсь указать на моменты, которые Вы не заметили.
К сожалению, вот этот случай, когда стоимости равны, может «увести» алгоритм в ветку, в которой на следующих шагах все гораздо хуже, чем если бы мы пошли в другую равную. Такая ситуация уникальна и возникает редко. Но в огромных графах даже почти нулевая вероятность может проявиться — и тогда Ваш алгоритм даст сильно неверный ответ.
Так что нельзя говорить, что он 100% корректен — бывают случаи, когда может «не получиться»
Ответов может быть несколько, да. И такое бывает.
Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
А какие моменты я не заметил? (с момента обновления поста).
не бывает таких случаев, почему вы не пытаетесь понятен написанный алгоритм, и то что я вам говорю?
ситуация когда в конечном ответе стоимость Х и другая нерешенная альтернатива, тоже равна Х, и тоже является минимальной, не означает что нам надо дальше решать эту ветку. Ведь мы же нашли решение. все. точка.
решая альтернативу можно будет прийти к другому, как с большим, так и с тем же ответом Х. Но никогда с еще меньшим.
Я же исправил ваш алгоритм! Он выбирает всегда с самой наименьшой стоимостью ветку ( вот в чем у вас была ошибка). и всегда самую глубокую
не бывает таких случаев, почему вы не пытаетесь понятен написанный алгоритм, и то что я вам говорю?
ситуация когда в конечном ответе стоимость Х и другая нерешенная альтернатива, тоже равна Х, и тоже является минимальной, не означает что нам надо дальше решать эту ветку. Ведь мы же нашли решение. все. точка.
решая альтернативу можно будет прийти к другому, как с большим, так и с тем же ответом Х. Но никогда с еще меньшим.
Я же исправил ваш алгоритм! Он выбирает всегда с самой наименьшой стоимостью ветку ( вот в чем у вас была ошибка). и всегда самую глубокую
Мой алгоритм не нуждался в исправлениях, у него другие цели.
Он работает на огромных данных за адекватное время и не упирается в оперативку.
Ваш же алгоритм будет работать столько, что до Пекина пешком можно успеть… Раз 200
Он работает на огромных данных за адекватное время и не упирается в оперативку.
Ваш же алгоритм будет работать столько, что до Пекина пешком можно успеть… Раз 200
Поймите же, наконец, что алгоритм с экспоненцальной сложностью не интересен — уже есть такой же по сложности — полный перебор.
Точного решения NP-трудных задач за хотя бы полиномиальное время на текущий момент не существует в природе.
А за нахождение такого алгоритма даже существует специальная премия с нехилым денежным бонусом.
Ваши графики ничего не говорят о сложности — слишком маленькие данные. Это как знаете, в окрестности 0 и x, x^2, x^4 и т.д. тоже почти одно и то же, на первый взгляд.
А x на отрезке [0,1] так вообще самый «большой». А вот потом все ровно наоборот.
Точного решения NP-трудных задач за хотя бы полиномиальное время на текущий момент не существует в природе.
А за нахождение такого алгоритма даже существует специальная премия с нехилым денежным бонусом.
Ваши графики ничего не говорят о сложности — слишком маленькие данные. Это как знаете, в окрестности 0 и x, x^2, x^4 и т.д. тоже почти одно и то же, на первый взгляд.
А x на отрезке [0,1] так вообще самый «большой». А вот потом все ровно наоборот.
Вообще-то нуждался. Прочитайте свою постановку задачи. И скажите, удовлетворяет ли ваш алгоритм этой задаче
задача стояла конкретно для одного графа.
понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.
Первый мой комментарий к моему посту. Так что идеально удовлетворяет.
В самом посте вы ничего не сказали о том, что описанные вами алгоритмы — не дают правильного решения зачем их вообще тогда надо было публиковать, проводить какие-то измерения?
И вообще, получается, что поставили себе задачу, но вы в первом посте с ней не справились. и сказали об этом лишь в комментарии, вместо того чтобы вынести это в вывод.
в самом то посте не сказано что надо решить только один конкретный граф ( и неужели вы считаете полезным знать способ решения только для одного графа?)
То есть, если бы никто вам в комментарии не написал, то так бы никто не узнал что ни один из алгоритмов не дает правильного ответа?
И вообще, получается, что поставили себе задачу, но вы в первом посте с ней не справились. и сказали об этом лишь в комментарии, вместо того чтобы вынести это в вывод.
в самом то посте не сказано что надо решить только один конкретный граф ( и неужели вы считаете полезным знать способ решения только для одного графа?)
То есть, если бы никто вам в комментарии не написал, то так бы никто не узнал что ни один из алгоритмов не дает правильного ответа?
Поверьте, компании готовы платить огромные деньги за то, чтобы получить хотя бы приближенные решения. Потому что на тех объемах данных, что у них есть, точное решение посчитать невозможно. В посте приведены алгоритмы, различные существующие. Ремарка про один граф относится к подбору констант, это всегда определяется данными и только ими. Нельзя их угадать заранее для любого графа.
Так что, подытожу.
Рекомендую Вам прочитать Кормена(главы про основы вычислительной сложности), книжку-методичку от MIT по алгоритмам приближенного решения NP-тяжелых задач(к сожалению, она так и не вышла, валяется в сети в виде презентации), и пересесть на более подходящий для таких целей язык(раз уж он Вас ограничивает), потому что на маленьких размерностях Вы никогда не увидите ничего интересного.
Рекомендую Вам прочитать Кормена(главы про основы вычислительной сложности), книжку-методичку от MIT по алгоритмам приближенного решения NP-тяжелых задач(к сожалению, она так и не вышла, валяется в сети в виде презентации), и пересесть на более подходящий для таких целей язык(раз уж он Вас ограничивает), потому что на маленьких размерностях Вы никогда не увидите ничего интересного.
Ради примера — приближенный МВиГ на данных одной крупной компании дал ответ только спустя 8 дней 23 часа 47 минут на кластере из 512 Intel XEON и 4000 Gb оперативки.
зачем вы мне советуете какие-то книги? причем тут сложность? Вы помните о чем был разговор?
1)Вы признаете что с помощью вашего алгоритма не всегда можно найти правильное решение?
2) Вы признаете что предоставленный мною алгоритм позволяет найти правильное решение (с эвристикой и без)?
и на маленьких размерностях можно увидеть (вы похоже не знаете, но к какому закону ближе та или иная кривая можно судить и по всего нескольким точкам)
1)Вы признаете что с помощью вашего алгоритма не всегда можно найти правильное решение?
2) Вы признаете что предоставленный мною алгоритм позволяет найти правильное решение (с эвристикой и без)?
и на маленьких размерностях можно увидеть (вы похоже не знаете, но к какому закону ближе та или иная кривая можно судить и по всего нескольким точкам)
Простите за нескромный вопрос, но какое у Вас образование?
Возможно, в разных сферах разные базовые понятия…
1) Я никогда и не отрицал этого, я утверждал лишь про приближенные решения
2) Без эвристики — да, будет найдено верное решение. С эвристикой — нет, не всегда.
По поводу нескольких точек — Вы не правы. Прошу ссылку подтверждающую Ваши слова.
Возможно, в разных сферах разные базовые понятия…
1) Я никогда и не отрицал этого, я утверждал лишь про приближенные решения
2) Без эвристики — да, будет найдено верное решение. С эвристикой — нет, не всегда.
По поводу нескольких точек — Вы не правы. Прошу ссылку подтверждающую Ваши слова.
2) объясните, почему вы до сих пор так думаете?
Смотрите. Пусть в графе 100 вершин. Вот такая ситуация с двумя равными возникла на выборе 50ого шага. Тут они равны. И Вы выбрали первую. А вторую ветку выкинули. Но на 99ом шаге в первой ветке есть только вариант пройти по ребру стоимостью 100000. А вот в другой ветке все шло приблизительно также, только последнее ребро пути(которое уже нельзя выбирать) весит 10. И все. Все сломалось.
По поводу корректности. Задача корректна, если
решение существует,
решение единственно,
решение устойчиво. ЗК не является корректной, т.к. решений может быть более одного
Вы под корректностью что-то другое понимаете и каждый свое?
решение существует,
решение единственно,
решение устойчиво. ЗК не является корректной, т.к. решений может быть более одного
Вы под корректностью что-то другое понимаете и каждый свое?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задачи коммивояжера с помощью метода ветвей и границ