[M_S] Fw: link utk cross-check Traveling Salesman Problem

 

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 KOMPUTER-TEKNOLOGI@yahoogroups.com, "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 KOMPUTER-TEKNOLOGI@yahoogroups.com, "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 > > >

__._,_.___

Reply to sender | Reply to group | Reply via web post | Start a New Topic

Messages in this topic (1)

Recent Activity:

• New Members 4

Visit Your Group

----------------------------------------------------------------------
"Muhammadiyah ini lain dengan Muhammadiyah yang akan datang. Maka teruslah
kamu bersekolah, menuntut ilmu pengetahuan dimana saja. Jadilah guru kembali
pada Muhammadiyah. Jadilah dokter, kembali kepada Muhammadiyah. Jadilah
Meester, insinyur dan lain-lain, dan kembalilah kepada Muhammadiyah"
(K.H. Ahmad Dahlan).

----------------------------------------------------------------------
Salurkan ZAKAT, INFAQ dan SHODAQOH anda melalui LAZIS
MUHAMMADIYAH

No. Rekening atas nama LAZIS Muhammadiyah
1. Bank BCA Central Cikini
    (zakat) 8780040077 - (infaq) 8780040051
2. BNI Syariah Cab. Jakarta Selatan
    (zakat) 00.91539400 -   (infaq) 00.91539411
3. Bank Syariah Mandiri (BSM) Cab. Thamrin
    ( Zakat) 009.0033333 -  (Infaq) 009.00666666
4. Bank Niaga Syariah
    (zakat) 520.01.00186.00.0 - (infaq) 520.01.00187.00.6
5. Bank Muamalat Indonesia Arthaloka
    (Zakat) 301.0054715
6. Bank Persyarikatan Pusat
   (zakat) 3001111110 -  (infaq) 3001112210
7. Bank Syariah Platinum Thamrin
    (zakat) 2.700.002888 -  (infaq) 2.700.002929
8. BRI cab. Cut Meutia
    (zakat) 0230-01.001403.30-9 -    (infaq) 0230-01.001404.30-5

Bantuan Kemanusiaan dan Bencana:
BNI Syariah no.rekening: 00.91539444

DONASI MELALUI SMS
a. Jadikan jum'at sebagai momentum kepedulian,
salurkan donasi anda, ketik: LM(spasi)JUMATPEDULI kirim ke 7505

b. Bantuan kemanusiaan  ketik: LM(spasi)ACK kirim ke 7505

Nilai donasi Rp. 5000, semua operator,belum termasuk PPN

email: lazis@muhammadiyah.or.id
website : www.lazismu.org

Switch to: Text-Only, Daily Digest • Unsubscribe • Terms of Use

.

__,_._,___