TUGAS Membuat Tampilan Garis(GRAFIK KOMPUTER & PENGOLAHAN CITRA)

Program ini untuk menampilkan output berupa garis Vertical,Horizontal dan Diagonal. Dalam hal ini untuk memenuhi salah satu tugas pada mata kuliah”GRAFIK KOMPUTER DAN PENGOLAHAN CITRA”, Bahasa pemrogram java merupakan bahasa yang saya gunakan dan agar bisa menampilkan output berupa titik yang berdekatan sehingga menampilkan sebuah garis maka dihandle dengan library OpenGL yaitu LWJGL.

Bahasa pemrograman java dapat  diaplikasikan pada banyak program misal Jcreator atau Netbeans. Untuk mempermudah dalam pengetikan script dan menjalankan script tersebut saya menggunakan software Netbeans IDE 8.1 serta library OpenGL (LWJGL).

bagi anda yang ingin mencoba program ini silahkan download file jar / exe dan cara penggunaan dari program tersebut yang saya jabarkan pada pdf/doc

download link jar program garis
DOWNLOAD
download link exe garis baru program
 DOWNLOAD
download link doc  User Guide Program garis
DOWNLOAD
download link pdf Uses Guide
DOWNLOAD

HEURISTIC SEARCH

Definisi

merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).
Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
           Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Jenis-jenis dari Heuristic Search:

·  Generate and Test

·  Hill Climbing

·  Best First Search

A.     Generate and test

Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan.
Pendekatan ini meliputi langkah–langkah sebagai berikut :

1. Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.
2. Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
3. Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada).  Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.

Contoh

A,B,C,D merupakan sebuah pos untuk dilalui dengan jalur yang memiliki nilai berbeda, setiap pos hanya boleh dilalui satu kali setiap perjalanan dengan suatu masalah berupa  mencari perjalanan ke seluruh pos yang memiliki nilai paling kecil.

A-B-C-D : 8+5+6= 19

A-C-B-D : 3+5+4=12

A-D-B-C : 7+4+5=16

A-D-C-B : 7+6+5=18

Maka dari algoritma diatas solusi yang diambil adalah rute A-C-B-D

Kelemahan

·         Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian

·         Membutuhkan waktu yang cukup lama dalam pencariannya

B.     Hill Climbing

Merupakan proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat  tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

Algoritma Simple Hill Climbing :
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang.
3. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
4. Evaluasi keadaan baru tersebut.
5. Jika keadaan baru merupakan tujuan, keluar.
6. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
7. 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 ) ! 

C.     Best First Search

Pencarian terbaik pertama (Best First Search) merupakan suatu cara yang menggabungkan keuntungan atau kelebihan dari pencarian Breadth-First Search dan Depth-First Search.
Pada setiap langkah proses pencarian terbaik pertama, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya.

Contoh:

Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

SUMBER:

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

https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/.html

http://slideplayer.info/slide/3206969/

BLIND SEARCH

METODE PENCARIAN

Metode pencarian berhubungan dengan AI (Artificial Intelligence) yang merupakan salah satu metode pencarian masalah dengan penyelesaian berupa pencarian solusi pada suatu permasalahan yang dihadapi.

Untuk mengukur perfomansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

1.      Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

2.      Time complexity : berapa lama waktu yang diperlukan? [semakin cepat, semakin baik]

3.      Space complexity : berapa banyak memori yang diperlukan

4.      Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

Metode pencarian atau teknik searching terbagi menjadi dua, yaitu:

-          Blind Searching

-          Heuristic searching

Blind Searching(Pencarian Buta)

Salah satu metode ini merupakan teknik pencarian yang tidak memiliki informasi awal, sehingga disebut dengan pencarian buta. Jadi jika suatu masalah lalu kita menemukan sebuah solusi maka pencarian tersebut akan berhenti dengan skema kasarnya berupa (masalahàpencarianàsolusi). Ciri-ciri dari metode ini yaitu:

-          Membangkitkan simpul berdasarkan urutan.

-          Kalau ada solusi maka solusi akan ditemukan.

-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui). 

-          Variabel data pada Blind Search tidak mempunyai atribut / informasi tambahan.

A.     Pencarian melebar pertama (Breadth – First Search)

 Breadth First Search yaitu model pencarian yang memakai metode melebar. Metode pencarian ini menggunakan teknik pencarian solusi yang menggunakan cara membuka node(titik) pada tiap levelnya. 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 simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

Keuntungan BFS:

·           Tidak menemui jalan buntu.

·           Jika ada suatu solusi, maka Braedth First Search akan menemukannya. Dan jika didapat lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan BFS:

·           Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam suatu pohon.

·           Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke – ( n + 1 )

·           Idenya mirip dengan algo prim dan dijkstra.

·           Traversal dimulai dari simpul v.

·           Algoritma :

-       Kunjungi simpul v,

-       Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu,

-       Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul – simpul yang tadi di kunjungi, demikian seterusnya.

·           Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul – simpul pada aras d + 1.

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:

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.

B.     Pencarian mendalam pertama (Depth – First Search)

Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian ini dilakukan 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 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.

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, 1

Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

Keuntungan DFS:

·           Membutuhkan memori yang relaatif kecil, karena hanya node – node pada lintasan yang aktif yang disimpan.

·           Secara kebetulan, metode Depth First Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan DFS:

·           Memungkinkan tidak ditemukannya tujuan yang diharapkan.

·           Hanya akan mendapatkan satu solusi pada setiap pencarian.

SUMBER:

 http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html