Задача о коммивояжере.
Имеются n городов, расстояния между которыми заданы; коммивояжеру необходимо выйти из какого-то города, посетить остальные n-1 город точно по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).
Входные данные:
10
-1 32 19 33 22 41 18 15 16 31
32 -1 51 58 27 42 35 18 17 34
19 51 -1 23 35 49 26 34 35 41
33 58 23 -1 33 37 23 46 46 32
22 27 35 33 -1 19 10 23 23 9
41 42 49 37 19 -1 24 42 42 10
18 35 26 23 10 24 -1 25 25 14
15 18 34 46 23 42 25 -1 1 32
16 17 35 46 23 42 25 1 -1 32
31 34 41 32 9 10 14 32 32 -1
Выходные данные:
Если идти из нулевого города, то 158.
Моя идея:
Есть минимальная сумма, если какое-то решение уже будет больше, чем эта минимальная сумма, то выходим из данного цикла, так как нужно минимальное решение. Поскольку нужно, чтобы прошли по всем городам, то создаём отдельный булевый вектор, в котором будем помечать уже пройденные населённые пункты. Дополнительно для откладки я стал выводить, в какие станции направится коммивояжёр.
Ответ моей программы к представленным входным данным:
168
2 3 6 5 9 4 1 8 7 0
#include <iostream>
#include <vector>
#include <fstream>
void minimumWay(std::vector<std::vector<int>>&board, std::vector<bool>& checker,
std::vector<int>& now, std::vector<int>& best,
long long int sum, long long int& sumMin, int number, int count)
{
if (sum < sumMin)
{
if (count == board[0].size() + 1)
{
best = now;
sumMin = sum;
}
else if (count == board[0].size())
{
sum += board[number][0];
minimumWay(board, checker, now, best, sum, sumMin, number, count + 1);
}
else
{
for (int i = 0; i < board[0].size(); i++)
{
if (board[number][i] > 0 && checker[i] == false)
{
now[count - 1] = i;
checker[i] = true;
minimumWay(board, checker, now, best,
sum + board[number][i], sumMin, i, count + 1);
now[count - 1] = -1;
checker[i] = false;
}
}
}
}
}
int main()
{
std::ifstream fin("C:\\Users\\User\\Documents\\Files\\INPUT3.txt");
int in = 0, count = 0;
fin >> count;
std::vector<std::vector<int>>board(count, std::vector<int>(count));
int x = 0, y = 0;
while (fin >> in)
{
board[x][y] = in;
y++;
if (y == count)
{
x++;
y = 0;
}
}
fin.close();
std::vector<bool> checker(count);
std::vector<int> now(count);
std::vector<int> best(count);
long long int sumMin = 900000000000000;
int start = 0;
std::cout << "Input a number of city where the salesman goes ";
std::cin >> start;
checker[start] = true;
minimumWay(board, checker, now, best, 0, sumMin, start, 1);
best[best.size() - 1] = start;
std::cout << sumMin << '\n';
for (int i = 0; i < best.size(); i++)
{
std::cout << best[i] << " ";
}
std::cout << '\n';
}
