Tugas Grafik Komputer dan Pengolahan Citra menjelaskan membuat garis vertikal,horizontal,dan diagonal.menggunakan software Netbeans IDE 8.1
Berikut adalah link download dari tugas :
File JAR:
File JAR
File PDF:
link PDF
Senin, 14 November 2016
Kamis, 03 November 2016
Teknik Pencarian Heuristik
Teknik
Pencarian Heuristik (Heuristic Search)
Heuristik
adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian,namum
dengan kemungkinan mengorbankan kelengkapan (completeness).
Fungsi
heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan
menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi
yang diinginkan.
Jenis-jenis
Heuristic Searching:
– Generate
and Test.
– Hill
Climbing.
PEMBANGKITAN dan PENGUJIAN
(Generate and Test)
§ Metode
ini merupakan penggabungan antara depth-first search dengan pelacakan mundur
(backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
§ Algoritma :
1. Bangkitkan suatu kemungkinan
solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan
awal).
2. Uji untuk melihat apakah node
tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut
atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan
yang diharapkan.
3. Jika solusi ditemukan, keluar.
Jika tidak, ulangi kembali langkah pertama.
§
Contoh : “Travelling Salesman
Problem (TSP)”
*) Seorang salesman ingin
mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin
mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi
tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota
seperti berikut ini :
Alur
pencarian dengan Generate and Test
PENDAKIAN BUKIT (Hill Climbing)
§
Metode ini hampir sama
dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan
dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung
pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini
akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap
keadaan-keadaan lainnyayang mungkin.
§
Algoritma:
1.
Cari operator yang belum pernah digunakan; gunakan operator ini untuk
mendapatkan keadaan yang baru.
a)
Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak
ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator
yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
b)
Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar –
Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka
jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru
tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
§
Contoh: TSP
dengan Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan
lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang
bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan
dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)! atau
sebanyak 6 kombinasi. Fungsi heuristic yang digunakan
adalah panjang lintasan yang terjadi.
SUMBER :
Metode pencarian
Pengertian
Breadth-First Search
Algoritma Breadth-First Search (BFS) atau
dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang
melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu
mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga
dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum
dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian
seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras ddikunjungi
lebih dahulu sebelum simpul-simpul pad aras d+1.
Algoritma ini memerlukan sebuah antrian q untuk
menyimpan simpul yang telah dikunjungi. Simpul-simpul ini diperlukan sebagai
acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul
yang telah dikunjungi masuk ke dalam antrian hanya satu kali. Algoritma ini
juga membutuhkan table Boolean untuk menyimpan simpul yang telah dikunjungi
sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.Breadth-first
search (BFS) melakukan proses searching pada semua node yang berada
pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses
searching pada node di level berikutnya. Urutan proses searching BFS
ditunjukkan dalam Gambar 1.1 adalah: A,B,C,D,E,F, ...
Gambar 1.1 : Diagram pohon dari BFS.
Cara Kerja Algoritma BFS
Dalam algoritma BFS, simpul anak yang telah
dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu
simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai
urutan pengantrian.Untuk memperjelas cara kerja algoritma BFS beserta antrian
yang digunakannya, berikut langkah-langkah algoritma BFS:
1. Masukkan simpul ujung
(akar) ke dalam antrian.
2. Ambil simpul dari awal
antrian, lalu cek apakah simpul merupakan solusi.
3. Jika simpul merupakan
solusi, pencarian selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi,
masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak)
ke dalam antrian.
5. Jika antrian kosong dan
setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi
tidak ditemukan.
6. Ulangi pencarian dari
langkah kedua.
Contohnya terlihat dibawah ini:
Maka penyelesaiannya adalah:Gambar (a) BFS(1): 1, 2, 3,
4, 5, 6, 7, 1.Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1Gambar (c) BFS(1): 1, 2,
3, 4, 5, 6, 7, 8, 9
Penerapan BFS dalam Algoritma
Adapun penerapan BFS pada algoritma adalah
sebagai berikut:
Keuntungan dan Kelemahan BFS
Keuntungan dari BFS adalah :
* Tidak
akan menemukan jalan buntu.
* Tidak
ada satu solusi, maka BFS search akan menemuknnya. Dan jika ada lebih dari satu
solusi, maka solusi minimum akan ditemukan.
Kelemahan dari BFS adalah :
* Membutuhkan
memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
* Membutuhkan
waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi
pada level yang ke –(n+1).
Contoh kasus
BFS
Berikut adalah contoh kasus dengan
menggunakan metode BFS. Kita akan mencari jalur tujuan dengan menggunakan
angkutan umum.Contoh :
Mencari jalur angkutan umum dari terminal
senen ke terminal Kp. Rambutan
* Initial
State : Senen
* Goal
State : Kp. Rambutan
RUTE PERJALANAN
Gambar 1.2 : Rute perjalanan
Penjelasan Gambar :
1. Membangkitakan anak dari terminal Senen = Terminal blok
M, Terminal Pulo Gadung, Terminal Manggarai
2. Karena goal state (Terminal Kp. Rambutan) belum tercapai
maka kita bangkitkan anak dari terminal senen
Terminal Blok M = Terminal
Grogol, Terminal Lebak Bulus
Terminal Lebak Bulus = Terminal Ciputat,
Terminal Kp.
Rambutan.
Terminal Pulo Gadung = Terminal
bekasi
Terminal Manggarai = Terminal Cililitan,
Terminal Harmoni
3. Akhirnya tercapai Goal State (Terminal Kp. Rambutan).
Kesimpulan
Dari pembahasan diatas
dapat ditarik kesimpulan yaitu :
Breadth-first search
(BFS) melakukan proses searching pada semua node yang berada pada level atau
hirarki tetangga yang terdekat terlebih dahulu sebelum melanjutkan
proses searching pada node di level berikutnya.
Metode BFS
membutuhkan memori yang cukup banyak namun dengan menggunakan metode ini
solusinya tidak akan menemukan jalan buntu.
Pengertian Depth-First Search
Depth-first search (DFS) melakukan pencarian
secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya.
Berikut gambar yang mengiilustrasikan urutan
simpul yang dikunjungi pada algoritma DFS:
Gambar Ilustrasi
urutan kunjungan simpul pada algoritma DFS
Dari gambar, dapat dilihat bahwa dengan
algoritma DFS, setiap anak simpul pertama yang bertetangga dengan simpul akar
dikunjungi sampai tingkat terdalamnya lebih dahulu, lalu seluruh simpul pada
subpohon tersebut, sebelum simpul lain yang juga bertetangga dengan simpul
akar.
2.Algoritma DFS
Berikut ini adalah
algoritma Depth-First Search :
procedure DFS(input v:integer)
Mengunjungi seluruh simpul graf dengan algoritma
pencarian DFS
Masukan: v adalah simpul awal kunjungan
Keluaran: semua simpulyang dikunjungi ditulis ke layar
Deklarasi
w : integer
Algoritma:
write(v)
dikunjungi[v]¬true
for tiap simpul w yang
bertetangga dengan simpul v do
if not dikunjungi[w] then
DFS(w)
endif
endfor
3.SKENARIO UJI COBA
Pencarian rute terpendek dilakukan dengan
cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan
dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang
dicari.
Dalam algoritma DFS, simpul yang telah
dikunjungi disimpan dalam suatu tumpukan (stack). Antrian
ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai
urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses
runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman
maksimal).
Untuk memperjelas cara kerja algoritma DFS
beserta tumpukan yang digunakannya, berikut langkah-langkah algoritma
DFS:
1. Masukkan simpul ujung (akar) ke dalam
tumpukan
2. Ambil simpul dari tumpukan teratas, lalu
cek apakah simpul merupakan solusi
3. Jika simpul merupakan solusi, pencarian
selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh
simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam
tumpukan
5. Jika tumpukan kosong dan setiap simpul
sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak
ditemukan
6. Ulangi pencarian dari langkah kedua
4. HASIL
UJI COBA
Keuntungan Dari Algoritma Depth-First Search
- Membutuhkan memori yang relative kecil,
karena hanya node-node pada lintasan yang aktif saja.
- Secara kebetulan, metode depth-first
search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam
ruang keadaan.
Kelemahan Dari Algoritma Depth-First Search
- Memungkinkan tidak ditemukannya tujuan
yang diharapkan.
- Hanya akan menemukan satu solusi pada
setiap pencarian.
5. KESIMPULAN
Algoritma Depth-First
Search bisa digunakan untuk melakukan pencarian rute terpendek. Dengan memperhatikan
keuntungan dan kelemahan dari algoritma tersebut, bisa diambil kesimpulan bahwa
algoritma ini bisa membantu pencarian rute terpendek, sehingga bisa mendapatkan
penyelesaian yang efektif.
Algoritma Depth-First
Search akan berhenti melakukan pencarian jika sudah ditemukan tujuan akhir.
SUMBER :
Langganan:
Postingan (Atom)