Рубрики

Реализация задач коммивояжера с использованием BackTracking

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

Обратите внимание на разницу между гамильтоновым циклом и TSP. Задача цикла Гамильтонина — найти тур, который посещает каждый город ровно один раз. Здесь мы знаем, что гамильтоновы туры существуют (поскольку граф полон), и на самом деле существует много таких туров, проблема состоит в том, чтобы найти минимальный вес гамильтонова цикла.
Например, рассмотрим график, показанный на рисунке. Тур TSP на графике: 1 -> 2 -> 4 -> 3 -> 1. Стоимость тура составляет 10 + 25 + 30 + 15, что составляет 80.

Проблема известная NP трудная проблема. Не существует полиномиального времени для решения этой проблемы.

Output of Given Graph:
Minimum weight Hamiltonian Cycle : 10 + 20 + 30 + 15 = 80

Подход: в этом посте обсуждается реализация простого решения.

  • Рассмотрим город 1 (скажем, 0-й узел) в качестве начальной и конечной точки. Поскольку маршрут является циклическим, мы можем рассматривать любую точку как отправную точку.
  • Начните обход от источника к соседним узлам способом dfs.
  • Рассчитайте стоимость каждого обхода и следите за минимальными затратами и продолжайте обновлять значение хранимой величины минимальной стоимости.
  • Верните перестановку с минимальными затратами.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

#define V 4

  
// Функция для нахождения минимального веса гамильтонова цикла

void tsp(int graph[][V], vector<bool>& v, int currPos,

         int n, int count, int cost, int& ans)

{

  

    // Если достигнут последний узел и есть ссылка

    // к начальному узлу, т.е. к источнику

    // сохранить минимальное значение от общей стоимости

    // прохождения и "ответ"

    // Наконец возвращаемся, чтобы проверить больше возможных значений

    if (count == n && graph[currPos][0]) {

        ans = min(ans, cost + graph[currPos][0]);

        return;

    }

  

    // BACKTRACKING STEP

    // Цикл для обхода списка смежности

    // узла currPos и увеличение количества

    // на 1 и стоимость по графику [currPos] [i] значение

    for (int i = 0; i < n; i++) {

        if (!v[i] && graph[currPos][i]) {

  

            // Пометить как посещенные

            v[i] = true;

            tsp(graph, v, i, n, count + 1,

                cost + graph[currPos][i], ans);

  

            // Пометить i-й узел как не посещенный

            v[i] = false;

        }

    }

};

  
// Код драйвера

int main()

{

    // n - количество узлов, т. е. V

    int n = 4;

  

    int graph[][V] = {

        { 0, 10, 15, 20 },

        { 10, 0, 35, 25 },

        { 15, 35, 0, 30 },

        { 20, 25, 30, 0 }

    };

  

    // логический массив для проверки наличия узла

    // посещали или нет

    vector<bool> v(n);

    for (int i = 0; i < n; i++)

        v[i] = false;

  

    // Пометить 0-й узел как посещенный

    v[0] = true;

    int ans = INT_MAX;

  

    // Находим минимальный вес гамильтонова цикла

    tsp(graph, v, 0, n, 1, 0, ans);

  

    // ans - гамильтонов цикл

    cout << ans;

  

    return 0;

}

Джава

// Java реализация подхода

class GFG 

{

  

    // Функция поиска минимального веса

    // Гамильтонов цикл

    static int tsp(int[][] graph, boolean[] v, 

                   int currPos, int n, 

                   int count, int cost, int ans) 

    {

  

        // Если достигнут последний узел и есть ссылка

        // к начальному узлу, т.е. к источнику

        // сохранить минимальное значение от общей стоимости

        // прохождения и "ответ"

        // Наконец возвращаемся, чтобы проверить больше возможных значений

        if (count == n && graph[currPos][0] > 0

        {

            ans = Math.min(ans, cost + graph[currPos][0]);

            return ans;

        }

  

        // BACKTRACKING STEP

        // Цикл для обхода списка смежности

        // узла currPos и увеличение количества

        // на 1 и стоимость на график [currPos, i] значение

        for (int i = 0; i < n; i++) 

        {

            if (v[i] == false && graph[currPos][i] > 0

            {

  

                // Пометить как посещенные

                v[i] = true;

                ans = tsp(graph, v, i, n, count + 1,

                          cost + graph[currPos][i], ans);

  

                // Пометить i-й узел как не посещенный

                v[i] = false;

            }

        }

        return ans;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        // n - количество узлов, т. е. V

        int n = 4;

  

        int[][] graph = {{0, 10, 15, 20},

                         {10, 0, 35, 25},

                         {15, 35, 0, 30},

                         {20, 25, 30, 0}};

  

        // логический массив для проверки наличия узла

        // посещали или нет

        boolean[] v = new boolean[n];

  

        // Пометить 0-й узел как посещенный

        v[0] = true;

        int ans = Integer.MAX_VALUE;

  

        // Находим минимальный вес гамильтонова цикла

        ans = tsp(graph, v, 0, n, 1, 0, ans);

  

        // ans - гамильтонов цикл

        System.out.println(ans);

    }

}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 реализация подхода

V = 4

answer = []

  
# Функция поиска минимального веса
# Гамильтонов цикл

def tsp(graph, v, currPos, n, count, cost):

  

    # Если достигнут последний узел и он имеет

    # ссылка на начальный узел т.е.

    # источник тогда держи минимум

    # значение из общей стоимости

    # обход и "ответ"

    # Наконец вернитесь, чтобы проверить

    # больше возможных значений

    if (count == n and graph[currPos][0]):

        answer.append(cost + graph[currPos][0])

        return

  

    # BACKTRACKING STEP

    # Цикл для обхода списка смежности

    # узла currPos и увеличение количества

    # на 1 и стоимость по графику [currPos] [i] значение

    for i in range(n):

        if (v[i] == False and graph[currPos][i]):

              

            # Отметить как посещенные

            v[i] = True

            tsp(graph, v, i, n, count + 1

                cost + graph[currPos][i])

              

            # Пометить i-й узел как не посещенный

            v[i] = False

  
# Код драйвера

  
# n - количество узлов, т. е. V

if __name__ == '__main__':

    n = 4

    graph= [[ 0, 10, 15, 20 ],

            [ 10, 0, 35, 25 ],

            [ 15, 35, 0, 30 ],

            [ 20, 25, 30, 0 ]]

  

    # Логический массив, чтобы проверить, является ли узел

    # был посещен или нет

    v = [False for i in range(n)]

      

    # Отметить 0-й узел как посещенный

    v[0] = True

  

    # Найти минимальный вес гамильтонова цикла

    tsp(graph, v, 0, n, 1, 0)

  

    # ans - минимальный вес гамильтонова цикла

    print(min(answer))

  
# Этот код предоставлен Мохит Кумар

C #

// C # реализация подхода

using System;

  

class GFG

{

  
// Функция для нахождения минимального веса гамильтонова цикла

static int tsp(int [,]graph, bool []v, int currPos,

        int n, int count, int cost, int ans)

{

  

    // Если достигнут последний узел и есть ссылка

    // к начальному узлу, т.е. к источнику

    // сохранить минимальное значение от общей стоимости

    // прохождения и "ответ"

    // Наконец возвращаемся, чтобы проверить больше возможных значений

    if (count == n && graph[currPos,0] > 0) 

    {

        ans = Math.Min(ans, cost + graph[currPos,0]);

        return ans;

    }

  

    // BACKTRACKING STEP

    // Цикл для обхода списка смежности

    // узла currPos и увеличение количества

    // на 1 и стоимость на график [currPos, i] значение

    for (int i = 0; i < n; i++) {

        if (v[i] == false && graph[currPos,i] > 0)

        {

  

            // Пометить как посещенные

            v[i] = true;

            ans = tsp(graph, v, i, n, count + 1,

                cost + graph[currPos,i], ans);

  

            // Пометить i-й узел как не посещенный

            v[i] = false;

        }

    }

    return ans;

}

  
// Код драйвера

static void Main()

{

    // n - количество узлов, т. е. V

    int n = 4;

  

    int [,]graph = {

        { 0, 10, 15, 20 },

        { 10, 0, 35, 25 },

        { 15, 35, 0, 30 },

        { 20, 25, 30, 0 }

    };

  

    // логический массив для проверки наличия узла

    // посещали или нет

    bool[] v = new bool[n];

  

    // Пометить 0-й узел как посещенный

    v[0] = true;

    int ans = int.MaxValue;

  

    // Находим минимальный вес гамильтонова цикла

    ans = tsp(graph, v, 0, n, 1, 0, ans);

  

    // ans - гамильтонов цикл

    Console.Write(ans);

  
}
}

  
// Этот код предоставлен mits

Выход:

80

Рекомендуемые посты:

Реализация задач коммивояжера с использованием BackTracking

0.00 (0%) 0 votes