BAB 2 TINJAUAN PUSTAKA

BAB 2

TINJAUAN PUSTAKA

2.1 Permainan

Di zaman sekarang, terkadang sebagian manusia lebih memilih untuk bermain di kehidupan maya dibandingkan di kehidupan nyata. Dan mereka memilih sebagai dunia baru karena memang lebih tentram juga lebih damai walau kadang ada keributan. Dunia permainan layaknya dunia maya yang kita sering online dan chatting. Namun dunia permainan dapat membuat kita seakan menjadi nyata. Karena kita dapat membentuk karakter yang kita inginkan dan kita juga dapat menjadi karakter yang kita inginkan. Dimana di dalam dunia ini kita membentuk karakter layaknya yang ada di dalam diri kita dan terkadang kita mencerminkan apa yang ada dalam diri kita dalam dunia ini. Sehingga kita tuangkan diri kita ini ke dunia permainan tersebut.

Andaikan dibandingkan dengan dunia nyata, sakit hati yang dicerminkan akibat dunia permainan ini terasa lebih menyakitkan. Dan imbasnya dapat ke dunia nyata, sehingga merubah pola pikir kita menjadi tidak layaknya biasanya.

2.1.1 Sejarah Permainan

Sebenarnya di zaman peradaban manusia telah mengenal dan memainkan permainan. Di sahara ditemukan sebuah papan permainan terbuat dari batu yang berusia ±5000 tahun. Menurut David Fox dan Roman Verhosek (2002), permainan Go, yang popular di Negara-negara oriental, telah ada sejak 2000 BC. Bahkan permainan mirip Backgamon dicatat pada script romawi kuno.

Universitas Sumatera Utara

Pada tahun 1952, seorang mahasiswa Universitas Cambridge bernama A.S Gouglas membuat permainan OXO (tic tac toe) dalam versi grafik. Permainan ini ia kembangkan ketika hendak mendemonstrasikan tesisnya tentang interaksi antara manusia dan komputer.

Memasuki era modern, pada tahun 1966 permainan digital pertama kali dibuat oleh Ralph Baer bersama timnya yang berjumlah 500 orang yang terdiri dari insinyur dan teknisi dan didanai oleh Pentagon. Permainan ini hanya dapat dimainkan dengan komputer seharga US$40.000. Unsur edukasi menjadi tujuan utama dalam permainan ini. Permainan dalam bentuk permainan antara papan dan bola tersebut diperuntukkan untuk membantu pasukan belajar strategi dan melatih kemampuan refleks pemainnya.

Pada tahun 1972, muncul permainan baru yang disebut Permainan Arcade, yang dipelopori oleh Nolan Brushnel dengan permainannya berjudul Pong. Mesin untuk memainkan permainan ini disebut mesin Arcade. Pemain yang ingin bermain diharuskan untuk memasukkan koin kedalam mesin. Pada hari kedua mesin ini diletakkan pada suatu bar, orang-orang mengantri untuk memainkan permainan Pong.

Tidak mau tertinggal dengan sistem Arcade, sistem konsol seperti Magnavox Odyssey, Atari 2006, Mattel Intelvision, Calleco Vision dan Nintendo Entertaiment Sistem menciptakan permainan yang dapat dimainkan di rumah. Permainan yang paling menghebohkan orang-orang dengan tampilan grafik dan permainan play yang luar biasa pada sistem konsol tersebut adalah Super Mario Brothers yang diciptakan oleh Nintendo.

Pada perkembangannya, permainan komputer berkembang dengan pesatnya seiring perkembangan perangkat keras yang mendukung. Hal ini dibuktikan dengan program permainan yang lebih kompleks dan tampilan grafik tiga dimensi.


2.1.2 Pengertian Permainan

Sosiolog Perancis Roger Caillois, dalam bukunya Les jeux et les Hommes (Games and Man), yang mendefinisikan permainan sebagai suatu kegiatan yang harus memiliki karakteristik berikut: 1. Menyenangkan: kegiatan yang dipilih pengguna untuk menjadikan dirinya karakter. 2. Terpisah: dibatasi dalam waktu dan tempat. 3. Kepasti: hasil kegiatan ini adalah tak terduga. 4. Partisipasi-produktif: tidak mencapai sesuatu tujuan yang berguna. 5. Diatur oleh aturan: kegiatan memiliki aturan yang berbeda dari kehidupan seharihari. 6. Fiktif: jika disertai kesadaran realitas yang berbeda.

Desainer Chris Crawford berusaha untuk mendefinisikan istilah permainan dengan menggunakan pembagian, diantaranya adalah: 1. Ekspresi kreatif adalah seni yang dibuat untuk kecantikan sendiri, dan hiburan jika dibuat untuk uang. (Ini adalah definisi yang paling kaku. Crawford mengakui bahwa ia sering memilih jalan yang kreatif atas kebijaksanaan bisnis konvensional, dimana hanya salah satu dari 13 game adalah sekuel game.) 2. Hiburan adalah sebuah mainan yang interaktif. Film dan buku-buku dikutip sebagai contoh hiburan non-interaktif. 3. Jika tidak ada tujuan yang terkait dengan permainan, itu adalah mainan. Cacatan dari Crawford bahwa definisinya menyatakan: a. Mainan dapat menjadi elemen permainan jika para pemain membuat aturannya sendiri b. The Sims dan SimCity adalah mainan, bukan permainan c. Jika memiliki tujuan, mainan adalah tantangan. 4. Jika tantangan tidak memiliki agen aktif terhadap dengan siapa anda bersaing, ini adalah teka-teki, jika ada satu, itu adalah konflik. Crawford mengakui bahwa ini adalah tes subjektif dari video game. Dengan kecerdasan buatan algoritma bisa dimainkan sebagai teka-teki, ini termasuk pola yang digunakan untuk menghindari dari permainan Pac-Man.


5. Akhirnya, jika para pemain hanya dapat mengalahkan lawan, tetapi tidak menyerang dan hanya mengganggu kinerja mereka sehingga terjadi konflik, konflik disini merupakan sebuah kompetisi. Kompetisi termasuk kecepatan dan ketangkasan dari tantangan seperti balapan dan skating gambar. Namun, Jika serangan diizinkan, kemudian konflik memenuhi syarat sebagai permainan.

Definisi Crawford demikian dapat diterjemahkan sebagai suatu kegiatan, interaktif berorientasi pada tujuan, dengan bahan aktif untuk bermain melawan, di mana pemain termasuk agen aktif dapat mengganggu satu sama lain.

2.1.3 Klasifikasi Permainan

Gameplay merupakan alat dan aturan-aturan yang

mendefinisikan konteks

keseluruhan permainan sehingga pada saat gilirannya, menghasilkan keterampilan, strategi, dan kesempatan.

Berdasarkan media permainannya, permainan dapat dikelompokkan menjadi beberapa bagian, yaitu:

1. Papan Permainan Papan permainan merupakan permainan yang menggunakan sebuah media papan sebagai alat atau tempat untuk berinteraksi dan melakukan sebuah permainan . Biasanya permainan ini dilakukan dengan menggunakan strategi untuk memenangi permainan tersebut. Contohnya: Catur.

2. Permainan Kartu Permainan kartu merupakan permainan yang menggunakan satu set kartu sebagai alat utama permainan. Permainan ini biasanya diawali dengan pengacakan kartu sehingga membutuhkan kesempatan dan keberuntungan untuk memenangi permainan ini. Contohnya: permainan kartu Uno, permainan Poker, permainan Spider Solitare dan sebagainya.


3. Permainan Dadu Permainan dadu merupakan permainan yang menggunakan dadu sebagai elemen utama permainan. Permainan dilakukan dengan cara mengacak angka dadu kemudian angka dadu inilah yang menjadi dampak kemungkinan besar kemenangan permainan ini. Contohnya: Ludo, dadu Poker dan sebagainya.

4. Permainan Domino dan Berubin Permainan Domino dan Berubin merupakan permainan yang menggunakan kartu berbentuk ubin sebagai alat permainannya. Permainan ini mirip dengan permainan kartu. Contohnya: Domino dan Mahjong.

5. Permainan Bergambar Permainan Bergambar merupakan suatu permainan yang memerlukan media kertas untuk menggambar arena permainan dan pensil untuk menulis langkah permainan tersebut. Contohnya, Scrabble, Tic-tac-toe, Sudoku dan sebagainya.

2.2 Magic Square Sebuah magic square N x N adalah array yang berisi bilangan bulat dari 1 sampai n2 diatur sedemikian rupa sehingga setiap baris, setiap kolom, dan kepala dua Diagonal-diagonal memiliki jumlah yang sama. Untuk setiap n > 2, ada banyak perbedaan dari magic square yang berurutan.

Gambar 2.1 Magic Square 3x3


2.2.1 Karakteristik Magic Square

Sebuah magic square terdiri dari serangkaian nomor jika diatur di papan permainannya, dimana jumlah setiap baris dan kolom dan kedua sudut Diagonaldiagonal harus memiliki jumlah yang sama yang mungkin disebut penjumlahan (S). Setiap pengaturan persegi dari bilangan yang memenuhi kondisi ini benar, maka dapat disebut magic square.

2.2.2 Metode Magic Square

Menurut W.S. Andrews, dengan metode De La, Sebuah magic square yang terdiri dari 4 x 4 dapat dibangun sebagai berikut: 1. Isi kolom paling sudut secara diagonal dari persegi 4 x 4 dengan angka 1 sampai 4 secara berurutan, mulai dari sudut atas dan bawah sebelah kiri.

Gambar 2.2 Magic Square dengan nilai berbentuk diagonal

2. Isi sel kosong yang tersisa dengan jumlah yang hilang dari seri 1 -- 4 sehingga jumlah setiap kolom tegak lurus dan horizontal sama.

Gambar 2.3 Magic Square yang sudah berisi dengan nilai


3. Transpose langkah no.2 yang telah menjadi bentuk matriks

Gambar 2.4 Magic Square yang sudah di Transpose

4. Bentuk bilangan baru lagi dimana hasilnya akan habis bila dibagi dengan 2 pada gambar 2.5 dan transpose pada gambar 2.6, lalu gambar 2.3 dan gambar 2.5 disubstitusikan sehingga menjadi yang utama. Dan hasilnya akan menjadi persegi terkait dari 4 x 4 ditunjukkan pada gambar 2.7. Setelah semuanya selesai maka gambar 2.7 transpose juga sehingga hasil pada gambar 2.8 dan nilai yang terjadi tidak akan pernah sama.

Gambar 2.5 Magic Square bilangan habis di bagi 2

Gambar 2.6 Magic Square Transpose gambar 2.5

Gambar 2.7 Magic Square dari gambar 2.3 dan 2.5

Gambar 2.8 Magic Square Transpose gambar 2.7


2.2.2.1 Magic Square Untuk Ordo Ganjil

Square dari 3 x 3 ditunjukkan pada gambar 2.1. Yang meliputi agregasi angka terkecil yang mampu melakukan pengaturan pada magic square, dan juga pengaturan hanya mungkin terjadi dari sembilan nomor yang berbeda. Akan terlihat bahwa jumlah masing-masing dari tiga vertikal, tiga kolom horizontal dan diagonal dua sudut di alun-alun ini adalah 15, sehingga dapat membuat dalam semua delapan kolom yang memiliki total juga, dimana jumlah dari dua nomor yang berbeda sudah kosong , yang merupakan dua kali nomor pusat, atau n2 + 1.

Magic square selanjutnya adalah 5 x 5, dan terdapat berbagai pengaturan besar dari dua puluh lima nomor, yang akan menampilkan hasil magic juga, setiap pengaturan sebagai produksi dari metode konstruktif yang berbeda. Gambar 2.10 berikut menggambarkan salah satu pengaturan dan paling terkenal dari persegi ini. Jumlah dari masing-masing kelima horizontal, kelima kolom vertikal dan diagonal dua sudut adalah 65, dan jumlah dari dua nomor yang diametris berjarak sama dari nomor pusat, adalah 26 atau dua kali nomor pusat.



Mengacu pada gambar 2.10, maka akan terlihat bahwa square dimulai dengan menulis kesatuan di tengah sel baris atas, dimana nomor secara berturut-turut melanjutkan diagonal dari arah tangan kanan. Menggunakan konsep silinder yang horisontal, dan keduanya akan terletak di baris bawah, diikuti dengan tiga di atas sel di sebelah kanan. Di sini pembentukan silinder secara vertikal yang dikandungnya, sel atas berikutnya dimana empat sudah tertera, maka dilanjutkan yang kelima secara


lebih lanjut di sini diblokir oleh kesatuan yang sudah menempati sel atas berikutnya secara diagonal.

Ketika pemblokan terjadi sehingga dalam jarak reguler (dimana di setiap nomor lima di sebuah square 5 x 5) dengan nomor berikutnya, dalam hal ini harus ditulis dalam sel secara vertikal di bawah dan terakhir diisi, sehingga enam ditulis dalam sel di bawah lima, dan tangan kanan secara diagonal agar dilanjutkan dalam sel ditempati oleh tujuh dan delapan. Di sini silinder horizontal dibayangkan, menunjukkan lokasi dari sembilan, maka konsepsi dari silinder vertikal akan menunjukkan lokasi sepuluh, pengembangan reguler lebih lanjut di sini sekali lagi diblokir oleh enam angka, jadi sebelas adalah tertulis di bawah sepuluh dan diagonal agar terus lanjut adalah lima belas. Sebuah gambaran dari kombinasi silinder vertikal dan horizontal di sini akan menunjukkan bahwa kemajuan diagonal lebih lanjut diblokir oleh sebelas, jadi enamabelas adalah tertulis di bawah limabelas. silinder vertikal kemudian akan menunjukkan sel di mana tujuhbelas harus terletak, dan silinder horisontal akan menampilkan sel berikutnya secara diagonal ke atas ke kanan yang akan ditempati oleh delapanbelas, dan seterusnya sampai jumlah akhir dua lima sudah tercapai dan square selesai.

Prinsip-prinsip umum yang mengatur pembentukkan magic square dengan metode ini, sekarang bisa dirumuskan.

1. Sel pusat di muat persegi selalu berisi nomor tengah serangkaian nomor yang digunakan, misalnya, nomor yang sama dengan satu setengah jumlah pertama dan terakhir nomor seri, atau n2 + 1.

2. Tidak ada magic square yang terkait sehingga dapat dimulai dari sel pusatnya, tapi mungkin bisa dimulai dari semua sel yang lain dari pusat. 3. Dengan pengecualian khusus tertentu yang akan disebut nanti, magic square aneh mungkin dibangun oleh salah satu tangan kanan atau kiri urutan diagonal, atau oleh sejumlah gerakan asing yang disebut itu, variasi dalam semua kasus dengan keberangkatan berkala dan terdefinisi dengan baik dari jarak normal. Arah dan


dimensi ini dimulai dari jarak normal, atau "awal bergerak" karena mungkin akan disebut yang diatur oleh jarak relatif dari sel yang ditempati oleh angka pertama dan terakhir dari seri ini, dan dapat ditentukan sebagai berikut: “Tempatkan nomor pertama dari seri dalam sel yang diinginkan (kecuali pusat satu) dan angka terakhir dari seri di sel yang diametris berlawanan dengan sel yang berisi nomor pertama. Jarak relatif antara sel yang berisi nomor terakhir dari seri dan sel yang berisi nomor pertama dari seri maka harus diulang setiap kali blok terjadi dalam perkembangan biasa.”

2.2.2.2 Magic Square Untuk Ordo Genap

Angka dalam kolom dua diagonal dalam magic square dapat ditentukan dengan menulis jumlah dari bilangan aritmatika dalam barisan horizontal, dimulai dengan nomor pertama di sel tangan kiri baris atas dan menulis baris demi baris seperti di buku W. S Andrew yaitu “Magic Squares and Cubes”, yang diakhiri dengan nomor terakhir di sel sebelah kanan garis bawah. Nomor-nomor kemudian ditemukan dalam dua kolom diagonal dalam magic square, tetapi posisi dari nomor-nomor lain pada umumnya harus diubah.

Gambar 2.11 Matriks tak beraturan

Gambar 2.12 Matriks beraturan

Kuadrat terkecil dari square yang dapat dibangun adalah 4 x 4, dan salah satu bentuk ditampilkan pada gambar 2.11. Akan terlihat bahwa jumlah masing-masing adalah empat horisontal, empat kolom vertikal dan dua diagonal pada square ini adalah 34, sehingga semuanya dapat dihitung totalnya, juga bahwa jumlah dari dua


nomor diametris berlawanan adalah 17, yang merupakan jumlah dari angka pertama dan terakhir dari seri.

Matriks pada magic square berukuran n x n, dengan elemen yang berbeda satu sama lain berupa bilangan bulat dari 1 hingga n2 . Jumlah dari deret 1+2+3+…+n2 dapat ditentukan melalui persamaan :

Dari persamaan (1), maka dapat ditentukan pula bahwa jumlah angka-angka pada tiap baris, kolom, dan diagonal adalah :

Jumlah tersebut menghasilkan angka yang disebut dengan konstanta magic square (Munir, 2007).

2.3 Algoritma Depth First Search (DFS)

Algoritma Depth First Search (DFS) menggunakan struktur data stack untuk mengingat kemana seharusnya Depth First Search (DFS) pergi saat ia mencapai suatu simpul tertentu.

Istilah “depth first” artinya melewati sebuah lintasan sejauh (sedalam) mungkin. Hanya pada titik tertentu yang tidak dapat ditelusuri, maka dilakukan runut balik (backtracking) dan menelusuri lintasan alternatif lain. Metode ini dapat dijelaskan dalam bentuk pseudocode berikut: Algorithm DFS(Vertex v): if v has already been visited: return else:


mark v as visited process(v) for each edge e that leaves v: let u be the other endpoint of e call DFS(u)

Algoritma ini akan mengunjungi dan memproses setiap simpul yang dapat dicapai dari v dan yang belum pernah dikunjungi. Hal ini dilakukan dengan mengikuti setiap sisi yang terhubung dengan v dan menggunakan prosedur yang sama secara rekursif untuk endpoint lain dari sisi tersebut.

Menurut Robert Laforce (1998) pada Adi dalam buku algoritma dan struktur data dengan C# di halaman 499, menyatakan algoritma Depth First Search (DFS) memiliki beberapa aturan, yaitu:

1. Jika mungkin, lakukan kunjungan pada simpul-simpul pendamping (adjacent vertex) yang belum pernah dikunjungi, tandai, dan masukkan (push) ke stack. Sebagai contoh, pada gambar 9 dan tabel 1, aturan ini dapat diterapkan pada simpul-simpul sebelum simpul H. Pada langkah terakhir ini kita perlu melakukan sesuatu karena tidak ada simpul pendamping yang belum dikunjungi. Dalam hal ini kita bisa masuk ke aturan 2 di bawah ini.

B

F

H

G

I

C A D

E

Gambar 2.13 Lintasan DFS


Tabel 2.1 Isi Stack dalam DFS Event

Isi Stack

Visit A

A

Visit B

AB

Visit F

ABF

Visit H

ABFH

Pop H

ABF

Pop F

AB

Pop B

A

Visit C

AC

Pop C

A

Visit D

AD

Visit G

ADG

Visit I

ADGI

Pop I

ADG

Pop G

AD

Pop D

A

Visit E

AE

Pop E

A

Pop A

FINISH

2. Jika saat kita melakukan aturan di atas kita mengalami kesulitan, kita keluarkan (popped off) simpul dari stack. Mengikuti aturan ini, jika kita mengeluarkan suatu simpul dari suatu stack, kita akan sampai ke simpul di bawahnya. Jika simpul di bawahnya ini bukan simpul pendamping yang belum dikunjungi, kita keluarkan lagi. Demikian selanjutnya hingga kita tidak bisa melakukannya lagi dan kita harus masuk ke aturan 3 di bawah ini.

3. Jika kita tidak bisa lagi mengikuti baik aturan 1 maupun 2 di atas, berarti kita telah menyelesaikan algoritma Depth First Search (DFS).


Beberapa kelebihan dari Depth First Search adalah : 1. Pemakaian memori hanya sedikit, berbeda dengan BFS (Breadth First Search) yang harus menyimpan semua simpul yang pernah dibangkitkan. 2. Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka akan ditemukan solusi secara cepat.

Dan beberapa kelemahan dari Depth First Searh adalah : 1. Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka solusi pun sulit untuk ditemukan. 2. Tidak memiliki titik optimal jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda.

2.4 Algoritma Runut Balik (Backtracking)

Istilah runut balik pertama kali diperkenalkan oleh D.H. Lehmer pada tahun 1950. Selanjutnya di tahun 1960, R. J. Walker, Golomb, dan Baumert menyajikan uraian umum tentang runut balik dan penerapannya pada berbagai persoalan.

Pada berbagai masalah real world, solusi diperoleh dengan memproses rangkaian titik keputusan dimana setiap kandidat memiliki beberapa lintasan yang dapat ditelusuri. Jika lintasan yang ditelusuri mengarah kepada solusi, maka penelusuran dihentikan dan solusi ditemukan. Namun, jika lintasan yang ditelusuri tidak mengarah kepada solusi, maka harus dilakukan runut balik ke titik keputusan sebelumnya dan mencoba lintasan yang lain. Metode yang digunakan pada proses tersebut adalah metode backtracking.

Teknik runut balik (backtracking) merupakan salah satu teknik dalam penyelesaian masalah secara umum (General Problem Solving). Adapun dasar dari teknik ini adalah suatu teknik pencarian (Teknik Searching). Teknik pencarian ini digunakan dalam rangka mendapatkan himpunan penyelesaian yang mungkin. Dari


himpunan penyelesaian yang mungkin ini akan diperoleh solusi optimal atau memuaskan (Astuti, 2006).

2.4.1 Pengertian Algoritma Runut Balik (Backtracking)

Runut balik (backtracking) adalah algoritma yang berbasis pada Depth First Search (DFS) untuk mencari solusi persoalan secara lebih mangkus. Runut balik, yang merupakan perbaikan dari algoritma brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Dengan metode runut balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat. Saat ini algoritma runut balik banyak diterapkan untuk program permainan (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, dll) dan masalah-masalah pada bidang kecerdasan buatan (artificial intelligence) (Munir, 2004).

2.4.2 Properti Umum dari Metode Runut Balik (Backtracking)

Untuk menerapkan metode runut balik, properti berikut didefinisikan: 1. Solusi persoalan. Solusi dinyatakan sebagai vektor n-tuple: Contoh: Si = {0,1} Si = 0 atau 1

2. Fungsi pembangkit nilai xk Dinyatakan sebagai: T(k) T(k) membangkitkan nilai untuk xk, yang merupakan komponen vektor solusi

3. Fungsi pembatas (fungsi kriteria) Dinyatakan sebagai:


B(x1, x2, ..., xk) Fungsi pembatas menentukan apakah (x1, x2, ..., xk) mengarah ke solusi. Jika ya, maka pembangkitan nilai untuk xk+1 dilanjutkan, tetapi jika tidak, maka (x1, x2, ..., xk) dibuang dan tidak dipertimbangkan lagi dalam pencarian solusi. Terdapat metode dalam pengisian elemen-elemen matriks, yakni elemen pertama yang akan diisi adalah elemen pada baris dan kolom pertama, kemudian dilanjutkan pada elemen kolom berikutnya dan setelah selesai mengisi satu baris, maka akan dilanjutkan pada kolom pertama pada baris selanjutnya. Elemen-elemen/kotak yang diisi direpresentasikan sebagai tingkatan dalam pembentukan pohon ruang status secara dinamis. Sedangkan angka-angka yang mungkin untuk diisi, direpresentasikan sebagai daun pada pohon ruang status. Selanjutnya akan dibahas mengenai fungsi batas yang digunakan dalam implementasi algoritma runut balik pada penyelesaian persoalan magic square tersebut.

Proses runut balik terjadi ketika daun yang dibangkitkan oleh program pada suatu tingkatan tidak sesuai dengan fungsi batas. Untuk persoalan magic square, fungsi batas terdiri dari beberapa kasus. Kasus yang pertama adalah ketika tingkatan yang dicapai merupakan elemen terakhir yang akan diisi pada suatu baris dan/atau kolom dan/atau diagonal. Fungsi batas mengharuskan kolom tersebut untuk diisi dengan elemen, sedemikian sehingga elemen tesebut menjadikan baris, kolom, atau diagonal tersebut berjumlah sama dengan konstanta magic square yang ditentukan sesuai dengan ordo matriks. Kasus kedua adalah ketika daun yang dibangkitkan untuk mengisi elemen matriks sudah berada pada elemen matriks lainnya. Fungsi batas mengharuskan setiap elemen memiliki nilai yang berbeda satu sama lain. Kasus ketiga adalah ketika pada suatu tingkatan daun yang telah dibangkitkan telah mencapai nilai maksimum, yakni jika matriks memiliki ordo n, maka nilai maksimum dari suatu elemen adalah n2, sehingga harus melakukan proses runut balik ke akar.

2.4.3 Prinsip Dasar dari Algoritma Runut Balik (Backtracking)

Secara konseptual, pencarian solusi dimulai dari akar pohon ruang status. Dimana setiap simpul, dimulai dari akar, pilih salah satu simpul anak yang bisa diperluas, dan


seterusnya. Jika pencarian sampai ke daun, maka selanjutnya dilakukan backtracking ke simpul orang tua. Pencarian dihentikan jika solusi ditemukan atau tidak dapat dilakukan backtracking lagi.

Berikut ini adalah algoritma (pseudocode) untuk melakukan backtracking dari simpul n: boolean solve(Node n) { if n is a leaf node { if the leaf is a goal node, return true else return false } else { for each child c of n { if solve(c) succeeds, return true } return false } }

Algoritma tersebut diekspresikan dengan fungsi boolean. Jika solve(n) benar, maka simpul n adalah bagian dari solusi, yaitu simpul n adalah salah satu simpul pada jalur dari root ke beberapa simpul tujuan. Sehingga dapat dikatakan bahwa n dapat diselesaikan. Jika solve(n) salah, maka tidak ada jalur yang termasuk simpul n yang mengarah ke simpul tujuan.

Maka, untuk menentukan adanya simpul n, yang bukan leaf, dapat diselesaikan, yang harus dilakukan adalah mengecek adanya cabang dari n yang dapat diselesaikan. Ini dilakukan secara rekursif pada setiap cabang dari n. Pada pseudocode tersebut, dikerjakan oleh baris: for each child c of n { if solve(c) succeeds, return true } return false


Pada akhirnya, proses rekursif akan berada pada simpul leaf. Jika simpul leaf adalah simpul tujuan, maka dapat diselesaikan; jika simpul leaf bukan simpul tujuan, maka tidak dapat diselesaikan. Pada pseudocode tersebut, dikerjakan oleh baris: if n is a leaf node { if the leaf is a goal node, return true else return false }

2.4.4 Prinsip Pencarian Solusi dengan Metode Runut Balik (Backtracking)

Langkah-langkah pencarian solusi dapat dilakukan dengan metode sebagai berikut:

1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan pembentukan yang dipakai adalah mengikuti aturan pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup (live node). Simpul hidup yang sedang diperluas dinamakan simpul-E (Expand-node).

2. Tiap kali simpul-E diperluas, lintasan yang dibangun olehnya bertambah panjang. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Fungsi yang digunakan untuk membunuh simpul-E adalah dengan menerapkan fungsi pembatas (bounding function). Simpul yang sudah mati tidak akan pernah diperluas lagi.

3. Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak yang lainnya. Bila tidak ada lagi simpul anak yang dapat dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan runut balik ke simpul hidup terdekat (simpul orangtua). Selanjutnya simpul ini menjadi simpul-E yang baru.

Pencarian dihentikan bila kita telah menemukan solusi atau tidak ada lagi simpul hidup untuk runut balik.


Berikut ini adalah contoh penerapan algoritma Backtracking pada persoalan NRatu (The N-Queens Problem).

Persoalan: Diberikan sebuah papan catur yang berukuran NxN dan empat buah ratu. Bagaimanakah menempatkan N buah ratu (Q) itu pada petak-petak papan catur sedemikian sehingga tidak ada dua ratu atau lebih yang terletak pada satu baris yang sama, atau pada satu kolom yang sama atau pada satu diagonal yang sama.

Berdasarkan pada “Bahan Kuliah ke- 10 : Algoritma Runut-Balik (Backtracking) Lanjutan” karangan Rinaldi Munir, solusi dari permasalahan tersebut adalah sebagai berikut: X = (x1,x2,x3,x4), dimana X merupakan vektor dan xi ∈ Si S = {1,2,3,4}, S menyatakan kolom pada papan catur.

Dari hal ini, dapat dibentuk pohon ruang solusi persoalan 4-Ratu yang terlihat pada Gambar 2.7 sebagai berikut:

1

x1=1

x1=2

2

x2=2

18

x2=4

x2=3

3

4

8

9

13

11

19

24

x3=3

x3=3 x3=3

14

16

20

5

7

x4=2

x4=2 10

29

12

50

x2=2

22

x3=2 x3=1

25

35

x3=4

x3=4

x4=4 x4=3

x2=1

x2=4

27

x4=4

30

40

x2=1

32

15

17

x4=3

x4=3

21

23

x4=3 26

28

38

x4=4 x4=1

31

33

x3=1 x3=1

36

41

43

39

46

42

48

44

x3=1

52

x4=1

47

49

x3=3

54

x3=1 57

59

55

62

x4=1 58

x3=2 64

x4=2

x4=3 x4=2

53

61

x3=3

x4=3

x4=2 x4=1

56

x3=2 x3=2

x2=3

x2=2

51

x3=4

x4=4 x4=2

37

45

x3=4

x3=3

x4=3

x4=4

x4=4

x2=4

x2=1

x3=4 x3=2 x3=4

6

34

x1=1

x3=2 x3=3

x1=4

x1=3

60

x4=1 63

65

Gambar 2.14 Pohon ruang kemungkinan solusi persoalan 4-Ratu


Dari gambar, dapat dilihat ruang seluruh solusi yang mungkin diterapkan pada persoalan 4-Ratu pada papan catur tersebut. Langkah-langkah solusi dengan menggunakan backtracking adalah berikut : 1.

Menelusuri node dari akar sampai ke daun yang membentuk ruang solusi secara DFS. Penelusuran dilakukan dengan mempertimbangkan setiap batasan atau kriteria yang telah ditetapkan.

2.

Apabila node yang dikunjungi memenuhi kriteria, maka akan dilakukan penulusuran menuju node berikutnya. Sebaliknya, apabila node yang dikunjungi tidak memenuhi kriteria, maka akan dilakukan backtracking menuju node yang berada di atas dan node tersebut sampai ke bawahnya tidak dipertimbangkan lagi.

3.

Pencarian berhenti apabila ditemukan solusi atau tidak ada node hidup pada pohon tersebut.

Dari langkah-langkah tersebut, dapat dilihat contoh solusi pada Gambar 2.8 dan pohon solusi persoalan 4-Ratu pada papan catur pada Gambar2.9.

1

1

1

1

2

2

2 3

(a)

(b)

1

1

(c)

(d)

1

1

2

2

3

2 3 4

(e)

(f)

(g)

(h)

Gambar 2.15 Penelusuran Solusi Backtraking 4-Ratu pada papan catur


1

x1=1

x1=2

2

x2=2

18

x2=3

3

x2=1

x2=4

8

13

B x3=2

x2=3

19

24

B

B

x2=4

29

x3=3

x3=1

x3=2 x3=4

9

11

B

B

14

16

30

B x4=3

15

x4=3

31

B

Gambar 2.16 Pohon pencarian solusi dengan Backtraking pada persoalan 4-Ratu


BAB 2 TINJAUAN PUSTAKA

Recommend Documents