English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtГрафики и СетиПроблема коммивояжера
Давайте еще раз подумаем о сетях и картах. Представьте, что служба доставки должна посетить
Служба доставки должна посетить все города, в любом порядке. В задаче о кенигсбергских мостах мы хотели найти пути, которые проходят по каждому краю ровно по одному. Теперь мы хотим найти пути, которые посещают каждую вершину ровно один раз. Эти пути называются гамильтоновыми циклами .
Существует множество различных возможностей для гамильтоновых циклов в полных графах. Фактически, мы можем выбрать любую вершину в качестве начальной, а затем выбрать любой из оставшихся городов в любом порядке:
Diagram coming soon…
Diagram Coming Soon…
В графе с
Это означает, что в общей сложности ${tsnPaths(tsn1)} возможные пути. Сокращение для этого продукта ${tsn1} ! или ${tsn1} Факториал .
Вы можете себе представить, что может быть невозможно путешествовать напрямую между двумя городами - без проезда через другой город. В этом случае у нас больше нет полного графа, и найти число гамильтоновых циклов, если они вообще существуют, становится намного сложнее.
До сих пор мы игнорировали тот факт, что некоторые города могут быть дальше друг от друга, чем другие. В реальной жизни, однако, это очень важное соображение: мы не просто хотим найти какой-либо путь, мы хотим найти кратчайший путь. Это называется проблемой коммивояжера . Это должно быть решено не только в сфере транспорта и логистики, но и при размещении транзисторов на микрочипах, для создания более быстрых компьютеров или при анализе структуры
Один простой метод - это попробовать все возможные пути, найти длину каждого, а затем выбрать самый короткий. Однако мы только что показали, что даже с
К сожалению, нет более эффективного алгоритма для решения проблемы коммивояжера. Вместо этого математики и компьютерные ученые разработали различные алгоритмы, которые находят хорошие решения, даже если они могут быть не самыми лучшими. Эти алгоритмы, которые дают только приблизительные решения, называются эвристикой .
Попробуйте изменить расположение городов на этой карте и посмотрите, как меняется кратчайший путь между ними. Вы можете удалить города, нажав на них, и вы можете добавить города, нажав в любом месте на карте (до 8):
Алгоритм жадности (или алгоритм ближайшего соседа) очень прост: вы начинаете в случайном городе и последовательно перемещаетесь в ближайший город, который вы раньше не посещали. Как только вы посетили все города, вы останавливаетесь.
Анимация скоро ...
Вы можете показать, что в среднем пути, найденные с использованием жадного алгоритма, на 25% длиннее, чем кратчайший путь.
Алгоритм 2-Opt начинается со случайного возможного пути. Затем вы неоднократно выбираете два ребра и меняете их местами, если это уменьшит длину пути. Вы останавливаетесь, когда не можете уменьшить длину дальше, меняя местами любые пары ребер.
Анимация скоро ...
Оказывается, задолго до того, как компьютеры появились, Природа нашла умный способ найти оптимальные пути между разными местами: в муравьиных колониях.
Муравьи хотят найти кратчайшие пути между своим гнездом и возможными источниками пищи. Они могут общаться друг с другом через химикаты, которые они оставляют на своем пути, и за которыми могут следовать другие муравьи.
- Муравьиная колония посылает много разведчиков, которые первоначально путешествуют в случайных направлениях. Как только они находят еду, они возвращаются, оставляя след феромона. * Другие муравьи, как правило, идут по следу, когда находят его, который приводит их к еде. На обратном пути они откладывают больше феромона, тем самым усиливая след. * Со временем феромон испаряется. Чем длиннее путь, тем больше времени требуется муравьям для его прохождения, и поэтому у феромона больше времени для испарения. Короткие пути, с другой стороны, могут быть усилены быстрее, поэтому их сила увеличивается быстрее.
Диаграмма в ближайшее время ...
Алгоритмы Ant Colony System (ACS) пытаются воспроизвести это поведение на компьютерах, используя множество «виртуальных» муравьев. Они могут быстро найти очень хорошие решения для проблемы коммивояжера.
Одним из особенно полезных свойств алгоритмов ACS является то, что они могут работать непрерывно и в реальном времени адаптироваться к изменениям на графике. Эти изменения могут быть вызваны автомобильными авариями и перекрытием дорог в уличных сетях или скачками трафика на веб-серверах в компьютерных сетях.
Задача коммивояжера является
Поиск быстрого и точного алгоритма имел бы серьезные последствия в области компьютерных наук: это означало бы, что существуют быстрые алгоритмы для всех NP-сложных задач. Это также сделает большую часть безопасности в Интернете бесполезной, поскольку полагается, что определенные проблемы считаются очень сложными для компьютеров.
Поиск быстрого алгоритма для решения проблемы коммивояжера также решил бы одну из самых известных открытых задач в математике и информатике, проблему P vs NP . Это одна из семи