Grafik Komputer & Pengolahan Citra

OpenGL. OpenGL adalah kumpulan standard API (Application Programming Interface) yang menghubungkan software dengan hardware grafis untuk menampilkan gambar 2D dan 3D. Intinya OpenGL itu adalah kumpulan library untuk mengakses hardware (GL= graphical library). Sedangkan , Java adalah bahasa pemrograman yang dapat dijalankan di berbagai komputer termasuk telepon genggam. Bahasa ini awalnya dibuat oleh James Gosling saat masih bergabung di Sun Microsystems saat ini merupakan bagian dari Oracle dan dirilis tahun 1995. Pada Pembuatan Garis ini terdapat 4 Class yaitu : Menu , Diagonal , Vertikal , Horizontal. dan yang menjadi main atau class yang dijalankan pertama kali adalah Menu. saya menggunakan library LWJGL yang memiliki 3 files yaitu :

LWJGL - 2.9.3

LWJGL Source

LWJGL Javadoc

==>> Logika Pemrograman dan User Guide <<==

==>> Exe Program <<==

Blind Research

Blind Search

Blind Search merupakan pencarian asal ketemu. Jika solusi sudah ketemu, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal tiga bagian, [masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah, nah, itulah solusinya.

Contoh lainnya adalah mari anggap seseorang berangkat dari Arad menuju Bucharest, dengan metode blind search, rencana keberangkatan akan dimulai secara acak mulai dari Zerind, Sibiu atau Timosoara yang kemudian mengikuti alur acak sampai ke bucharest, blind search tidak berpengaruh kepada seberapa jauh jarak yang harus ditempuh, jika sudah sampai Bucharest, maka rencana keerangkatan selesai.

· Breadth-First Search
BREADTH-FIRST SEARCH (BFS) adalah sebuah algoritma pencarian graf yang dimulai dari node pangkal dan menjelajahi semua node yang berdekatan.dan untuk setiap node yang berdekatan, bfs menjelajahi node-node yang tidak terlihat sebelumnya (unexplored) dan seterusnya
BFS adalah sebuah metode pencarian yang bertujuan untuk memperluas dan memeriksa semua node dari sebuah graf atau kombinasi dari urutan dengan menggunakan semua solusi secara sistematis. dengan kata lain, bfs mencari ke seluruh graf atau urutan secara mendalam tanpa mempertimbangkan tujuannya (goal) sampai tujuan itu tercapai. bfs tidak menggunakan algoritma heuristis.
Contoh Algoritma Breadth First Search :
Dalam algoritma Breadth First Search, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma Breadth First Search beserta antrian yang digunakannya, berikut langkah-langkah algoritma 

Breadth First Search:
Masukkan simpul ujung (akar) ke dalam antrian.
Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.
Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.
Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.
Ulangi pencarian dari langkah kedua.

Keuntungan :
· Tidak akan menemui jalan buntu
· Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan :
· Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon
· Membutuhkan waktu yang cukup lama.
· Depth-First Search (DFS)
Depth-First Search (DFS) adalah pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node 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. Jika solusi  ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Keuntungan:
• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.
Kelemahan:
• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
• 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).

Heuristic Search

Heuristic Search

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

· Generate & Test

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma: 

Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal). 

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. 

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 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini:

· 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 lainnya yang mungkin. 

Algoritma Simple Hill Climbing 

Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai  tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang: 

Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

Evaluasi keadaan baru tersebut : 

Jika keadaan baru merupakan tujuan, keluar 

Jika bukan tujuan, namun nilainya lebih baik dari pada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. 

Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi. 

Pada simple hill climbing, ada 3 masalah yang mungkin: 

Algoritma akan berhenti kalau mencapai nilai optimum local 

Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi 

Tidak diijinkan untuk melihat satupun langkah sebelumnya.

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 l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak:

atau sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi 

 Sumber : http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html