Contoh Laporan dan Tugas Kuliah ~ Ilmu Berlian

ALGORITMA MENENTUKAN SOLUSI DARI PENCARIAN POSISI TUJUAN PADA PERMAINAN KOTAK

“Menggunakan Metode DFS”

Disusun oleh :

ALBERTHUS DIMAS ANANTA 09021381419121

ANUGERAH FADHILA DUHA 09021381419115

DENNY MARANTHA 09021381419069

DONI MIKHA 09021381419107

JOERIZA PERDANA ARTORYAN 09021381419109

THEO VHALDINO 09021381419087

TEKNIK INFORMATIKA BILINGUAL

TAHUN AKADEMIK 2015/2016

UNIVERSITAS SRIWIJAYA

Algoritma Dept First Search (DFS)

Algoritma Depth First Search (DFS) adalah salah satu algoritma pencarian solusi yang digunakan di dalam kecerdasan buatan. Algoritma ini termasuk salah satu jenis uninformed algorithm yaitu algoritma yang melakukan pencarian dalam urutan tertentu tetapi tidak memiliki informasi apa-apa sebagai dasar pencarian kecuali hanya mengikuti pola yang diberikan.

Di dalam DFS, pencarian dilakukan pada suatu struktur pohon yaitu kumpulan semua kondisi yang mungkin yang diimplementasikan dalam sebuah struktur pohon. Paling atas adalah akar (root) yang berisi kondisi awal pencarian (initial state) dan di bawahnya adalah kondisi-kondisi berikutnya sampai kepada kondisi tujuan (goal state).

Deskripsi Permainan Kotak

Adapun kebutuhan aturan-aturan yang harus dipenuhi dalam menjalankan game puzzle angka ini, antara lain sebagai berikut :

1. Aturan-aturan yang terdapat pada game puzzle angka :

· Arah perpindahan kotak kosong (blank tile) harus secara vertikal atau horizontal atau tidak diperbolehkan diagonal atau melengkung.

· Kotak-kotak yang terdapat pada suatu game adalah saling merapat dan tidak berpotongan terisi penuh oleh angka kecuali satu kotak kosong untuk perpindahan angka puzzle.

· Solusi pada game puzzle angka adalah semua angka yang terdapat pada kotak tersusun dengan benar dari angka yang paling rendah yaitu 1 pada atas sebelah kiri sampai dengan angka yang paling tinggi yaitu 15 pada sebelah kanan bawah.

Teknik Depth-First Search

Dari keadaan awal game puzzle angka, algoritma Depth-First Search akan mengembangkan pencarian pada kedalaman pertama sehingga akan menghasilkan pengembangan berikutnya pada kedalaman pertama, selanjutnya algoritma Depth-First Search akan memajukan pencarian pada kedalaman berikutnya dan mengembangkan pada kedalaman tersebut hingga menemukan solusi.

· Mulai pencarian dari simpul yang berada pada posisi s1 sebagai dari pengacakan angka pertama sebagai inputan.

· Kembangkan setiap kemungkinan yang ada pada setiap node dengan menggunakan struktur ruang pohon hingga solusi game puzzle ditemukan, namun jika sudah tidak ada lagi node yang dapat dikembangkan pada struktur ruang pohon sedangkan puzzle masih belum selesai berarti pada pengacakan tersebut memang tidak memiliki jawaban.

Terdapat tiga kotak 1, 2, 3 pada sebuah papan. Sebuah kotak dapat dipindahkan jika tidak ada kotak lain di atasnya dan hanya ada satu kotak yang nantinya boleh dipindahkan. Ada dua kemungkinan pemindahannya, antara lain:

1. Pindahkan sebuah kotak ke atas papan.

2. Pindahkan sebuah kotak ke atas kotak lainnya.

Masalah muncul jika diketahui keadaan awalnya (initial state atau current state) dan tujuan akhirnya (goal state atau final state).

Seperti pada gambar berikut :

Susunan Awal Sususnan Akhir

Gambar 3.1.

Pada gambar 3.1 dapat dilihat bahwa ruang keadaan tersebut memiliki 13 elemen atau node, dengan perpindahan sebagai berikut:

1. Perpindahan kotak 1 ke atas papan untuk lintasan d dan e.

2. Perpindahan kotak 3 ke atas papan untuk lintasan a.

3. Perpindahan kotak 1 ke atas kotak 2 untuk lintasan l.

4. Perpindahan kotak 1 ke atas kotak 3 untuk lintasan b dan m.

5. Perpindahan kotak 2 ke atas kotak 1 untuk lintasan c dan g.

6. Perpindahan kotak 2 ke atas kotak 3 untuk lintasan i dan j.

7. Perpindahan kotak 3 ke atas kotak 1 untuk lintasan h.

8. Perpindahan kotak 3 ke atas kotak 2 untuk lintasan f dan k.

Pseudocode Algoritma

Prosedur depth first search

Begin

Open := [start]

Closed := []

While open = [] do

Begin

Pindahkan verteks paling kiri dari open, namakan x

Jika x adalah tujuan maka

return SUCCESS;

Else

Begin

Hasilkan cabang dari x;

Letakkan x pada closed;

Abaikan cabang dari x jika sudah terletak pada open or closed;

Menempatkan cabang yang tersisa pada ujung kiri dari open;

End;

End

return FAIL

End.

Itulah tadi yang dapat saya sampaikan tentang Contoh Laporan dan Tugas Kuliah.

Jika ada pertanyaan sampaikan dikolom komentar.Semoga dapat membantu dan bermanfaat.

Contoh Laporan dan Tugas Kuliah

Related Post