Задача коммивояжёра


Содержание

Задача коммивояжёра

Постановка задачи

При обсуждении метода «грубой силы» (последовательный перебор) была сформулирована задача коммивояжёра:

Eсть N городов, соединённых между собой дорогами. Необходимо проложить между ними кратчайший замкнутый маршрут, проходящий через каждый город только один раз.

Приведём небольшую классификацию вариантов задачи:

  • Симметричная проблема коммивояжёра (TSP = traveling salesman problem) в которой расстояния заданы между любыми двумя городами и матрица расстояний симметрична: Dji = Dij.
  • Асимметричная проблема коммивояжёра (ATSP) допускает несимметричность матрицы Dji ≠ Dij. В ещё более общем случае, пути между некоторыми городами могут отсутствать ( == иметь бесконечную длину).
  • Задача с частичным упорядочиванием (SOP = sequential ordering problem) требующая, чтобы определённый город i был посещён до города j (таких условий может быть несколько).
  • Поиск цикла Гамильтона (HCP = нamiltonian cycle problem) — обнаружение в произвольном графе замкнутых путей, проходящих через каждую вершину в точности один раз.

В TSP (симметричной задаче коммивояжёра) путь замкнут и стартовать можно с любого города (и в любую сторону). Поэтому для N городов существует (N-1)!/2 различных путей. Факториал растёт очень быстро: N!

N N и пространство в котором ищется оптимальное решение оказывается огромным. Именно поэтому задача коммивояжёра интересна для тестирования различных алгоритмов.

Евклидова задача коммивояжёра

Если Dji = Dij и расстояния между любыми городами i, j, k удовлетворяют неравенству треугольника: Dij + Djk ≥ Dik, то задачу коммивояжёра называют метрической. Её частным случаем является задача соединения кратчайшей замкнутой ломаной линией точек на плоскости (расстояние равно обычному евклидовому расстоянию). Ниже приведены решения такой задачи для 20 и 50 городов:

Несложно видеть, что в евклидовой задача коммивояжёра (ETSP) оптимальный путь не должен иметь пересечений. Действительно, пусть есть некоторый путь, изображённый ниже на первом рисунке. Пунктиром обозначены остальные его участки (т.е. приведены только 4-е города). Если перебросить два участка пути (как на второй картинке), то общий путь вырастет (сумма диагоналей 4-угольника всегда длиннее суммы двух противоположных сторон):

С ETSP связаны интересные вопросы статистического характера. Рассмотрим, например, квадрат в котором случайно, с равномерным распределением размещено N городов. Оказывается, что в большинстве случаев такие «карты городов» имеют кратчайшие пути примерно одной длины, пропорциональной квадратному корню из N.

Методы решения

Задача коммивояжёра относится к классу NP-трудных и не известен алгоритм, который позволет гарантировано её решить за полиномиальное по числу городов N время T

N k , k=const. Тем не менее, для «обозримого» количества городов существует множество способов решения:

1. Точные методы не только находят некоторое решение, но и при окончании своей работы доказывают, что это решение — наилучшее. Отметим следующие из них:

  • Полный перебор перестановок N-1 чисел (стартовый город фиксирован). Практически бесполезен при N > 15.
  • Направленный поиск с возвратами — перебор вариантов «вокруг» некоторого решения с отсечением путей, имеющих длину большую, чем лучший к текущему моменту путь.
  • Метод ветвей и границ — наиболее эффективный из известных метод отсечения «неперспективных» узлов, за счёт анализа матрицы расстояний. При поиске оптимального решения строится бинарное дерево (в каждом узле порождаются 2 ветви: коммивояжёр идёт в некоторый город или не идёт в него).
  • Линейное программирование применяется для минимизации (с ограничениями) линейной формы d·x, где x — искомый бинарный вектор размерности N(N-1)/2, компоненты которого xi равны 1 или 0, в зависимости от того, входит i-е ребро в путь или нет. Вектор d (той же размерности) равен длинам рёбер.

2. Эвристические методы, обычно, существенно быстрее точных, однако они не гарантируют оптимальности найденного решения. Результат их комбинации может далее использоваться как первое приближение для последующего улучшения, например, при помощи поиска с возвратом:

  • Жадный алгоритм при выборе очередного города берёт ближайший не посещённый до этого город.
  • Метод шнурка — геометрическая вариация жадного алгоритма, в которой города охватываются замкнутым контуром. Он постепенно растягивается, стараясь пройти через все города, минимальным образов увеличив свою длину.
  • Скользящий перебор переставляет местами города из небольшой части пути. Затем такое «окно перебора» скользит вдоль всего пути. Метод имеет различные вариации и оказывается эффективным способом улучшения решения, найденного предыдущими двумя эвристическими методами.

3. Вероятностные методы фактически ни когда не останавливаются, совершая случайные изменения пути, в ожидании получения более короткого. Из этого класса методов отметим:

  • Метод отжига в котором происходят перестановки городов с постепенно «затухающей» интенсивностью. При этом постоянно сохраняется наилучшее найденное решение.
  • Генетический алгоритм — более «продвинутый» вариант, при котором создаётся большое количество различных путей. Они постоянно «мутируют» и «скрещиваются» друг с другом, обмениваясь отдельным участками.

Глава 45. Задача коммивояжёра

Общие сведения

Может быть, алгоритм, основанный на полном переборе вариантов, не является самым эффективным (в смысле быстродействия) для решения задачи коммивояжёра? Увы, доказано, что не существует алгоритма решения, имеющего степенную сложность (то есть требующего порядка n a операций для некоторого a ) — любой алгоритм будет хуже. Всё это делает задачу коммивояжёра безнадёжной для ЭВМ с последовательным выполнением операций, если n хоть сколько-нибудь велико.

В таком случае следует отказаться от попыток отыскать точное решение задачи коммивояжёра и сосредоточиться на поиске приближённого — пускай не оптимального, но хотя бы близкого к нему. В виду большой практической важности задачи полезными будут и приближённые решения.

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

Задачи комбинаторной оптимизации


Переборные задачи, нацеленные на поиск оптимального варианта, называют задачами комбинаторной оптимизации.

Задача коммивояжёра может быть поставлена как задача оптимизации. В качестве множества X достаточно взять S n (множество перестановок n -элементного множества), а в качестве целевой функции U ⁡ x — длину замкнутой ломаной, проходящей через n заданных точек в порядке, заданной перестановкой x ∈ X .

Метод градиентного спуска

Для множеств X , для которых определено отношение близости, годятся и другие методы. Среди них — метод градиентного спуска.

Отношение близости — это способ определить для двух элементов множества, являются ли они близкими (в каком-нибудь смысле). Для числовых множеств, для множеств точек на плоскости или в пространстве близкими можно считать два числа (две точки), расстояние между которыми не превосходит некоторого маленького числа ε . Для множества S n близкими удобно считать две перестановки, отличающиеся на одну транспозицию, то есть получающиеся друг из друга «рокировкой» двух элементов множества. Например, перестановки 2 4 1 3 и 2 3 1 4 являются близкими в этом смысле, так как отличаются перестановкой элементов с номерами 2 и 4 . Можно определить и более строгое отношение близости, при котором близкие перестановки отличаются на соседнюю транспозицию, когда рокировка затрагивает элементы множества с соседними номерами. Тогда указанные выше перестановки близкими уже не будут, но близкими окажутся 2 4 1 3 и 2 4 3 1 .

Суть метода градиентного спуска отражена в его названии и заключается в следующем. Строится последовательность x 0 x 1 x 2 x 3 … ⊂ X , в которой начальный элемент x 0 выбирается произвольно (возможно, случайным образом), а каждый последующий является одним из соседей предыдущего, причём именно тем из соседей, для которого значение функции U будет наименьшим. Построение последовательности завершается тогда, когда последовательность значений целевой функции U ⁡ x 0 U ⁡ x 1 U ⁡ x 2 U ⁡ x 3 … перестанет быть монотонно убывающей.

Имеется вероятностная версия метода градиентного спуска. На каждом шаге для элемента множества X выбирается случайный сосед. Если значение целевой функции в случайной соседней точке уменьшилось, она добавляется в последовательность, и мы переходим к следующему шагу. Если же нет, то снова выбирается случайный сосед. Алгоритм останавливается, если достаточно долго не пополняется последовательность (не происходит переход к следующему шагу): вероятно, алгоритм в этом случае привёл в точку локального минимума.

Метод имитации отжига

Метод имитации отжига является модификацией вероятностного метода градиентного спуска. Отличие заключается в поведении алгоритма, когда U ⁡ x ⩽ U ⁡ x ˜ , где x — очередной элемент последовательности, а x ˜ — его сосед, выбранный наугад. Вероятностный метод градиентного спуска отвергал такого соседа безусловно, а метод имитации отжига допускает добавление такого «плохого» соседа в последовательность, правда, с некоторой вероятностью p , зависящей от того, насколько плохой сосед ухудшил целевую функцию. Возьмём разность ∆ U = U ⁡ x ˜ − U ⁡ x (она неотрицательна, если сосед «плохой») и положим p = e − ∆ U Θ . Здесь e — некоторое число, большее единицы (какое именно, не принципиально, но обычно берут e ≈ 2,718281828459045… — основание натуральных логарифмов), а Θ — некоторое положительное число, называемое температурой.

На рисунке 45.1. «Вероятность мутации для метода имитации отжига» показаны зависимости вероятности мутации от величины ∆ U при различных значениях температуры Θ . Высоким температурам соответствуют графики, чей цвет ближе к красному, низким — к синему. Как и положено, значение вероятности заключено в отрезке 0 1 . При отрицательных ∆ U вероятность равна 1 , что соответствует случаю «хорошей» мутации.

Приложение на рисунке 45.2 позволяет понаблюдать за процессами, присходящими при поиске оптимального решения задачи коммивояжёра методом имитации отжига.

Гамильтоновы графы

Содержание

Основные определения [ править ]

Примечание
Определение:
Гамильтоновым путём (англ. Hamiltonian path) называется простой путь, проходящий через каждую вершину графа ровно один раз.
Определение:
Гамильтоновым циклом (англ. Hamiltonian cycle) называют замкнутый гамильтонов путь.
Определение:
Граф называется полугамильтоновым (англ. Semihamiltonian graph), если он содержит гамильтонов путь.
Определение:
Граф называется гамильтоновым (англ. Hamiltonian graph), если он содержит гамильтонов цикл.

Очевидно, что любой гамильтонов граф также и полугамильтонов.

Достаточные условия гамильтоновости графа [ править ]

Теорема Дирака [ править ]

Теорема Оре [ править ]

Теорема Поша [ править ]

Теорема Редеи-Камиона [ править ]

Теорема Гуйя-Ури [ править ]

Теорема (Поша):

Теорема Хватала [ править ]

Теорема (Ghouila-Houri):

Тогда если [math] \forall k \in \mathbb N [/math] верна импликация:

[math] d_k \leqslant k \lt n/2 \Rightarrow d_ \geqslant n — k, (*) [/math] то граф [math] G [/math] гамильтонов.

Задача о коммивояжере [ править ]

Рассмотрим алгоритм нахождения гамильтонова цикла на примере задачи о коммивояжёре.

Описание задачи [ править ]

Теорема (Хватал):
Задача:
Задача о коммивояжере (англ. Travelling salesman problem, TSP) — задача, в которой коммивояжер должен посетить [math] N [/math] городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

Варианты решения [ править ]

Задача о коммивояжере относится к классу NP-полных задач. Рассмотрим два варианта решения с экспоненциальным временем работы.

Перебор перестановок [ править ]

Можно решить задачу перебором всевозможных перестановок. Для этого нужно сгенерировать все [math] N! [/math] всевозможных перестановок вершин исходного графа, подсчитать для каждой перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших [math]N[/math] . Сложность алгоритма [math]O(\times)[/math] .

Динамическое программирование по подмножествам (по маскам) [ править ]

Задача о коммивояжере представляет собой поиск кратчайшего гамильтонова цикла в графе. Зафиксируем начальную вершину [math]s[/math] и будем искать гамильтонов цикл наименьшей стоимости — путь от [math]s[/math] до [math]s[/math] , проходящий по всем вершинам (кроме первоначальной) один раз. Т.к. искомый цикл проходит через каждую вершину, то выбор [math]s[/math] не имеет значения. Поэтому будем считать [math]s = 0 [/math] .

Подмножества вершин будем кодировать битовыми векторами, обозначим [math]mask_i[/math] значение [math]i[/math] -ого бита в векторе [math]mask[/math] .

Обозначим [math]d[i][mask][/math] как наименьшую стоимость пути из вершины [math]i[/math] в вершину [math]0[/math] , проходящую (не считая вершины [math]i[/math] ) единожды по всем тем и только тем вершинам [math]j[/math] , для которых [math]mask_j = 1[/math] (т.е. [math]d[i][mask][/math] уже найденный оптимальный путь от [math]i[/math] -ой вершины до [math]0[/math] -ой, проходящий через те вершины, где [math]mask_j=1[/math] . Если [math]mask_j=0[/math] ,то эти вершины еще не посещены).

Алгоритм поиска цикла будет выглядеть следующим образом:

  • Начальное состояние — когда находимся в [math]0[/math] -й вершине, ни одна вершина не посещена, а пройденный путь равен [math]0[/math] (т.е. [math]i = 0[/math] и [math]mask = 0[/math] ).
  • Для остальных состояний ( [math]i \ne 0[/math] или [math]mask \ne 0[/math] ) перебираем все возможные переходы в [math]i[/math] -ую вершину из любой посещенной ранее и выбираем минимальный результат.
  • Если возможные переходы отсутствуют, решения для данной подзадачи не существует (обозначим ответ для такой подзадачи как [math]\infty[/math] ).

Стоимостью минимального гамильтонова цикла в исходном графе будет значение [math] d[0][2^n-1][/math] — стоимость пути из [math]0[/math] -й вершины в [math]0[/math] -ю, при необходимости посетить все вершины. Данное решение требует [math]O(<2^n>\times)[/math] памяти и [math]O(<2^n>\times)[/math] времени.

Для того, чтобы восстановить сам путь, воспользуемся соотношением [math] d[i][mask] = w(i, j) + d[j][mask — 2^j] [/math] , которое выполняется для всех ребер, входящих в минимальный цикл . Начнем с состояния [math] i = 0 [/math] , [math] mask = 2^n — 1[/math] , найдем вершину [math]j[/math] , для которой выполняется указанное соотношение, добавим [math]j[/math] в ответ, пересчитаем текущее состояние как [math]i = j[/math] , [math] mask = mask — 2^j [/math] . Процесс заканчивается в состоянии [math]i = 0[/math] , [math] mask = 0 [/math] .

Оптимизация решения методом динамического программирования [ править ]

Пусть [math]d[mask][i][/math] содержит булево значение — существует ли в подмножестве [math]mask[/math] гамильтонов путь, заканчивающийся в вершине [math]i[/math] .

Сама динамика будет такая:
[math] d[mask][i] = \left\<\begin 1&;\ |mask| = 1,\ mask_i = 1\\ \bigvee_\limits d[mask \oplus 2^i][j] &;\ |mask| \gt 1,\ mask_i= 1 \\ 0&;\ otherwise\\ \end\right. [/math]

Это решение требует [math]O(2^nn)[/math] памяти и [math]O(2^nn^2)[/math] времени. Эту оценку можно улучшить, если изменить динамику следующим образом.

Пусть теперь [math]d'[mask][/math] хранит маску подмножества всех вершин, для которых существует гамильтонов путь в подмножестве [math]mask[/math] , заканчивающихся в этой вершине. Другими словами, сожмем предыдущую динамику: [math]d'[mask][/math] будет равно [math]\sum_\limits d[mask][i] \cdot 2 ^i [/math] . Для графа [math]G[/math] выпишем [math]n[/math] масок [math]M_i[/math] , для каждой вершины задающие множество вершин, которые связаны ребром с данной вершиной. То есть [math]M_i = \sum_\limits 2^j \cdot ((i, j) \in E ? 1:0) [/math] .

Тогда динамика перепишется следующим образом:
[math] d'[mask] = \left\<\begin mask &;\ |mask| = 1 \\ \sum_\limits 2^i \cdot ((d[mask \oplus 2^i] \& M_i) \neq 0?1:0) &;\ |mask| \gt 1 \\ 0&;\ otherwise\\ \end\right. [/math]


Особое внимание следует уделить выражению [math]d[mask \oplus 2^i] \& M_i[/math] . Первая часть выражения содержит подмножество вершин, для которых существует гамильтонов путь, заканчивающихся в соответствующих вершинах в подмножестве [math]mask[/math] без вершины [math]i[/math] , а вторая — подмножество вершин, связанных с [math]i[/math] ребром. Если эти множества пересекаются хотя бы по одной вершине (их [math]\&[/math] не равен [math]0[/math] ), то, как нетрудно понять, в [math]mask[/math] существует гамильтонов путь, заканчивающийся в вершине [math]i[/math] .

Окончательная проверка состоит в сравнении [math]d[2^n — 1][/math] c [math]0[/math] .

Это решение использует [math]O(2^n)[/math] памяти и имеет асимптотику [math]O(2^nn)[/math] .

Псевдокод [ править ]

Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за [math]|mask|[/math] количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния [math]\langle i, mask \rangle[/math] мы смотрим на состояния

[math]\langle j, mask — 2^j \rangle[/math] , и [math]|mask| = |mask — 2^j| + 1[/math] , то состояния с большим [math]|mask|[/math] должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта. Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).

Дальше ищем сам цикл:

Алгоритм нахождения гамильтонова цикла [ править ]

Алгоритм нахождения гамильтонова цикла легко получить слегка изменив алгоритм нахождения минимального гамильтонова цикла. В массиве [math]d[i][mask][/math] мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает [math] true[/math] , то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.

Алгоритм нахождения гамильтонова пути [ править ]

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

Задача коммивояжёра

Оптимизация занимает достаточно большую часть в жизни людей. Порой мы даже не задумываемся о том, что мы что-то оптимизируем. Так, к примеру, мы отправляемся в путешествие и нам необходимо собрать много вещей, а чемодан средних размеров. (Мы тоже имеем физические ограничения) Если мы пойдем на пляж, то взять шорты, очки и крем от загара будет значительно лучшим решением, если бы возьмем с собой зимнюю куртку, то есть опираясь на приоритет вещей мы делаем свой выбор, чтобы суммарная ценность груза была максимальной.

Делаем вывод, что оптимизация необходима нам для нахождения позитивного решения, оно может быть не самым лучшим, но точно будет хорошим.

Более строгим будет определение, что оптимизация – это инструмент, который находит оптимальное решение.

Математически «оптимизация» — представляет собой, нахождение MAX и MIN функции [1].

Наконец разобравшись с тем, что такое оптимизация и, что она делает.

Попробуем разобраться – «How does it work?!» (Как это работает?)

Представим на секунду, что наш чемодан превратился в корабль, а в котором множество отсеков, задача которого переправить товар в точку доставки (наша задача осталась неизменна – привести суммарную ценность к ее максимуму), целевой функцией будет сумма стоимости продукции. Теперь, нам понадобиться значительно больше времени для нахождения оптимального решения.

Взяв случайное решение, мы не сможем быть уверенны, что оно хоть сколько-нибудь будет приближенно к искомому экстремуму. Существует большое количество методов, которые помогут решить данную задачу [2]. Их такое количество, что их разделяют на классы.

Одним из них является метод имитации отжига (или просто метод отжига.), он входит в класс стохастических.(то-есть который может угадывать) Зачем же здесь вероятность? Ответим на это дальше. Но для начала приведем примеры прикладного применения глобальной оптимизации.

Существует множество применений методов глобальной оптимизации [3]. Используется для реконструкции изображений, глобальной маршрутизации, назначение задач и планирование, и многое другое.

К примеру, попробуем решить задачу коммивояжера двумя разными методами: «Венгерский метод» и «метод ветвей и границ». Данная статья посвящена сравнению двух этих алгоритмов. Эта задача представляет собой поиск самого выгодного маршрута, проходящего через указанные города.

Задача коммивояжера с возвращениями

Прямой перебор маршрутов в классической задаче коммивояжера. Источник изображения: http://en.wikipedia.org/wiki/File:Bruteforce.gif

Пусть проектируется сеть электроснабжения заданного набора взаимно удаленных потребителей. Примером могут служить населенные пункты одного района. Возникает задача оптимизации такой электросети по стоимости капиталовложений или потерям мощности в процессе эксплуатации. Интересно, что будущих инженеров-энергетиков не учат методам ее решения, а сами эти методы не разработаны. При выполнении дипломных проектов схему сети выбирают почти интуитивно, оценивая лишь малую часть возможных вариантов (от 2-х до 5-ти). Таким образом, задача оптимизации электросети декларируется, как цель, но фактически не решается и даже не формулируется. По-видимому, это связано с тем, что электрические сети развиваются эволюционно, следуя за новыми потребителями. Если в данный момент времени необходимо подключить новый пункт к существующей системе, то это не вызывает математических затруднений. Тем не менее, проблема выбора оптимальной сети является технически интересной и актуальной.

Рис. 1 Графы электросетей


Будем изображать сеть в виде графа, где каждое ребро отвечает одной трехфазной линии, а каждая вершина – главной понижающей подстанции (ГПП) или узловой подстанции (УП). Стандартное требование надежности состоит в том, что ГПП должна иметь два трансформатора, к которым подключены две входные (трехфазные) линии. В каждом пункте должна располагаться ГПП или УП, к последней могут быть подключены несколько ГПП. Связь между ГПП и УП также осуществляется по двойной цепи. Легко видеть, что в сетях a), b) и с) на рис. 1 обрыв любой из линий не прерывает электроснабжение каждого из пунктов. Один пункт подключен к внешней энергосистеме (ЭС) цепью, которая на рис. 1 показана пунктиром. Пунктирные линии не входят в графы и алгоритмах не рассматриваются. Однако пункт подключения к ЭС определяет выделенную вершину графа, которая будет называться точкой старта.

Кратность вершины – это число ребер, которым она инцидента. Например, граф а) имеет одну вершину кратности 4 и четыре вершины кратности 2 (линии подключения к ЭС в граф не входят). Каждая вершина на рис. 1 a), b) и c) имеет четную кратность. На более низком уровне системы электроснабжения, т.е., при подключении потребителей могут возникать вершины нечетной кратности. Однако мы исходим из того, что на уровне ГПП и УП кратность вершин должна быть четной. Это соответствует инженерной практике, согласно которой в процессе формирования сети некоторые пункты соединяются по топологии кольца (рис. 1 c)), а некоторые подключаются радиально (рис. 1 b)). По соображениям надежности, каждая радиальная линия должна быть задублирована. Такими двойными цепями также могут быть связаны между собой отдельные кольца. Ниже мы уточним тип представляющего графа, а пока заметим, что он является связным и имеет вершины только четной кратности.

Цикл удобно рассматривать, как замкнутую траекторию точки, движущейся от пункта к пункту. Поскольку каждая вершина сетевого графа имеет четную кратность, то, начав обход с любой из них, необходимо вернуться в исходной вершину. Так возникает цикл. При этом по одному ребру запрещено проходить дважды, но можно вернуться назад по второму, если данная пара вершин связана двойным ребром. Двойные ребра будем называть параллельными. Например, параллельными являются ребра между вершинами УП и ГПП на рис. 1 b). Такой путь вдоль ребер графа может не быть гамильтоновым циклом, поскольку последний не должен иметь самопересечений.

Поскольку сетевой граф имеет выделенную вершину (точка подключения к ЭС), мы будем рассматривать только те циклы, которые начинаются и заканчиваются в этой вершине. Если такой цикл проходит через все вершины, то будем называть его маршрутом. Примеры маршрутов тривиально получаются на рис. 1 a), b), c), если начать движение с выделенной вершины и проходить по каждому ребру строго один раз, обходя вершины в любом порядке и возвращаясь в точку старта. Траекториями таких движений являются графы, а маршрутов может быть несколько. Например, на графе a) существует 8 маршрутов, а на графе с) их только 2 (по часовой стрелке и против).

Теперь мы готовы дать определение маршрутам того типа, который рассматривается в данной статье. Пусть задан конечный набор точек, одна из которых называется точкой старта. Рассмотрим произвольный маршрут, проходящий через все эти точки, который начинается и заканчивается в точке старта. Разрешается многократно заходить в одну и ту же точку, однако эта возможность ограничена следующим требованием. Если произвольная точка пройдена более одного раза, то маршруту запрещается вторично заходить в любую другую точку, которая была пройдена между любыми двумя посещениями точки . Исключением является точка старта, в которую можно возвращаться без ограничений. Наконец, ни одно из ребер графа, представляющего маршрут, не должно соединять какую-либо вершину саму с собой (т.е., запрещено идти из точки сразу в нее же, делая петлю). Маршрут, удовлетворяющий этим условиям, называется квази-гамильтоновым.

На рис. 1 a), b) и c) таковыми являются все маршруты. Данное условие соответствует практике строительства электрических сетей. Весьма вероятно, хотя это строго не доказано, что всякий не квази-гамильтонов маршрут может быть переделан в более выгодный, квази-гамильтоновый. На рис. 1 d) маршрут 123425461 не является квази-гамильтоновым, т.к. он второй раз заходит в точку 4, ранее пройденную между двумя посещениями точки 2. На рис. 2 показаны варианты перестройки этого маршрута в квази-гамильтоновый: а) 1234252161 и b) 16432521. Если оптимизировать маршруты по длине пути, то в силу неравенства треугольника рис. 2 b) будет лучше, чем рис. 1 d), независимо от расстояний между точками.

Рис. 2 Квази-гамильтоновы маршруты

Заметим, что всякий гамильтонов цикл является квази-гамильтоновым маршрутом. Пусть выделенная вершина имеет номер 1. Тогда произвольный маршрут определяется последовательностью чисел , где каждое — номер вершины графа. Условие квази-гамильтоновости выглядит так: если любое число 1′ title=’j>1′ /> встречается в этом маршруте на местах и , так что , то ни одно из чисел последовательности не встречается в маршруте после позиции .

Задача оптимизации электросети свелась к поиску оптимального квази-гамильтонова маршрута через пункты подключения, со стартовой точкой подключения к ЭС. Траекторией такого маршрута будет граф, который задает искомую конфигурацию сети. Осталось определить целевую функцию от маршрута , которая должна быть минимизирована или максимизирована. Задав стоимость линии между каждой парой пунктов , определим стоимость маршрута:

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

Маршруты (циклы), которые рассматриваются в классической задаче коммивояжера, называются гамильтоновыми и характеризуются тем, что цикл заходит в каждый промежуточный пункт ровно один раз. Циклам, которые возникают в задачах оптимизации электросетей, разрешено возвращаться в одни и те же пункты, но не как попало. Квази-гамильтоновы циклы соответствуют реальным маршрутам объезда пунктов доставки, если требуется развести по ним грузы, начиная движение от склада и возвращаясь в него. При этом грузовик может проехать через ранее посещенный пункт той же самой дорогой, но в обратном направлении, если это помогает экономить время. Более того, другая дорога может оказаться недоступной. Поэтому условие задачи коммивояжера, которое исключает такого рода маршруты, выглядит чрезмерно жестким и не вполне адекватным реальности.

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

Пусть заданы набор точек (пунктов) и — матрица , которая определяет «стоимости» путей между пунктами, так что — стоимость прямого пути из точки в точку . При значение не определено или считается равным . Требуется найти квази-гамильтонов маршрут через все пункты, на котором функция (1) принимает наименьшее значение.

В качестве дополнительного условия может быть задан граф разрешенных путей . Его ребра соединяют пункты , между которыми «движение» разрешено. В этом случае минимум функции (1) ищется на множестве тех квази-гамильтоновых маршрутов, графы которых вложены в без учета параллельных ребер (т.е., только одно из любой пары параллельных ребер обязано совпадать с соответствующим ребром графа ). Граф должен быть, конечно, связным и проходить через все точки . В этом и только этом случае существует решение задачи с разрешенными путями!

Слово «стоимость» не следует воспринимать буквально. Число может быть просто расстоянием между пунктами или иной мерой. Однако следует заметить, что если в данной задаче стоимость – не географическое расстояние и не пропорциональна ему, то привычные свойства расстояний могут не выполняться. Например, может не выполняться неравенство треугольника ( не обязана быть симметричной.

В общем случае классическая задача коммивояжера не имеет точного алгоритма, объем вычислений которого имел бы порядок для какого-нибудь 0′ title=’s>0′ />, где — количество пунктов. Иначе говоря, точно и не слишком долго решать задачу коммивояжера невозможно. Прямой перебор маршрутов требует вычислений объемом порядка , поэтому такой метод практически неосуществим уже при близких к 30. При это — миллиарды лет вычислений на суперкомпьютере, а при прямой перебор всех 360 гамильтоновых циклов, начинающихся в заданной точке, можно наблюдать на анимации под заголовком статьи. Последнее ребро, замыкающее цикл, там не отображается.

Часто применяются приближенные алгоритмы, которые позволяют перестроить и этим улучшить любой исходный маршрут (методы локального оптимума). Обычно такие подходы дают хорошие результаты, хотя и не гарантируют, что полученный маршрут является оптимальным среди всех возможных. Подобным образом действуют студенты-энергетики, когда почти наугад выбирают исходный вариант сети, после чего пытаются его оптимизировать несколькими перестройками, обсчитывая варианты «вручную».

Другой тип алгоритмов эквивалентен введению графов разрешенных маршрутов , которые неявно определяются в процессе отсечения ветвей, заведомо не ведущих к оптимальному маршруту. Таков алгоритм Литтла, который достаточно быстро и точно находит глобальное решение задачи коммивояжера (однако нуждается в неравенстве треугольника для матрицы , как было замечено).

В задаче коммивояжера с возвращениями также можно использовать методы локального оптимума, которые просты для реализации и достаточно эффективны. Для этого нужно построить квази-гамильтонов маршрут «на глазок», после чего начать его варьировать каким-то образом, выбрав из возникающих вариантов наилучший. Пример таких действий, предпринимаемых в классической задаче коммивояжера, описан в статье http://habrparser.blogspot.ru/2014/02/blog-post_1.html . Такой подход не гарантирует оптимальное решение, поэтому остается только верить в то, что полученное решение является достаточно хорошим. Однако при большом размере задачи, т.е. при >10′ title=’n>>10′ />, с этим приходится мириться.

В задаче коммивояжера с возвращениями объем вычислений значительно больше, чем в классической задаче. Приближенная закономерность роста числа маршрутов очевидна из таблицы.

Общее число квази-гамильтоновых маршрутов

Прирост от предыдущего значения в число раз (приблизительно)

Задача коммивояжера

Задача коммивояжера (Travelling salesman problem, сокращённо TSP) является одной из самых известных задач комбинаторной оптимизации, состоящей в поиске оптимального объекта в конечном множестве объектов. Попросту говоря, заключается эта задача в том, что нужно найти наиболее выгодный маршрут, проходящий через конкретные города хотя бы один раз, а затем возвращающийся в исходный город.

Краткая историческая справка

Доподлинно неизвестно, когда задача коммивояжера была поставлена в первый раз. Но в 1832 году появилась книга «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера», и в ней описывалась данная проблема.

Одним из ранних вариантов задачи можно назвать задачу Icosian Game, разработанную ирландским математиком Уильямом Гамильтоном в 19 столетии. В ней нужно было найти маршруты на графе с двадцатью узлами. А первые данные о подобной задаче в качестве математической датируются 1930 годом.

Тогда австрийский экономист Карл Менгер на математическом коллоквиуме сказал, что проблемой посыльного называется задача определения кратчайшего пути между конечным множеством мест с известным расстоянием между ними. Некоторое время спустя появилась и известная нам вариация задачи – задача странствующего торговца (коммивояжера). Ее предложил американский математик Хасслер Уитни.


Коротко о значении задачи

Условия задачи говорят о критерии выгодности маршрута (с точки зрения расстояния, дешевизны и других составляющих). Маршрут должен проходить только один раз через каждый город, а после – возвращаться в начальную точку.

На первый взгляд может показаться, что найти оптимальный маршрут очень просто, но в действительности это нелегкая задача. К тому же есть разные вариации задачи, например, геометрическая, метрическая, симметричная, асимметричная или обобщенная задача.

С учетом разных свойств задачи уже во второй половине 20 века изучать ее стали не столько с практическим уклоном, сколько с теоретическим – она послужила моделью для разработки новейших алгоритмов оптимизации. На ее примере были разработаны метод ветвей и границ, метод отсечений, всевозможные эвристические алгоритмы и другие.

Начиная с 1960 года, задачу коммивояжера начали изучать программисты, экономисты, химики, биологи и представители других наук. А все по той простой причине, что к ее решению сводятся и решения огромного количества практических задач в разных областях науки и жизни.

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

Способность решить эту задачу позволяет оптимизировать и многие производственные процессы, находить оптимальные стратегии ведения хозяйства, экономить ресурсы.

Чем задача коммивояжера полезна для развития мышления

Ритм современной жизни кардинально меняет отношение людей ко времени. Сегодня люди становятся все более нетерпеливыми, не любят ждать, ищут новые возможности оптимизировать свое время и находить наиболее эффективные решения задач и проблем. Естественно, здесь же встает и вопрос о более оптимальном использовании других ресурсов, в том числе и интеллектуальных, и физических, и финансовых.

Именно поэтому решение задачи коммивояжера несет практическую пользу. Оно не просто настраивает сознание и интеллект человека на определенный – более эффективный с практической точки зрения лад, но и развивает абстрактное, логическое, пространственное и другие виды мышления, которыми мы все активно пользуемся в каждодневной жизни.

Безусловно, решить эту задачу может попытаться каждый, но без специальных знаний и навыков не стоит ждать каких-то серьезных продвижений (не зря же ее решением занимаются целые научные сообщества!). Однако потренироваться вполне можно.

Для этого у вас есть прекрасная возможность пройти нашу бесплатную онлайн-программу «Нейробика», некоторые задания из которой включают в себя элементы задачи коммивояжера. Всего же в ней представлено более 20 интересных заданий, направленных на развитие мышления. Попробуйте – думаем, что вам понравится этот курс.

Задача коммивояжёра

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

Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-сложных задач.

Методы решения Править

Простейшие Править

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

Задача коммивояжёра есть NP-полная задача. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

Метод ветвей и границ Править

Для решения задачи коммивояжёра предложен в 1963 году группой авторов (Дж. Литл, К. Мурти, Д. Суини, К.Кэрол). [1]

Литература Править

  • Ананий В. Левитин.Глава 3. Метод грубой силы: Задача коммивояжера // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М .: «Вильямс», 2006. — С. 159-160. — ISBN 0-201-74395-7. (см. ISBN )


  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн.Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М .: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1. (см. ISBN )

Задача коммивояжера

Задача коммивояжера считается классической задачей дискретной оптимизации. Для ее решения были применены все известные методы поиска экстремумов функций на конечных множествах: целочисленное линейное программирование, в частности, метод отсечения, динамическое программирование, схема ветвей и границ. Однако только метод ветвей и границ, в полной мере продемонстрированный именно на этой задаче, дал возможность решать ее практически приемлемого размера за приемлемое время. Поэтому далее будет изложен только этот метод и в той реализации, которая была предложена Литлем и его сотрудниками в 1963 году [17].

Задача путешествующего продавца (коммивояжера) была сформулирована нами ранее (гл. 5, п.5.3) как задача, в которой необходимо найти оптимальный маршрут объезда п городов продавцом, побывать в каждом из них ровно 1 раз и вернуться в исходный город выезда. Такая постановка является собирательной для многих практически важных задач, которые могут быть сформулированы, как задача коммивояжера. Это, например, задачи развозки грузов из центральной базы потребителям, сбора мусора из городских контейнеров, составления маршрута школьного автобуса для доставки детей в школу, определения порядка загрузки химического реактора при циклическом производстве п продуктов в фармацевтической промышленности

и целый ряд других задач.

В том случае, когда город выезда продавца указан, а путем перенумерации в качестве такого города всегда можно определить город п, всего, как было показано выше (гл. 6, п. 6.1), необходимо сформировать (п — 1)! маршрутов объезда городов, чтобы выбрать лучший из них. Когда же выезд может быть осуществлен из любого города, согласно правилу умножения для определения лучшего маршрута, необходимо рассмотреть (п-)п — п замкнутых маршрутов.

Стоимости переезда из города в город в данной задаче принято задавать квадратной матрицей С = си , / = 1, 2. п, у = 1, 2. п, в которой строки — это номера городов выезда, а столбцы — номера городов въезда.

Таким образом, элемент си матрицы С определяет стоимость переезда продавца из города / в город у. При этом элементы си, / = у, т. е. элементы главной диагонали матрицы С полагаются равными °°, как подтверждение того факта, что переезд из города /’ в город /’ не может быть осуществлен.

Каждый выбранный замкнутый маршрут объезда городов представляет собой последовательность их номеров, т. е. перестановку п чисел л = (/,, /2, /,), определяющую некоторую

стоимость переезда с

Таким образом, в задаче коммивояжера на множестве перестановок мощностью п необходимо найти такую циклическую перестановку п = (/,, /2, . /’„, /,), которая бы определяла минимальную стоимость объезда.

Рассмотрим следующий пример. Заданы четыре города и мат

рица стоимости С =

л, = (1, 2, 3, 4, 1). Тогда стоимость объезда будет равна с,3 + с32 + + с244, =3 + 5 + 3+10 = 21. Другая перестановка, например, тг2 = (2, 3, 1, 4, 2) даст стоимость с2331 +с,4 + с42 = 1 + 4 +8 + 5 = = 18, что меньше стоимости объезда, определенной перестановкой 71, .

Обратим внимание на то, что при определении стоимости в матрице С из каждой ее строки и каждого столбца берется ровно один элемент. Это подтверждает тот факт, что продавец въезжает в один и тот же город ровно один раз.

Различают несколько разновидностей задачи коммивояжера. Они порождаются свойствами элементов матрицы стоимости С и отношениями между этими элементами.

Если расстояние из города / в город у и наоборот из города у в город /’ одинаково для /’ = 1, 2, . п, у = 1, 2, . п, задача характеризуется симметричной матрицей расстояний. Например, еле-

оо дующая матрица С =

симметричная. Когда же эти рас-

стояния различны, задача коммивояжера с соответствующей матрицей стоимости С называется несимметричной.

Когда для любой тройки городов /, у, к справедливо условие С и + С ]к — С ‘к > говорят, что элементы матрицы С удовлетворяют условию треугольника. В противном случае это условие ей не свойственно.

Для всех разновидностей задач в алгоритмах их решения учитываются перечисленные особенности элементов матрицы С, так как, забегая вперед, следует сказать, что они существенно влияют на время решения задачи. Самая общая постановка задачи та, для которой матрица стоимости С несимметрична и для ее элементов не выполняется условие треугольника.

Кроме комбинаторной формулировки, задачу коммивояжера можно представить в терминах графов. Для этого каждому городу

Рис. 6.12. Мультиграф (7„, (а) и матрица стоимостей переезда С (б) для задачи коммивояжера с пятью городами

1, 2, . п поставим в соответствие вершину у,-,у 2, . уп. Каждую пару вершин V,-, у ., / ф у, / = 1, 2, . п, у = 1, 2 . /7 соединим парой ребер, указывающей на то, что возможен переезд как из города / в городу, так и наоборот, из города у в город /. Каждому ребру у отнесем вес си стоимость переезда из города /’ в городу. В результате получим взвешенный мультиграф (7т, содержащий п вершин и п 2 ребер. Для задачи с симметричной матрицей это будет обычный граф с п вершинами и я 2 /2 ребрами. В связи с тем что смысл задачи коммивояжера состоит в поиске замкнутого маршрута объезда городов, порождающего наименьшую стоимость объезда, на графе (7,„ это интерпретируется как поиск гамильтонова цикла наименьшей длины.

Ниже на рис. 6.12 для задачи с пятью городами приведен мультиграф и матрица стоимости переезда С.


На этом примере рассмотрим схему ветвления, ее стратегию и вычисление нижних границ оптимизируемой функции на подмножествах замкнутых маршрутов.

В алгоритме Литла все множество замкнутых маршрутов разбивается на два подмножества: одно из них содержит переезды из города /’ в городу, а другое не содержит таких переездов. В результате принятый метод разбиения формирует дерево решений задачи.

Выберем в качестве начальной вершины третью вершину, т. е. город 3, и рассмотрим переезд из него в город 5, хотя бы потому,

Рис. 6.13. Процесс разбиения множеств маршрутов в алгоритме Литла

что он самый дешевый из всех переездов. Тогда все множество замкнутых маршрутов будет разбито на два подмножества: одно из них <3, 5>будет содержать маршр уты, в которых обязателен переезд из города 3 в город 5, а другое <3, 5>не будет содержать таких

маршрутов. Дал ее для разбиения выбирается одно из подмножеств <3, 5>или <3, 5>и снова разбивается на два подмножества.

Этот процесс схематично изображен на рис. 6.13.

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

В качестве такого числа обычно берут минимальный элемент строки матрицы С. Пусть, например, Z(t) — стоимость некоторого маршрута t и си минимальный элемент некоторой строки /. Если вычесть этот элемент из всех остальных элементов этой строки матрицы С, а затем подсчитать стоимость нового маршрута Z ), то очевидно, что Z(t) — Z'(t) + си. Таким образом, си в данном случае — это нижняя граница для стоимости маршрута t.

Однако полученная таким путем граница является слишком неточной. Поэтому необходимо уточнение границы. Оно выполняется следующим образом. Поскольку в любой замкнутый маршрут продавца входит ровно один элемент каждой строки и каждого столбца матрицы С, определяющего стоимость переезда из города / в город у, и вычитание из строки / константы /? не изменяет оптимального маршрута продавца, то можно вычесть соответствующие константы из каждой строки матрицы С, сложить их и получить более точную нижнюю границу для выбранного маршрута.

Это вычитание и сложение констант и называется приведением матрицы С. Оно выполняется в два этапа. Сначала из каждой строки С вычитаются, а затем складываются минимальные элементы. После чего эта же процедура осуществляется для столбцов. В результате получают нижнюю границу

т = х mine,у + ^mine,у. При этом стоимость маршрута t

по строкам С по столбцам С

остается равной Z(t) = Z'(t) + h(t), где Z'(t) — стоимость этого маршрута для приведенной матрицы С. Ниже для рассматриваемого примера показано приведение исходной матрицы С.

Минимальный элемент первой строки сп = 25. Вычитаем его из остальных элементов строки.

Данную процедуру выполняем для оставшихся строк матрицы С. Затем повторяем ее для столбцов новой матрицы С 1 .

Задача 4. Задача коммивояжера

Коммивояжер должен объехать 7 городов. Выехав из одного города, он должен вернуться в него, заехав в каждый из других городов только один раз. Маршрут коммивояжера должен представлять собой замкнутый цикл без петель. Требуется найти кратчайший замкнутый путь коммивояжера. Карта расположения городов показана на рисунке. Расстояния между городами показаны в таблице.

Математическая модель данной транспортной задачи сводится к заданию двух матриц:

— число прохождений пути из города в город . Переменная принимает значение 1, если коммивояжер переезжает из города в город и 0 в противном случае.

— расстояния между городами (в общем случае матрица несимметрична, т.е. .

Кроме того, должны быть заданы два вектора:

— ресурс выезда (число выездов из каждого города);

— ресурс въезда (число въездов в каждый город).

Целевая функция определяет пройденный путь коммивояжера, который должен быть минимальным. Она равна скалярному произведению матриц:

Множество допустимых решений ограничивается ресурсами въезда и ресурсами выезда:

— число прохождений пути из города в город не может превышать заданный ресурс выезда из города ;


— число прохождений пути из города в город не может превышать заданный ресурс въезда в город .

Кроме того, для предупреждения петель вводятся дополнительные условия:

Для решения задачи средствами MS Excel нам нужно на листе книги представить дополнительно к матрице расстояний между городами матрицу числа прохождений пути из города в город и сформировать целевую функцию в виде суммы всех маршрутов коммивояжера. Подготовленные таблицы будут выглядеть следующим образом:

В первой матрице диагональные элементы, вообще говоря, равны нулю. Но мы поставили в них большие числа, чтобы предотвратить выезд из города и немедленный въезд в него. Во вторую таблицу вставлены следующие формулы:

В диалоговом окне «Параметры поиска решения» вводим ограничения въездов и выездов заданными ресурсами:

В столбце О приведены переходы коммивояжера между городами. Отсутствие петель обеспечивается вторым ограничением.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 10386 — | 7888 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Задача о коммивояжере (стр. 1 из 3)

Нижегородский Ордена Трудового Красного Знамени
Государственный Университет им. Н.И. Лобачевского

Кафедра информатики и вычислительной техники

Курсовая работа
по программному обеспечению

Решение задачи о коммивояжере

Нижний Новгород
1995 год

Оглавление

Постановка задачи. 4

Алгоритм решения. 4

Математическая модель задачи. 5

Описание программной реализации алгоритма. 6

Описание программного интерфейса. 9

Описание программы. 12

Введение

В настоящее время быстро развивается научно-техническая революция. Появившись в 40-х годах нашего столетия компьютеры и компьютерные технологии прошли за это время путь от ламповых систем с прямым заданием кодов операций до сверхбыстрых персональных компьютеров на монокристальной технологии, использующих при работе многопользовательские операционные системы с графическим интерфейсом. Наиболее бурное развитие компьютерных технологий произошло за последние 10-15 лет, после того как была разработана технология производства СБИС, а на их основе микрочипов. Также в начале 80-х годов начала развиваться концепция персональной ЭВМ, которая со временем выразилась в существовании двух наиболее распространенных аппаратных платформ: Macintosh (производится фирмой Apple, процессоры фирмы Motorola) и IBM PC (производится фирмой IBM, процессоры фирмы Intel).

Каждая из этих платформ имеет свою направленность и особенности. Компьютеры Macintosh в основном ориентированы на работу в глобальных сетях и обработку информации, как бы внешнего восприятия, то есть графической и звуковой. Их главными особенностями являются встроенная в ПЗУ (ROM) графическая операционная система и несовместимость различных моделей этой фирмы, однако за счет этого достигнут очень быстрый рост производительности процессоров и системы в целом.

Фирма IBM, в отличие от Apple, придерживается концепции открытой системы, что выражается в том, что, во-первых, IBM не имеет эксклюзивного права на производство и продажу IBM-совместимых компьютеров (их производит множество фирм, таких как Hewlett Packard, AT&T, Compaq и другие), а также полной совместимости поздних моделей с более ранними, что позволяло IBM долгое время удерживать рынок сбыта, несмотря на то, что в начале 90-х годов Macintosh-и заметно превосходили PC по производительности (сейчас, с появлением Pentium и PowerPC, Macintosh-и потеряли безоговорочное лидерство по производительности).


Персональные компьютеры сейчас в основном используются в четырех областях:

· обработка текстов и компьютерная верстка;

· хранение баз данных с возможностью быстрой их обработки;

· управление производственными процессами;

· анализ сложных процессов;

Также сейчас интенсивно развиваются еще несколько областей применения ПЭВМ, таких как компьютерные игры (в 1994 году 43% рынка программных продуктов составляли игровые программы), гео-информационные системы, обучающие системы и системы мультимедиа.

Программа данной курсовой работы входит в раздел «анализ сложных процессов». Данная область начала развиваться в середине 80-х годов, когда производительность ПЭВМ достигла достаточного уровня для обработки необходимых объемов информации в реальном масштабе времени, что позволило начать применение компьютеров в областях, связанных с контролем сложных процессов и их анализом. Одной из таких проблем стала оптимизация систем со многими неизвестными, когда некоторый параметр было необходимо свести к какому-либо значению или просто максимизировать.

Наиболее ярким и характерным примером применения задачи «О коммивояжере» стала оптимизация операций на конвейере: в 1984 году, после того как был проведен анализ последовательности и временных затрат на операции на конвейерах заводов компании «General Motors» и приняты рекомендованные меры, удалось увеличить общую производительность почти на 13% при неизменном числе рабочих и том же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые в то время являлись одними из самых производительных систем в мире. Просчет и оптимизация 200 основных и 87 вспомогательных операций занял около 230 часов. Считается, что это было первое коммерческое применение компьютерных технологий в области управления производством в целом.

Сейчас решение данной задачи необходимо во многих областях связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.

Поэтому данная проблема на современном этапе развития общества имеет не самое последнее по значимости место.

Постановка задачи

Классическая постановка задачи о коммивояжере выглядит следующим образом:

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

· маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

· в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.

Алгоритм решения

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

Общая схема метода такова (данная программная реализация):

Математическая модель задачи

N — число городов.

Ci j , i, j=1..N — матрица затрат, где Ci j — затраты на переход из i-го города в j-й.

Xi j — матрица переходов с компонентами:

Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода,

где i, j = 1..N и i¹j.

Ui — Uj + N × Xi j£ N-1, i, j = 1..N, i ¹ j. (4)

Доказательство, что модель (1-4) описывает задачу о коммивояжере:

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) — въезжает в каждый город только один раз; условие (4) — обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4). Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R

Илон Маск рекомендует:  Псевдокласс required
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL