Masalah Salesman Perjalanan

[ad_1]

Masalah salesman bepergian adalah masalah klasik dalam riset operasi yang melibatkan salesman keliling yang harus mengunjungi N sejumlah kota. Di sini kita dihadapkan pada masalah penentuan jalur terpendek yang dia perlukan untuk dilalui. Masalah ini tidak memiliki solusi waktu polinomial sebagai kompleksitas penentuan jalur terpendek meningkat sebagai fungsi faktorial N untuk nilai-nilai besar N.

Sebuah komputer yang diberi tugas untuk menemukan jalur terpendek dari serangkaian kemungkinan wisata yang berbeda tidak akan dapat menghitung jalur terpendek untuk nilai-nilai yang sangat besar dari sejumlah kota. Kompleksitas algoritma diklasifikasikan sebagai eksponensial, polinomial, logaritma dll, kompleksitas TSP adalah fungsi faktorial (n).

Mari kita ilustrasikan dengan sebuah contoh. Untuk tur 3 kota tidak ada kombinasi yang mungkin adalah 6. Di sini di daftar di bawah ini ditunjukkan tidak ada tur yang mungkin vs tidak ada kota di tur

4 tur kota = no. dari kemungkinan wisata adalah 24

5 tur kota = no. dari kemungkinan wisata adalah 120

6 tur kota = no. dari kemungkinan wisata adalah 720

7 tur kota = no. dari kemungkinan tur adalah 5040

8 tur kota = jumlah tur yang mungkin adalah 40320

9 tur kota = jumlah kemungkinan wisata adalah 362880

10 tur kota = jumlah kemungkinan wisata adalah 3628800

Karena dapat dilihat dengan mudah jumlah perhitungan yang diperlukan oleh komputer untuk menentukan jalur terpendek meningkat menjadi 362880 untuk tur hanya 9 kota dan untuk 50 tur kota, kompleksitas meningkat menjadi 3,04141E + 64.

Jadi komputer tidak bisa memproses begitu banyak instruksi dalam waktu yang terbatas untuk persyaratan kehidupan yang lebih besar dan nyata. Kekuatan pemrosesan yang tersedia di komputer modern akan membutuhkan triliunan tahun untuk menemukan solusi bagi Masalah Salesman Perjalanan karena nilai input (tidak ada kota) mengatakan sama dengan 100.

TSP dapat dipecahkan menggunakan formulasi Linear Programming / Integer Linear Programming dan menggunakan metode Simplex atau Cutting Plane.

Alih-alih menggunakan teknik brute force seseorang dapat mengurangi jumlah kemungkinan tur dengan menggunakan pemrograman dinamis. Satu juga dapat memecahkan TSP menggunakan heuristik.

TSP dianggap NP -Hard atau dengan kata lain tidak ada solusi umum untuk masalah ini kecuali terbukti bahwa P = NP.

[ad_2]