Jumat, 16 Oktober 2009

Strategi Greedy pada Kasus Pencarian Lintasan Terpendek

Abstrak

Kita semua tahu kemacetan yang sering terjadi selama perjalanan, sering mengganggu kegiatan kita

sehari-hari, selain itu hal tersebut membuat kita tidak merasa nyaman dalam perjalanan. Dalam setiap

perjalanan, manusia ingin sampai ke tujuan dengan tepat waktu. Tetapi, sering kali kemacetan

menyebabkan keinginan manusia yang satu ini terganggu. Oleh karena itu, dibutuhkan suatu cara untuk

menanggulangi gangguan tersebut. Untuk mencapai suatu tempat dengan waktu yang lebih cepat, kita

akan mencari lintasan terpendek dari tempat asal ke tempat tujuan. Lintasan terpendek ini juga

memperhitungkan waktu-waktu dimana kemacetan sering terjadi. Contoh pencarian lintasan terpendek

adalah: ketika kita dari kampus ingin ke pasar Dayeuhkolot pukul 13.00 hari Senin. Kita bisa melewati

Jl. Sukabirus, tidak melewati Jl. Moch Toha yang melewati Jl. Radio Palasari . Tentu saja ini akan

menghemat waktu kita. Pada makalah ini akan mencoba membahas masalah pencarian lintasan

terpendek berdasarkan jarak dan waktu-waktu terjadinya kemacetan.

Kata kunci : strategi greedy, lintasan terpendek, graf berbobot

1. Pendahuluan

Informasi yang akurat dan realistis sangat

dibutuhkan saat ini. Beberapa tahun ini

perkembangan teknologi berkembang sangat pesat

, sehingga kebutuhan manusia akan informasi

tersebut semakin meningkat. Oleh karena itu

dibutuhkan waktu yang cepat untuk mencapai

kebutuhan tersebut.

Strategi Greedy merupakan suatu urutan langkah-

langkah (program) yang tepat untuk meningkatkan

efisiensi waktu.

2. Strategi Greedy

2.1 Definisi Strategi Greedy

Strategi greedy adalah strategi yang memecahkan

masalah langkah demi langkah, pada setiap

langkah, adapun urutan langkah strategi Greedy

adalah :

1. mengambil pilihan yang terbaik yang dapat

diperoleh saat itu,

2. berharap bahwa dengan memilih solusi optimum

lokal, pada setiap langkah akan mencapai solusi

optimum global. Strategi greedy mengasumsikan

bahwa optimum lokal merupakan bagian dari

optimum global.

Prinsip strategi greedy adalah: “take what you can

get now!”. Ambil apa yang anda peroleh sekarang!

Prinsip ini juga dipakai dalam pemecahan masalah

optimasi. Dalam kehidupan sehari-hari, kita juga

pernah menggunakan prinsip greedy, misalnya:

a. Memilih jurusan di Perguruan Tinggi

b. Memilih jalur tersingkat dari Bandung ke

Jakarta.

2.2 Skema Umum Strategi Greedy

Persoalan optimasi dalam konteks strategi greedy

disusun oleh elemen-elemen sebagai berikut:

1. Himpunan kandidat, C.

Himpunan ini berisi elemen-elemen pembentuk

solusi. Pada setiap langkah, satu buah kandidat

diambil dari himpunannya.

Tidak ada komentar:

Posting Komentar