Неориентированный граф задачи коммивояжера. Метод ветвей и границ: понятие, особенности применения. Практический пример реализации метода. Нахождение легчайшего простого основного ориентированного цикла в полном взвешенном графе на четырех вершинах.
Когда имеется та или иная дополнительная информация о множестве, решение этой задачи иногда удается осуществить без полного перебора элементов всего множества M. В этих условиях можно организовать перебор элементов множества M с целью минимизации функции на этом множестве так: разобьем множество M на части (любым способом) и выберем ту из его частей W1, на которой функция j минимальна; Вот ее формулировка: «Имеется несколько городов, соединенных некоторым образом дорогами с известной длиной; требуется установить, имеется ли путь, двигаясь по которому можно побывать в каждом городе только один раз и при этом вернуться в город, откуда путь был начат («обход коммивояжера»), и, если таковой путь имеется, установить кратчайший из таких путей». Путь, который требуется найти, это - ориентированный остовный простой цикл минимального веса в орграфе (напомним: цикл называется остовным, если он проходит по всем вершинам графа; цикл называется простым, если он проходит по каждой своей вершине только один раз; цикл называется ориентированным, если начало каждого последующего ребра совпадает с концом предыдущего; вес цикла - это сумма весов его ребер; наконец, орграф называется полным, если в нем имеются все возможные ребра); такие циклы называются также гамильтоновыми. Выберем в матрице M1 самый тяжелый нуль; пусть он стоит в клетке ; фиксируем ребро графа и разделим множество G на две части: на часть , состоящую из обходов, которые проходят через ребро , и на часть , состоящую из обходов, которые не проходят через ребро .В данной курсовой работе были рассмотрены основные теоретические вопросы по задаче коммивояжера. Приведено решение вручную задачи методом ветвей и границ.Пример исходного текстового файла input.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
