@fjaerj12

Какая ошибка в решении задачи о коммивояжёре методом перебора с возвратом?

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

Имеются 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';
}
  • Вопрос задан
  • 83 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Ошибки какой-то в коде не вижу.

Попробуйте переписать с помощью std::next_permutation для перебора всех перестановок. Просто для сравнения и проверки теста - вдруг там опечатка.

Оно будет работать медленнее рекурсивного перебора из-за отсутствия отсечений, да и одно и то же решение с циклическим сдвигом будет получатся n раз, но для 10 городов должно быстро отработать. Но зато код будет совсем простой: один цикл, как в примере из документации перебирает все перестановки от 0 до n-1. Внутри вы циклом эти числа берете как индексы городов и суммируете расстояния между ними + расстояние между последним до начального. И запоминаете, если сумма меньше известного минимума. Если и там 168 получится - в тесте опечатка.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы