Monday 14 February 2011
LAPORAN
Perbandingan Algoritma Greedy dan Algoritma Branch and Bound
Dalam pencarian lintasan terpendek
Di ajukan untuk memenuhi tugas pada mata kuliah Strategi Algoritma
JURUSAN TEKNIK INFORMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI
SUNAN GUNUNG DJATI
BANDUNG
2010
BAB I
PEBDAHULUAN
1. Latar Belakang
Dalam kehidupan sehari-hari sering kita lakukan perjalanan dari suatu tempat ke tempat dari kota ke kota lain dengan pertimbangan waktu yang efisien dan juga biaya sehingga di perlukan ketepatan dalam menentukan jalur terpendek antara suatu tempat hasil dari penentuan jalur terpendek akan menjadi pertimbangan dalam pengambilan keputusan untuk menunjukan jalur yang di tempuh. Hasil yang di dapatkan juga membutuhkan kecepatan dan keakuratan dengan bantuan computer
Secara umum, pencarian jalur terpendek dapat dibagi menjadi 2 bagian yaitu :metode konvensional dan metode heuristic, metode konvensionalmerupakan metode yang menggunakan perhitungan matematik biasa, pada pencarian lintasan terpendek hanya dapat diselesikan untuk 5 sampai 10 veteks, untuk verteks yang lebih banyak metode heuristic lebih variatif dan waktu perhitungan yang diperlukan lebih singkat, karena metode heuristic menggunakan metode pendekatan dan melakukan pencarian
Untuk menggunakan atau memfungsikan sebuah computer harus terdapat program yang terdistribusi di dalamnya. Tanpa program tersebut kmputer hanyalah menjadi sebuah kotak yang tak berguna, program yang terdapat dalam computer sangat bervariasi dan setiap program tersebut pasti menggunakan Algoritma.
Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah perintahnya dapat diterjemahkan secara bertahap dari awal sampai akhir
Algoritma yang akan digunakan untuk mencari lintasan terpendek dalam hal ini adalah Algoritma greedy dan Algoritma branch and bound, serta Algoritma Djikstra yang merupakan Algoritma yang paling terkenal untuk mencari lintasan terpendek yang diterapkan pada graph berarah dan berbobot, dimana jarak antara vertex adalah bobot dari tiap arc pada graph tersebut, selain Algoritma djikstra Algoritma greedy juga merupakan salah satu metode untuk memecahkan masalah langkah demi lakah,yang pada setiap langkahnya mengambil pilihan yang terbaik yang diperoleh saat itu tanpa memperhatikan konsekuensi kedepannya dengan gagasan dasar adalah membangun solusi besar diatas solusi kecil
2. Rumusan Masalah
Rumusan masalah yang akan diteliti dalam tulisam ini adalah bagaimana perbandingan Algoritma Greedy dan branch and bound sehingga diperoleh Algoritma yang tepat dan akurat dan dapat di implementasikan untuk menyelesaikan masalah lintasan terpendek
Dalam melakukan perbandingan Algoritma ini dilakukan beberapa batasan sebagai berikut:
1. Algoritma Greedy dan B&B yang digunakan dibatasi pada permasalahan shortest path saja, dengan input graph yang terdiri dari jumlah titik,nama dan koordinat titik, letak titik dapat dibangkitkan secara acak maupun manual.
2. Bobot antar titik yang ditentukan hanyalah bobot jarak, dengan mengabaikan bobot-bobot lainnya, sehingga jalur terpendekberdasarkan jarak tependek antar titik
3. Keluaran yang dihasilkan adalah hasil dari Algoritma Greedy dan B&B yang diiplementasikan dalam suatuprogram sederhana
3. Tujuan Laporan
Tujuan dari laporan ini untuk membandingkan pencarian lintasan tependek manakan yang lebih baik dan efisien dari implementasi Algoritma Greedy dan bench and bound
4. Tinjauan Pustaka
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 langkahlangkah
(program) yang tepat untuk meningkatkan efisiensi waktu.
BABA II
PEMBAHASAN
1. Pengertian lintasan terpendek
Lintasan terperndek adalah lintasan minimum yang
diperlukan untuk mencapai suatu tempat dari
tempat tertentu.
Ada beberapa macam persoalan lintasan terpendek, antara lain:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
c. Lintasan terpendek dari simpul tertentu ke semua
simpul yang lain (single-source shoertest path).
d. Lintasan terpendek antara dua buah simpul yang
melalui beberapa simpul tertentu (intermediate shortest path).
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 Sukabumi
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
2. Himpunan solusi, S.
Merupakan himpunan dari kandidat-kandidat yang terpilih sebagai solusi persoalan. Himpunan solusi adalah himpunan bagian dari himpunan kandidat.
3. Fungsi seleksi – dinyatakan sebagai predikat SELEKSI –Merupakan fungsi yang pada setiap langkah memilih kandidat yang paling mungkin untuk
mendapatkan solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
4. Fungsi kelayakan (feasible) – dinyatakan dengan predikat LAYAK – Merupakan fungsi yang 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 aturan yang ada.
5. Fungsi obyektif, merupakan fungsi yang memaksimumkan atau meminimumkan nilai solusi. Dalam strategi ini, kita berharap optimum global mmerupakan solusi optimum dari persoalan. Namun, adakalanya optimum global belum tentu merupakan solusi optimum (terbaik), tetapi dapat merupakan solusi sub-optimum atau pseudo-optimum.
Hal ini dapat dijelaskan dari dua faktor berikut:
1. strategi greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada.
2. pemilihan fungsi SELEKSI: fungsi SELEKSI biasanya didasarkan pada fungsi obyektif (fungsi SELEKSI bisa saja identik dengan fungsi obyektif). Jika fungsi SELEKSI tidak identik dengan fungsi obyektif, kita harus memilih fungsi yang tepat untuk menghasilkan nilai yang optimum. Karena itu, pada sebagian masalah strategi Greedy tidak selalu berhasil memberikan solusi yang benarbenar optimum. Tetapi, strategi greedy pasti memberikan solusi yang mendekati (approximation) nilai optimum.
3. Lintasan Terpendek (Shortest Path)
3.1 Definisi Lintasan Terpendek
Lintasan terperndek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Dalam kasus ini, bobot yang dimaksud berupa jarak
dan waktu kemacetan terjadi.
3.2 Single-source shortest path
Ada beberapa macam persoalan lintasan terpendek,
antara lain:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain
(single-source shoertest path).
d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).
Dalam makalah ini, persoalan yang digunakan adalah single-source shortest path. Diberikan
sebuah persoalan: “Diberikan sebuah graf berbobot G(V, E). Tentukan lintasan terpendek dari simpul awal, a, ke setiap simpul lainnya di G. Asumsi bahwa bobot
semua sisi bernilai positif.” Strategi greedy untuk mencari lintasan terpendek dapat dirumuskan sebagai berikut:
1. Periksa semua sisi yang langsung bersisian dengan simpul a. Pilih sisi yang bobotnya
terkecil. Sisi ini menjadi lintasan terpendek pertama, sebut saja L(1).
2. Tentukan lintasan terpendek kedua dengan cara berikut:
(i) hitung: d(i) = panjang L(1) + bobot sisi dari simpul akhir L(1) ke simpul i yang lain
(ii) pilih d(i) yang terkecil Bandingkan d(i) dengan bobot sisi (a, i). Jika bobot sisi (a,i) lebih kecil daripada d(i), maka
L(2)=L(1) U (sisi dari simpul akhir L(i) ke simpul i)
3. Dengan cara yang sama, ulangi langkah 2 untuk menentukan lintasan terpendek berikutnya.
4. Strategi Greedy pada Algoritma Dijkstra
4.1 Algoritmai Dijkstra
Algoritma Dijkstra ditemukan oleh Edger Wybe Dijkstra. Strategi ini merupakan strategi yang paling terkenal untuk mencari lintasan terpendek. Algoritma Dijkstra diterapkan pada graf berarah, tetapi selalu benar untuk graf tak-berarah. Strategi ini menggunakan strategi Greedy sebagai berikut: “Pada setiap langkah, ambil sisi yang berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang
terpendek diantara semua lintasannya ke simpulsimpul yang belum terpilih.”
Langkah-langkah Algoritma Dijkstra yang lebih jelas dapat dilihat di buku Matematika Diskrit Edisi ketiga, penulis Ir. Rinaldi Munir
5. Analisis Algoritma Dijkstra untuk Mencari Lintasan Terpendek.
Analisis yang dilakukan meliputi 2 aspek, yaitu:
1. berdasarkan graf berbobot yang bobotnya
merupakan panjang lintasan
2. berdasarkan graf berbobot yang bobotnya
merupakan waktu terjadinya kemacetan.
Gambar 1. Penggambaran Graf Berbobot
Keterangan:
A = Cileunyi
B = Bundaran cibiru
C = Cicaheum
D = Kiara condong
E = Terminal Leuwi Panjang
Tabel 1. Panjang Lintasan dari Satu Tempat ke
Tempat lainnya
Contoh persoalan: carilah lintasan terpendek dari
Kiara condong menuju Terminal LeuwiPanjang! Jadi, lintasan terpendek dari kircon menuju
terminal Leuwi Panjang adalah: D-C-B-E, yaitu
sepanjang: 300m+850m+3000m = 4150 m
Keterangan :
Jarak yang digunakan dari satu tempat ke tempat yang lainnya sama dengan jarak yang digunakan pada tabel 1. Contoh persoalan : carilah lintasan terpendek dari Kiara condong ke terminal Leuwi Panjang pada pukul 12.00!
Ditinjau dari tingkat kemacetan yang terjadi maka lintasan terpendek dari kampus STT Telkom ke terminal Leuwi Panjang adalah D – E = 4500 m
Dari solusi kasus pada tabel 1 dan 2 dapat dilihat penerapan strategi greedy, dimana solusi didapat berdasarkan satu aspek tanpa memperhatikan aspek lain. Pada tabel 1 dimana aspek yang diminta adalah jarak maka akan dipilih lintasan terpendek berdasarkan jarak real-nya tanpa memperhatikan aspek kemacetan pada jam-jam tertentu. Demikian juga pada table 2.
6. Algoritma Branch and Bound
1. BFS (Breadth First Search)
BFS dikenal sebagai pencarian melebar dalam pohon. Misalkan graf G mempunya n buah simpul. Traversal di dalam graf dilakukan mulai simpul v. Algortima BFS adalah sebagai berikut : bangkitkan simpul v, kemudian semua simpul yang bertetangga dengan simpul v dibangkitkan terlebih dahulu. Selanjutnya, simpul yang belum dibangkitkan dan bertetangga dengan simpulsimpul tadi dibangkitkan, demikian seterusnya
Jika graf berbentuk pohon berakar, maka semua simpul pada level d dibangkitkan terlebih dahulu sebelum membangkitkan simpul-simpul pada level d+1. [1]
Algoritma BFS menggunakan antrian untuk menyimpan simpul-simpul yang baru dibangkitkan. Simpul-simpul yang baru dibangkitkan ditempatkan di belakang antrian. [1]
Prinsip antrian yang digunakan adalah FIFO (First In First Out). Dengan skema ini, simpul
hidup dimasukkan ke dalam antrian, simpul berikutnya yang akan menjadi simpul ekspansi
adalah simpul yang pertama masuk ke dalam antrian.
2. Pencarian Solusi Algoritma B&B
Pada algoritma B&B ruang solusi diorganisasikan ke dalam pohon ruang status
yang dibangun dengan skema BFS. Untuk mempercepat pencarian ke simpul solusi, setiap
simpul diberi nilai ongkos c(i) yang merupakan taksiran lintasan termurah dari simpul akar
simpul status jutuan. Simpul berikutnya yang akan diekspansi tidak lagi berdasarkan prinsip
FIFO pada antrian, melainkan dipilih simpul dengan nilai ongkos terkecil.
Fungsi heuristik untuk menghitung taksiran nilai ongkos dinyatakan secara umum sebagai :
c(i) = f(i) + g(i) (1)
yang dalam hal ini:
c(i) = ongkos untuk simpul i
f(i) = ongkos untuk mencapai simpul i
g(i) = ongkos untuk mencapai simpul
tujuan dari simpul i [1]
Algoritma B&B :
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul
solusi, maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai c(i) terkecil.
Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.
4. Jika simpul i adalah simpul simpul solusi, berarti simpul telah ditemukan,
stop. Jika simpul i bukan simpul solusi maka bangkitkan semua anak-anaknya.
Jika i tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul i, hitung c(i), dan masukkan anak-anak tersebut
ke dalam antrian Q.
6. Kembali ke langkah 2. [1]
3. Persoalan Lintasan Terpendek (Shortest Path)
Persoalan lintasan terpendek adalah menemukan lintasan terpendek dari sebuah simpul asal a ke simpul lain dalam graf G. Graf G merupakan graf berbobot positif.
4. Metode
Untuk menjelaskan dan menguji metode, diambil contoh sebuah matriks yang merepresentasikan sebuah graph berarah G :
Metode yang digunakan adalah metode B&B untuk TSP. Pada TSP, solusi adalah sirkuit
Hamilton dengan panjang rute terpendek. Persoalan Shortest Path memiliki tujuan yang
sama yaitu menemukan rute terpendek namun bukan untuk sebuah sirkuit Hamilton melainkan rute terpendek dari sebuah simpul ke simpul lainnya. Metode yang digunakan berikut ini berdasarkan metode B&B untuk TSP dari [1].
Akan dicari rute terpendek dari simpul 3 ke simpul 6. Langkah pertama dilakukan reduksi matriks G :
Karena belum terdapat nilai nol pada kolom satu dan empat, maka masing-masing kolom tersebut dikurangi dengan nilai terkecil dalam kolom. Matriks tereduksi akhir yang didapat adalah :
Total nilai pengurang adalah (10 + 5 + 15 + 3 +
10 + 6) + (4 + 20) = 63. Simpul akar ini dimasukkan antrian Q dengan nilai batas 63.
Simpul akar ini selanjutnya akan diekspansi. Pohon ruang status yang dibangun :
Langkah untuk membangkitkan simpul selanjutnya adalah :
1. Ubah semua nilai pada matriks bobot tereduksi untuk simpul bapak pada baris
ke i dan kolom ke j dengan ~. Dimana I dan j menunjukkan simpul yang dituju pada graf.
2. Ubah nilai matriks tereduksi pada (j,3) agar simpul tersebut tidak digunakan.
3. Reduksi kembali matriksnya.
4. Hitung nilai batas simpul pada pohon yang sedang dibangkitkan.
5. Masukkan simpul tersebut dalam antrian Q.
6. Bangkitkan simpul anak yang lain seperti pada langkah pertama.
7. Pilih simpul dengan nilai batas terkecil untuk diekspansi.
8. Kembali ke langkah 1. Selanjutnya dibangkitkan simpul-simpul yang
bertetangga dengan simpul 3 yaitu simpul 1 dan 4.
Simpul hidup dalam antrian Q adalah : 2(73), 3(63). Karena simpul 3 memiliki nilai batas
terkecil, simpul selanjutnya yang diekspansi adalah simpul 3. Pohon yang terbentuk :
Karena simpul 4 memiliki nilai batas terkecil, selanjutnya akan diekspansi. Pada graf, dari
simpul 2 kita bisa ke simpul 3, 5 dan 6. Sampai saat ini jalur yang terbentuk adalah 3-5-2, karena itu dari simpul 2 kita tidak akan mengunjungi simpul 3 dan 5.
Sampai di sini telah terbentuk lintasan 3-5-2-6 yang artinya telah ditemukan solusi jadi,
pembentukan pohon dapat dihentikan. Solusi ini merupakan solusi terbaik sejauh ini. Simpulsimpul yang lain dapat dibunuh karena dari simpul-simpul tersebut tidak mungkin dihasilkan solusi yang lebih baik.
5 Persoalan Lintasan Terpendek ( Path-finding)
Persoalan pencarian jalan (path-finding) adalah persoalan menjacari lintasan dari titik awal menuju titik akhir yang ditentukan dengan melewati hambatanhambatan (constrains) yang ada.
Gambar 1. Salah satu contoh persoalan path-finding. S adalah titik awal dan F adalah titik akhir.
Konsep Branch and Bound
Sebagaimana pada algortima runut-balik, Algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runut-balik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth- First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).
Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk
setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :
c(i) = ƒ(i) + g(i)
yang dalam hal ini,
c(i) = ongkos untuk simpul i
ƒ(i) = ongkos mencapai simpul i dari akar
g(i) = ongkos mencapai simpul tujuan dari simpul akar i
Nilai c digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki c minimum.
Algoritma Branch and Bound
Algoritma B&B jika dituliskan secara procedural adalah
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi . Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul I yang mempunyai c(i) paling kecil. Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika I tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul i, hitung c(j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.
6. Kembali ke langkah 2.
c. Pseudo-Code
Algoritma branch and bound
procedure findPath()
while not found and ada simpul hidup
node n1 = findLeastCost();
generateChilds(n1);
function findLeastCost() : node
{mengembalikan node dengan cost terkecil}
procedure generateChilds(node n)
{membangkitkan simpul anak n}
7. UJI SIMULASI
Algoritma ini akan diuji coba pada kasus yang lebih
rumit. yaitu pada matriks ukurang 21 x 51 dengan
hambatan-habatan yang lebih banyak. Pada bagian ini
hanya akan diperlihatkan hasil programnya (PathFinder
1.0). Program tersebut dibuat oleh penulis untuk keperluan
pengujian.
Berikut ini adalah matriks yang diberikan
Gambar 9. Screenshot program
Tanda ‘x’ pada gambar merupakan hambatan yang tidak
dapat dilalui. Tanda ‘S’ merupakan titik awal dan tanda
‘F’ merupakan titik akhir. Hasil dari program tersebut
adalah seperti di bawah ini.
Gambar 9. Screenshot program (solusi)
Tanda ‘*’ menyatakan lintasan penyelesaian. Jika tidak
terdapat penyelesaian, maka program akan mencetak
‘Tidak ada solusi’.
8. Kesimpulan
Pada kasus serta analisa dari contoh soal tersebut, dapat disimpulkan bahwa pencarian lintasan terpendek sangat berguna untuk menentukan jalan tersingkat untuk menuju suatu tempat dimana terdapat suatu variabel lain yang juga mempengaruhi. Dalam hal ini adalah waktu kemacetan yang dapat digunakan sebagai variable yang mempengaruhi kecepatan kita, sehingga, kita dapat sampai tepat waktu menuju tempat tujuan. Hasil analisis berdasarkan bobot-bobot yang berbeda, menunjukkan bahwa semakin banyak bobot yang diberikan, maka semakin akurat pula data yang dihasilkan. Sehingga menghasilkan waktu yang efisien. Penerapan strategi greedy pada pencarian lintasan terpendek belum tentu menghasilkan nilai yang optimum karena hanya mengacu pada satu aspek dan akan mencari nilai maksimum pada aspek tersebut dengan mengabaikan aspek yang lain.
1. Metode B&B
Algoritma pencarian jarak terpendek dengan metode B&B :
1. Reduksi matrik yang merepresentasikan graf dengan mengurangi setiap baris atau kolom dengan nilai terkecil baris atau kolom tersebut sehingga didapat matriks dengan minimal satu nilai nol pada setiap baris dan kolom.
2. Masukkan simpul akar dengan nilai batas c(1) = total pengurang matriks ke dalam antrian Q. Jika simpul akar adalah simpul solusi, maka solusi telah ditemukan. Stop.
3. Jika Q kosong, tidak ada solusi. Stop.
4. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai c(i) terkecil.
Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.
5. Jika simpul i adalah simpul solusi, berarti solusi telah ditemukan, stop. Jika
simpul i bukan simpul solusi maka bangkitkan semua anak-anaknya. Cara membangkitkan simpul anak :
1. Ubah semua nilai pada matriks bobot tereduksi milik simpul bapak pada baris ke i dan kolom ke j dengan ~. Dimana i dan j menunjukkan simpul yang dituju pada graf.
2. Ubah nilai matriks tereduksi pada (j,simpul asal pada graf) agar simpul tersebut tidak digunakan.
3. Reduksi kembali matriksnya. Jika i tidak mempunyai anak, kembali ke langkah 2.
4. Untuk setiap anak j dari simpul i, hitung c(j), dan masukkan anak-anak tersebut
ke dalam antrian Q. c(j) didapat dari rumus :
c(j) = c(i) + M(k,l) + r
dimana :
c(j) : nilai ongkos simpul anak
c(i) : nilai ongkos simpul bapak
M(k,l) : bobot sisi k ke l
R : total pengurang pada proses reduksi
5. Kembali ke langkah 2.
DAFTAR PUSTAKA
[1] Munir, Rinaldi. (2007). Diktat Kuliah IF2251
Strategi Algoritmik. Departemen Teknik
Informatika, Institut Teknologi Bandung.
[ 1 ] Strategi Greedy.
http://kur2003.if.itb.ac.id/strategialgoritmik.
Diakses tanggal 18 Maret 2006.
[ 2 ] Arif Y, Fazmah , Diktat Kuliah CS3024 Desain
dan Analisis Strategi , Bandung, 2006.
[ 3 ] Prama, Irvan, dkk. Makalah Algoritma Greedy
untuk Mencari Lintasan Terpendek, Departemen
Teknik Informatika ITB, 2005.
[ 4 ] S., Mehran, April 2005, Exhaustive Recursion
and Backtracking.
Perbandingan Algoritma Greedy dan Algoritma Branch and Bound
Dalam pencarian lintasan terpendek
Di ajukan untuk memenuhi tugas pada mata kuliah Strategi Algoritma
JURUSAN TEKNIK INFORMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI
SUNAN GUNUNG DJATI
BANDUNG
2010
BAB I
PEBDAHULUAN
1. Latar Belakang
Dalam kehidupan sehari-hari sering kita lakukan perjalanan dari suatu tempat ke tempat dari kota ke kota lain dengan pertimbangan waktu yang efisien dan juga biaya sehingga di perlukan ketepatan dalam menentukan jalur terpendek antara suatu tempat hasil dari penentuan jalur terpendek akan menjadi pertimbangan dalam pengambilan keputusan untuk menunjukan jalur yang di tempuh. Hasil yang di dapatkan juga membutuhkan kecepatan dan keakuratan dengan bantuan computer
Secara umum, pencarian jalur terpendek dapat dibagi menjadi 2 bagian yaitu :metode konvensional dan metode heuristic, metode konvensionalmerupakan metode yang menggunakan perhitungan matematik biasa, pada pencarian lintasan terpendek hanya dapat diselesikan untuk 5 sampai 10 veteks, untuk verteks yang lebih banyak metode heuristic lebih variatif dan waktu perhitungan yang diperlukan lebih singkat, karena metode heuristic menggunakan metode pendekatan dan melakukan pencarian
Untuk menggunakan atau memfungsikan sebuah computer harus terdapat program yang terdistribusi di dalamnya. Tanpa program tersebut kmputer hanyalah menjadi sebuah kotak yang tak berguna, program yang terdapat dalam computer sangat bervariasi dan setiap program tersebut pasti menggunakan Algoritma.
Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah perintahnya dapat diterjemahkan secara bertahap dari awal sampai akhir
Algoritma yang akan digunakan untuk mencari lintasan terpendek dalam hal ini adalah Algoritma greedy dan Algoritma branch and bound, serta Algoritma Djikstra yang merupakan Algoritma yang paling terkenal untuk mencari lintasan terpendek yang diterapkan pada graph berarah dan berbobot, dimana jarak antara vertex adalah bobot dari tiap arc pada graph tersebut, selain Algoritma djikstra Algoritma greedy juga merupakan salah satu metode untuk memecahkan masalah langkah demi lakah,yang pada setiap langkahnya mengambil pilihan yang terbaik yang diperoleh saat itu tanpa memperhatikan konsekuensi kedepannya dengan gagasan dasar adalah membangun solusi besar diatas solusi kecil
2. Rumusan Masalah
Rumusan masalah yang akan diteliti dalam tulisam ini adalah bagaimana perbandingan Algoritma Greedy dan branch and bound sehingga diperoleh Algoritma yang tepat dan akurat dan dapat di implementasikan untuk menyelesaikan masalah lintasan terpendek
Dalam melakukan perbandingan Algoritma ini dilakukan beberapa batasan sebagai berikut:
1. Algoritma Greedy dan B&B yang digunakan dibatasi pada permasalahan shortest path saja, dengan input graph yang terdiri dari jumlah titik,nama dan koordinat titik, letak titik dapat dibangkitkan secara acak maupun manual.
2. Bobot antar titik yang ditentukan hanyalah bobot jarak, dengan mengabaikan bobot-bobot lainnya, sehingga jalur terpendekberdasarkan jarak tependek antar titik
3. Keluaran yang dihasilkan adalah hasil dari Algoritma Greedy dan B&B yang diiplementasikan dalam suatuprogram sederhana
3. Tujuan Laporan
Tujuan dari laporan ini untuk membandingkan pencarian lintasan tependek manakan yang lebih baik dan efisien dari implementasi Algoritma Greedy dan bench and bound
4. Tinjauan Pustaka
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 langkahlangkah
(program) yang tepat untuk meningkatkan efisiensi waktu.
BABA II
PEMBAHASAN
1. Pengertian lintasan terpendek
Lintasan terperndek adalah lintasan minimum yang
diperlukan untuk mencapai suatu tempat dari
tempat tertentu.
Ada beberapa macam persoalan lintasan terpendek, antara lain:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
c. Lintasan terpendek dari simpul tertentu ke semua
simpul yang lain (single-source shoertest path).
d. Lintasan terpendek antara dua buah simpul yang
melalui beberapa simpul tertentu (intermediate shortest path).
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 Sukabumi
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
2. Himpunan solusi, S.
Merupakan himpunan dari kandidat-kandidat yang terpilih sebagai solusi persoalan. Himpunan solusi adalah himpunan bagian dari himpunan kandidat.
3. Fungsi seleksi – dinyatakan sebagai predikat SELEKSI –Merupakan fungsi yang pada setiap langkah memilih kandidat yang paling mungkin untuk
mendapatkan solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
4. Fungsi kelayakan (feasible) – dinyatakan dengan predikat LAYAK – Merupakan fungsi yang 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 aturan yang ada.
5. Fungsi obyektif, merupakan fungsi yang memaksimumkan atau meminimumkan nilai solusi. Dalam strategi ini, kita berharap optimum global mmerupakan solusi optimum dari persoalan. Namun, adakalanya optimum global belum tentu merupakan solusi optimum (terbaik), tetapi dapat merupakan solusi sub-optimum atau pseudo-optimum.
Hal ini dapat dijelaskan dari dua faktor berikut:
1. strategi greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada.
2. pemilihan fungsi SELEKSI: fungsi SELEKSI biasanya didasarkan pada fungsi obyektif (fungsi SELEKSI bisa saja identik dengan fungsi obyektif). Jika fungsi SELEKSI tidak identik dengan fungsi obyektif, kita harus memilih fungsi yang tepat untuk menghasilkan nilai yang optimum. Karena itu, pada sebagian masalah strategi Greedy tidak selalu berhasil memberikan solusi yang benarbenar optimum. Tetapi, strategi greedy pasti memberikan solusi yang mendekati (approximation) nilai optimum.
3. Lintasan Terpendek (Shortest Path)
3.1 Definisi Lintasan Terpendek
Lintasan terperndek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Dalam kasus ini, bobot yang dimaksud berupa jarak
dan waktu kemacetan terjadi.
3.2 Single-source shortest path
Ada beberapa macam persoalan lintasan terpendek,
antara lain:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortets path).
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain
(single-source shoertest path).
d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).
Dalam makalah ini, persoalan yang digunakan adalah single-source shortest path. Diberikan
sebuah persoalan: “Diberikan sebuah graf berbobot G(V, E). Tentukan lintasan terpendek dari simpul awal, a, ke setiap simpul lainnya di G. Asumsi bahwa bobot
semua sisi bernilai positif.” Strategi greedy untuk mencari lintasan terpendek dapat dirumuskan sebagai berikut:
1. Periksa semua sisi yang langsung bersisian dengan simpul a. Pilih sisi yang bobotnya
terkecil. Sisi ini menjadi lintasan terpendek pertama, sebut saja L(1).
2. Tentukan lintasan terpendek kedua dengan cara berikut:
(i) hitung: d(i) = panjang L(1) + bobot sisi dari simpul akhir L(1) ke simpul i yang lain
(ii) pilih d(i) yang terkecil Bandingkan d(i) dengan bobot sisi (a, i). Jika bobot sisi (a,i) lebih kecil daripada d(i), maka
L(2)=L(1) U (sisi dari simpul akhir L(i) ke simpul i)
3. Dengan cara yang sama, ulangi langkah 2 untuk menentukan lintasan terpendek berikutnya.
4. Strategi Greedy pada Algoritma Dijkstra
4.1 Algoritmai Dijkstra
Algoritma Dijkstra ditemukan oleh Edger Wybe Dijkstra. Strategi ini merupakan strategi yang paling terkenal untuk mencari lintasan terpendek. Algoritma Dijkstra diterapkan pada graf berarah, tetapi selalu benar untuk graf tak-berarah. Strategi ini menggunakan strategi Greedy sebagai berikut: “Pada setiap langkah, ambil sisi yang berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang
terpendek diantara semua lintasannya ke simpulsimpul yang belum terpilih.”
Langkah-langkah Algoritma Dijkstra yang lebih jelas dapat dilihat di buku Matematika Diskrit Edisi ketiga, penulis Ir. Rinaldi Munir
5. Analisis Algoritma Dijkstra untuk Mencari Lintasan Terpendek.
Analisis yang dilakukan meliputi 2 aspek, yaitu:
1. berdasarkan graf berbobot yang bobotnya
merupakan panjang lintasan
2. berdasarkan graf berbobot yang bobotnya
merupakan waktu terjadinya kemacetan.
Gambar 1. Penggambaran Graf Berbobot
Keterangan:
A = Cileunyi
B = Bundaran cibiru
C = Cicaheum
D = Kiara condong
E = Terminal Leuwi Panjang
Tabel 1. Panjang Lintasan dari Satu Tempat ke
Tempat lainnya
Contoh persoalan: carilah lintasan terpendek dari
Kiara condong menuju Terminal LeuwiPanjang! Jadi, lintasan terpendek dari kircon menuju
terminal Leuwi Panjang adalah: D-C-B-E, yaitu
sepanjang: 300m+850m+3000m = 4150 m
Keterangan :
Jarak yang digunakan dari satu tempat ke tempat yang lainnya sama dengan jarak yang digunakan pada tabel 1. Contoh persoalan : carilah lintasan terpendek dari Kiara condong ke terminal Leuwi Panjang pada pukul 12.00!
Ditinjau dari tingkat kemacetan yang terjadi maka lintasan terpendek dari kampus STT Telkom ke terminal Leuwi Panjang adalah D – E = 4500 m
Dari solusi kasus pada tabel 1 dan 2 dapat dilihat penerapan strategi greedy, dimana solusi didapat berdasarkan satu aspek tanpa memperhatikan aspek lain. Pada tabel 1 dimana aspek yang diminta adalah jarak maka akan dipilih lintasan terpendek berdasarkan jarak real-nya tanpa memperhatikan aspek kemacetan pada jam-jam tertentu. Demikian juga pada table 2.
6. Algoritma Branch and Bound
1. BFS (Breadth First Search)
BFS dikenal sebagai pencarian melebar dalam pohon. Misalkan graf G mempunya n buah simpul. Traversal di dalam graf dilakukan mulai simpul v. Algortima BFS adalah sebagai berikut : bangkitkan simpul v, kemudian semua simpul yang bertetangga dengan simpul v dibangkitkan terlebih dahulu. Selanjutnya, simpul yang belum dibangkitkan dan bertetangga dengan simpulsimpul tadi dibangkitkan, demikian seterusnya
Jika graf berbentuk pohon berakar, maka semua simpul pada level d dibangkitkan terlebih dahulu sebelum membangkitkan simpul-simpul pada level d+1. [1]
Algoritma BFS menggunakan antrian untuk menyimpan simpul-simpul yang baru dibangkitkan. Simpul-simpul yang baru dibangkitkan ditempatkan di belakang antrian. [1]
Prinsip antrian yang digunakan adalah FIFO (First In First Out). Dengan skema ini, simpul
hidup dimasukkan ke dalam antrian, simpul berikutnya yang akan menjadi simpul ekspansi
adalah simpul yang pertama masuk ke dalam antrian.
2. Pencarian Solusi Algoritma B&B
Pada algoritma B&B ruang solusi diorganisasikan ke dalam pohon ruang status
yang dibangun dengan skema BFS. Untuk mempercepat pencarian ke simpul solusi, setiap
simpul diberi nilai ongkos c(i) yang merupakan taksiran lintasan termurah dari simpul akar
simpul status jutuan. Simpul berikutnya yang akan diekspansi tidak lagi berdasarkan prinsip
FIFO pada antrian, melainkan dipilih simpul dengan nilai ongkos terkecil.
Fungsi heuristik untuk menghitung taksiran nilai ongkos dinyatakan secara umum sebagai :
c(i) = f(i) + g(i) (1)
yang dalam hal ini:
c(i) = ongkos untuk simpul i
f(i) = ongkos untuk mencapai simpul i
g(i) = ongkos untuk mencapai simpul
tujuan dari simpul i [1]
Algoritma B&B :
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul
solusi, maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai c(i) terkecil.
Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.
4. Jika simpul i adalah simpul simpul solusi, berarti simpul telah ditemukan,
stop. Jika simpul i bukan simpul solusi maka bangkitkan semua anak-anaknya.
Jika i tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul i, hitung c(i), dan masukkan anak-anak tersebut
ke dalam antrian Q.
6. Kembali ke langkah 2. [1]
3. Persoalan Lintasan Terpendek (Shortest Path)
Persoalan lintasan terpendek adalah menemukan lintasan terpendek dari sebuah simpul asal a ke simpul lain dalam graf G. Graf G merupakan graf berbobot positif.
4. Metode
Untuk menjelaskan dan menguji metode, diambil contoh sebuah matriks yang merepresentasikan sebuah graph berarah G :
Metode yang digunakan adalah metode B&B untuk TSP. Pada TSP, solusi adalah sirkuit
Hamilton dengan panjang rute terpendek. Persoalan Shortest Path memiliki tujuan yang
sama yaitu menemukan rute terpendek namun bukan untuk sebuah sirkuit Hamilton melainkan rute terpendek dari sebuah simpul ke simpul lainnya. Metode yang digunakan berikut ini berdasarkan metode B&B untuk TSP dari [1].
Akan dicari rute terpendek dari simpul 3 ke simpul 6. Langkah pertama dilakukan reduksi matriks G :
Karena belum terdapat nilai nol pada kolom satu dan empat, maka masing-masing kolom tersebut dikurangi dengan nilai terkecil dalam kolom. Matriks tereduksi akhir yang didapat adalah :
Total nilai pengurang adalah (10 + 5 + 15 + 3 +
10 + 6) + (4 + 20) = 63. Simpul akar ini dimasukkan antrian Q dengan nilai batas 63.
Simpul akar ini selanjutnya akan diekspansi. Pohon ruang status yang dibangun :
Langkah untuk membangkitkan simpul selanjutnya adalah :
1. Ubah semua nilai pada matriks bobot tereduksi untuk simpul bapak pada baris
ke i dan kolom ke j dengan ~. Dimana I dan j menunjukkan simpul yang dituju pada graf.
2. Ubah nilai matriks tereduksi pada (j,3) agar simpul tersebut tidak digunakan.
3. Reduksi kembali matriksnya.
4. Hitung nilai batas simpul pada pohon yang sedang dibangkitkan.
5. Masukkan simpul tersebut dalam antrian Q.
6. Bangkitkan simpul anak yang lain seperti pada langkah pertama.
7. Pilih simpul dengan nilai batas terkecil untuk diekspansi.
8. Kembali ke langkah 1. Selanjutnya dibangkitkan simpul-simpul yang
bertetangga dengan simpul 3 yaitu simpul 1 dan 4.
Simpul hidup dalam antrian Q adalah : 2(73), 3(63). Karena simpul 3 memiliki nilai batas
terkecil, simpul selanjutnya yang diekspansi adalah simpul 3. Pohon yang terbentuk :
Karena simpul 4 memiliki nilai batas terkecil, selanjutnya akan diekspansi. Pada graf, dari
simpul 2 kita bisa ke simpul 3, 5 dan 6. Sampai saat ini jalur yang terbentuk adalah 3-5-2, karena itu dari simpul 2 kita tidak akan mengunjungi simpul 3 dan 5.
Sampai di sini telah terbentuk lintasan 3-5-2-6 yang artinya telah ditemukan solusi jadi,
pembentukan pohon dapat dihentikan. Solusi ini merupakan solusi terbaik sejauh ini. Simpulsimpul yang lain dapat dibunuh karena dari simpul-simpul tersebut tidak mungkin dihasilkan solusi yang lebih baik.
5 Persoalan Lintasan Terpendek ( Path-finding)
Persoalan pencarian jalan (path-finding) adalah persoalan menjacari lintasan dari titik awal menuju titik akhir yang ditentukan dengan melewati hambatanhambatan (constrains) yang ada.
Gambar 1. Salah satu contoh persoalan path-finding. S adalah titik awal dan F adalah titik akhir.
Konsep Branch and Bound
Sebagaimana pada algortima runut-balik, Algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runut-balik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth- First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).
Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk
setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :
c(i) = ƒ(i) + g(i)
yang dalam hal ini,
c(i) = ongkos untuk simpul i
ƒ(i) = ongkos mencapai simpul i dari akar
g(i) = ongkos mencapai simpul tujuan dari simpul akar i
Nilai c digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki c minimum.
Algoritma Branch and Bound
Algoritma B&B jika dituliskan secara procedural adalah
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi . Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul I yang mempunyai c(i) paling kecil. Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika I tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul i, hitung c(j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.
6. Kembali ke langkah 2.
c. Pseudo-Code
Algoritma branch and bound
procedure findPath()
while not found and ada simpul hidup
node n1 = findLeastCost();
generateChilds(n1);
function findLeastCost() : node
{mengembalikan node dengan cost terkecil}
procedure generateChilds(node n)
{membangkitkan simpul anak n}
7. UJI SIMULASI
Algoritma ini akan diuji coba pada kasus yang lebih
rumit. yaitu pada matriks ukurang 21 x 51 dengan
hambatan-habatan yang lebih banyak. Pada bagian ini
hanya akan diperlihatkan hasil programnya (PathFinder
1.0). Program tersebut dibuat oleh penulis untuk keperluan
pengujian.
Berikut ini adalah matriks yang diberikan
Gambar 9. Screenshot program
Tanda ‘x’ pada gambar merupakan hambatan yang tidak
dapat dilalui. Tanda ‘S’ merupakan titik awal dan tanda
‘F’ merupakan titik akhir. Hasil dari program tersebut
adalah seperti di bawah ini.
Gambar 9. Screenshot program (solusi)
Tanda ‘*’ menyatakan lintasan penyelesaian. Jika tidak
terdapat penyelesaian, maka program akan mencetak
‘Tidak ada solusi’.
8. Kesimpulan
Pada kasus serta analisa dari contoh soal tersebut, dapat disimpulkan bahwa pencarian lintasan terpendek sangat berguna untuk menentukan jalan tersingkat untuk menuju suatu tempat dimana terdapat suatu variabel lain yang juga mempengaruhi. Dalam hal ini adalah waktu kemacetan yang dapat digunakan sebagai variable yang mempengaruhi kecepatan kita, sehingga, kita dapat sampai tepat waktu menuju tempat tujuan. Hasil analisis berdasarkan bobot-bobot yang berbeda, menunjukkan bahwa semakin banyak bobot yang diberikan, maka semakin akurat pula data yang dihasilkan. Sehingga menghasilkan waktu yang efisien. Penerapan strategi greedy pada pencarian lintasan terpendek belum tentu menghasilkan nilai yang optimum karena hanya mengacu pada satu aspek dan akan mencari nilai maksimum pada aspek tersebut dengan mengabaikan aspek yang lain.
1. Metode B&B
Algoritma pencarian jarak terpendek dengan metode B&B :
1. Reduksi matrik yang merepresentasikan graf dengan mengurangi setiap baris atau kolom dengan nilai terkecil baris atau kolom tersebut sehingga didapat matriks dengan minimal satu nilai nol pada setiap baris dan kolom.
2. Masukkan simpul akar dengan nilai batas c(1) = total pengurang matriks ke dalam antrian Q. Jika simpul akar adalah simpul solusi, maka solusi telah ditemukan. Stop.
3. Jika Q kosong, tidak ada solusi. Stop.
4. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai c(i) terkecil.
Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang.
5. Jika simpul i adalah simpul solusi, berarti solusi telah ditemukan, stop. Jika
simpul i bukan simpul solusi maka bangkitkan semua anak-anaknya. Cara membangkitkan simpul anak :
1. Ubah semua nilai pada matriks bobot tereduksi milik simpul bapak pada baris ke i dan kolom ke j dengan ~. Dimana i dan j menunjukkan simpul yang dituju pada graf.
2. Ubah nilai matriks tereduksi pada (j,simpul asal pada graf) agar simpul tersebut tidak digunakan.
3. Reduksi kembali matriksnya. Jika i tidak mempunyai anak, kembali ke langkah 2.
4. Untuk setiap anak j dari simpul i, hitung c(j), dan masukkan anak-anak tersebut
ke dalam antrian Q. c(j) didapat dari rumus :
c(j) = c(i) + M(k,l) + r
dimana :
c(j) : nilai ongkos simpul anak
c(i) : nilai ongkos simpul bapak
M(k,l) : bobot sisi k ke l
R : total pengurang pada proses reduksi
5. Kembali ke langkah 2.
DAFTAR PUSTAKA
[1] Munir, Rinaldi. (2007). Diktat Kuliah IF2251
Strategi Algoritmik. Departemen Teknik
Informatika, Institut Teknologi Bandung.
[ 1 ] Strategi Greedy.
http://kur2003.if.itb.ac.id/strategialgoritmik.
Diakses tanggal 18 Maret 2006.
[ 2 ] Arif Y, Fazmah , Diktat Kuliah CS3024 Desain
dan Analisis Strategi , Bandung, 2006.
[ 3 ] Prama, Irvan, dkk. Makalah Algoritma Greedy
untuk Mencari Lintasan Terpendek, Departemen
Teknik Informatika ITB, 2005.
[ 4 ] S., Mehran, April 2005, Exhaustive Recursion
and Backtracking.