ТГиК-2019-Лекция-16.12.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

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

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

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

Пусть есть взвешенный граф \( G=<V,E>\) и функция, которая задаёт рёбрам вес \( \omega : E \longrightarrow \mathbb{R} \). Гамильтонов цикл - это маршрут, включающий ровно по одному разу каждую вершину графа. Решение задачи коммивояжёра — это нахождение гамильтонова цикла минимального веса в взвешенном графе.

Существует несколько подходов к решению задачи коммивояжёра.

рис.1. Иллюстрация к подходу 1

Подход 1. Динамическое программирование

Пусть мы находимся в вершине \(u\). Если цикл - оптимальный, то пусть из \(u\) через \(S_2\) в \(v_0\) - кратчайший. Если это не так, цикл не оптимален.

Введем функцию \(F\) - стоимость прохода из \(u\) через \(S_2\) в \(v_0\), то есть ее аргументами будет вершина и множество. Определим функцию следующим образом: стоимость прохода из вершины \(u\) через вершины \(S_2\) - это наименьшая сумма веса пути из вершины \(u\) в вершину \(z \in S_2\) и значения функции \(F(z, S_2 \backslash \left \{ z \right \} )\), где \(z\) - это такая вершина из \(S_2\), что данная сумма для неё является наименьшей\[F(u;S_2) = min [ \omega ( \left \{ u,z \right \} ) + F(z, S_2 \backslash \left \{ z \right \} ) ] \]

Очевидно, что путь из вершины \(u\) в вершину \(v_0\) через пустое множество вершин - это просто путь из \(u\) в \(v_0\)\[F(u, \varnothing ) = \omega ({u, v_0}) \]

Таким образом, для введённых нами условий задачу коммивояжёра можно переформулировать следующим образом: нам требуется пройти от вершины \(v_0\) в вершину \(v_0\) по всем вершинам из множества \(V\). Запишем это с помощью введённой функции\[F(v_0; V \backslash \left \{ v_0 \right \} ) \]

Сложность такого алгоритма \(O(n^2 2^n)\)

Подход 2. Метод ветвей и границ (branch & bound)

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

//s - множество вершин
//c - текущая стоимость
//n - количество вершин
//p - текущая вершина
bestCost = inf;

def bb (n, p, s, c) 
 if len(p) == n: 
   bestCost= min(bestCost, C); 
 for next in range (n)
   if next in S: 
    continue; 

 newC= c + weight(p[-1], next); 
 if newC > bestCost : 
   continue

 s.add(next); 
 bb(n,p+[next], s, newC); 
 s.remove(next);

//сам вызов процедуры в теле программы
bb(n, [v0], s, 0);

Сложность \(O(n!n^2)\)

Изоморфизм

Изоморфизм графов \( G_1 \sim G_2\) - это биекция \( \varphi : V_1 \longleftrightarrow V_2 : ( \left \{ v, z \right \} \Longleftrightarrow \left \{ \varphi (v), \mbox{ } \varphi (z) \right \} \in E_2 ) \)

Для изоморфизма важно понятие инварианта. Инвариант (глобальный) - это некоторая характеристика графа. Инвариант задаётся следующим образом: если \( G_1 \sim G_2 \Longrightarrow f(G_1) = f(G_2) \), то \(f\) - инвариант. Например, у изоморфных графов инвариантами являются число вершин и число дуг/ребер (\(f(G)=|V|, f(G)=|E| \)). Также, например, это \(f=const \)

Кроме того, есть локальный инвариант - это характеристика подмножества вершин или конкретной вершины.

рис.2. Жадный алгоритм и задача коммивояжёра

Жадный алгоритм

Жадный алгоритм (англ. greedy algorithm) — это алгоритм, который на каждом шагу делает локально лучший выбор в надежде, что итоговое решение будет оптимальным.

В случае задачи коммивояжёра жадный алгоритм можно назвать "nearest neighbor". Принцип алгоритма состоит в том, чтобы идти в ближайший город от текущего. Однако жадный алгоритм не даёт оптимального решения: может получиться и обычный путь, а может получиться и искомый нами кратчайший путь (рис.2).

Матроиды

Пусть \(X\) - конечное множество (будем называть его носитель); \(U\) - некоторая система подмножеств такая, что \(U \subseteq 2^X \). Тогда пара \(<X, U> \) - матроид.

Обязательно должны выполняться следующие условия:

1) \( \varnothing \in U \)

2) \( A \in U, B \subseteq A \Longrightarrow B \in U \)

3) \( A, B \in U, |B|>|A| \Longrightarrow \exists x \in B \backslash A : A \cup \left \{ x \right \} \in U \)

Простейшим примером является матричный матроид. В матричном матроиде \(U\) - линейно независимые множества векторов из \(X\). Проверим выполнение условий:

1) \( \varnothing \in U \)

Множество, в котором нет векторов, является линейно независимым

2) \( A \in U, B \subseteq A \Longrightarrow B \in U \)

Если из множества линейно независимых векторов убрать один вектор, множество не станет линейно зависимым

3) \( A, B \in U, |B|>|A| \Longrightarrow \exists x \in B \backslash A : A \cup \left \{ x \right \} \in U \)

То есть \( \exists x \in B \mbox{: } x \not\in A \). Тогда множество \( A \cup \left \{ x \right \} \) линейно-независимо по определению линейной оболочки.