Problem Traveling Salesman Problem (TSP) Terpecahkan?

Seorang matematikawan ITB menemukan teori baru yang bisa memecahkan misteri
matematika yang selama 200 tahun tak terungkap. Masih perlu pengujian secara internasional.

Suatu kali, Anda mendapat tugas mengunjungi emapat kota dengan pesawat carteran. Anda berangkat dari Jakarta. Kota-kota yang harus anda kunjungi, katakanlah, Surabaya, Denpasar, Ujungpandang, serta Pontianak. Jika Anda mendapat instruksi untuk menempuh jalur terpendek rute mana yang harus Anda lewati?

Kening Anda harus berkerut-kerut lebih dahulu, sebelum jawaban yang pasti bisa ketemu. Syukur kalau Anda hafal di luar kepala jarak antara satu dan lain kota. Kalau tidak, Anda harus encari jawaban di buku panduan wisata atau mengukur skla jarak di peta. Itu baru langkah pertama. Selanjutnya, Anda mesti menyusun beberapa alternative lintasan dan memilih jalur yang paling hemat bahan bakar dan murah.

Jika Anda berhasil menemukan jawaban yang tepat dalam waktu singkat, Anda termasuk kategori manusia cerdas. Betapa tidak, untuk mengunjungi 4 kota itu ada 12 alternatif lintasan. Dan semua alternative itu harus dijajaki satu persatu dengan menjumlahkan panjang lintasannya dan membandingkan satu dengan yang lain.

Problem mencari lintasan semacam itu akan lebih memusingkan jika kota yang harus disinggahi makin banyak. Ambil contoh, umpamanya trip itu ditambah dengan Medan .Alternatif lintasan pada enam kota itu, termasuk Jakarta, jumlahnya menjadi 60. Jika ditambah Padang, misalnya, alternatifnya menjadi 360 lintasan. Kalau 16 kota?

Konon, problem matematis seperti itu telah ramai diperdebatkan sejak dua abad silam. Selama ini, "teka-teki" tersebut tak pernah memperoleh jawaban tuntas. Menghitung jumlah kombinasinya pun sudah pusing, apalagi kalau harus menentukan misalnya, lintasan terpendek atau terjauh. Kasus pelik, seperti mencari lintasan terpendek pada trip ke sejumlah kota, adalah sebuah contoh kasus, dari gugus problem sejenis, yang oleh pakar matematika disebut (nonpolynomial) -complete problem.

Kasus-kasus NP-complete problem ini mempunyai cirri yang khas: sebuah problem matematik yang jika variabelnya bertambah sedikit saja akan menyebabkan pertambahan waktu computer yang sangat besar untuk memcahkannya. Pertambahan waktu yang berlipat-lipat itu tak lain disebabkan tidak tersedianya kunci praktis untuk menerobos inti persoalan.

Namun, problem tua itu agaknya kini mulai terkuak. Dr. Anang Zaini Gani, 48 tahun, matematikawan ITB, mengemukakan sebuah teori yang disebut "teori interaksi", sebagai kunci pemecah NP-complete problem. Bahkan kasus-kasus paling rumit dalam gugus itu, yang disebut The Trveling Salesman Problem (TSP), aleh Anang Zaini dikatakan bisa ditembus oleh teori temuannya.

"Teori saya ini mampu memecahkan problem TSP samapai jumlah variable 57," ujar dosen teknik industri ITB itu.

TSP memang boleh disebut problem matematik yang gila-gilan. Sepintas, seperti problem mencari lintasan tadi, persoalan tampak sederhana. Tapi program konvensional pada supercomputer pun bisa dibikin menyerah. Bayangkan, untuk lima buah variable, supercomputer - dengan kemampuan satu juta operasi per detik - hanya memerlukan 0,02 detik untuk memcahkan TSP.

Jika peubah bebas itu ditambah menjadi sepuluh, waktu yang diperlukan untuk
memecahkannya berlipat hingga sepuluh menit. Namun, jika variable itu digandakan menjadi 50, "Waktu yang diperlukan sampai bermilyar tahun," kata Anang Zaini. Maklum, komputer itu harus membandingkan komninasi-kombinasi yang jumlahnya mencapai sebuah bilangan yang terdiri atas 65 angka!

Anang Zaini mengembangkan teorinya berdasarkan sebuah gagasan unik: sebuah angka tidaklah mutlak adanya. "Nilai suatu elemen dalam sistem itu sesungguhnya relative, tidak absolute," kata Zaini. Kenisbian nilai elemen sistem itu, kata ayah empat anak ini, tergantung lingkungannya. Maka, dalam membangun teorinya, Zaini mengaitkan satu elemen dengan elemen lain disekelilingnya, sehingga memperoleh koefisien interaksi. Komponen inilah yang memungkinkan ahli desain industri itu memperoleh nilai-nilai nisbi.

Dalam memecahkan persolan TSP, Zaini tak melakukan pendekatan dengan matematika tinggi."Cukup dengan aritmatika (ilmu hitung) biasa, " ujarnya. Elemen TSP biasanya disusun dalam matriks. Ukuran matriks itu tentu tergantung variable yang ada. Jika peubah bebasnya 50, matriksnya pun berukuran 50 x50.

Anggota matriks kemudian ditransformasikan dengan mengalikan terhadap koefisien interaksi. Indeks koefisien itu diperoleh dari penguadratan anggota matriks terhadap besaran tertentu. Tahap berikutnya, setelah transformasi, adalah penggarapan terhadap nilai-nilai nisbi dalam tubuh matriks itu. Dan yang paling penting pada metode interaksi itu, "Hasil yang diperoleh dijamin optimal dan eksak," kata Zaini.

Sumber : Tempo