Постановка задачи
Имется связанный граф. Необходимо найти оптимальный путь начинающийся и заканчивающийся в данной точке, также необходимо посетить подмножество вершин графа.
Для решения данной задачи, сначала найдём минимальные расстояния между всеми необходимыми для посещения вершинами и остальными с помощью алгоритма Дейкстры. Затем будем искать минимальную сумму расстояний изменяя порядок посещения вершин.
Эту задачу можно встретить и на практике. Например, поиск маршрута для полета квадрокоптера-курьера.
Реализация графа
Граф с N вершинами будет храниться в матрице размера NxN.
По умолчанию зададим граф показанный на рисунке ниже (это делается для облегчения отладки):
Graph.h:
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <iomanip>
using namespace std;
class Graph {
private:
int n; // количество вершин графа
int** data; // данные о ребрах графа: -1 - отсутствует ребро; >0 - расттояние между вершинами i и j
public:
Graph(int n); // создание графа с n вершинами
Graph(); // граф по умолчанию
int** Get_data() const; // данные о графе
int Get_n() const; // количество вершин графа
};
ostream& operator<<(ostream& os, const Graph& g);
#endif
Graph.cpp:
#include "Graph.h"
Graph::Graph() {
this->n = 5;
data = new int*[5];
for (int i = 0; i < 5; i++) {
data[i] = new int[5];
}
// граф по умолчанию
data[0][0] = 0; data[0][1] = 2; data[0][2] = -1; data[0][3] = 3; data[0][4] = -1;
data[1][0] =2; data[1][1] = 0; data[1][2] = 4; data[1][3] = 4; data[1][4] = -1;
data[2][0] = -1; data[2][1] = 4; data[2][2] = 0; data[2][3] = 5; data[2][4] = 6;
data[3][0] = 3; data[3][1] = 4; data[3][2] = 5; data[3][3] = 0; data[3][4] = -1;
data[4][0] = -1; data[4][1] = -1; data[4][2] = 6; data[4][3] = -1; data[4][4] = 0;
}
// создание графа с n вершинами
Graph::Graph(int n) {
this->n = n;
data = new int*[n];
for (int i = 0; i < n; i++) {
data[i] = new int[n];
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cout << "Input " << i << '-' << j << ": ";
cin >> data[i][j];
data[j][i] = data[i][j];
}
}
}
// данные о графе
int** Graph::Get_data() const {
int** d = new int*[n];
for (int i = 0; i < n; ++i) {
d[i] = new int[n];
for (int j = 0; j < n; ++j) {
d[i][j] = data[i][j];
}
}
return d;
}
// количество вершин графа
int Graph::Get_n() const { return n; }
// вывод графа
ostream& operator<<(ostream& os, const Graph& g) {
int** d = g.Get_data();
for (int i = 0; i < g.Get_n(); i++) {
for (int j = 0; j < g.Get_n(); j++) {
os << setw(4) << d[i][j] << ' ';
}
os << endl;
}
return os;
}
Реализация пути
Путь хранится в виде вектора, так как он представляет из себя последовательность вершин, также я храню длину всего пути. Реализуем функции добавления в конец пути одной вершины и другого пути (это будет использоваться дальше при переборе порядка вершин обхода).
Path.h:
#ifndef PATH_H
#define PATH_H
#include <iostream>
#include <set>
#include <vector>
using namespace std;
class Path {
private:
vector<int> path; // путь
int length; // длина пути
public:
Path(int start);
Path& operator= (const Path& p);
vector<int> Get_path() const; // путь
int Get_length() const; // длина пути
void push_back(int v, int l); // добавление вершины в конец
void push_back(Path p); // добавление пути в конец
};
ostream& operator<<(ostream& os, const Path& p);
#endif
Path.cpp:
#include "Path.h"
Path::Path(int start) {
path.push_back(start);
length = 0;
}
Path& Path::operator=(const Path& p) {
path = p.Get_path();
length = p.Get_length();
return *this;
}
// путь
vector<int> Path::Get_path() const { return path; }
// длина пути
int Path::Get_length() const { return length; }
// добавление вершины в конец
void Path::push_back(int v, int l) {
path.push_back(v);
length += l;
}
// добавление пути в конец
void Path::push_back(Path p) {
for (size_t i = 0; i < p.Get_path().size(); ++i) {
int last = path[path.size() - 1];
if (last != p.Get_path()[i]) {
path.push_back(p.Get_path()[i]);
}
}
length += p.Get_length();
}
ostream& operator<<(ostream& os, const Path& p) {
size_t n = p.Get_path().size();
for (size_t i = 0; i < n; i++) {
os << p.Get_path()[i] + 1;
if (i != n - 1) {
os << "->";
} else {
os << " (";
}
}
os << p.Get_length() << ')' << endl;
return os;
}
Алгоритм Дейкстры
Обозначим все вершины бесконечностью, это будет означать, что вершина ещё не посещена, а начальную 0. Очевидно, что расстояние до самой себя равно 0. Теперь найдем расстояние из исходной точки в соседние, затем отметим её. Далее на каждом шаге находим минимальную не отмеченную точку и находим сумму с соседними, не отмеченными и сравниваем ее со значением вершины, если полученное расстояние меньше, то заменяем его.
Реализация алгоритма Дейкстры и решения задачи коммивояжёра
Алгоритм Дейкстры мы уже разобрали, но при его выполнении я также сразу сохраняю кратчайший путь от данной вершины к другим. Если вес вершины оказался больше, чем новый, то кроме нового веса, мы также заменяем путь: он будет равен пути к предыдущей вершине плюс сама вершина.
Все пути я записываю в словарь, ключом является вершина, а значением массив путей (i-ый элемент соответсвует кротчайшему пути до (i+1)-ой вершины).
После выполнения алгоритма Дейкстры с помощью next_permutation я перебираю порядок посещения вершин и нахожу путь минимальной длины.
Solution.h:
#ifndef SOLUTION_H
#define SOLUTION_H
#include "Graph.h"
#include "Path.h"
#include <iostream>
#include <limits>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
class Solution {
private:
Graph graph; // граф
public:
Solution(const Graph& g);
Path* Dijkstra(int v, Path* data); // алгоритм Дейкстры
Path calc(vector<int> v, int start); // вычисление оптимального пути
};
#endif
Solution.cpp:
#include "Solution.h"
Solution::Solution(const Graph& g) {
graph = g;
}
// алгоритм Дейкстры
Path* Solution::Dijkstra(int v, Path* data) {
data = (Path*)calloc(graph.Get_n(), sizeof(Path)); //пути от вершины v до других вершин графа
int distaces[graph.Get_n()]; //минимальное расстояние от вершины v до других
int out[graph.Get_n()]; //посещенные вершины
for (int i = 0; i < graph.Get_n(); ++i) {
if (i == v) {
distaces[i] = 0;
data[i] = Path(v);
} else {
distaces[i] = numeric_limits<int>::max();
}
out[i] = 0;
}
int min = numeric_limits<int>::max(), index = -1;
do {
min = numeric_limits<int>::max();
for (int i = 0; i < graph.Get_n(); ++i) {
if ((out[i] == 0) && (distaces[i] < min)) {
min = distaces[i];
index = i;
}
}
if (min != numeric_limits<int>::max()) {
for (int i = 0; i < graph.Get_n(); ++i) {
if (graph.Get_data()[index][i] > 0) {
int temp = min + graph.Get_data()[index][i];
if (temp < distaces[i]) {
distaces[i] = temp;
data[i] = data[index];
data[i].push_back(i, graph.Get_data()[index][i]);
}
}
}
out[index] = 1;
}
} while (min < numeric_limits<int>::max());
return data;
}
// вычисление оптимального пути
Path Solution::calc(vector<int> v, int start) {
map<int, Path*> distaces;
Path* temp = (Path*)calloc(graph.Get_n(), sizeof(Path));
temp = Dijkstra(start, temp);
distaces[start] = temp;
for (size_t i = 0; i < v.size(); ++i) {
temp = Dijkstra(v[i], temp);
distaces[v[i]] = temp;
}
Path p = Path(start);
sort(v.begin(), v.end());
for (size_t i = 0; i < v.size(); ++i) {
int last = p.Get_path()[p.Get_path().size() - 1];
p.push_back(distaces[last][v[i]]);
}
int last = p.Get_path()[p.Get_path().size() - 1];
p.push_back(distaces[last][start]);
next_permutation(v.begin(), v.end());
do {
Path temp = Path(start);
for (size_t i = 0; i < v.size(); ++i) {
int last = temp.Get_path()[temp.Get_path().size() - 1];
temp.push_back(distaces[last][v[i]]);
if (temp.Get_length() > p.Get_length())
break;
}
int last = temp.Get_path()[temp.Get_path().size() - 1];
temp.push_back(distaces[last][start]);
if (temp.Get_length() < p.Get_length()) {
p = temp;
}
} while (next_permutation(v.begin(), v.end()));
return p;
}
Итоги
Данное решение далеко от идеального, необходимо как минимум сделать многопоточность при переборе порядка вершин. Также в дальнейшем я оптимизирую алгоритм Дейкстры, уменьшив его сложность (O(n2)) с помощью Фибоначчиевой кучи (O(n log(n))).
Проект задачи Вы можете скачать на GitHub.