Minggu, 13 November 2016

Membuat Garis Vertikal, Horizontal dan Diagonal Menggunakan Java dan Opengl

Cara Membuat Garis Vertikal, Horizontal dan Diagonal Menggunakan Java dan Opengl
Disini saya akan membuat program garis vertikal, horizontal dan diagonal menggunakan java (NetBeans IDE 8.0.2) dan opengl.kalian bisa download disini Cara Memakai Aplikasi Java Menu dan Program nya ada Disini

OpenGl mempunyai tujuan yang diantaranya:

*Untuk tidak menampilkan kompleksitas dari interfacing dengan berbagai 3D accelerators,
ditunjukan oleh programmer dengan satu, seragam API.
*Untuk tidak menampilkan kemampuan yang berbeda dari hardware platform, karena semua yang mendukung implementasi penuh fitur opengl set (menggunakan software
emulation jika dibutuhkan).

Tahap 1


Buka NetBeans, kemudian buat new project dan new file. Beri nama file sesuai yang diinginkan. Di file pertama ini saya beri nama LineMaker. File ini digunakan untuk membuat menu pilihan. Lalu ketik kodingannya seperti pada gambar 1.




Penjelasan :

import java.util.*;  yaitu memanggil library untuk fungsi scanner yang berguna untuk inputan.
import org.lwjgl.LWJGLException; yaitu memanggil library untuk menjalankan fungsi pengecualian pada 'lwjgl'.

public class LineMaker { yaitu public class yang digunakan pada program ini adalah “LineMaker”.
public static void main(String[] args) throws LWJGLException{ yaitu merupakan statemen yang digunakan untuk membuat argumen dengan menggunakan variabel.

int pil; yaitu mendefinisikan variabel pil untuk menerima inputan pilihan user nantinya.
Scanner input = new Scanner(System.in); yaitu membuat fungsi inputan menggunakan fungsi scanner.

System.out.println("========Aplikasi Pembuat Garis========");yaitu mencetak teks yang ada dalam tanda kutip.

System.out.println("1. Membuat Garis Vertical"); yaitu mencetak teks yang ada dalam tanda kutip.
System.out.println("2. Membuat Garis Horizontal"); yaitu mencetak teks yang ada dalam tanda kutip.
System.out.println("3. Membuat Garis Diagonal"); yaitu mencetak teks yang ada dalam tanda kutip.
System.out.print("Silahkan Masukan Pilihan yang diinginkan : "); yaitu mencetak teks yang ada dalam tanda kutip.

pil = input.nextInt(); yaitu menerima inputan user dan memasukannya kedalam variabel 'pil'.
switch(pil){  yaitu memilih kondisi pada 'case' berdasarkan inputan user (misal : 1 untuk case 1).

case 1:

Vertikal vet = new Vertikal(); yaitu memanggil class 'Vertikal'.
vet.layar(); yaitu menjalankan fungsi 'layar' pada class 'Vertikal'.
break; yaitu memberhentikan kondisi.

case 2:

Horizontal hoz = new Horizontal(); yaitu memanggil class 'Horizontal'.
hoz.layar(); yaitu menjalankan fungsi 'layar' pada class 'Horizontal'.
break; yaitu memberhentikan kondisi.

case 3:

Diagonal dig = new Diagonal(); yaitu memanggil class 'Diagonal.
dig.layar(); yaitu menjalankan fungsi 'layar' pada class 'Diagonal.
break; yaitu memberhentikan kondisi.
default:

System.out.println("Pilihan yang anda pilih salah!!"); yaitu memunculkan pesan apabila input pada pil tidak sesuai dengan case yang ada.
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.

Tahap 2

Jika sudah selesai membuat file pertama, buat kembali file baru di project yang sama dan beri nama file sesuai keinginan. File ke-2 disini saya beri nama Vertikal. File ini digunakan untuk membuat garis vertikal. Lalu ketik kodingannya seperti pada gambar 2.


Penjelasan :

import org.lwjgl.LWJGLException; yaitu memanggil library untuk menjalankan fungsi pengecualian pada lwjgl.

import org.lwjgl.opengl.*; yaitu memanggil library 'lwjgl' untuk menjalankan renderer opengl.

import java.util.*; yaitu memanggil library untuk fungsi scanner yang berguna untuk inputan.

public class Vertikal { yaitu public class yang digunakan pada program ini adalah “Vertical”.

public void layar() throws LWJGLException { yaitu merupakan statemen yang digunakan untuk 

membuat argumen dengan menggunakan variabel.

int a,kordin1,kordin2; yaitu mendefinisikan variabel 'a,kordin1,dan kordin2'.

Scanner putin = new Scanner(System.in); yaitu mendefinisikan fungsi Scanner pada 'putin' untuk 
menerima input user.

System.out.print("Masukan titik awal (x) : "); yaitu mencetak teks yang ada dalam tanda kutip.

kordin1 = putin.nextInt(); yaitu untuk menginput kordin1 (koordinat x).

System.out.print("Masukan titik awal (y) : "); yaitu mencetak teks yang ada dalam tanda kutip.

kordin2 = putin.nextInt(); yaitu untuk menginput kordin2 (koordinat y).

System.out.print("Masukan Panjang garis yang diinginkan (dalam Pixel) : "); yaitu mencetak teks yang ada dalam tanda kutip.

a = putin.nextInt(); yaitu menerima input user dan memasukannya kedalam variabel 'a' yang akan digunakan sebagai panjang dari garis yang akan dibuat.
try {

Display.setDisplayMode(new DisplayMode(300,300)); yaitu membuat sebuah jendela rendering dengan seting luas layar = 300x300.

Display.setTitle("Garis Vertikal"); yaitu mengubah nama jendela rendering menjadi "Garis Vertikal".

Display.create(); yaitu membuat jendela rendering.
} catch (LWJGLException e) {

System.exit(0); yaitu mencegah jendela rendering tertutup apabila tidak ada aktivitas pada library LWJGL.

} yaitu untuk mengakhiri statemen.

GL11.glMatrixMode(GL11.GL_PROJECTION);
GL11.glLoadIdentity(); yaitu memanggil opengl sebagai renderer.
GL11.glOrtho(0, 800, 0, 600, 1, -1);
GL11.glMatrixMode(GL11.GL_MODELVIEW);

while (!Display.isCloseRequested()) { yaitu mencegah jendela renderer tertutup kecuali ditutup sendiri oleh user.

GL11.glBegin(GL11.GL_QUADS); yaitu memanggil fungsi 'GL_QUADS untuk merender berdasarkan 4 titik yang ditentukan.
GL11.glVertex2f(kordin1,kordin2); yaitu titik awal.
GL11.glVertex2f(kordin1+5,kordin2); yaitu titik awal, pada sumbu x sengaja diberi jeda agar mempertebal garis yang akan dibentuk.
GL11.glVertex2f(kordin1+5,kordin2+a); yaitu titik akhir, pada sumbu x sengaja diberi jeda agar mempertebal garis yang akan dibentuk.
GL11.glVertex2f(kordin1,kordin2+a); yaitu titik akhir, pada sumbu y variabel akan ditambahkan 'a' yang sesuai dengan inputan user.
GL11.glEnd();  yaitu mengakhiri proses render.
Display.update();
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.

Tahap 3

Jika sudah selesai membuat file ke-2, buat kembali file baru di project yang sama dan beri nama file sesuai keinginan. File ke-3 disini saya beri nama Horizontal. File ini digunakan untuk membuat garis horizontal. Lalu ketik kodingannya seperti pada gambar 3.
Penjelasan :

import org.lwjgl.LWJGLException; yaitu memanggil library untuk menjalankan fungsi pengecualian pada lwjgl.

import org.lwjgl.opengl.*; yaitu memanggil library 'lwjgl' untuk menjalankan renderer opengl.

import java.util.*; yaitu memanggil library untuk fungsi scanner yang berguna untuk inputan.

public class Horizontal { yaitu public class yang digunakan pada program ini adalah “Horizontal”.

public void layar() throws LWJGLException { yaitu merupakan statemen yang digunakan untuk 

membuat argumen dengan menggunakan variabel.

int a,kordin1,kordin2; yaitu mendefinisikan variabel 'a,kordin1,dan kordin2'.

Scanner putin = new Scanner(System.in); yaitu mendefinisikan fungsi Scanner pada 'putin' untuk 
menerima input user.

System.out.print("Masukan titik awal (x) : "); yaitu mencetak teks yang ada dalam tanda kutip.
kordin1 = putin.nextInt(); yaitu untuk menginput kordin1 (koordinat x).

System.out.print("Masukan titik awal (y) : "); yaitu mencetak teks yang ada dalam tanda kutip.

kordin2 = putin.nextInt(); yaitu untuk menginput kordin2 (koordinat y).

System.out.print("Masukan Panjang garis yang diinginkan (dalam Pixel) : "); yaitu mencetak teks yang ada dalam tanda kutip.

a = putin.nextInt(); yaitu menerima input user dan memasukannya kedalam variabel 'a' yang akan digunakan sebagai panjang dari garis yang akan dibuat.
try {

Display.setDisplayMode(new DisplayMode(300,300)); yaitu membuat sebuah jendela rendering dengan seting luas layar = 300x300.

Display.setTitle("Garis Horizontal"); yaitu mengubah nama jendela rendering menjadi "Garis Horizontal"

Display.create(); yaitu membuat jendela rendering.
} catch (LWJGLException e) {

System.exit(0); yaitu mencegah jendela rendering tertutup apabila tidak ada aktivitas pada library LWJGL.

} yaitu untuk mengakhiri statemen.

GL11.glMatrixMode(GL11.GL_PROJECTION);
GL11.glLoadIdentity(); yaitu memanggil opengl sebagai renderer.
GL11.glOrtho(0, 800, 0, 600, 1, -1);
GL11.glMatrixMode(GL11.GL_MODELVIEW);

while (!Display.isCloseRequested()) { yaitu mencegah jendela renderer tertutup kecuali ditutup sendiri oleh user.
GL11.glBegin(GL11.GL_QUADS); yaitu memanggil fungsi 'GL_QUADS untuk merender berdasarkan 4 titik yang ditentukan.
GL11.glVertex2f(kordin1,kordin2); yaitu titik awal.
GL11.glVertex2f(kordin1,kordin2+5); yaitu titik awal, pada sumbu y sengaja diberi jeda agar mempertebal garis yang akan dibentuk.
GL11.glVertex2f(kordin1+a,kordin2+5); yaitu titik akhir, pada sumbu x variabel akan ditambahkan 'a' yang sesuai dengan inputan user dan pada sumbu y sengaja diberi jeda agar mempertebal garis yang akan dibentuk.
GL11.glVertex2f(kordin1+a,kordin2);  yaitu titik akhir, pada sumbu x variabel akan ditambahkan 'a' yang sesuai dengan inputan user.
GL11.glEnd(); yaitu mengakhiri proses render.
Display.update();
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.

Tahap 4

Jika sudah selesai membuat file ke-3, buat kembali file baru di project yang sama dan beri nama file sesuai keinginan. File ke-4 disini saya beri nama Diagonal. File ini digunakan untuk membuat garis diagonal. Lalu ketik kodingannya seperti pada gambar 4.
Penjelasan :
Import org.lwjgl.LWJGLException; yaitu memanggil library untuk menjalankan fungsi pengecualian pada lwjgl.

Import org.lwjgl.opengl.*; yaitu memanggil library ‘lwjgl’ untuk menjalankan rendere opengl.

Import java.util.*; yaitu memanggil library untuk fungsi scanner yang berguna untuk inputan.

Pubilc class Diagonal { yaitu public class yang digunakan pada program ini adalah “Diagonal”.

Public void layar() throws LWJGLException { yaitu merupakan statemen yang digunakan untuk membuat argumen dengan menggunakan variabel.

Int a, kordin1, kordin2; yaitu mendefinisikan variabel ‘a, kordin1, dan kordin2.

Scanner putin = new Scanner(System.in); yaitu mendefinisikan fungsi Scanner pada ‘putin’ untuk menerima input user.

System.out.print(“Masukan titik awal (x) : “); yaitu mencetak teks yang ada dalam tanda kutip.
Kordin1 = putin.nextInt(); yaitu untuk menginput kordin1 (koordinat x)

System.out.print(“Masukan titik awal (y) : “); yaitu mencetak teks yang ada dalam tanda kutip.
Kordin2 = putin.nextInt(); yaitu untuk menginput kordin2 (koordinat y)

System.out.print(“Masukan panjang garis yang diinginkan (dalam pixel) : “); yaitu mencetak teks yang ada dalam tanda kutip.

a = putin.nextInt(); yaitu menerima input user dan memasukannya kedalam variabel ‘a’ yang akan digunakan sebagai panjang dari garis yang akan dibuat.
Try {

Display.setDisplayMode(new DisplayMode(300, 300)); yaitu membuat sebuah jendela rendering dengan seting luas layar = 300x300.

Display.setTitle(“Garis Diagonal”); yaitu mengubah nama jendela rendering menjadi “Garis Diagonal”

Display.create(); yaitu membuat jendela rendering.
} catch (LWJGLException e) {
System.exit(0); yaitu mencegah jendela rendering tertutup apabila tidak ada aktifitas pada library LWJGL.
} yaitu untuk mengakhiri statemen.
GL11.glMatrixMode(GL11.GL_PROJECTION);
GL11.glLoadIdentity(); yaitu memanggil opengl sebagai renderer.
GL11.glOrtho(0, 800, 0, 600, 1, -1);
GL11.glMartixMode(GL11.GL_MODELVIEW);
While (!Display.isCloseRequested()) { yaitu mencegah jendela renderer tertutup kecuali ditutup sendiri oleh user.
GL11.glBegin(GL11.GL_QUADS);
GL11.glVertex2f(kordin1, kordin2); yaitu titik awal.
GL11.glVertex2f(kordin1-5, kordin2); yaitu titik awal, pada sumbu x sengaja diberi jeda untuk mempertebal garis.
GL11.glVertex2f(koordin1+a-5, kordin2+a); yaitu titik akhir, pada sumbu x dan y variabel akan ditambahkan ‘a’ yang sesuai dengan inputan user dan pada sumbu x sengaja diberi jeda untuk mempertebal garis.
GL11.glVertex2f(kordin1+a, kordin2+a); yaitu titik akhir, pada sumbu x dan y variabel akan ditambahkan ‘a’ yang sesuai dengan inputan user.
GL11.glEnd(); yaitu mengakhiri proses render
Display.update();
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.
} yaitu untuk mengakhiri statemen.

Tahap 5

Pada tahap ini kita akan melihat output dari hasil kodingan tersebut. Adapun cara kerjanya sebagai berikut.
Pertama compile program tersebut.
Setelah itu run program.
Maka muncul outputnya.
Pada outputnya muncul 3 menu pilihan.
Pilih salah satu menu sesuai keinginan.



Jika memilih menu pilihan 1 maka akan membuat garis vertikal. Masukan titik awal (x) dan titik awal (y) serta panjang garis yang diinginkan (dalam pixel) sesuai keinginan, seperti pada gambar 5.


Output yang diperoleh yaitu seperti pada gambar 6.



Jika memilih menu pilihan 2 maka akan membuat garis horizontal. Masukan titik awal (x) dan titik awal (y) serta panjang garis yang diinginkan (dalam pixel) sesuai keinginan, seperti pada gambar 7.


Output yang diperoleh yaitu seperti pada gambar 8.



Jika memilih menu pilihan 3 maka akan membuat garis diagonal. Masukan titik awal (x) dan titik awal (y) serta panjang garis yang diinginkan (dalam pixel) sesuai keinginan, seperti pada gambar 9.


Output yang diperoleh yaitu seperti pada gambar 10.








Selasa, 01 November 2016

Hill Climbing

Hill Climbing
Metode ini hampir sama dengan metode generate and test dan merupakan salah satu
variasi dari metode tersebut. Yang membedakan kedua metode ini adalah umpan balik
(feed back) yang berasal dari prosedur pengujian digunakan untuk memutuskan arah
gerak dalam pencarian.
Ada dua macam metode hill climbing, yaitu simple hill climbing dan steepest ascent
hill climbing.

Simple Hill Climbing
Algoritma untuk simple hill climbing adalah sebagai berikut.

1. Mulai dari keadaan awal, lakukan pengujian. Jika merupakan tujuan maka
berhenti. Jika sebaliknya, lanjutkan dengan keadaan sekarang sebagai keadaan
awal.

2. Ulangi langkah – langkah berikut hingga solusi ditemukan, atau sampai tidak ada
operator baru yang akan diaplikasikan pada keadaan sekarang.

a. Pilih operator yang belum pernah digunakan, gunakan operator ini untuk
mendapatkan keadaan yang baru.

b. Evaluasi keadaan yang baru tersebut. Jika keadaan baru merupakan tujuan maka keluar
. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang,
maka jadikan keadaan baru tersebut menjadi keadaan sekarang. Jika keadaan baru tidak lebih baik daripada keadaan sekarang maka lanjutkan iterasi.

Sebagai ilustrasi pencarian solusi dengan simple hill climbing, kita gunakan contoh
masalah TSP pada generate and test. Operator yang digunakan adalah operator yang
bisa menghasilkan kombinasi lintasan kota yang berbeda – beda, yaitu dengan cara
menukar posisi masing – masing kota. Untuk mempermudah penukaran posisi, kita
cukup menukar posisi 2 kota, operator untuk kombinasi lintasan dengan menukar
posisi 2 kota dapat dihitung dengan rumus 2! ( 2 )!!
n −n
sehingga operator yang kita
peroleh untuk masalah ini adalah 2! ( 4 2 )!4!

kombinasi operator, yaitu :
1. (1,2) : Menukar posisi kota kesatu dengan kota kedua
2. (1,3) : Menukar posisi kota kesatu dengan kota ketiga
3. (1,4) : Menukar posisi kota kesatu dengan kota keempat
4. (2,3) : Menukar posisi kota kedua dengan kota ketiga
5. (2,4) : Menukar posisi kota kedua dengan kota keempat
6. (3,4) : Menukar posisi kota ketiga dengan kota keempat
Pada pencarian dengan menggunakan simple hill climbing, penggunaan urutan
operator harus konsisten, tidak boleh berbeda dalam setiap level. Urutan penggunaan
operator juga sangat menentukan kecepatan dalam menemukan solusi.

Setelah urutan operator ditentukan, gunakan algoritma pengerjaan sesuai aturan
metode simple hill climbing. Keadaan awal yang dibangkitkan, misalnya kita pilih
ABCD, sesuai dengan gambar berikut ini.

Pencarian pada simple hill climbing mulai dilihat dari anak kiri. Apabila nilai
heuristik anak kiri lebih baik maka dibuka untuk pencarian selanjutnya. Jika tidak,
barulah kita dapat melihat tetangga dari anak kiri tersebut, dan seterusnya.
Pada gambar di atas, terlihat bahwa pada level satu BACD nilai heuristiknya lebih
baik daripada ABCD (ABCD = 10 < BACD = 9) sehingga yang dibuka untuk
pencarian selanjutnya adalah BACD tanpa harus mengecek nilai heuristik tiap node
yang selevel BACD. Pada level dua untuk operator (1,2), lintasan yang ditemui adalah
ABCD. Oleh karena lintasan tersebut telah dilalui dan dicek sebelumnya maka tidak
perlu dilakukan pengecekan lagi. Kemudian, dipilih node CBAD yang ternyata nilai
heuristiknya sama dengan BACD sehingga pengecekan dilanjutkan pada tetangga
CABD yaitu DACB, yang ternyata nilai heuristiknya juga lebih jelek dari BACD
(BACD = 8 < DACB = 10). Cek node tetangganya, yaitu BCAD, yang nilai
heuristiknya juga lebih jelek dibandingkan BACD (BACD = 8 < BCAD = 10).
Lakukan pengecekan untuk node selanjutnya, yaitu BDCA, yang ternyata nilai
heuristiknya juga lebih jelek dibandingkan BACD (BACD = 8 < BDCA = 10).
Pengecekan terakhir dilakukan pada node BADC yang ternyata nilai heuristiknya
ABCD
(10)
BACD
(9)
CBAD
(8)
DBCA
(12)
ACBD
(12)
ADCB
(9)
ABDC
(8)
ABCD
(10)
CABD
(9)
DACB
(10)
BCAD
(10)
BDAC
(8)
BADC
(6)
CADB
(8)
BDAC
(8)
BCDA
(9)
BACD
(9)
DABC
(8)
ABDC
(8)
(1,2) (1,3)
(1,4)
(2,4)
(2,3)
(3,4)
(1,2)
(1,2)
(1,3)
(1,3)
(1,4)
(1,4)
(2,3)
(2,3)
(2,4)
(2,4)
(3,4)
(3,4)
23
lebih baik dari BACD (BACD = 8 > BADC = 6) sehingga untuk pencarian
selanjutnya, yang dibuka adalah node BADC.
Node yang dibuka untuk level tiga adalah BADC, setelah dieksplorasi dengan urutan
operator yang telah ditentukan, secara berturut – turut diperoleh node berikut : node
ABDC yang nilai heuristiknya lebih jelek dari BADC (BADC = 6 < ABDC = 8),
DABC yang juga nilai heuristiknya lebih jelek dari BADC (BADC = 6 < DABC = 8),
CADB yang nilai heuristiknya juga jelek (BADC = 6 < CADB = 8), BDAC yang nilai
heuristiknya juga jelek (BADC = 6 < BDAC = 8), BCDA yang nilai heuristiknya juga
lebih jelek dari BADC (BADC = 6 < BCDA = 9), selanjutnya pengecekan pada node
terakhir BACD yang ternyata nilai heuristiknya juga lebih jelek dari BDAC (BDAC =
6 < BCAD = 9). Oleh karena pada level tiga tidak ada node yang menghasilkan nilai
heuristik yang lebih baik dari BDAC maka pencarian solusi dihentikan. Solusi yang
ditemukan dari metode simple hill climbing tersebut adalah BADC dengan panjang
lintasan adalah 6. Berbeda apabila kita menggunakan metode generate and test di
mana semua solusi dapat diperoleh yaitu BADC atau CDBA. Pada metode simple hill
climbing, tidak semua solusi dapat kita temukan.

Penggunaan operator sangat mempengaruhi penemuan solusi pada metode simple hill
climbing, begitu juga apabila penggunaan operator dibatasi misalnya untuk masalah
TSP sebelumya. Pada masalah TSP tersebut, diperlukan penggunaan 6 operator, tetapi
kita batasi hanya menggunakan 4 operator. Dengan demikian, solusi yang dihasilkan
belum tentu merupakan solusi optimal karena tidak semua kemungkinan solusi
dilakukan pengecekan yang disebabkan oleh kurangnya penggunaan operator yang
diperlukan untuk membangkitkan kemungkinan solusi yang ada.

Steepest Ascent Hill Climbing

Steepest Ascent Hill Climbing hampir sama dengan simple hill climbing, dan yang
membedakan keduanya adalah pada gerakan pencarian yang bila menemukan satu
node tidak langsung berhenti tetapi dilanjutkan dengan mencari apakah ada node lain
yang memiliki nilai heuristik yang lebih baik. Dalam hal ini, urutan penggunaan
operator tidak menentukan penemuan solusi.

solusi bagi masalah TSP tersebut adalah CDAB dengan panjang
lintasan sebesar 6. Metode Steepest Ascent Hill Climbing tidak harus melihat naka kiri
pertama kali, tetapi dengan mencari semua nilai heuristik yang lebih baik pada node –
node selevel. Gambar di atas menunjukkan bahwa pada level satu, yang memiliki nilai
heuristik yang lebih baik dari lintasan ABCD yang panjangnya 10 adalah lintasan
CBAD dan ABDC dengan lintasan sama dengan 8. Oleh karena ada dua node yang
nilainya sama dan lebih baik dibandingkan node tetangganya yang lain maka kita
dapat memilih salah satu node yang ingin dibuka untuk melanjutkan pencarian solusi
selanjutnya. Pada gambar, dipilih node CBAD untuk pencarian selanjutnya. Pada
level dua, diperoleh node CDAB dengan panjang lintasan adalah 6 sebagai lintasan
yang lebih baik nilai heuristiknya dibandingkan node lintasan sebelumnya dan juga
bila dibandingkan dengan node – node tetangganya. Pada level tiga tidak ditemukan
nilai heuristik yang lebih baik dibandingkan lintasan CDAB sehingga pencarian
berhenti dan solusi yang diperoleh untuk lintasan terpendek adalah CDAB dengan
panjang lintasan adalah 6.
ABCD
(10)
BACD
(9)
CBAD
(8)
DBCA
(12)
ACBD
(12)
ADCB
(9)
ABDC
(8)
(1,2) (1,3)
(1,4)
(2,4)
(2,3)
(3,4)
BCAD
(10)
ABCD
(10)
DBAC
(9)
CABD
(9)
CDAB
(6)
DCAB
(9)
ADCB
(9)
BDAC
(8)
CADB
(8)
CBAD
(8)
CDBA
(8)
CBDA
(9)
(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)
(1,2)
(1,3) (1,4) (2,3) (2,4) (3,4).


http://ibbi.ac.id/ibbiacid/bahan/kecerdasan-buatan.pdf

Blind Search

Strategi Pencarian Mendalam

Pencarian boleh jadi merupakan hasil dari suatu solusi atau ruang keadaan yang
mungkin telah terkunjungi semua, tetapi tanpa penyelesaian. Pencarian yang
mendalam (Exhaustive Search Strategy) mungkin dilakukan dengan menggunakan
strategi Breadth First Search atau Depth First Search). Kedua pencarian ini
merupakan pencarian buta (Blind Search)

Breadth First Search

Prosedur Breadth First Search merupakan pencarian yang dilakukan dengan
mengunjungi tiap – tiap node secara sistematis pada setiap level hingga keadaan
tujuan (goal state) ditemukan. Atau dengan kata lain, penelusuran yang dilakukan
adalah dengan mengunjungi node – node pada level yang sama hingga ditemukan
goal state nya. Untuk lebih jelasnya, perhatikan ilustrasi dari Breadth First Search
pada gambar berikut ini.

Pengimplementasian Breadth First Search dapat ditelusuri dengan menggunakan
daftar (List) open dan closed, untuk menelusuri gerakan pencarian di dalam ruang
keadaan, prosedur untuk Breadth First Search dapat dituliskan sebagai berikut




(Luger : 2002) :

Prosedure breadth first search
Begin
Open := [Start];
Closed := [];
While Open ≠ [] do
Begin
S
A D
B F
C E
M N
G
O P
H I
J
Q R
K L
T U V
9
Remove leftmost state from open, call it x
If X is a goal then return SUCCESS
Else
Begin
Generate children of x;
Put x on closed;
Discard children of x is already open or closed;
Put remaining children on right end of open;
End;
End;
Return FAIL
End.



Pada gambar di atas, U* adalah node tujuannya (goal) sehingga bila ditelusuri
menggunakan prosedur Depth First Search, diperoleh :
1. Open = [A]; Closed = []
2. Open = [B, C, D]; Closed = [A]
A
B C D
E F
K L M
S T
G H
N O P
I J
Q
U*
R
10
3. Open = [C, D, E, F]; Closed = [B, A]
4. Open = [D, E, F, G, H]; Closed = [C, B, A]
5. Open = [E, F, G, H, I, J]; Closed = [D, C, B, A]
6. Open = [F, G, H, I, J, K, L]; Closed = [E, D, C, B, A]
7. Open = [G, H, I, J, K, L, M]; Closed = [G, F, E, D, C, B, A]
8. dan seterusnya sampai U diperoleh atau open =[]

Keuntungan :

1. Tidak akan menemui jalan buntu dan jika ada satu solusi maka Breadth First
Search akan menemukannya.
2. Jika ada lebih dari satu solusi maka solusi minimum akan ditemukan

Kerugian :

1. Membutuhkan memori yang besar, karena menyimpan semua node dalam satu
pohon.
2. Membutuhkan sejumlah besar pekerjaan, khususnya bila solusi terpendek cukup
panjang, karena jumlah node yang perlu diperiksa bertambah secara eksponensial
terhadap panjang lintasan.

Depth First Search

Pencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang
paling akhir n(dead end) atau sampai ditemukan. Dengan kata lain, simpul cabang
atau anak yang terlebih dahulu dikunjungi. Sebagai ilustrasinya dapat dilihat pada
gambar berikut ini.
11

Prosedur Depth First Search dapat diimplementasikan dengan melakukan modifikasi
proses Breadth First Search menjadi 



(Luger : 2002) :

Prosedure depth first search
Begin
Open := [Start];
Closed := [];
While Open ≠ [] do
Begin
Remove leftmost state from open, call it x
If X is a goal then return SUCCESS
Else
Begin
Generate children of x;
Put x on closed;
Discard children of x is already open or closed;
Put remaining children on left end of open;
1
2 11
3 5
8
4 6 7
9
10
12 14
13 15 16
12
End;
End;
Return FAIL
End.

Untuk memeriksa algoritma di atas, dapat dilihat bahwa keadaan – keadaan turunan
(descendant) ditambahkan atau dihapuskan dari ujung kiri open. Untuk lebih jelasnya,
dapat dilihat aplikasi algoritma tersebut untuk contoh sebelumnya seperti pada
Breadth First Search. Langkah penelusuran adalah sebagai berikut.

1. Open = [A]; Closed = []
2. Open = [B, C, D]; Closed = [A]
3. Open = [E, F, C, D]; Closed = [B, A]
4. Open = [K, L, F, C, D]; Closed = [E, B, A]
5. Open = [S, L, F, C, D]; Closed = [K, E, B, A]
6. Open = [L, F, C, D]; Closed = [S, K, E, B, A]
7. Open = [T, F, C, D]; Closed = [L, S, K, E, B, A]
8. Open = [F, C, D]; Closed = [T, L, S, K, E, B, A]
9. Open = [M, C, D]; Closed = [F, T, L, S, K, E, B, A]
10. Open = [C, D]; Closed = [M, F, T, L, S, K, E, B, A]
11. Open = [G, H, D]; Closed = [C, M, F, T, L, S, K, E, B, A]
12. dan seterusnya sampai U diperoleh atau open =[]

http://ibbi.ac.id/ibbiacid/bahan/kecerdasan-buatan.pdf

Template by:

BlackHat48