Вопрос №24435
 
 
 
 
Категории

 

В чем заключается "задача коммивояжера"?

Женя · почти 7 лет назад · 3 ответа
 

Хороший вопрос Ф топку
1
1
Ответы
Павел · почти 7 лет назад

На сколько я понял речь идёт именно о «задаче коммивояжера» - одной из самых известных задач комбинаторной оптимизации. Но для начала: коммивояжёр — это бродячий торговец, сейчас ездящий, который распродает товары из одной точки (со склада) по большому количеству другим разным точкам (городам). Клиентов (покупателей)обычно находит сам. Большое развитие коммивояжерство получило в Америке с начала прошлого века и существует до сих пор. Пример продавцы известных фирм парфюмерии. Кстати и в России аналог существовал – коробейники. Теперь о задаче. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Условием задачи является выгодность маршрута (кратчайший, самый дешёвый, совокупность разных критериев и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Обычно указывается, что маршрут должен проходить через каждый город только один раз. Существует несколько частных случаев общей постановки задачи, в частности геометрическая, треугольная задача, симметричная и асимметричная задачи и обобщённая задача коммивояжёра. Пример решения можно посмотреть на сайте www.mgopu.ru/PVU/2.1/Recurs/Ba..., но там голову сломаешь.

 
 
Galina · почти 7 лет назад

Задачей коммивояжёра является задача комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Условия задачи:
критерий маршрута
матрица расстояний, стоимости
Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
В частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости).

 
 
Ответ выбран голосованием
Колобок · больше 6 лет назад

В терминах теории графов эта задача формулируется таким образом: в заданном связном взвешенном графе найти гамильтонов цикл наименьшей длины. Граф называется гамилътоновым, если в нем имеется простой цикл, проходящий через каждую вершину этого графа (по одному разу). Сам этот цикл также называется гамилътоновым. Слово “гамильтонов” в этих определениях связано с именем известного ирландского математика Уильяма Гамильтона, которым в 1859 году предложена игра “Кругосветное путешествие”. Каждой из двадцати вершин додекаэдра приписано название одного из крупных городов мира. Требуется, переходя от одного города к другому по ребрам додекаэдра, посетить каждый город в точности один раз и вернуться в исходный город. Эта задача, очевидно, сводится к отысканию в графе додекаэдра простого цикла, проходящего через каждую вершину этого графа.
В произвольном графе может быть, в отличие от эйлеровых, множество гамильтоновых циклов. Однако не существует сформулированного условия существования гамильтонового цикла (необходимость и достаточность). Нет также и эффективного алгоритма его построения.

Примером нахождения гамильтонового цикла является задача о коммивояжёре. Коммивояжёр (фр. commisvoyageur) – разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам.
В этой задаче считается, что имеется n городов, которые непременно должен посетить коммивояжёр, - все и ровно по одному разу, проделав путь между городами наименьшей суммарной протяженности.
В терминах теории графов эта задача формулируется таким образом: в заданном связном взвешенном графе найти гамильтонов цикл наименьшей длины.

Эта задача имеет большое практическое и теоретическое значение. В силу своей вычислительной сложности - при полном переборе существует (n - 1) • (n - 2) • … • 2 • 1 = (n - 1) решений (т.е. сгенерировать все возможные перестановки вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать из них кратчайший), равносильной целому классу переборных задач, она часто используется математиками для сравнительного анализа и изучения сложности алгоритмов оптимизации в дискретной математике.
Таким образом, решение задачи о коммивояжёре методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших n.
Более того, известно, что задача о коммивояжёре принадлежит к числу так называемых NP – полных задач, суть которых вкратце такова. В различных областях дискретной математики, комбинаторики, логики и т.п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует.
Однако, существуют алгоритмы, позволяющие сократить полный перебор гамильтоновых циклов, но не исключающий его:
1.Эвристический.
2.Монте-Карло (статистические выборки).
3.Целочисленного линейного программирования.
4.Динамического программирования.

Алгоритм поиска гамильтонова цикла
1.Осуществить приведение матрицы смежности по строкам и столбцам и определить значение и для каждой строки и столбца. Матрицу приводим по правилу: из каждого элемента вычитаем сумму констант приведения. Эта сумма равна нижней оценке границы исходного множества решений.
2.Для всех элементов, у которых найти и выбрать максимальное приращение оценки. Определить и строку и столбец.
3.Вычёркиваем строку равную и столбец равный, а также накладываем запрет на дугу, образующую цикл с ранее выбранными дугами, если он не гамильтонов.
4.Разбиваем множество решений на два подмножества, включающее дугу и не включающее эту дугу. Если не выбраны все вершины графа, то переходим к пункту 1, иначе формируем гамильтонов цикл. Длина цикла будет определена суммой нижних оценок длин путей, полученных при каждом приведении матрицы.

 
Источник: наковырял на кампе свою методу по дискретной мат
 
 
 
 
 
 
Ссылка на этот вопрос
 
Поискать ответ на вопрос: ответы@mail.ru, otvety@google.ru, Яндекс.Ответы
 
Читать новые вопросы в: LiveJournal, Livinternet, Google Reader
 
Этот вопрос посмотрели 3349 раз, в среднем 1 просмотр в день (1.33)
 
 
 
 
 
 
Адрес друга:
 
 
 
 
 
 
 
 
 
 
 

© vorum.ru — вопросы и ответы, 2006–2016
Пишите нам на in@vorum.ru

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

Цифры не для всех: 207

 
 
× Нравится наш сайт?
Нажмите кнопку «Мне нравится» (Like), чтобы присоединиться к нам на Facebook