Отлично. Вот я говорю Вам, что МВиГ, как и любой эвристический алгоритм, не гарантирует нахождение точного решения.
Дабы не вникать в потоки теории ввиду явной разницы в математической подготовке, я предлагаю Вам взять Ваш собственный алгоритм и запустить его на большом графе(500 вершин как минимум), а потом вспомнить, что Вы сами ввели в алгоритм эвристику.
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух и более детей — Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
И немного поменять ее. И Вы сами увидите, что результат работы программы поменялся. Т.е. входные данные одни и те же, а результаты разные! Значит, что-то не так с алгоритмом.
Я же не говорю возьмите то, а скачайте то. Просто возьмите Ваш собственный алгоритм и потестируйте его.
Постойте, постойте. Вроде бы Вы убеждаете меня, что все работает, а я, наоборот, утверждаю, что МВиГ не всегда верно работает. Давайте хоть с постановкой задачи определимся…
Да, пора менять работу… Занимаюсь этой темой четвертый год уже :)
Ладно, черт с ней, с теорией. Давайте что попроще, практика.
Просто проведите тесты на большом графе. Поиграйте с эвристиками, Вы все увидите сами.
Ну никто в мире, никто, не проверяет алгоритмы для NP-трудных задач на таких маленьких размерностях. У Вас лишь несколько сотен вариантов перебора, это несерьезно.
Запустите ваш алгоритм на большом графе.
Потом чуть-чуть измените параметры эвристики, которая отвечает за движение в глубину.
Ой! А решение-то поменялось… У задачи же не могут быть два точных решения, но почему-то разные по стоимости…
Не верите теории — проверяйте на практике.
Граф 15х15 — не аргумент, слишком мало вариантов. Берите минимум 500х500
Практика не подтверждает теории, а вот опровергать может.
Если Вы реализуете алгоритм МВиГ так, чтобы в худшем случае пересмотреть все варианты — да, у Вас будет гарантированно точное решение, однако алгоритм выродится в полный перебор, а значит и сложность будет иметь экспоненциальную. Так что такой вариант алгоритма МВиГ можно рассматривать лишь как по-другому записанный полный перебор.
Если Вы все же откидываете некие варианты, то и точное решение Вы также можете и «откинуть»
Если Вы прочитаете комментарии выше, то заметите, что я постоянно говорю об одном — алгоритм не гарантирует точное решение. Он гарантирует в некоторой степени неплохое решение, не более того.
Единственный алгоритм, дающий точное решение — полный перебор.
Более того, современные алгоритмы, использующие комбинации эволюционных алгоритмов и алгоритмов муравьиной колонии, превосходят метод ветвей и границ по качеству решения.
Вопрос был, где обещанное Вами доказательство того, что алгоритм в 100% случаях дает правильное и точное решение задачи коммивояжера?
И где доказательство того, что вероятность озвученного выше события = 0?
У меня в свое время на Nexus 5 c (тогда еще) 4.4 LTE не работал ровно никак, интернет был, а вот голосовые вызовы после 3х секунд разговора прерывались. Звонил по Hangouts с видеовызовом, и все было прекрасно.
Обращался в службу поддержки, обещали решить. Через неделю пришла смска — обновитесь до 5.0, как он выйдет.
Обновился на developer preview, все заработало. Насчет покрытия — в Москве почти повсеместно LTE (~50Mbit/s download), в Питере и в Казани тоже нареканий не было.
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (hi,ki) или нет, и вешаем двух и более детей — Sw(hi,ki) и Sw/o(hi,ki). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
как минимум эта эвристика может увести Вас от оптимального решения.
Уважаемый webmasterx, графики пузырьковой сортировки и qsorta на массивах длиной по 10-15 элементов тоже будут одинаковы. На массивах по паре миллионов элементов — нет.
и Ваш алгоритм не альтернатива полному перебору — он не гарантирует оптимальное решение
Единственное ныне существующее точное решение коммивояжера — полный перебор.
Увы, но это так.
Полный перебор — это пара десятков строчек кода, никому не интересных, потому что алгоритм очевиден.
Но только Ваш алгоритм не дает гарантированно верное решение.
Таки да, однако алгоритм, приведенный автором, далеко не линеен, как он утверждает, а экспоненциален.
И несмотря на его утверждения, точного решения он тоже не гарантирует.
Скорее, вопрос в том, имеет ли смысл рассматривать большее число ветвей на каждом шаге. Эта идея сильно увеличивает время вычислений, однако на больших графах вероятность того, что такой подход что-то сильно улучшит, невысока, ибо проблема, которую решает данное изменение алгоритма, маловероятна и эта вероятность падает с увеличением размера графа. Возможно, стоит рассматривать большее число ветвей не глобально и всегда, а лишь на неких локальных итерациях. Однако, непонятно, как понимать, на каких.
и просто, чтобы Вы понимали масштабы. Алгоритм, приведенный мной в посте, на который Вы ссылались, реализованный на c++11, с многопоточностью на 64 ядра для просчета ветвей, сохраненных из предыдущих итераций, на графе 500х500 работал 9.5 часов. И это лишь при раздвоении на каждой итерации и с ограничением на число сохраненных ветвей.
Дабы не вникать в потоки теории ввиду явной разницы в математической подготовке, я предлагаю Вам взять Ваш собственный алгоритм и запустить его на большом графе(500 вершин как минимум), а потом вспомнить, что Вы сами ввели в алгоритм эвристику.
И немного поменять ее. И Вы сами увидите, что результат работы программы поменялся. Т.е. входные данные одни и те же, а результаты разные! Значит, что-то не так с алгоритмом.
Я же не говорю возьмите то, а скачайте то. Просто возьмите Ваш собственный алгоритм и потестируйте его.
Ладно, черт с ней, с теорией. Давайте что попроще, практика.
Просто проведите тесты на большом графе. Поиграйте с эвристиками, Вы все увидите сами.
Ну никто в мире, никто, не проверяет алгоритмы для NP-трудных задач на таких маленьких размерностях. У Вас лишь несколько сотен вариантов перебора, это несерьезно.
Потом чуть-чуть измените параметры эвристики, которая отвечает за движение в глубину.
Ой! А решение-то поменялось… У задачи же не могут быть два точных решения, но почему-то разные по стоимости…
Не верите теории — проверяйте на практике.
Граф 15х15 — не аргумент, слишком мало вариантов. Берите минимум 500х500
Практика не подтверждает теории, а вот опровергать может.
Вы сами писали выше, что описание МВиГ выглядело для Вас «расплывчатым».
По ссылке неплохое объяснение, как это работает.
Еще, для ознакомления с темой, рекомендую вот это.
Это хотя бы для начала.
Если Вы реализуете алгоритм МВиГ так, чтобы в худшем случае пересмотреть все варианты — да, у Вас будет гарантированно точное решение, однако алгоритм выродится в полный перебор, а значит и сложность будет иметь экспоненциальную. Так что такой вариант алгоритма МВиГ можно рассматривать лишь как по-другому записанный полный перебор.
Если Вы все же откидываете некие варианты, то и точное решение Вы также можете и «откинуть»
Единственный алгоритм, дающий точное решение — полный перебор.
Более того, современные алгоритмы, использующие комбинации эволюционных алгоритмов и алгоритмов муравьиной колонии, превосходят метод ветвей и границ по качеству решения.
И где доказательство того, что вероятность озвученного выше события = 0?
Что с корректностью?
Что с вероятностью пропустить «точное решение» в «менее вероятных ветвях»?
будет вторая часть)
Обращался в службу поддержки, обещали решить. Через неделю пришла смска — обновитесь до 5.0, как он выйдет.
Обновился на developer preview, все заработало. Насчет покрытия — в Москве почти повсеместно LTE (~50Mbit/s download), в Питере и в Казани тоже нареканий не было.
Прослушал его лично от автора поста в качестве студента ФИВТ МФТИ.
Сначала думал, не понадобится.
А через год писал LCS через цепи в булеане.
Так что всем рекомендую)
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (hi,ki) или нет, и вешаем двух и более детей — Sw(hi,ki) и Sw/o(hi,ki). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
как минимум эта эвристика может увести Вас от оптимального решения.
и Ваш алгоритм не альтернатива полному перебору — он не гарантирует оптимальное решение
Увы, но это так.
Полный перебор — это пара десятков строчек кода, никому не интересных, потому что алгоритм очевиден.
Но только Ваш алгоритм не дает гарантированно верное решение.
И несмотря на его утверждения, точного решения он тоже не гарантирует.
Скорее, вопрос в том, имеет ли смысл рассматривать большее число ветвей на каждом шаге. Эта идея сильно увеличивает время вычислений, однако на больших графах вероятность того, что такой подход что-то сильно улучшит, невысока, ибо проблема, которую решает данное изменение алгоритма, маловероятна и эта вероятность падает с увеличением размера графа. Возможно, стоит рассматривать большее число ветвей не глобально и всегда, а лишь на неких локальных итерациях. Однако, непонятно, как понимать, на каких.