Как внедрить коммивояжера с неполной графикой? - PullRequest
Новая
       45

Как внедрить коммивояжера с неполной графикой?

0 голосов
/ 14 мая 2019

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

Пример 1: https://www.autonomousrobotslab.com/uploads/5/8/4/4/58449511/cs302_final_preparation_treasure_hunter.pdf

Пример 2: https://www.autonomousrobotslab.com/uploads/5/8/4/4/58449511/cs302_final_preparation_tsp.pdf

Однако, подавляющее большинство видео / кода, на которые я смотрел, решают tsp с полным графиком, как в следующем примере: https://www.geeksforgeeks.org/traveling-salesman-problem-tsp-implementation/

Оба примера, которые мой профессор хочет, чтобы мы могли решить, являются примерами неполных графиков. Есть ли какие-то изменения, которые можно было бы внести в реализацию на geeksforgeeks, чтобы учесть неполный граф? Я думал о том, чтобы просто поместить нули в матрицу смежности, где вершины не связаны, но код в geeksforgeeks предполагает, что все вершины связаны с каждой другой вершиной, а в неполном графе это не так. Я предполагаю, что мне нужен какой-то способ найти все перестановки вершин, которые связаны, вместо нахождения всех перестановок вершин в целом.

1 Ответ

0 голосов
/ 14 мая 2019

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

int main(int argc, char** argv) {

    const int NUM_NODES = 5;

    int adjacencyMatrix[NUM_NODES][NUM_NODES] = {
        {0, 10, 16, 12, 8},
        {10, 0, 15, INT_MAX, 20},
        {16, 15, 0, 10, INT_MAX},
        {12, INT_MAX, 10, 0, 8},
        {8, 20, INT_MAX, 8, 0}
    };
    int min;
    int bestScore = INT_MAX;
    int currentScore = 0;
    vector<int> bestTrip;
    vector<int> trip;
    int legCost = 0;

    //set a default trip
    for (int i = 0; i < NUM_NODES; ++i) {
        trip.insert(trip.end(), i);
    }
    //insert trip back home
    trip.insert(trip.end(), 0);

    while (next_permutation(trip.begin() + 1, trip.end() - 1)) {
        currentScore = 0;
        for (int i = 0; i < NUM_NODES; i++) {
            legCost = adjacencyMatrix[trip[i]][trip[i + 1]];
            if (legCost == INT_MAX || currentScore == INT_MAX) {
                currentScore = INT_MAX;
            } else {
                currentScore += legCost;
            }
        }
        if (currentScore < bestScore) {
            bestScore = currentScore;
            bestTrip = trip;
        }
    }

    cout << "best trip: ";
    for (int i = 0; i < NUM_NODES + 1; i++) {
        cout << bestTrip[i];
    }
    cout << endl;
    cout << "best score:" << bestScore << endl;
    return 0;
}
...