TUGAS ANALISA DAN PERANCANGAN ALGORITMA
REVIEW JURNAL
TENTANG
Perbandingan
Algoritma Greedy Search dan Algoritma Depth-First- Search pada Pencarian Kota
dengan Graph Romania Problem
Disusun Oleh
:
1.
Septiani Dian Lestari NIM : 5235152786
2.
Tiara Susmadhita NIM : 5235151814
PROGRAM STUDI PENDIDIKAN INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS NEGERI JAKARTA
2018
Pada jurnal ini membahas
penelitian tentang perbandingan kinerja dari Algoritma Greedy Search dan DFS dengan
menggunakan graph Romania Problem. Kinerja akan diukur dengan menghitung total
cost dari masing – masing algortima untuk menemukan solusi atau kota yang
dicari. Bahasa pemrograman yang digunakan adalah prolog. Dengan adjacency list
berada pada source code.
Romania Problem adalah
permasalahan negara Roma dengan kota- kotanya yang setiap kota memiliki
jarak-jarak dan jalan dengan kota-kota terdekatnya. Berikut Peta Romania :
1.
Algoritma Search Greedy : mencari solusi
optimum(pilihan yang minimum). Tidak melakukan proses backtracking apabila
sudah melalukan expand pada suatu node, sehingga bisa saja tidak menemukan
solusi.
2.
Algoritma Depth-First-Search(DFS) :
algoritma pencarian yang melakukan ekspansi node atau child pertama. Bersifat
complete apabila graph atau tree memiliki sifat finite state space namun
apabila infinite state space, maka algoritma tidak complete. Beriku pseudocode
yaitu :
1) Begin
2)
2) open
= [start]
3) closed
= []
4) while
open != []
5) begin
6) hapus
state paling kiri dari open, panggil sebagai X.
8) Else
begin
9) expand
child dari X
10) masukkan
X dalam closed
11) hapus
child dari X yang ada di closed atau open
12) end
13) return(gagal)
14) end
15) end
DFS akan selalu lengkap apabila graph memiliki sifat infinite state
space, karena DFS akan mengekspansi seluruh node yang ada
Pengujian
dilakukan dengan membandingkan total cost dari dua algoritma pencarian.
Peneliti mengambil 10 sampel initial dan final state, kemudian dibandingkan
hasilnya.
Beberapa sample menggunakan algoritma greedy ditemukan kegagalan, namun
menggunakan algoritma DFS selalu ditemukan costnya, walaupun tidak selalu
menemukan hasil yang efisien terlihat pada sample Oradea – zerind. Maka secara
umum DFS lebih bisa digunakan untuk menemukan solusi dibandingkan greedy, namun
pada beberapa kasus DFS tidak lebih baik dari algoritma Greedy.
Link Upload :
DAFTAR PUSTAKA DALAM JURNAL :
Annu Malik, Anju
Sharma, Mr. Vinod Saroha, “Greedy Algorithm”,International Journal of
Scientific and Research Publications, Volume 3, Issue 8, 2013.
Jon Freeman,
“Parallel Algorithms for Depth-First Search”,University of Pennsylvania
Departement of Computer and Information Science Technical Report No.
MS-CIS-91-71, 1991
Prama, Irvan,
dkk.Makalah Algoritma Greedyuntuk Mencari Lintasan Terpendek, DepartemenTeknik
Informatika ITB, 2005.
SUMBER JURNAL :
Muhammad Yudha
Syuhada*, Sudirman Universitas Sumatera Utara,STMIK &AMIK Logika Medan,
Available onlinehttp://ojs.uma.ac.id/index.php/jite , JITE,
Vol.1(2)Januari(2018) p-ISSN:2549-6247e-ISSN:2549-6255 JOURNAL OF INFORMATICS
AND TELECOMMUNICATION ENGINEERING
