PEMBUATAN PROGRAM GARIS MENGGUNAKAN C++

TUJUAN PEMBUATAN PROGRAM

Tujuan dalam membuat program garis vertikal, horizontal dan diagonal ini adalah untuk memenuhi tugas mata kuliah Grafik Komputer dan Pengolahan Citra. Aplikasi untuk pembuatan garis vertical, horizontal dan diagonal dengan menggunakan bahasa pemrograman C++ dan Library GLUT OpenGL.

PENGERTIAN OPENGL

OpenGL (Open Graphics Library) adalah suatu spesifikasi grafik yang low-level yang menyediakan fungsi untuk mempermudah pekerjaan atau untuk keperluan – keperluan pemrograman grafis (Graphics Programming / GP), termasuk grafik primitif (titik, garis, dan lingkaran). OpenGL digunakan untuk menggambar sebuah objek dua dimensi(2D) atau tiga dimensi (3D).

Berikut ini adalah program garis vertikal, horizontal dan diagonal menggunakan aplikasi dev C++ dengan render OpenGL, untuk selengkapnya silahkan download dibawah ini :

Download file DOC & PDF :  Click here!

Download program garis        :  Click here!

PENCARIAN HEURISTIK (HEURISTIC SEARCH)

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun 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.

Ada 4 metode  Heuristic Searching:

a)      Generate and Test.

b)      Hill Climbing.

c)      Best First Search.

d)      Simulated Anealing

A.                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 : Pada Traveling 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 gambar di bawah ini :

Penyelesaian dengan metode Generate and Test :

penyelesaian dengan menggunakan Generate and Test dilakukan dengan membangkitkan solusi-solusi yang mungkin dengan menyusun kota-kota dalam urutan abjad, yaitu :

·         A-B-C-D

·         A-B-D-C

·         A-C-B-D

·         A-C-D-D

·         dan seterusnya

Dari gambar diatas dapat dijelakan sebagai berikut :

1.      misalkan kita mulai dari node A. Kita pilih sebagai keadaan awal adalah lintasan ABCD dengan panjang lintasan = 19.

2.      Kemudian kita lakukan backtracking untuk mendapatkan lintasan ABDC dengan panjang lintasan =18.

3.      Lintasan ini kita bandingkan dengan lintasan ABCD, ternyata ABDC < ABCD, sehingga lintasan terpilih adalah ABDC.

4.      Kita lakukan lagi backtracking untuk mendapatkan lintasan ACBD (=12), ternyata ACBD < ABDC, maka lintasan terpilih sekarang adalah ACBD.

5.      Demikian seterusnya hingga ditemukan solusi yang sebenarnya.

6.      Salah satu kelemahan dari metode ini adalah perlunya dibangkitkan semua kemungkinan solusi sehingga membutuhkan waktu yang cukup besar dalam  pencariannya.

Alur pencarian dengan Generate and Test

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

Algoritma Simple Hill Climbing :

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

2.      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.

Evaluasi keadaan baru tersebut :

1)      Jika keadaan baru merupakan tujuan, keluar

2)      Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

3)      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 llintasan 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 : 

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

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.

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:

*  Tukar 1, 2 (menukar urutan posisi kota ke-1 dengan kota ke-2).

*  Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke-3).

*  Tukar 3, 4 (menukar urutan posisi kota ke-3 dengan kota ke-4).

*  Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke-1).

*  Tukar 2, 4 (menukar urutan posisi kota ke-2 dengan kota ke-4).

*  Tukar 1, 3 (menukar urutan posisi kota ke-1 dengan kota ke-3).

Pada Gambar 2.22 terlihat bahwa, pada keadaan awal, lintasan terpilih adalah ABCD (=19). Pada level pertama, hill climbing akan mengunjungi BACD (=17) yang ternyata memiliki nilai heuristik lebih kecil dibandingkan dengan ABCD (17<19), sehingga BACD menjadi pilihan selanjutnya dengan operator terpakai Tukar1,2. Pada level kedua, hill climbing akan   mengunjungi ABCD.  Karena  operator  Tukar  1,  2  sudah  digunakan  oleh  BACD,  maka dipilih node yang lain yaitu BCAD (=15). Karena nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3. Kemudian hill climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding dengan BCAD (20>17), maka dipilih node lain. Pencarian menuju ke node BACD, karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain. Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar dari nilai heuristik BCAD, sehingga dipilih node lain. Node vang dikunjungi berikutnya adalah DCAB (=19). Nilai heuristic DCAB ternyata juga lebih besar dibanding dengan BCAD, sehingga pencarian dilanjutkan di node lainnya lagi, yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil daripada nilai heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi. Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai BDAC. Nilai heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga node BDCA ini akan diekplorasi. Pencarian pertama sudah mendapatkan node dengan  nilai heuristik yang lebih kecil, yaitu DBCA (=12). Sehingga node ini diekplorasi juga. Dari hasil ekplorasi dengan pemakaian semua operator, ternyata sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding dengan nilai heuristik DBCA, sehingga sebenarnya node DBCA (=12) inilah lintasan terpendek yang kita cari (SOLUSI). Misalkan kita tidak menggunakan semua operator, melainkan kita hanya menggunakan 4 operator pertama saja, yaitu :

*          Tukar 1,2 (menukar urutan posisi kota ke'1 dengan kota ke'2).

*          Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke'3).

*          Tukar 3,4 (menukar urutan posisi kota ke-3 dengan kota ke'4).

*          Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke'l).

Maka pencarian dengan simple hill climbing ini dapat dilihat pada Gambar 2.23. Lintasan terpendek yang diperoleh adalah B-C-A-D yaitu sebesar 15. Disini kita akan terjebak pada nilai minimum local yang disebabkan oleh kurangnya operator yang kita gunakan. Kita tidak dapat memperoleh nilai minimum globalnya yaitu sebesar 12.

 

Contoh TSP di atas adalah contoh pertama yang dibahas dalam makalah ini. Untuk contoh kedua adalah game Number Puzzle Slider dengan langkah- langkah menggunakan Simple Hill Climbing.

Berikut adalah contoh menyelesaikan Number Puzzle Slider dengan kondisi tertentu menggunakan Simple Hill Climbing;

h(n) adalah nilai total heuristik dari kondisi puzzle. Bernilai 0 untuk posisi yang benar dan untuk posisi yang salah nilainya adalah jarak terpendek  menuju posisi benar. Proses evaluasi yang dilakukan selalu mengambil nilai heuristik terkecil.

References      :

-          elib.unikom.ac.id/download.php?id=191397

-          viska.web.id/wp-content/uploads/2012/03/Modul-Pertemuan-2-7.pdf

-          web.unair.ac.id/admin/file/f_22572_2_Simple_Hill_Climbing.pdf

-          http://www.academia.edu/9820429/Generate-and-Test_GT

BLIND SEARCH

Blind Search adalah pencarian solusi tanpa adanya informasi yang dapat mengarahkan pencarian untuk mencapai goal state dari current state (keadaan sekarang). Informasi yang ada hanyalah definisi goal state itu sendiri, sehingga algoritma dapat mengenali goal state bila menjumpainya.

Dengan ketiadaan informasi, maka blind search dalam kerjanya memeriksa/mengembangkan node-node secara tidak terarah dan kurang efisien untuk kebanyakan kasus karena banyaknya node yang dikembangkan.

Dikatakan “blind” atau “buta” karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

Blind Search meliputi :

a)      Breadth First Search (BFS)

b)      Uniform Cost Search (UCS)

c)      Depth First Search (DFS)

d)      Depth Limited Search (DLS)

e)      Iterative Deepening Search (IDS)

f)       Bi-Directional Search (BDS)

Dari ke-enam macam pencarian buta di atas, yang sering dibahas adalah “Breadth First Search (BFS)” dan “Depth First Search (DFS)”.

A.    BREADTH FIRST SEARCH (BFS)

Breadth First Search (BFS) merupakan metode pencarian yang bertujuan untuk memperluas dan memeriksa semua simpul pada graph atau urutan kombinasi dengan pencarian secara sistematis melalui setiap solusi.

BFS melakukan pencarian secara mendalam pada keseluruhan graph atau urutan tanpa memperhatikan tujuan sehingga menemukan tujuan tersebut. BFS tidak menggunakan algoritma heuristik.

Karakteristik Breadth First Search :

·                     Jika ada solusi, BFS akan menemukannya.

·                     BFS akan menemukan solusi dengan jalur terpendek.

·                     BFS tidak akan terjebak dalam “looping”.

·                     BFS membutuhkan space untuk menyimpan node list antrian dan space yang dibutuhkan dan mungkin space yang dibutuhkan itu cukup besar.

·                     Asumsi :

1.      Ada solusi dalam pohon

2.      Pencarian tree adalah secara terurut.

BFS melakukan searching pada semua node yang berada pada level yang sama terlebih dahulu, sebelum melanjutkan proses searching pada node di level berikutnya.

Keterangan :

1.      Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.

2.      Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri ke kanan hingga ditemukannya solusi.

Keuntungan Breadth First Search :

·         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 Breadth First Search :

·         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 Implementasi Breadth First Search pada Java :

Untuk mengimplementasikan java pada BFS, saya menukil kodingannya Mark Watson dalam buku beliau Programming AI with Java. Beliau memberikan dua contoh penerapan BFS untuk pencarian jalur terpendek.

1.      Pencarian jalur terpendek pada game Maze

2.      Pencarian jalur terpendek pada simpul Graph

Pencarian Jalur terpendek pada game Maze :

Game maze adalah game yang mengharuskan user untuk menemukan jalan keluar dan melewati banyak halangan (obstacle) dari sebuah ruang yang mirip labirin. Titik awalnya dimulai dari huruf S (Start) dan diakhiri pada kotak bertuliskan G (Goal). Ketika program dijalankan, sistem akan otomatis mencari rute terpendek dari kotak S menuju kotak G menggunakan metode BFS. Panjang rute hasil pencarian dituliskan dalam bentuk angka disetiap kotak.

BFS for Maze

Pencarian Jalur Terpendek pada Graph :

Titik awal adalah simpul 0 dan titik akhir adalah simpul 9, program secara otomatis akan mencari jalur terpendek dari simpul 0 menuju simpul 9 menggunakan metode BFS.

B.     DEPTH FIRST SEARCH (DFS)

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan  ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end.

Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi.

Kelebihan Depth-first search :

·         Pemakaian 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 Depth-first search :

·         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).

Contoh penerapan Depth-first search :

Studi Kasus : Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan serigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.

Permasalahannya : adalah di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.

Deskripsi

·         P = Petani

·         Sy = Sayuran

·         K = Kambing

·         Sg = Serigala

Ruang Keadaan

·         Untuk daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)

Keadaan Awal

·         Daerah Asal = (P, Sy, K, Sg)

·         Daerah seberang = (0, 0, 0, 0)

Tujuan

·         Daerah Asal = (0, 0, 0, 0)

·         Daerah seberang = (P, Sy, K, Sg)

Metode Penyelesaian :

a.       Berikut ini adalah algoritma BFS :

1.      Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.

2.      Jika Q kosong, tidak ada solusi. Stop.

3.      Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.

4.      Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.

b.      Menggunakan algoritma DFS :

1.      Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.

2.      Jika Q kosong, tidak ada solusi. Stop.

3.      Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2

4.      Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.

References      :

-          elib.unikom.ac.id/download.php?id=191397

-          viska.web.id/wp-content/uploads/2012/03/Modul-Pertemuan-2-7.pdf

-         http://www.charisfauzan.net/2015/01/pencarian-buta-teori-dan-implementasi.html