BREADTH FIRST SEARC

 

Implementasi Algoritma Breadth First Search Pada Pacman Untuk

Mengatur Pergerakan Karakter

1.      PENDAHULUAN

 

Kecerdasan buatan merupakan salah satu cabang ilmu komputer yang memberikan ilmu pengetahuan terhadap komputer agar mampu menyelesaikan tugas-tugas atau berpikir seperti manusia. Dalam perkembangannya kecerdasan buatan dalam bidang game saat ini sangat populer untuk permainan manusia melawan komputer (NPC). Permainan antara manusia dan komputer dapat meningkatkan kualitas game agar dapat lebih menyenangkan dan menantang untuk dimainkan.

Algoritma Breadth First Search (BFS) merupakan algoritma penelusuran graf. Breadth First Search meupakan algoritma sederhana untuk melakukan penelusuran pada graf, algoritma ini merupakan algoritma yangmenjadi pola dasar dan fundamental bagi banyak algoritma graf. Algoritma BFS menelusuri batas ambang antara node yang sudah dikunjungi dan node yang belum dikunjungi. Algoritma ini mengunjungi node sedemikian sehingga setiap node yang berjarak dari node awal akan dikunjungi sebelum mengunjungi node yang berjarak s+1dari node awal(layer orde). Penelusuan graf pada algoritma Breadth First Search dilakukan dengan menelusuri setiap node dari awal. Struktur data antrian(queue) digunakkan untuk melakukan proses ekspansi Breadth First Search.

Struktur data antrian digunakkan untuk menampung setiap node atau kemungkinan node yang valid untuk dilalui. Sifat dari queue adalah First In First Out. Oleh karena itu setiap node yang dipilih dan di-expand pertama kali oleh algoritma ini akan pertama kali juga diproses dan ditelusuri. Sifat dari queue tersebut mempertahankan sifat dari algoritma Breadth First Search itu sendiri, dimana algoritma ini menelusuri secara layer order. Setiap node yang telah ditelusuri oleh algoritma breadth first search tidak akan dikunjungi lagi.

Dewasa ini Algoritma BFS merupakan algoritma untuk penentuan jalur terpendek antara titik awal dengan titik akhir tanpa melewati hambatan. Algoritma BFS menggunakkan pendekatan heuristik yang menelusuri seluruh verteks yang direpresentasikan dengan node, dengan cara memperikirakan rute tebaik yang dapat dilalui dari node tersebut. Algoritma BFS banyak digunakkan dalam menyelesaikan masalah jalur terpendek dalam game karena kesederhanaan dan efektifitasnya.

2.      METODE PENELITIAN

 

2.1 Logika Fuzzy

Logika fuzzy merupakan kecerdasan buatan yang dapat membuat komputer menyelesaikan masalah perilaku sistem yang kompleks dan ketidakpastian yang disebabkan oleh kemampuan mengolah informasi numerik dari variabel yang diukur. Logika fuzzy dapat diterapkan untuk pengambilan keputusan perilaku komputer dalam game. Algoritma BFS dan Logika Fuzzy digunakkan karena Algoitma BFS lebih cepat dan lebih tepat dalam pencarian dan lebih tepat dalam penentuan keputusan.

 

3.      ANALISA DAN PEMBAHASAN

 

Berdasarkan penjelasan diatas akan dilakukan penelitian dengan memilih game classic yaitu Pac-Man untuk menerapkan algoritma Breadth First Search (BFS) untuk mencari dan mengejar Pac-Man(player) dan menerapkan logika fuzzy metode Sugeno sebagai pengambilan keputusan perilaku ghost, serta jumlah item berdasarkan kondisi-kondisi yang diberikan, penelitian ini dilakukan dengan beberapa tahap yang saling berkesinambungan.

3.1 Merancang Prototype

a. Menentukan titik yang akan dilalui oleh NPC

Titik atau node yang akan dilalui oleh NPC direpresentasikan dengan huruf didalam elipse disetiap

persimpangan, sedangkan jalur yang akan dilalui NPC direpresentasikan dengan angka 1.

            b. Merancang tampilan Game

Karakter NPC memiliki pergerakan yang berbeda yakni random dan BFS, Karakter random memiliki

pergerakan yang dibuat secara acak tanpa menggunakkan algoritma BFS sedangkan karakter BFS

menggunakkan algoritma BFS serta Logika Fuzzy.

Maze atau labirin yang menjadi jalur lintasan yang akan dilalui oleh PacMan dan Ghost dibuat seperti game PacMan pada umumnya.

3.2 Menerapkan Algoritma Breadth First Search

Penerapan algoritma Breadth First Search pada penelitian ini memeiliki beberapa tahap yakni

a. memasukkan simpul node ke dalam antrian,

b. Ambil node pada awal antrian, kemudian dicek apakah merupakan solusi,

c. jika node merupakan solusi maka pencarian selesai dan hasil dikembalikan,

d. jika simpul bukan solusi, masukkan seluruh node yang bertetangga dengan node tersebut(node anak)

ke dalam antrian,

e. jika antrian kosong dan setiap node sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak

ditemukan,

f. lalu mengulangi langkah b

4. KESIMPULAN

 

Berdasarkan penelitian yang telah dilakukan, dapat diambil kesimpulan sebagai berikut :

1. Pengambilan keputusan perilaku ghos (NPC = Non-Player Character) dan jumlah item pada game sudah sesuaidengan harapan dengan menggunakkan logika fuzzy metode Sugeno, dimana ghost akan bereaksi dan menentukan jumlah item yang keluar berdasarkan kondisi-kondisi yang sudah diberikan.

2. Penerapan Algoritma BFS dapat berjalan sesuai dengan harapan, dimana ghost dapat menentukan jalur

terpendek yang digunakkan dalam mencari dan mengejar pada game Pac-Man.

 

REFERENCES

https://www.ejurnal.stmik-budidarma.ac.id/index.php/jurikom/article/view/1004/999

STATISTIKA

v MEDIAN

Pada data tunggal, penghitungan median cukup mudah. Data diurutkan berdasarkan nilai datanya mulai dari yang terkecil sampai yang terbesar. Kemudian median bisa diketahui langsung dari nilai tengah urutan data tersebut.

Namun pada data berkelompok, cara tersebut tidak bisa digunakan. Data berkelompok merupakan data yang berbentuk kelas interval, sehingga kita tidak bisa langsung mengetahui nilai median jika kelas mediannya sudah diketahui.

Oleh karena itu, kita harus menggunakan rumus berikut ini.

Me = median

xii = batas bawah median

n = jumlah data

fkii = frekuensi kumulatif data di bawah kelas median

fi = frekuensi data pada kelas median

p = panjang interval kelas

Contoh Soal No. 1

Sebanyak 26 orang mahasiswa terpilih sebagai sampel dalam penelitian kesehatan di sebuah universitas. Mahasiswa yang terpilih tersebut diukur berat badannya. Hasil pengukuran berat badan disajikan dalam bentuk data berkelompok seperti di bawah ini.

Hitunglah median berat badan mahasiswa!

Jawab:

Sebelum menggunakan rumus di atas, terlebih dahulu dibuat tabel untuk menghitung frekuensi kumulatif data. Tabelnya adalah sebagai berikut.

Selanjutnya adalah menentukan nilai-nilai yang akan digunakan pada rumus.

Jumlah data adalah 26, sehingga mediannya terletak di antara data ke 13 dan 14. Data ke-13 dan 14 ini berada pada kelas interval ke-4 (61 – 65). Kelas interval ke-4 ini kita sebut kelas median.

Melalui informasi kelas median, bisa kita peroleh batas bawah kelas median sama dengan 60,5. Frekuensi kumulatif sebelum kelas median adalah 9, dan frekuensi kelas median sama dengan 5. Diketahui juga, bahwa panjang kelas sama dengan 5.

Secara matematis bisa diringkas sebagai berikut:

xii = 60,5

n = 26

fkii = 9

fi = 5

p = 5

Dari nilai-nilai tersebut dapat kita hitung median dengan menggunakan rumus median data berkelompok.

Sehingga median berat badan mahasiswa adalah 64,5 kg.

v MODUS

Rumus Modus Data Kelompok

Pengertian modus adalah nilai data yang paling sering muncul atau data yang mempunyai nilai frekuensi paling tinggi. Cara mencari nilai modus pada data tunggal sangat mudah, sobat idschool hanya perlu mencari data dengan frekuensi paling banyak.

Cara mencari nilai modus data kelompok tidak semudah mencari nilai modus pada data tunggal. Hal ini dikarenakan penyajian data kelompok yang disajikan dalam sebuah rentang kelas. Sehingga, nilai modus data kelompok tidak mudah untuk langsung didapat.

Untuk mendapatkan nilai modus data kelompok dapat menggunakan sebuah rumus. Rumus modus data kelompok dapat dilihat seperti persamaan di bawah.

Keterangan:

Tb = tepi bawah kelas modus

d₁ = selisih frekuensi kelas modus dengan frekuensi sebelum kelas modus

d₂ = selisih frekuensi kelas modus dengan frekuensi setelah kelas modus

p = panjang kelas interval

Contoh 1:

 soal dan pembahasan modus pada data kelompok.

Perhatikan gambar diagram batang di bawah!

Modus dari data yang disajikan pada diagram batang di atas adalah ….

A. 46,0
B. 46,5
C. 47,0
D. 49,0
E.  49,5

Pembahasan:

Dari diagram diketahui modus ada pada interval 45 – 49, sehingga Maka nilai Modus (Mo) dari data tersebut adalah:  

Jawaban: B

v MEAN

Rumus Mean (Rata-rata) Data Kelompok

Inti dari menentukan nilai rata-rata dari suatu data kelompok sama dengan mencari nilai rata-rata data tunggal. Idenya adalah menjumlahkan semua data kemudian membagi dengan banyaknyanya data. Hanya saja, karena penyajian data kelompok diberikan dalam bentuk berbeda, maka rumus mencari nilai mean untuk data kelompok sedikit berbeda dengan cara mencari nilai mean pada data tunggal.

Rumus mean data kelompok dinyatakan dalam persamaan di bawah.

Keterangan:

 = rataan hitung dari data kelompok

f_i = frekuensi kelas ke-i

x_i = nilai tengah kelas ke-i

Contoh 1: soal dan pembahasan cara mencari nilai median pada data kelompok.

Perhatikan data pada tabel berikut!

Nilai mean (rata-rata) dari data pada tabel tersebut adalah ….

A.60,75
B.61,75
C.62,75
D.63,75
E.64,75

Pembahasan:

Untuk menentukan rata-rata dari suatu kelompok, kita membutuhkan nilai tengah dari masing-masing kelas. Nilai tengah dari masing-masing kelas dapat diperoleh menggunanan rumus berikut.

Nilai tengah masing-masing kelas adalah sebagai berikut. 

Hasil perkalian nilai tengah masing-masing kelas dan frekuensinya dapat dilihat pada tabel di bawah.

Sehingga

Jadi, nilai mean dari data yang diberikan pada soal adalah 61,75.

Jawaban: B

v KUARTIL, DESIL, DAN PERSENTIL

Mencari Nilai Kuartil Untuk Data Tunggal

Seperti yang telah disebutkan sebelumnya, kuartil membagi data menjadi empat bagian sama banyak. Sehingga terdapat tiga nilai kuartil yang membagi data tersebut. Sebelum membagi data, pastikan bahwa data sudah diurutkan terlebih dahulu. Ilustrasinya dapat dilihat seperti gambar di bawah.

Rumus mencari nilai kuartil untuk data tunggal dibedakan menjadi dua kasus, yaitu untuk jumah data ganjil dan jumlah data genap.

Untuk n ganjil:

Untuk n genap:

Langkah-langkah mencari tiga nilai kuartil data tunggal untuk jumlah data genap adalah sebagai berikut.

1.                        Carilah nilai yang menjadi nilai tengah (median atau Q₂).

2.                        Membagi data di sebelah kiri median menjadi dua bagian yang sama dan menghasilkan kuartil bawah atau Q₁.

3.                        Membagi data di sebelah kanan median menjadi dua bagian sama dan menghasilkan kuartil atas atau Q₃.

Berikutnya adalah ulasan materi tentang desil.

Mencari Nilai Desil Untuk Data Tunggal

Desil adalah cara membagi n data terurut menjadi 10 bagian data yang masing-masing bagian mempunyai jumlah data yang sama. Setiap n data terurut dibagi menjadi 10 bagian, sehingga terdapat 9 nilai desil. Ilustrasi pembagian n data terurut menjadi 10 bagian sama banyak dan letak nilai desilnya dapat dilihat pada gambar di bawah.

Rumus desil dinyatakan dalam persamaan di bawah.

Keterangan:

i = bilangan bulat kurang dari 10 (1, 2, 3, …, 9)
n = banyak data

Mencari Nilai Persentil Untuk Data Tunggal

Persentil diambil dari kata persen, per seratus. Sehingga, persentil merupakan pembagian n data terurut menjadi 100 bagian sama banyak. Dari 100 bagian yang dibagi sama banyak tersebut, dibatasi oleh 99 nilai persentil. Perhatikan ilustrasi pembagian data dan letak nilai persentil seperti gambar di bawah.

Rumus persentil data tunggal di berikan seperti persamaan di bawah.

Keterangan:

i = bilangan bulat kurang dari 100 (1, 2, 3, …, 99)
n = banyak data

Pembahasan selanjutnya adalah rumus kuartil, desil, dan persentil pada data kelompok.

Rumus Kuartil, Desil, dan Persentil Data Kelompok

Seperti halnya data tunggal, data yang telah disajikan menjadi data kelompok juga dapat dicari nilai kuartil, desil, dan persentilnya. Rumus kuartil, desil, dan persentil data kelompok berbeda dengan rumus kuartil, desil, dan pesentil untuk data tunggal. Meskipun begitu, ide dan pengertian kuartil, desil, dan persentil pada data kelompok sama dengan pada data tunggal.

Berikut ini adalah rumus kuartil, desil, dan persentil untuk data kelompok.

Rumus Kuartil Data Kelompok

Terdapat tiga nilai kuartil pada data kelompok, yaitu kuartil bawah, kuartil tengah, dan kuartil atas. Rumus kuartil data kelompok diberikan seperti persamaan di bawah.

Keterangan:

i = 1 untuk kuartil bawah
i = 2 untuk kuartil tengah
i = 3 untuk kuartil atas
Tb = tepi bawah kelas kuartil
n = jumlah seluruh frekuensi
f_k = jumlah frekuensi sebelum kelas kuartil
f_i = frekuensi kelas kuartil
p = panjang kelas interval

Rumus Desil Data Kelompok

Cara mencari nilai desil pada data kelompok dapat menggunakan rumus desil untuk data kelompok yang diberikan di bawah.

Keterangan:

i = bilangan bulat kurang dari 10 (1, 2, 3, … ,9)
Tb = tepi bawah kelas desil
n = jumlah seluruh frekuensi
f_k = jumlah frekuensi sebelum kelas desil
f_i = frekuensi kelas desil
p = panjang kelas interval

Rumus Persentil Data Kelompok

Rumus persentil data kelompok digunakan untuk menentukan nilai persentil dari suatu data kelompok. Rumus tersebut ditunjukkan seperti persamaan di bawah.

Keterangan:

i = bilangan bulat kurang dari 100 (1, 2, 3, … ,99)
Tb = tepi bawah kelas persentil
n = jumlah seluruh frekuensi
f_k = jumlah frekuensi sebelum kelas persentil
f_i = frekuensi kelas persentil
p = panjang kelas interval

Untuk menambah pemahaman sobat idschool tentang materi rumus kuartil, desil, dan persentil akan diberikan contoh soal kuartil, desil, dan persentil beserta cara menyelesaikan menggunakan rumus-rumus yang telah diberikan di atas.

Contoh Soal dan Pembahasan

Contoh Soal Kuartil Data Tunggal

Perhatikan data nilai matematika yang diperoleh sekelompok siswa berikut.

Nilai kuartil bawah pada data yang diberikan di atas adalah ….

A. 49
B. 52
C. 55
D. 59
E. 68

Pembahasan:

Langkah pertama yang dilakukan adalah mengurutkan data dan mencari nilai mediannya. Data yang telah diurutkan dan nilai median dapat dilihat pada gambar di bawah.

Selanjutnya, mencari nilai kuartil bawahnya , diperoleh dari nilai tengah dari data terurut di sebelah kiri median.

Jadi, nilai kuartil bawahnya adalah 59

Jawaban: D

DAFTAR PUSTAKA

v https://idschool.net/sma/rumus-kuartil-desil-dan-persentil/

v https://www.rumusstatistik.com/2013/08/mean-median-modus-data-berkelompok.html