Simulasi Visual Penerapan Metode Breadth First Search (BFS) Pada Penyelesaian Masalah State dan Space (Sampel kasus: Farmer’s Problem) Ilka Zufria[1]
[email protected] Fak. Sains dan Teknologi UIN Sumatera Utara Medan & Irma Indah Sari[2]
ABSTRACT State represents the state at one time or decryption system configuration. State and space is all possible state and is usually described as a network with vertex. State and edge are possible changes. State space representation and allows a formal definition of a problem as the problem by changing the status by using a set of operators (rule). The software will find the shortest solution (Shortest path) of a problem, because the software uses the first method extends search (Breadth First Search Method) to find a solution. Farmer's Problem is used as a sample for solved the problem which many state to be served and worked in the same time and the state can normally operated. In application, this simulation also illustrates how to solved the multitasking on an operating system.
Keywords : State, Space, Breadth First Search Method and Farmer’s Problem. 1.
PENDAHULUAN
State merupakan representasi suatu keadaan pada suatu saat ataupun dekripsi konfigurasi sistem. State and space adalah semua state yang mungkin dan biasanya digambarkan sebagai jaringan dengan verteks. State dan edge merupakan perubahan yang mungkin. Representasi state and space memungkinkan definisi formal suatu masalah sebagai persoalan dengan mengubah status dengan menggunakan sekumpulan operator (rule) dan juga mendefinisikan masalah sebagai search yaitu mencari lintasan di dalam state and space dari initial state ke goal state dalam hal ini menggunakan pendekatan metode Breadth First Search dimana nantinya perangkat lunak ini menggunakan metode pencarian melebar pertama. Salah satu masalah yang akan diangkat state and space ini adalah Farmer’s problem (masalah petani) yang dapat didekripsikan sebagai berikut, seorang petani akan menyeberangkan seekor kambing, seekor serigala dan sayur-sayuran dengan sebuah rakit yang melalui sungai. Rakit hanya mampu memuat petani dan satu penumpang yang lain
(kambing, serigala atau sayur-sayuran). Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala dan hanya petani yang dapat mengemudikan rakit, salah satu yang juga diangkat dalam tulisan ini adalah bagian Sistem Operasi mengenai Multitasking. Multitasking sendiri merupakan suatu kemampuan yang memungkinkan seseorang pemakai menjalankan sejumlah program dalam waktu yang sama. Misalkan suatu data akan dipindahkan dari memori ke disk dan sebaliknya. Sistem multitasking juga disebut dengan sistem komputasi interaktif, dimana sistem komputer menyediakan komunikasi on-line antara user dengan sistem. User memberikan instruksi pada sistem operasi atau program secara langsung dan menerima respon segera. Perangkat input berupa keyboard dan perangkat output berupa display screen, seperti cathode-ray tube (CRT) atau monitor. Bila sistem operasi selesai mengeksekusi satu perintah, maka sistem akan mencari pernyataan berikutnya dari user melalui
keyboard. Sistem menyediakan editor interaktif untuk menulis program dan sistem debug untuk membantu melakukan debugging program. Agar user dapat mengakses data dan kode program dengan nyaman, sistem menyediakan sistem file online. Sistem multitaskng juga disebut sistem time sharing. Masalah ini akan dimodifikasi sehingga dapat digunakan untuk menyelesaikan semua persoalan yang hampir mirip dengan masalah ini. Masalah ini dapat diselesaikan dengan menggunakan tahapantahapan berikut ini. Tahapan pertama dimulai dari identifikasi ruang keadaan (state and space) yaitu dengan mendeklarasikan permasalahan ini dengan menentukan variabel-variabel yang terdapat dalam masalah ini. Misalkan variabel yang terdapat dalam Metode Farmer’s problem adalah petani, kambing, serigala dan sayur-sayuran. Kemudian, tentukan aturan-aturan yang terdapat dalam masalah , dalam Farmer’s problem terdapat aturan bahwa serigala akan memakan kambing apabila petani tidak berada di tempat, kambing akan memakan sayuran apabila petani tidak berada di tempat, dan hanya petani yang dapat mengemudikan rakit. Kondisi awal adalah semua variabel masih terdapat pada tepi sungai kiri dan kondisi tujuan adalah semua variabel berada pada tepi sungai sebelah kanan. Masalah diselesaikan dengan menggunakan bantuan pohon pelacakan. Kondisi-kondisi (state) yang mungkin digambarkan dalam struktur pohon dengan dimulai dari kondisi awal (start state) sebagai akar dari pohon. Proses dilanjutkan dengan menggambarkan kondisi (state) berikutnya yang dapat dibentuk dari state tersebut. Proses berlanjut hingga didapatkan kondisi tujuan (goal state) atau tidak terdapat kondisi baru yang dapat dikembangkan.
2.
1. 2.
3.
Breadth First Search pada Farmer’s Problem Illustrasi Farmer’s Problem dari permasalahan ini adalah sebagai berikut, seorang petani akan menyeberangkan seekor kambing, seekor serigala dan sayur-sayuran dengan sebuah rakit melalui sungai. Rakit hanya bisa memuat petani dan satu penumpang yang lain (kambing, serigala atau sayur-sayuran). Jika ditinggalkan oleh petani tersebut, maka sayur-sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala. Tabel variabel dan aturan dapat dilihat pada tabel 1 dan tabel 2. Tabel 1. Tabel Variabel Farmer’s Problem Variabel ID
Nama Variabel
Bisa mengemudikan rakit (Driver)
K
Kambing
Tidak
P
Petani
Ya
SR
Serigala
Tidak
SY
Sayur-sayuran
Tidak
Tabel 2. Tabel Aturan Farmer’s Problem No.
Rule / Aturan
1
Kambing akan memakan sayur-sayuran apabila Petani tidak berada di tempat.
2
Serigala akan memakan Kambing apabila Petani tidak berada di tempat.
PEMBAHASAN
Lingkungan Perangkat Keras Perangkat keras yang digunakan adalah Laptop dengan spesifikasi HP Seri 430 INTeL®Core ™ M380 @2,53Ghz (4 CPUs), 4 GB RAM dan hardisk 320 GB. Perangkat keras ini digunakan untuk merancang dan menjalankan simulasi dengan software-software yang digunakan. Lingkungan Perangkat Lunak Adapun perangkat lunak yang digunakan diantaranya adalah:
Windows 7 ultimate sebagai sistem operasi yang digunakan. Microsoft Visual Basic 6.0 sebagai software untuk perancangan aplikasi simulasi visual masalah state and space.. Microsoft Access 2007 sebagai software untuk pembuatan database.
Dari variabel dan aturan yang terdapat pada Farmer’s Problem, kita dapat menyimpulkan aksi-aksi apa saja yang dapat dilakukan dengan tetap mematuhi aturanaturan yang ada. Aksi-aksi yang dapat dilakukan dapat dilihat pada tabel 3.
Tabel 3. Tabel Aksi-aksi yang dapat terjadi pada Farmer’s Problem Aksi ke-
Aturan
1
Petani dan kambing menyeberang.
2
Petani dan serigala menyeberang.
3
Petani dan sayur-sayuran menyeberang.
4
Petani dan kambing kembali.
5
Petani dan serigala kembali.
6
Petani dan sayur-sayuran kembali.
7
Petani kembali.
tidak ada cabang yang dapat dikembangkan lagi dan ternyata belum ditemukan solusi, maka permasalahan yang sedang diselesaikan tidak memiliki solusi. Struktur pohon pelacakan untuk mencari solusi pada Farmer’s Problem dapat dilihat pada gambar 1.
Setiap keadaan dari Farmer’s Problem dapat direpresentasikan dengan (kambing, petani, serigala, sayur-sayuran) dan posisi rakit. Keadaan awal dan keadaan tujuan dapat direpresentasikan sebagai berikut: 1.
Keadaan awal (start state): a. Daerah kiri = (1,1,1,1). b. Daerah kanan = (0,0,0,0) c. Posisi rakit berada di kiri. Artinya, terdapat kambing, petani, serigala dan sayur-sayuran di daerah kiri.
2.
Keadaan tujuan (goal state): a. Daerah kiri = (0,0,0,0). b. Daerah kanan = (1,1,1,1) c. Posisi rakit berada di kanan. Artinya, terdapat kambing, petani, serigala dan sayur-sayuran di daerah kanan.
Pencarian solusi dari permasalahan di atas adalah dengan menggunakan bantuan pohon pelacakan. Akar dari pohon merupakan keadaan awal. Akar pohon kemudian membentuk cabang-cabang baru dengan melakukan semua aksi-aksi yang dapat terjadi pada keadaan awal. Keadaan-keadaan baru yang dihasilkan merupakan cabang baru dari pohon. Proses pengembangan dan pencarian dilanjutkan dengan membentuk keadaan baru (cabang baru) dari cabangcabang yang sudah ada hingga didapatkan solusi. Proses pembentukan keadaan baru juga melakukan prosedur pengecekan apakah keadaan tersebut sudah pernah dibentuk sebelumnya pada pohon. Apabila sudah ada, maka cabang baru tidak dibentuk dan apabila tidak, maka cabang baru dibentuk. Apabila
Gambar 1. Struktur pohon pelacakan untuk Farmer’s Problem
Dari struktur pohon pelacakan yang dikembangkan pada gambar 1, didapatkan solusi seperti terlihat pada tabel 4.
Tabel 4. Solusi Farmer’s Problem Daerah Kiri
Aksi
Posisi Rakit
Daerah Kanan
KIRI
(0,0,0,0)
KANAN
(1,1,0,0)
KIRI
(1,0,0,0)
ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala.
(1,1,1,1)
-
(0,0,1,1)
Aksi ke-1 (Petani dan kambing menyeberang)
(0,1,1,1)
Aksi ke-7 (Petani kembali)
(0,0,0,1)
Aksi ke-2 (Petani dan serigala menyeberang)
KANAN
(1,1,1,0)
Begitu pula jika kambing ditinggalkan dengan sayuranan, maka sayuran akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau sayuran dimakan. Masalah ini dapat dimodelkan dengan memperhatikan mereka yang menempati setiap sisi sungai. Misalnya kita akan menggunakan kombinasi pada setiap sisi sungai sebagai keadaan/state yang mungkin.
(1,1,0,1)
Aksi ke-4 (Petani dan kambing kembali)
KIRI
(0,0,1,0)
Terdapat 16 kombinasi state untuk Petani (P), serigala (SR), kambing (K) dan sayuran ( SY) yaitu :
(1,0,0,0)
Aksi ke-3 (Petani dan sayuran menyeberang)
KANAN
(0,1,1,1)
(1,1,0,0)
Aksi ke-7 (Petani kembali)
KIRI
(0,0,1,1)
(0,0,0,0)
Aksi ke-1 (Petani dan kambing menyeberang)
KANAN
(1,1,1,1)
Pencarian solusi pada struktur pohon pelacakan menggunakan metode pencarian melebar pertama (breadth-first search), sehingga solusi yang didapatkan adalah merupakan solusi terpendek. Finite State Automata Farmer’s Problem Finite State Automata (FSA) adalah suatu mesin abstrak yang digunakan untuk merepresentasikan penyelesaian suatu persoalan dari suatu sistem diskrit. Sebagai sebuah mesin maka FSA akan bekerja jika diberikan suatu masukan. Hasil proses adalah suatu nilaia kebenaran diterima atau tidaknya masukan yang diberikan. FSA memiliki state yang banyaknya berhingga, jika diberikan suatu simbol input maka dapat terjadi suatu perpindahan dari sebuah state ke state lainnya. Perubahan state tersebut dinyatakan oleh suatu simbol transisi. Mekanisme FSA tidak memiliki memori sehingga selalu mendasarkan prosesnya pada posisi state “saat ini”. Misalnya pada mekanisme kontrol pada sebuah lift, selalu didasari pada posisi lift saat itu pada suatu lantai, pergerakan ke atas atau ke bawah dan sekumpulan permintaan yang belum terpenuhi. Finite State Automata merupakan suatu tool yang berguna untuk merancang sistem nyata. Sebagai contoh pada penyelesaian kasus: seorang petani dengan seekor serigala, kambing dan sayuranan berada pada suatu sisi sungai. Tersedianya hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau sayuranan. Petani tersebut harus menyeberangkan
Sisi Kiri PSRKSY SR.SY SR.K KSY PSR.SY PSRK PKSY PK PSY PSR K SY SR SRKSR P Ø
Tabel 5. Kombinasi State Sisi Kanan Simbol State Ø PSRKSY – Ø PK SR.SY – PK P.SY SR.K – P.SR PSR KSY– PSR K PSR.SY – K SY PSRK – SY SR PKSY – SR SR.SY PK – SS SRK PSY – SRK KSR PSR – KSY PSR.SY K – PSR.SY PSRK SY – PSRK PKSY SR – PKSY P SRKSY – P SRKSY P – SRKSY PSRKSY Ø - PSRKSY
Dari 16 kombinasi state tersebut, hanya 10 state yang mungkin, yaitu : Tabel 6. Kombinasi State Sisi Kiri Sisi Kanan Simbol State PSRKSY Ø PSRKSY – Ø SR.SY PK SR.SY – PK PSR.SY K PSR.SY – K PSRK SY PSRK – SY PKSY SR PKSY – SR PK SR.SY PK – SR.SY K PSR.SY K – PSR.SY SY PSRK SY – PSRK SR PKSY S R– PKSY Ø PSRKSY Ø – PSRKSY
Berdasarkan kemungkinan state tersebut, dapat digambarkan diagram transisi dari persoalan tersebut dengan mesin automata, sbb :
PKSRS Y- Ø
SRSY – PK
PSRSY –K
SY – PKSR
SR PKSY
PKSR – SY
PKSY SR
KPSRSY
Secara formal FSA didefinisikan dengan 5 tuple : M = (Q, ∑, δ, S, F), dimana : Q : himpunan state/kedudukan ∑ : himpunan table input ∂ : fungsi transisi S : State awal (initial state) F : himpunan state akhir (Final State) Untuk kasus petani d engan bawaanya, dapat didefinisikan FSA sebagai berikut : Q = { PSRKSY–Ø, SR.SY–PK, PSR.SY–K, PSRK– SY, PKSY–SR, PK–SR.SY, K–PSR.SY, SY– PSRK, SR.SY–PKR, Ø–PSRKSY} ∑ = {P, PK, PSY, PSR } Δ = Tabel 7. Definisi FSA P PK PSY PSR PSRKSY – Ø SR.SY – PK PSR.SY – K PSRK – SY
SR.SY – PK PSR.SY –K SR.SY – PK -
-
-
-
PSRKSY – Ø -
-
-
SR – PKSY -
SY – PKSR K– PSR.SY -
SR – PKSY
PKSY – SR
-
SY – PKSR
PK – SR.SY K– PSR.SY SY – PSRK
K– PSR.SY PK – SR.SY -
Ø– PSRKSY PKSY – SR
SR – PKSY
-
PKSR – SY
Ø– PSRKSY
-
PK – SR.SY
K– PSR.SY
PKSY – SY PSR.SY –K -
PKSR – SY PSR.SY –K -
PK SRSY
S = PSRKSY – Ø F = { Ø – PSRKSY }
ØPKSRS
Deterministic Finite Automata ( DFA ) A deterministic finite automaton (DFA) M = (Q, ∑, δ , S, F), dimana :
Gambar 2. Finite State Automata (FSA) Farmer’s Problem
Q : himpunan state/kedudukan ∑ : himpunan 5able5 input ∂ : fungsi transisi, dimana ∂ Q x ∑ Q
Pada diagram diatas, arti bentuk-bentuk adalah sebagai berikut : a. b. c. d. e. f.
Lingkaran merepresentasikan kedudukan (state). Label pada lingkaran adalah nama state tersebut. Busur menyatakan transisi. Label pada busur adalah masukan / input Lingkaran didahului dengan sebuah busur tanpa label adalah state awal Lingkaran ganda menyatakan state akhir (final)
S : State awal (initial state) F : himpunan state akhir (Final State) Sebagai contoh mesin otomata berikut: B = ({q0, q1, q2,},{0,1}, δB, q0,{q2,}) Dimana δB = {((q0, 0), q1), (( q0, 1), q0), (( q1, 0), q1), (( q1, 1), q2), (( q2, 0), q2), (( q2, 1), q2)
FSA tersebut dikatakan DFA, jika selalu memenuhi tabel transisi berikut :
State Diagram
0 q0 q0 q0
q0 q0 q0
1 q0 q0 q0
H
b
ɑ
ɑ P
ɑ Tabel mewakili fungsi δ, yaitu untuk menemukan nilai δ (q,x) kita harus melihat pada baris q label dan kolom berlabel x. Keadaan awal ditandai oleh semua negara dan akhir ditandai dengan. Namun lain, optik lebih menginspirasi, alternatif adalah diagram transisi:
b ɑ
S
F
b b
Namun lain, optik lebih menginspirasi, alternatif adalah diagram transisi:
b
Q
0
1
ɑ q0 0
b
G
Tabel 8. Transisi
q1
0
q2
ɑ
b
ɑ
ɑ
b
ɑ
ɑ
b
0.1
1
Gambar 4. State Diagram
Gambar 3. Diagram Transisi Ada panah ke keadaan awal dan semua negara akhir ditandai dengan cincin ganda. Jika δ(q,x) kemudian ada panah dari state q ke q1 yang diberi label x. Penulisan ∑* untuk himpunan kata-kata (yaitu urutan) selama alphabet ∑. Ini termasuk kata kosong yang ditulis €. {0,1}* = {€, 0,1,00,01,10,11,000,…} Gambar 5. NDFA State Diagram
Non-Deterministic Finite Automata (NDFA) Sebuah non-deterministik finite automaton adalah 5tuple M = (Q,∑,δ, q0,F) dimana. Q : State awal ∑ : Alpabet q0 € Q : Keadaan Awal State F ʗ Q : State akhir δ : Fungsi Transisi δ : Q x {∑ U €} P (Q) (€ string kosong. P (Q) adalah himpunan semua himpunan bagian dari Q.
Antar Muka Simulasi Visual dengan Metode Breadth First Search pada Farmer’s Problem Pada langkah awal ini terdapat tampilan gambaran Simulasi Farmer’s Problem, terdapat tabel berupa tabel Variabel, tabel Rule dan solusi penyelesaian. Solusi yang didapatkan dari permasalahan menyeberang sungai (Farmer’s Problem) adalah sebagai berikut bisa kita lihat gambar langkah 0 hingga selesai (langkah-7)
Gambar 9. Langkah-3( Petani dan Serigala menyeberang ke kanan)
Gambar 6. Langkah-0 (Keadaan Awal)
4. Langkah-4 ( Petani dan kambing menyeberang) 1.
Langkah-1 ( Petani dan kambing menyeberang ke kanan).
Gambar 10. Langkah-4( Petani dan kambing menyeberang ke kiri) Gambar 7. Langkah-1( Petani dan kambing menyeberang ke kanan) 2.
5.
Langkah-5 /(Petani dan Sayuran menyeberang ke kanan).
Langkah-2 (Petani menyeberang ke kiri).
Gambar 11. Langkah-5(Petani dan Sayuran menyeberang ke kanan) Gambar 8. Langkah-2 (Petani menyeberang ke kiri) 3. Langkah-3 ( Petani dan Serigala menyeberang ke kanan).
6.
Langkah-6 (Petani menyeberang ke kiri).
3.
Pencarian tidak selalu menghasilkan solusi. Bila setelah semua keadaan pada pohon pelacakan diperiksa dan dikembangkan dan solusi belum ditemukan, maka permasalahan tidak memiliki solusi.
4. DAFTAR PUSTAKA
Gambar 12. Langkah-6 (Petani menyeberang ke kiri) 7.
Langkah-7 (Petani dan Kambing menyeberang ke kanan).
Gambar 13. Langkah-7 (Petani dan Kambing menyeberang ke kanan)
3. PENUTUP 1.
2.
Perangkat lunak akan menemukan solusi terpendek (shortest path) dari suatu permasalahan, karena perangkat lunak menggunakan metode pencarian melebar pertama (Breadth First Search) untuk mencari solusi. Hal ini disimulasikan dengan Farmer’s Problem ini yang penerapan contohnya juga pada proses kasus multitasking. Perangkat lunak menampilkan semua pergerakan (secara bertahap) dari solusi yang didapatkan, sehingga solusi akan terlihat lebih jelas.
[1]. Kusumadewi, S (2003), Artificial Intelligence (Teknik dan Aplikasinya), Penerbit: Graha Ilmu, Bogor. [2]. Desiani, A., dan Arhami, M (2006), Konsep Kecerdasan Buatan, Penerbit: Andi, Yogyakarta. [3]. Arhani, M (2005), Konsep Dasar Sistem Pakar, Penerbit: Andi, Yogyakarta. [4]. Ramadhan, A (2004), 36 Jam Belajar Komputer Visual Basic 6.0, Penerbit: PT.Elexmedia Komputindo, Jakarta. [5]. Wikipedia (2012), Breadth First Search, from: http://en.wikipedia.org/wiki/Breadthfirst_search, 3 Juli 2013. [6]. Britton, Jill (2013), The Wolf, The Goat and The Cabbage, from: http://britton.disted.comosun.bc.ca/jbwolfgoa t.htm, 3 Juli 2013. [7]. Wikipedia (2013), Pengertian Tugas Ganda, from:http://id.wikipedia.org/wiki/Tugas_gan da, 10 Juli 2013. [8]. Smitdev (2009), Pengertian Multitasking, from:http://www.smitdev.com/posts/multitas king341.php, 10 Juli 2013. [9]. Poole David, Alan Mackworth (2010), State Spaces, From: http://artint.info/html/ArtInt_48.html, 10 Juli 2013. [10]. Wikipedia (2013), from: http://en.wikipedia.org/wiki/State_space_sear ch, 10 Juli 2013.
