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