Travelling Salesman Problem

Persoalan yang cukup menarik bagi ahli matematik sampai saat ini ialah persoalan TSP (Traveling Salesman Problem), yang dikenal sebagai NP complete problem (Non-Polynomial Complete Problem) dan TSP juga dikenal oleh ahli matematika sebagai persoalan yang bandel ("Stubborn resistance to all kinds of attack").

Pemecahan TSP memerlukan waktu yang amat banyak. Sebagai contoh untuk soal yang sederhana yaitu n=50 maka diperlukan 65 x 1065 langkah pemecahan.

Suatu pernyataan yang menarik dalam usaha memecahkan NP-complete problem ialah :
1. No NP complete can be solved by any known polynomial algorithm (and this despite persistent efforts by many brilliant researchers for many decades).
2. If there is a polynomial algorithm for any NP complete problem, then there are polynomial algorthm for all NP complete problems.

Sumber: Papandimitrion, Christo H, Steglitzs K.; "Combinatorial Optimization". Prentice Hall, 1982.

Dicomot dari milis Komputer dan Teknologi, posted by MSY

~RH~
Windows® 6.5 Phone