โปรแกรม C++ แก้ปัญหา Traveling Salesman สำหรับกราฟไม่มีน้ำหนัก

Traveling Salesman Problem ใช้คำนวณเส้นทางสั้นที่สุดเพื่อเยี่ยมชมเมืองทั้งหมดและกลับมายังเมืองต้นทาง ใช้หาเส้นทางสั้นที่สุดครอบคลุมโหนดทั้งหมดของกราฟ

นี่คือโปรแกรมหาเส้นทางสั้นที่สุดของกราฟไม่มีน้ำหนัก (unweighted graph)

อัลกอริทึม

เริ่มต้น
  กำหนดตัวแปร vr = 4 แบบ global
  ประกาศฟังก์ชัน integer TSP สำหรับ Traveling Salesman Problem
  รับพารามิเตอร์กราฟ grph[][] เป็นเมทริกซ์ 2D และตัวแปร p
  ประกาศตัวแปร ver ชนิด vector
  สำหรับ (int i = 0; i < vr; i++)
    ถ้า (i != p) แล้ว
      เรียก push_back(i) เก็บโหนดทั้งหมดยกเว้นโหนดต้นทาง
    จบถ้า
  จบลูป
  กำหนด m_p = INT_MAX เก็บน้ำหนักขั้นต่ำ
  ทำ
    ประกาศ cur_pth, k ชนิด integer
      กำหนด cur_pth = 0
      กำหนด k = p
    สำหรับ (int i = 0; i < ver.size(); i++)
      cur_pth += grph[k][ver[i]]
      k = ver[i]
    จบลูป
    cur_pth += grph[k][p]
    m_p = min(m_p, cur_pth) // อัปเดตน้ำหนักขั้นต่ำ
  ในขณะที่ (next_permutation(ver.begin(), ver.end()))
  คืนค่า m_p
  ประกาศกราฟ grph[][] ชนิด integer
    กำหนดค่า grph[][]
  ประกาศตัวแปร p ชนิด integer
    กำหนด p = 0
  พิมพ์ "The result is: "
  พิมพ์ค่าที่คืนจาก TSP()
สิ้นสุด

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

#define vr 4

int TSP(int grph[][vr], int p) {
    vector<int> ver;
    for (int i = 0; i < vr; i++)
        if (i != p)
            ver.push_back(i);
    int m_p = INT_MAX;
    do {
        int cur_pth = 0;
        int k = p;
        for (int i = 0; i < ver.size(); i++) {
            cur_pth += grph[k][ver[i]];
            k = ver[i];
        }
        cur_pth += grph[k][p];
        m_p = min(m_p, cur_pth);
    } while (next_permutation(ver.begin(), ver.end()));
    return m_p;
}

int main() {
    int grph[][vr] = {
        {0, 5, 10, 15},
        {5, 0, 20, 30},
        {10, 20, 0, 35},
        {15, 30, 35, 0}
    };
    int p = 0;
    cout << "\nThe result is: " << TSP(grph, p) << endl;
    return 0;
}

ผลลัพธ์

The result is: 75