Senin, 14 November 2016
GRAFIK KOMPUTER & PENGOLAHAN CITRA
Membuat program untuk menggambar garis Horizontal, Vertikal, dan Diagonal. Tugas ini diberikan oleh dosen Bu Lily Wulandari. Deadline M9 (15 nov 2016).
download file -> klik
download jar -> klik
Jumat, 04 November 2016
HEURISTIC SEARCH
2. HEURISTIC
SEARCH / Pencarian Heuristik
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.
2.1.
Generate and Test
Metode ini merupakan penggabungan antara depth-first
search dengan pelacakan mundur (backtracking) , yaitu bergerak
ke belakang menuju pada suatu keadaan awal.
Contoh : “Travelling Salesman Problem (TSP)”
Seorang salesman ingin mengunjungi 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 :
Penyelesaian dengan metode Generate and Test
Alur pencarian dengan Generate and Test
Contoh :
a.
Kasus 4 puzzle (kotak permainan)
b.
Kasus 8 puzzle (kotak permainan)
c.
Kasus Travelling Salesman Problem (TSP)
2.2.
Hill Climbing / PENDAKIAN BUKIT
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 lain nya yang mungkin.
Contoh Penerapan
Algoritma Simple Hill Climbing
Salah satu
contoh dari penerapan Algoritma Simple Hill Climbing adalah Traveling Salesman
Problem.
Disini ruang keadaan
berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk
menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan
adalah panjang lintasan yang terjadi.
Gambar Metode Simple
Hill Clibing Dengan 6 Operator
Operator yang
akan kita gunakan, adalah menukar urutan posisi 2 kota dalam suatu lintasan.
Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar
posisi urutan 2 kota, maka kita akan mendapatkan sebanyak :
Sehingga kalau
ada 4 kota, kita bisa memperoleh :
kombinasi.
Keenam
kombinasi ini akan kita pakai semuanya sebagai operator, yaitu:
1.
Tukar 1, 2 (menukar urutan posisi kota ke-1 dengan kota ke-2).
2.
Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke-3).
3.
Tukar 3, 4 (menukar urutan posisi kota ke-3 dengan kota ke-4).
4.
Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke-1).
5.
Tukar 2, 4 (menukar urutan posisi kota ke-2 dengan kota ke-4).
6.
Tukar 1, 3 (menukar urutan posisi kota ke-1 dengan kota ke-3).
Sumber :
karmila.staff.gunadarma.ac.id/Downloads/folder/0
Kamis, 03 November 2016
BLIND SEARCH
BLIND SEARCH
Blind Searching adalah model pencarian buta atau pencarian yang tidak
memiliki informasi awal, model pencarian ini memiliki tiga ciri-ciri utama
yaitu :
1. Membangkitkan simpul
berdasarkan urutan.
2.
Jika ada solusi, maka solusi akan ditemukan.
3. Hanya memiliki
informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
A. Pencarian Melebar pertama (Breadth-First
Search)
Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1.BFS (Breadth First Search) juga merupakan
salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun
bedanya BFS melakukan pencarian secara melebar atau per level pohon. Simpul
ditelusuri dari rootkemudian menelusuri semua simpul pada setiap
level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ), maka
penelusuran dilakukan terus dari simpul paling kiri ke simpul anak – anak
tetangganya yang selevel. Jadi, untuk pohon biner :
Maka, urutan penelusurannya
adalah : A – B – C – D – E – F – G – H – I – J – K – L
Salah satu cara implementasi
BFS adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS,
queue yang digunakan adalah queue yang isi elemennya adalah simpul pohon /
tree. Berikut ini adalah urutan algoritmanya :
1.
Masukkan simpul root ke
dalam antrian.
2.
Periksa antrian terdepan
apakah memiliki anak simpul.
3.
Jika ya, masukan semua anak
simpul ke dalam antrian.
4.
Hapus antrian terdepan.
5.
Jika antrian kosong
berhenti, tapi jika tidak kembali ke langkah dua.
Untuk gambar pohon biner di
atas, urutan langkah dan kondisi queue pada setiap iterasinya adalah sebagai
berikut :
Contoh diatas menggunakan
prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke
dalam queue. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak
simpulnya yaitu B dulu, baru C ke dalam stack. Untuk penelusurannya yang
dilihat adalah bagian yang berwarna biru, yaitu antrian terdepan yang setiap
iterasinya memiliki urutan A – B – C – D – E – F – G – H – I – J – K – L. Sama
seperti DFS lagi pada iterasi ke 13 itu kondisi antrian sudah kosong.
Keuntungan
Breadth First Search :
1. Tidak
akan menemui jalan buntu.
2. Jika
ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada
lebih dari satu solusi, maka solusi minimum akan ditemukan.
Keuntungan
Breadth First Search :
1. Tidak
akan menemui jalan buntu.
2. Jika
ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada
lebih dari satu solusi, maka solusi minimum akan ditemukan.
B. Pencarian
mendalam pertama (Depth-First Search)
Proses pencarian dilakukan
pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel.
Pencarian inidilakukan pada suatu simpul dalam setiap level dari yang paling
kiri. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian
dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari
memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka
pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai
ditemukan solusi.
Dalam implementasinya DFS
dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data
stack. Kita akan membahas dengan cara yang menggunakan stack. Stack yang
digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Bagaimana
cara kerjanya ? Berikut ini adalah urutan algoritmanya :
1.
Masukkan simpul root ke
dalam tumpukan dengan push.
2.
Ambil dan simpan isi elemen
(berupa simpul pohon) dari tumpukan teratas.
3.
Hapus isi stack teratas
dengan prosedur pop.
4.
Periksa apakah simpul pohon
yang disimpan tadi memiliki anak simpul.
5.
Jika ya, push semua anak
simpul yang dibangkitkan ke dalam stack.
6.
Jika tumpukan kosong
berhenti, tapi jika tidak kembali ke langkah dua
Jadi, untuk gambar pohon
biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :
Maka, urutan penelusurannya adalah : A – B – D – H –
E – I – C – F – G – J – K – L.
Contoh diatas menggunakan
prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke
dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak
simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack
teratas (yang diwarna biru) pada tiap iterasi memiliki urutan A – B – D – H – E
– I – C – F – G – J – K – L. Oiya, pada iterasi ke 13 itu kondisi stack sudah
kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang
dimasukkan ke stack.
Kelebihan Depth
First Search adalah:
1. Pemakain
memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node
yang pernah dibangkitkan.
2. Jika
solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan
menemukannya secara cepat.
Kelemahan Depth First Search adalah:
1. Jika
pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak
ada jaminan untuk menemukan solusi (Tidak Complete).
2. Jika
terdapat lebih dari satu solusi yang sama tetapi berada pada level yang
berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling
baik (Tidak Optimal).
Sumber :
Langganan:
Postingan (Atom)