Artificial Intelligence Pada Game Mario Bros
Pengenalan Game Mario Bross
Super Mario Bros. (スーパーマリオブラザーズ Sūpā Mario Burazāzu?. Siapa yang tidak kenal dengan tukang ledeng berkumis tebal berbaju merah lengkap dengan topi berhuruf ‘M’ di kepalanya. Adalah suatu permainan platform yang dikembangkan dan diterbitkan oleh Nintendo pada akhir 1985 untuk NES (Nintendo Entertainment System). Super Mario Bros adalah sebuah game yang dikenal oleh semua orang. Sejak kehadiran Nintendo 64 dan Super Mario 64, Mario hijrah ke dunia 3D dan tidak pernah kembali ke 2D Platform lagi. Super Mario Bros, game konsol NES (Nintendo Entertaintment System).Permainan ini membawa pengaruh luar biasa pada dunia hiburan rumahan sewaktu diluncurkan, dan sekarang dianggap sebagai contoh klasik dari medium tersebut. Super Mario Bross menyuguhkan suatu dunia yang cerah dan dapat berkembang yang mengubah cara pembuatan permainan video. Walaupun sering salah dirujuk sebagai permainan platform bergulir (scrolling) pertama (paling tidak ada setengah lusin permainan serupa yang telah muncul sebelumnya), permainan ini merupakan konsol asli pertama dalam genre ini yang menyuguhkan tingkatan bergulir mulus dan menjadikannya sebagai tengaran (landmark) dalam permainan video rumahan.
Super Mario Bros bisa dibilang game paling dikenal sepanjang sejarah Nintendo, tidak ada game lain yang memiliki dampak yang cukup signifikan terhadap dunia seperti game yang satu ini, bahkan termasuk menjadi game yang membantu mengangkat industri video game dari era tahun 80-an. Selama 20 tahun, super mario bros menjadi game dengan penjualan tertinggi sepanjang masa, hanya dapat dilampaui oleh wii sport yang di bundle untuk konsol Wii.
Spesifikasi yang di butuhkan untuk dapat memainkan game ini adalah :
The minimum requirements are:
* Processor: Pentium MMX or comparable AMD
* Ram: 64MB
* Video: Direct3D 9.0 compatible graphic card.
* OS: Windows 98/Me/2000/XP
* Software Installed: DirectX 9.0c or superior
Ada beberapa hal mengenai game super Mario bros yaitu:
§ Asal mula Mario
Mario pertama kali muncul dalam game Donkey Kong. Pertama kali kemunculannya Mario belum memiliki nama panggilan, Mario hanya dipanggil dengan nama “Jumpman”. Tadinya Mario dipanggil dengan nama Mr. Video Game di Jepang. Nama Mario diberikan karena karakter Mario sangat mirip dengan pimpinan Nintendo Amerika yang berkebangsaan Italia bernama Mario Seagle. Shigeru Miyamoto sadar betul kalau nama-nama Jepang akan sulit diterima masyarakat umum dan akan mengurangi kepopuleran karakter buatannya di luar Jepang.
§ Pekerjaan
Mario sebenarnya berprofesi sebagai tukang kayu, bukan tukang ledeng seperti sekarang ini. Percaya atau tidak, pekerjaannya sebagai tukang ledeng tidak pernah dibawa ke dalam game, bahkan pipa ledeng dalam game Super Mario Bros berfungsi sebagai alat transportasi. Keahlian Mario memperbaiki pipa ledeng justru disoroti pada serial animasinya. Mario sebenarnya memiliki beberapa profesi lainnya, seperti dokter dalam game Dr. Mario, Arkeolog dalam game Mario Picross dan pembuat mainan dalam game Mario vs. Donkey Kong 2: March of the Minis. Saat ini Mario sering sekali berganti-ganti pekerjaan mengikuti judul game yang sedang dibintanginya. Terkadang Mario menjadi pebasket, atlit sepak bola dan lain sebagainya.
§ Penampilan
Shigeru Miyamoto sebagai pencipta Mario memakaikan topi pada karakter Mario karena merasa kesulitan menggambar rambut pada saat itu. Selain itu mulut juga mengalami nasib yang sama, Shigeru lebih memilih memakaikan kumis tebal pada Mario karena lebih mudah digambar dibandingkan harus menggambar mulut. Mario biasanya memakai baju yang merupakan kombinasi antara kaus biru dan overall berwarna merah, tetapi pada game Super Mario Bross, kaus Mario berubah menjadi warna coklat muda. Sampai saat ini tidak ada laporan resmi tentang mengapa Mario harus berganti warna kaus, menurut dugaan beberapa orang penggantian tersebut dimaksudkan untuk membedakan warna baju Mario dengan langit dalam game.
§ Saudara Kandung
Mario memiliki seorang saudara kandung yang bernama Luigi. Luigi muncul pertama kali pada tahun 1983 dalam game Mario Bros. Pada awalnya Luigi selalu dianggap sebagai adik Mario yang sedikit lebih muda, cerita tersebut diubah pada game Super Mario World 2: Yoshi's Island. Mario dan Luigi digambarkan sebagai anak kembar yang lahir bersamaan, bedanya Mario dinaikkan ke atas burung bangau terlebih dahulu sehingga dianggap lebih tua sekian detik dari Luigi. Mario dan Luigi memiliki nama panjang yang cukup aneh, nama panjang mereka adalah Mario. Mengapa bisa begitu? Karena, Mario dan Luigi selalui dipanggil sebagai Mario Bros/Brothers, penggunaan kata bros atau brothers selalu mengacu pada nama belakang seseorang. Sebagai contoh bila kamu dan adikmu memiliki nama belakang Edison maka kalian berdua bisa dipanggil sebagai Edison brothers atau Edison bersaudara. Melihat fakta tersebut bisa dipastikan kalau nama lengkap Mario adalah Mario Mario dan Luigi Mario.
§ Pengisi Suara
Mario pernah diisikan suaranya oleh banyak aktor terkenal seperti, Charles Martinet, Mark Graue, Ronald B. Ruben termasuk Peter Cullen sang pengisi suara Optimus Prime di Transformers. Suara Mario yang tinggi dimaksudkan untuk memberikan kesan ceria pada karakter Mario, aksen Itali ditambahkan karena Mario sangat menyukai pasta dan pizza.
§ Musuh Abadi
Memang Bowser selalu tampil menjadi musuh utama Mario dalam kebanyakan game, tetapi sesungguhnya Mario memiliki musuh abadi yang memiliki nama Wario. Nama Wario itu sendiri berasal dari gabungan kata 'warui' yang artinya tidak baik dan Mario. Berbeda dengan Mario yang diciptakan oleh Shigeru Miyamoto, Wario diciptakan oleh Gunpei Yoko. Wario muncul pertama kali pada tahun 1992 dalam game Super Mario Land 2: 6 Golden Coins sebagai musuh utama sekaligus raja terakhir game tersebut. Sejak saat itu nama Wario mulai dikenal oleh publik dan akhirnya Wario menjadi bintang utama beberapa judul game buatan Nintendo. Biasanya Wario selalu digambarkan sebagai seorang yang egois dan tamak, tetapi biasanya dia melakukan berbagai hal baik untuk mencapai tujuannya. Wario digambarkan sangat berlawanan dengan Mario yang tipikal pahlawan baik hati, bahkan Wario memakai huruf W di topinya berlawanan dengan Mario yang memakai huruf M. Karakter Wario memiliki beberapa fakta unik, pertama-tama tinggi badan Wario selalu berubah-ubah, terkadang Wario digambarkan lebih tinggi dari Mario dan terkadang sebaliknya. Fakta unik lain Wario adalah, Wario memiliki pengisi suara yang sama dengan Mario, Luigi dan Waluigi.
§ Pasangan Romantis
Banyak orang yang mengira kalau Mario sudah berpasangan dengan tuan puteri Peach dari dulu, padahal cerita tersebut tidak tepat 100%. Mario sempat memiliki kekasih lain dalam game Donkey Kong. Di game tersebut dikisahkan kalau Mario harus menyelamatkan kekasih hatinya yang bernama Pauline dari cengkraman kera raksasa yang jahat. Mario dan Peach baru dipertemukan pada game Super Mario Bros. Banyak yang menyangka kalau puteri yang ada dalam game Donkey Kong merupakan puteri yang sama dalam game Super Mario Bros. Tadinya tuan puteri Peach lebih dikenal sebagai Toadstool, sampai akhirnya pada game Super Mario 64 nama Peach dikenal oleh penggemarnya secara lebih luas. Lalu bagaimana dengan nasib puteri Pauline yang ditinggal Mario? Rupanya Pauline kembali dimunculkan dalam game Mario vs. Donkey Kong 2: March of the Minis.
§ Kekuatan Mario
Mario memiliki beragam kekuatan yang terus bertambah sampai sekarang. Mario biasanya memiliki tiga buah kekuatan dasar seperti, Jamur untuk membesar, bunga api untuk membuat Mario menembakkan api dan bintang yang membuat Mario tidak bisa dilukai oleh serangan apapun. Kekuatan Mario lainnya terkadang mengambil wujud binatang seperti pakaian kodok, daun cerepelai dan wortel kelinci. Setiap ada serial baru biasanya Mario memperoleh kekuatan baru, seperti dalam game New Super Mario Bros, Mario mendapatkan dua jamur tipe baru, yang pertama bernama jamur raksaksa yang membuat Mario berubah menjadi besar sekali dan yang kedua adalah jamur mini yang menyebabkan Mario menciut menjadi kecil sehingga cukup ringan untuk berjalan di atas air. Mario terkadang bisa memanfaatkan benda-benda yang ada di sekitarnya untuk dijadikan senjata, sebagai contoh dalam Super Mario Bros 2 Mario bisa mengangkat tanaman yang ada di dalam tanah untuk dilemparkan ke arah musuh.
§ Musik Dalam Mario
Musik di super mario bros bener-bener sempurna. Catchy tune yang mudah diingat dan benar-benar menyatu dengan gameplay. Mungkin suara yang dihasilkan chip 8 bit tua tidak akan terdengar semeriah game-game baru yang make dolby atau 5.1 audio, nintendo terbukti mampu menciptakan suara yang bisa dikenang hingga sekarang.
Selain itu, sudah tidak terhitung berapa kali lagu tersebut dimainkan oleh penggemarnya dengan beragam versi dan variasi. Ada yang diaransemen ulang, ada yang dimainkan dengan dua gitar sekaligus bahkan ada yang acapela. Banyak orang yang mendapatkan popularitas karena memainkan lagu Super Mario Bros Theme, seperti Zack Kim yang memainkan lagu tersebut memakai dua gitar sekaligus di YouTube, Jean Baudin yang memakai bass dengan 11 senar, Greg Patillo memakai flute untuk memainkan lagu tersebut.
§ Ketenaran Mario
Karakter Mario telah muncul dalam 200 judul game yang telah terjual kurang lebih 193 juta kopi di seluruh dunia. Kepopuleran Mario tidak berhenti sampai situ saja, Mario memiliki acara TV sendiri, animasi, komik dan film layar lebar. Bahkan pemain NHL, Mario Lemieux dipanggil oleh media dengan julukan 'Super Mario'. Julukan Super Mario sempat hinggap pada atlit-atlit lainnya seperti pembalab sepeda profesional Mario Cipolini dan pesepak bola Jerman Mario Basler. Ketenaran Mario jauh mengalahkan Cloud dari Final Fantasy VII atau Solid Snake dari serial Metal Gear. Mario masuk ke dalam Walk of Game pada tahun 2005 bersama-sama dengan, Link, Sonic dan Master Chief selain itu Mario juga memiliki patung lilinnya sendiri di Hollywood Wax Museum. Bahkan ada sebuah nama jalan di Swedia yang didedikasikan langsung untuk Mario bernama 'Mario's Gata 21' yang berarti Jalan Mario 21. Mario sampai sekarang masih memegang tujuh rekor Guinness termasuk di antaranya, game yang memiliki jumlah penjualan terbanyak sepanjang waktu dan game pertama yang diadaptasi ke dalam film. Yang cukup mengejutkan menurut hasil survei Marketing Evaluations pada tahun 1990, ternyata ketenaran Mario mampu mengalahkan ikon Amerika Mickey Mouse.
Kelebihan:
- Transisi scolling stage yang begitu halus, layar dan background bergerak sesuai posisi Mario.
- Catchy tune yang mudah diingat dan benar-benar menyatu dengan gameplay.
- Gameplay dari super mario bros yang simple tapi benar-benar mengena.
- Kontrol cukup mudah dan responsive.
- Layar dan background bergerak sesuai posisi mario. game pada era itu pada umumnya mempunya single screen, sehingga gameplay pada umumnya berpindah screen, dan jika ada game yang memiliki screen scrolling yang sama dengan metode super mario bros, tidka ada yang memiliki transisi sehalus super mario bros, bahkan setelah bertahun-tahun game tersebut dirilis. hal ini mungkin terdengar sepele untuk standar saat ini, tapi pada masa itu, hal tersebut adalah aspek yang luar biasa.
- Smooth scrolling membuat keseluruhan game menjadi lebih baik dan tidak terlihat adanya slow down.
Kekurangan:
- Untuk game zaman sekarang tampilan masih kurang bagus.
- Gameplay terlalu simple untuk zaman sekarang.
- Kualitas suara yang kurang memadai untuk game zaman sekarang.
Beberapa Versi Game Mario Bross Dari Yang Lama Sampai Terbaru
§ Mario Forever 4.1a
Mario Forever dibuat mengikuti desain dan cara main game Mario Bros klasik keluaran Nintendo. Anda akan merasakan lingkungan yang mirip Mario Bros lama dengan beberapa penambahan seperti desain yang lebih halus, warna-warna yang terang dan tetap tajam, walau dimainkan dalam tampilan fullscreen. Setiap level disajikan dengan sangat baik dan semakin lama akan semakin sulit dan menantang.
Game ini juga mengemas aplikasi Mario Worker yang dapat membantu Anda membuat level permainan sendiri. Anda dapat menata lingkungan yang ada seperti menambahkan awan, rintangan, level dan cerita sehingga permainan yang Anda buat menjadi lebih hidup. Hasilnya nanti bisa di-unggah dan Anda juga bisa mengunduh level permainan hasil kreasi orang lain.
§ Mario Forever Galaxy 1.8
Setiap karakter memiliki kemampuan sendiri yang berbeda. Setiap misi akan menggunakan pesawat luar angkasa yang dapat di-upgrade dengan 60 jenis senjata yang berbeda dengan level kekuatan yang dapat ditingkatkan. Dalam game ini kita kan melewati 8 map yang memiliki bos-bos yang kuat.
Penjelasan Cara Bermain Dalam Game Mario Bross
Sang pemain akan berperan sebagai Mario, seorang lelaki berkumis yang menggunakan pakaian overall merah dengan baju kecokelatan, atau pemain kedua, Luigi, adik Mario, seorang lelaki berkumis serupa yang menggunakan overall putih dengan baju hijau. Dalam petualangan menyelamakan putri dari kura-kura raksasa bernama Bowser. Meski menyelamatkan putri terdengar cukup klise dan tidak original, untuk game semacam ini cerita tidaklah terlalu penting. dengan setting di mushrom kingdom, super mario bros memiliki banyak musuh yang inovatif dan menantang, mulai dari goomba hingga koopa. Ssemua musuh memiliki satu persamaan dasar, loncat dan injak kepala mereka untuk membunuhnya.
Game ini memiliki fitur power-up dalam bentuk jamur dan bunga. pemain mulai dengan mario kecil, ambil jamur untuk power-up menjadi mario yang lebih besar yang akan memiliki kemampuan untuk menghancurkan blok, setelah itu power-up bunga akan mengubah pemain menjadi super mario yang memiliki kemampuan menembakkan bola api.
Game ini penuh dengan rahasia, mulai dari jamur 1-up yang tersembunyi hingga warp point untuk melewati 1 atau beberapa dunia secara keseluruhan. Game ini punya cukup rahasia untuk membuat seseorang bermain dan bermain lagi untuk mendapatkan rahasia-rahasia baru atau sekedar bermain dengan jalan yang berbeda. Game ini juga mendukung 2 pemain. dengan bermain secara bergantian pada 1 stage yang sama.
Tampilan-tampilan Yang Ada Pada Game Mario Bross
Gambar disamping merupakan sebuah koin yang harus didapatkan, jika kau telah mengumpulkan koin tersebut sebanyak 100 koin maka nyawa Mario dalam permainan akan bertambah.
Musuh-musuh Mario Bross
Gambar-gambar diatas adalah musuh-musuh Mario.
Video Game Mario Bros
Sumber :
Searching
Dalam pencarian data juga terdapat beberapa jenis algoritma, tujuan dari adanya banyak algoritma yang di temukan adalah karena memiliki keuntungan-keuntungan tersendiri, seperti lebih cepatnya bila mengolah data yang jumlahnya lebih dari juta data, ada yang lebih efisien dengan jumlah kurang dari jutaan. serta ada pula yang tidak perlu untuk mengurutkan data terlebih dahulu, tetapi memakan waktu lebih lama. Sehingga itu diperlukan teknik SEARCHING sehingga memudahkan pekerjaan kita.
Searching adalah salah satu pekerjaan yang paling mendasar dalam bidang perkomputeran . Searching digunakan dalam setiap tindakan yang perlu untuk mengetahui bilamana sebuah elemen tercantum dalam daftar atau lebih umum lagi, pencarian ulang dari file informasi yang berhubungan dengan unsur tersebut . Macam – macam teknik searching adalah :
Algoritma searching dapat dikelompokkan menjadi 2, yaitu pencarian terhadap kumpulan data yang belum terurut dan pencarian terhadap kumpulan data yang sudah terurut. Salah satu contoh algoritma searching untuk data tidak terurut adalah Sequential Search dan Line Search.
Line Search
Teknik searching ini dibuat dengan cara melakukan pengecekkan satu persatu, yaitu antara data yang di cari dengan kumpulan data yang di miliki, Keuntungan metode ini adalah kita tidak perlu mengurutkan data yang ada, bila mencari data pada kumpulan data yang tidak urut hanya terdapat metode ini yang dapat di lakukan.
Sequential Search
Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal).
Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).
“Pencarian Sekuensial (sequential search)” :
1. Relatif lebih cepat dan efisien, dapat menghemat waktumu karena pencarian datanya cepat.
2. Untuk data yang terbatas tetapi kurang cepat untuk data dalam jumlah besar (pencarian datanya lama banget, apalagi mencari indeks array yang paling akhir)
3. Algoritma-Nya agak sederhana
4. Beban komputasi nya cenderung lebih besar
Misalnya terdapat array satu dimensi sebagai berikut:
Kemudian program akan meminta data yang akan dicari, misalnya 6.
Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika tidak ada maka akan ditampilkan tulisan “TIDAK ADA”.
Contoh Program
Output :
Pembahasan Program
• Program menggunakan sebuah variabel flag yang berguna untuk menadai ada atau tidaknya data yang dicari dalam array data. Hanya bernilai 0 atau 1.
• Flag pertama kali diinisialiasasi dengan nilai 0.
• Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
• Semua elemen array data akan dibandingkan satu persatu dengan data yang dicari dan diinputkan oleh user.
Sedangkan contoh algoritma searching untuk data terurut adalah Binary Search, Fibonachi Search dan Interpolation Search.
Binnary Search
Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian. Teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data pada index yang tengah, apakah lebih besar/lebih kecil/sama dengan. bila hasil sama dengan maka nilai yang di cari telah di temukan. bila lebih kecil/lebih besar maka akan di buang setengah data dari yang salah, dan mencari dari indeks yang tengah dari sisanya. demikian sampai data ditemukan atau tidak di temukan.
Prinsip pencarian biner adalah:
• Data diambil dari posisi 1 sampai posisi akhir N
• Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
• Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
• Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
• Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
• Jika data sama, berarti ketemu.
“Pencarian Biner (binary search)” :
1. Sangat rumit, membutuhkan waktu yang lebih banyak.
2. Untuk data dalam jumlah besar, waktu searching lebih cepat tetapi data harus sudah di-sorting lebih dulu ( dalam keadaan terurut ), jadi mesti mengurutkan data terlebih dulu.
3. Algoritma-Nya agak rumit, tapi hasilnya bisa memuaskan kamu lho, soalnya agak cepat dalam pencarian datanya
4. Beban komputasi-nya lebih kecil, tidak baik untuk data berangkai.
Ilustrasi
Contoh Program
Output :
Fibonachi Search
Teknik ini hanya dapat digunakan hanya pada kumpulan data yang sudah di urutkan, karena teknik ini melakukan pencarian dengan mencari data melalui pola bilangan fibonachi. Bila pada binnary search pembandingnya adalah nilai pada index tengahnya jumlah data, pada fibonachi search berbeda yaitu: bilangan fibonachi, yang bilangan fibonachinya terdekat dengan jumlah data tetapi tidak lebih besar dari jumlah data yang akan di proses. Bilangan fibonachi itu di jumlahkan dengan batas paling awal data dikurangi 1. Contohnya: jumlah data yang akan di cari adalah 15, maka batas paling bawah adalah 1 dan batas paling akhir=15 dan index pembandingnya= 13(nilai awal + dijumlahkan Bilangan fibonachi - 1) karena bilangan fibonachi terdekat dengan 15 (data ke 1- data ke 15) adalah 13 (1,2,3,5,8,13,21,34.....), bila data yang di cari lebih besar dari bilangan indeks ke tengahnya maka. batas paling bawah= tetap, batas akhir nilai tengah-1, bila data yang dicari lebih kecil maka batas bawah = nilai tengah +1 dan batas akhir tetap, sedangkan nilai tengahnya memakai fungsi tadi.
Interpolation Search
Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu. Teknik searching ini dilakukan dengan perkiraan letak data.
Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 2/3 atau ¾ dari tebal buku.
Rumus posisi relatif kunci pencarian dihitung dengan rumus:
- Jika data[posisi] > data yg dicari, high = pos – 1
- Jika data[posisi] < data yg dicari, low = pos + 1
Kasus
Misal terdapat data sebagai berikut:
Penyelesaian
• Kunci Pencarian ? 088
• Low ? 0
• High ? 7
• Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]
• Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005
• Kunci Pencarian ? 060
• Low ? 0
• High ? 7
• Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]
• Kunci[3] < kunci pencarian, maka teruskan
• Low = 3 + 1 = 4
• High = 7
• Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.
• Berarti tidak ada kunci 060.
Contoh Program
Algoritma Greedy
Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.
Greedy = rakus, tamak, loba, ….
Prinsip greedy adalah: “take what you can get now!”. Contoh masalah sehari-hari yang menggunakan prinsip greedy:
o Memilih beberapa jenis investasi (penanaman modal)
o Mencari jalur tersingkat dari Bandung ke Surabaya
o Memilih jurusan di Perguruan Tinggi
o Bermain kartu remi
Algoritma greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.
Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum. Persoalan optimasi ada dua macam:
1. Maksimasi (maximization)
2. Minimasi (minimization)
Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.
Elemen persoalan optimasi:
1. kendala (constraints)
2. fungsi objektif(atau fungsi optiamsi)
Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.
Pendekatan Algoritma Greedy
Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah ke solusi optimum global (global optimm).
Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah, pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.
Contoh (Masalah Penukaran uang):
Persoalan: Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Contoh: tersedia koin-koin 1, 5, 10, dan 25
Uang senilai 32 dapat ditukar dengan cara berikut:
32 = 1 + 1 + … + 1 (32 koin)
32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)
32 = 10 + 10 + 10 + 1 + 1 (5 koin)
… dan seterusnya
Minimum: 32 = 25 + 5 + 1 + 1 ) hanya 4 koin
Strategi greedy yang digunakan adalah:
Pada setiap langkah, pilihlah koin dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai uang yang ditukarkan.
Tinjau masalah menukarkan uang 32 dengan koin 1, 5, 10, dan 25:
Langkah 1: pilih 1 buah koin 25 (Total = 25)
Langkah 2: pilih 1 buah koin 5 (Total = 25 + 5 = 30)
Langkah 3: pilih 2 buah koin 1 (Total = 25+5+1+1= 32)
Solusi: Jumlah koin minimum = 4 (solusi optimal!)
Pada setiap langkah di atas kita memperoleh optimum lokal, dan pada akhir algoritma kita memperoleh optimum global (yang pada contoh ini merupakan solusi optimum).
Skema Umum Algoritma Greedy
Algoritma greedy disusun oleh elemen-elemen berikut:
1. Himpunan kandidat.
Berisi elemen-elemen pembentuk solusi.
2. Himpunan solusi
Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
3. Fungsi seleksi (selection function)
Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
4. Fungsi kelayakan (feasible)
Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.
5. Fungsi obyektif, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).
Contoh pada masalah penukaran uang, elemen-elemen algoritma greedy-nya adalah:
1. Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
2. Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
3. Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
4. Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
5. Fungsi obyektif: jumlah koin yang digunakan minimum.
Sumber :
Tidak ada komentar:
Posting Komentar