kereen ...
________________________________ Dari: Morry Infra <[email protected]> Kepada: Ahlan Riyadh <[email protected]>; [email protected]; ex-cii <[email protected]>; ARII Drlg Milist <[email protected]>; Moderator MMIT <[email protected]> Dikirim: Jumat, 31 Agustus 2012 7:54 Judul: [sma1bks] Fwd: Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem) ---------- Forwarded message ---------- From: Rusdi <> Date: 2012/8/31 Subject: Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem) Dari milist sebelah ,,,, Sent from my iPad Begin forwarded message: From: "syarwani" <[email protected]> >Date: August 31, 2012 12:19:17 AM GMT+08:00 >To: [email protected] >Subject: IPOMS-APICS Problem Gila-gilaan itu Terpecahkan (Traveling Salesman >Problem) >Reply-To: [email protected] > > >Catatan: sudah dilakukan pengujian untuk problem2 TSP sekala international yg >dikenal sukar dan berhasil dipecahkan dengan solusi yg optimal. > >MSY >==== >Problem Gila-gilaan itu 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, 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), oleh Anang Zaini dikatakan bisa ditembus oleh teori temuannya. >"Teori saya ini mampu memecahkan problem TSP sampai jumlah variable 57 >atau lebih," > >TSP memang boleh disebut problem matematik yang gila-gilaan. 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 tahunan," >kata >Anang Zaini. Maklum, komputer itu harus membandingkan kombinasi-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 > >
