Re: Problem Gila-gilaan itu Terpecahkan (Traveling Salesman Problem)
Posted By: * syarwani
*
*
* Fri Aug 31, 2012 6:22 pm | * Options
*
*
*
Coba ke link2 sbb:
Teori Interaksi, Menjawab yang Sulit dengan Mudah
http://www.facebook.com/notes/l-a-n-g-g-e-e-2-0-1-0/teori-interaksi/109423592418\
072
Prof Anang Z Gani
https://twitter.com/profazg
The 5th International Workshop on Optimal Network Topologies
(IWONT 2012)
July 27 – 29, 2012
Institut Teknologi Bandung, Indonesia
http://iwont.maths.web.id/schedule
MSY
--- In [email protected], "nugon19" <nugon19@...> wrote:
>
> Mas , mohon maaf, bisa minta link web page utk berita ini?buat arsip dan
> cross-check.
> Thanks a lot.Jazaakalloohu.Wassalam - Nugon
> --- In [email protected], "syarwani" <syarwani@>
> wrote:
> >
> > 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 empat 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
> >
>
