Travelling Salesman Problem: สุดยอดคำถามแห่งนักเดินทางในโลกของการเขียนโปรแกรม

ในโลกที่เราทุกคนเป็นนักเดินทาง ปัญหาที่ต้องพบเจอบ่อยครั้งคือการเดินทางให้ครอบคลุมทุกจุดที่ต้องการไปในเวลาน้อยที่สุด และนี่คือหัวใจสำคัญของ "Travelling Salesman Problem" (TSP) หรือ "ปัญหานักขายเร่" ซึ่งเป็นหนึ่งในปัญหาที่ได้รับความนิยมและเป็นที่ท้าทายสำหรับนักวิทยาการคอมพิวเตอร์ตั้งแต่อดีตจนถึงปัจจุบัน

ความหมายและวัตถุประสงค์ของ Algorithm Travelling Salesman Problem

Algorithm TSP มีจุดประสงค์เพื่อหาเส้นทางที่มีระยะทางรวมน้อยที่สุดที่นักขายหรือ "Salesman" สามารถเดินทางไปยังจำนวนเมือง X โดยที่จะต้องผ่านทุกเมืองเพียงครั้งเดียวแล้วกลับมายังจุดเริ่มต้น หลักการนี้สามารถนำไปใช้กับหลายสถานการณ์ อาทิเช่น การเดินทางของรถขนส่งสินค้าที่ต้องไปยังจุดจำหน่ายต่างๆ เพื่อให้ได้ค่าใช้จ่ายในการเดินทางที่ต่ำที่สุด

ตัวอย่าง Code ในภาษา Java

import java.util.ArrayList;

public class TravellingSalesman {

    private final int numberOfCities;
    private final int[][] distanceMatrix;
    private ArrayList bestPath;
    private int bestPathLength = Integer.MAX_VALUE;

    public TravellingSalesman(int numberOfCities, int[][] distanceMatrix) {
        this.numberOfCities = numberOfCities;
        this.distanceMatrix = distanceMatrix;
    }

    public void findShortestPath() {
        ArrayList currentPath = new ArrayList<>();
        boolean[] visited = new boolean[numberOfCities];
        currentPath.add(0); // เริ่มต้นที่เมือง 0
        visited[0] = true;

        findBestRoute(0, currentPath, visited, 0);
    }

    private void findBestRoute(int currentCity, ArrayList currentPath, boolean[] visited, int currentPathLength) {
        if (currentPath.size() == numberOfCities) {
            currentPathLength += distanceMatrix[currentCity][0]; // กลับไปยังจุดเริ่มต้น
            if (currentPathLength < bestPathLength) {
                bestPathLength = currentPathLength;
                bestPath = new ArrayList<>(currentPath);
            }
            return;
        }

        for (int city = 0; city < numberOfCities; city++) {
            if (!visited[city]) {
                visited[city] = true;
                currentPath.add(city);
                findBestRoute(city, currentPath, visited, currentPathLength + distanceMatrix[currentCity][city]);
                visited[city] = false;
                currentPath.remove(currentPath.size() - 1);
            }
        }
    }

    public ArrayList getBestPath() {
        return bestPath;
    }

    public int getBestPathLength() {
        return bestPathLength;
    }

    public static void main(String[] args) {
        int numberOfCities = 4;
        int[][] distanceMatrix = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        TravellingSalesman tsp = new TravellingSalesman(numberOfCities, distanceMatrix);
        tsp.findShortestPath();
        System.out.println("เส้นทางที่ดีที่สุดคือ: " + tsp.getBestPath() + " ด้วยระยะทาง " + tsp.getBestPathLength());
    }
}

Code ดังกล่าวสาธิตการใช้งาน Algorithm TSP ด้วยการใช้ brute force ในการหาเส้นทางที่สั้นที่สุด ในการทำงานกับเมืองจำนวนน้อย เนื่องจาก complexity ที่สูงมากจึงไม่เหมาะกับการใช้งานในปัญหาที่มีเมืองจำนวนมาก

Usecase ในโลกจริง

ปัญหา TSP ไม่ได้มีเพียงแค่ในสถานการณ์ของนักขายเร่เท่านั้น แต่ยังครอบคลุมถึงด้านการตระเวนบริการ, การกำหนดเส้นทางของโดรนในงานสำรวจ, และแม้กระทั่งด้านการวางผังผังเมืองหรือการจัดวางหุ่นยนต์ในโรงงาน

Complexity และข้อดีข้อเสีย

Complexity ของ Brute Force TSP Algorithm คือ O(n!) เนื่องจากวิธีนี้จะทดลองหาเส้นทางทุกเส้นทางที่เป็นไปได้ ข้อดีคือการันตีว่าจะได้เส้นทางที่สั้นที่สุดแต่ข้อเสียคือไม่เหมาะสมกับปัญหาที่มีขนาดใหญ่เนื่องจากจะใช้เวลาในการคำนวณนานมาก

ในที่สุดนี้หากคุณพบว่าความท้าทายในการแก้ปัญหา TSP น่าสนใจ และเป็นสิ่งที่คุณอยากพัฒนาฝีมือด้านการเขียนโปรแกรม ขอเชิญชวนคุณมาเรียนรู้และสัมผัสประสบการณ์การพัฒนาโปรแกรมด้วยตัวคุณเองที่ EPT ที่สถาบันของเรานอกจากจะมีคอร์สเรียนการเขียนโปรแกรมคุณภาพสูงแล้วยังมีการทำ workshop และห้องปฏิบัติการที่ทันสมัยอีกด้วย!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง