Program Pembuat Garis Horizontal, Vertikal & Diagonal dengan Java

Posting ini dibuat dengan tujuan untuk memenuhi tugas mata kuliah Grafik Komputer & Pengolahan Citra, dalam mengerjakan tugas ini saya menggunakan bahasa pemrograman Java dengan IDE Eclipse dalam membuat aplikasi ini.
Untuk download file yang telah saya compile silahkan klik tautan di bawah, file JAR ini sudah dicompile agar dapat dijalankan pada Windows, Linux, dan Mac OS. Jika file tidak jalan pada Windows 10 silahkan downgrade jre Anda ke versi 7u79 untuk menjalankannya.
Download JAR File [6MB]
Untuk yang komputernya belum terinstall java, silahkan download bundle dalam bentuk exe berikut untuk menjalankan program ini, karena dalam exe sudah termasuk jre7 maka Anda tidak perlu menginstall jre lagi cukup jalankan file exe dan program akan berjalan. Untuk file exe di bawah hanya dapat berjalan di Windows (Silahkan download sesuai dengan arsitektur windows Anda).
Download File exe 32Bit [38MB]
Download File exe 64Bit [40MB]
PDF User Guide:
Download PDF User Guide [743KB]

Metode Pencarian: Heuristic Search

A. Generate & Test

Definisi

Metode Generate-and-Test adalah metode yang paling sederhana dalam pencarian heuristic. Jika pembangkitan possible solution dikerjakan secara sistematis, maka prosedur akan mencari solusinya, jika ada. Tetapi jika ruang masalahnya sangat luas, mungkin memerlukan waktu yang sangat lama.

Algoritma Generate-and-Test adalah prosedur DFS karena solusi harus dibangkitkan secara lengkap sebelum dilakukan test. Algoritma ini berbentuk sistematis, pencarian sederhana yang mendalam dari ruang permasalahan. Generate & test juga dapat dilakukan dengan pembangkitan solusi secara acak, tetapi tidak ada jaminan solusinya akan ditemukan.

Algoritma Generate and Test adalah sebagai berikut :

  1. Bangkitkan sebuah solusi yang mungkin.
  2. Menguji tiap-tiap node yang merupakan solusi dengan cara membandingkan node tersebut dengan node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
  3. Jika solusi telah ditemukan, maka keluar dari sistem. Jika belum menemukan solusi, maka kembali ke langkah 1.
Contoh

Rute dikatakan valid jika jalur yang dilalui tidak berjarak 0. Jika rute valid, maka jarak dihitung lalu dibandingkan untuk mendapatkan jarak yang paling optimal.

Setiap rute yang valid akan dibandingkan dengan rute valid lainnya guna mendapatkan rute terpendek yang merupakan solusi dari kasus TSP-nya. Yang dalam hal ini dipecahkan menggunakan algoritma Generate & Test.

Kelebihan dari algoritma ini merupakan pencariannya yang lengkap dan selalu menghasilkan solusi yg optimal. Sedangkan kekurangannya adalah tidak cocok untuk data yang besar atau banyak dan waktu pencariannya yang lama sesuai dengan banyak datanya.

B. Hill Climbing

Definisi

Hill Climbing berbeda Generate-and-Test, yaitu pada feedback dari prosedur test untuk membantu pembangkit menentukan yang langsung dipindahkan dalam ruang pencarian. Dalam prosedur Generate & test , respon fungsi pengujian hanya ya atau tidak. Tapi jika pengujian ditambahkan dengan atauran fungsi-fungsi yang menyediakan estimasi dari bagaimana mendekati state yang diberikan ke state tujuan, prosedur pembangkit dapat mengeksplorasi ini sebagaimana ditunjukkan di bawah. HC sering digunakan jika terdapat fungsi heuristic yang baik untuk mengevaluasi state. Sebagai contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah gedung yang tinggi. Fungsi heuristics-nya adalah jarak antara lokasi sekarang dengan gedung yang tinggi dan state yang diperlukan adalah jarak yang terpendek.

Berikut adalah algoritma dari 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:
    1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
    2. 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 ini, ada 3 masalah yang mungkin, yaitu:

  1. Algoritma akan berhenti kalau mencapai nilai optimum lokal.
  2. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi.
  3. Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Contoh

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.

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 di atas 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 mengunjung ABCD. Karena operator Tukar 1, 2 sudah digunakan oleh BACD, maka dipilih node yang lain yaitu BCAD (=15). Karena nilai heuristik BCAD lebihkecil 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 di banding 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 per tama 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 di bawah. 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.

Sumber:
  • http://slideplayer.info/slide/2321953/
  • http://download.portalgaruda.org/article.php?article=59741&val=4485
  • http://www.metode-algoritma.com/2013/06/tsp-dengan-algoritma-generate-test.html
  • http://web.unair.ac.id/admin/file/f_22572_2_Simple_Hill_Climbing.pdf

Metode Pencarian: Blind Search

A. Breadth First Search

Definisi

Breadth First Search merupakan salah satu dari metode pencarian buta. Mengapa dikatakan pencarian buta ? istilah buta disini lebih dikenal dengan nama blind. Dikatakan buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

Breadth First Search (BFS) juga memiliki alur algoritma yang paling sederhana dibandingkan dengan metode blind yang lain. Itulah alasan mengapa BFS selalu dipelajari lebih dulu ketika membahas masalah pencarian buta.

Sebelum menelaah lebih jauh bagaimana metode BFS dijalankan, kita telisik dulu mengapa metode ini dinamakan pencarian Breadth First. Breadth dapat diartikan dengan luas / lebar, sedangkan first adalah pertama. Jadi, Breadth First adalah lebar pertama, apa maksudnya? Penamaan metode ini disesuaikan dengan konsep algoritma secara garis besar yaitu melakukan proses pencarian pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses pencarian pada node di level berikutnya.

BFS akan mencari satu per satu node secara melebar dari kiri ke kanan secara berurutan berdasarkan tingkat level nodenya. Jika pada satu level belum ditemukan solusi yang diinginkan, maka pencarian dilanjutkan hingga level berikutnya. Demikian seterusnya hingga ditemukan solusi. Maka, dengan cara seperti ini, BFS menjamin ditemukannya solusi apabila solusinya memang ada.

Contoh

Seperti pada gambar, jika dicari bagaimana jalur dari kota a menuju kota k, maka sistem akan menjelajahi setiap node hingga menemui titik kota k, sehingga hasil pencarian jalur terpendeknya adalah : a - b - c - d - e - f - g - h - i - j - k . Contoh lain seperti gambar dibawah ini :

Gambar a : Tentukan jalur terpendek dari simpul 1 hingga kembali ke simpul 1 lagi. !
Gambar b : Tentukan rute dari node 1 hingga node 7 !
Gambar c : Tentukan lintasan terpendek dari kota 1 ke kota 8 !

Maka, solusi yang ditemukan adalah :
Gambar a : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 1
Gambar b : 1 - 2 - 3 - 4 - 5 - 6 - 7
Gambar c : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

Dalam implementasinya pada program, maka setiap node yang telah dikunjungi harus dimasukkan dalam sebuah queue (antrian) sebagai tempat menampung urutan node tahap demi tahap. untuk memperjelas bagaimana alur algoritmanya, berikut langkah-langkahnya :

  1. Masukkan node akar (root) ke dalam queue
  2. Ambil node dari awal antrian, lalu cek apakah node tersebut merupakan solusi
  3. Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan.
  4. Jika node bukan solusi, masukkan node yang bertetangga dengan node tersebut (node anak) ke dalam queue
  5. Jika queue kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
  6. Ulangi pencarian dari langkah kedua.

B. Depth First Search

Definisi

Pada algoritma DFS, 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 di kiri dapat dihapus dari memori. Jika pada level yang paling dalam belum ditemukan solusi, maka pencarian dilanjutkan ke level sebelumnya. Demikian seterusnya sampai ditemukannya solusi. Jika solusi ditemukan, maka tidak diperlukan proses backtracking (penelusuran untuk mendapatkan jalur yang diinginkan). Beberapa kelebihan dari algoritma DFS adalah pemakaian memori hanya sedikit karena hanya menyimpan lintasan yang aktif saja. Selain itu kelebihannya adalah jika solusi berada pada level yang paling dalam dan paling kiri, maka DFS akan menemukannya secara cepat. Misal suatu ruang keadaan masalah ditunjukkan dengan suatu seperti gambar berikut ini.

Contoh

Dalam pencarian menggunakan algoritma DFS, simpul-simpul yang paling dalam pada tree yang akan di cari paling awal. Sebagai contoh pada Gambar di atas. Urutan pencarian keadaan awal (S) sampai keadaan tujuan (G) adalah dimulai dari node S, kemudian ke node A, kemudian ke node B, kemudian ke node C, setelah itu akan melewati node B kembali dan menuju ke node E, selanjutnya akan menuju node D, setelah itu akan menuju node F setelah melewati node E, dan yang terakhir akan menuju node G.

Sumber:
  • http://repository.usu.ac.id/bitstream/123456789/25380/4/Chapter%20II.pdf
  • http://www.charisfauzan.net/2015/01/pencarian-buta-teori-dan-implementasi.html
loading...