Tugas Besar II IF2211 Strategi Algoritma Halaman 2 dari 16 04/11/13

Table of Contents Bab 1 Deskripsi Utama .................................................................................................................. 3

1.1 Deskripsi Umum ................................................................................................................... 3 1.2 Mode Permainan ................................................................................................................... 4

Bab 2 Dasar Teori ........................................................................................................................... 5 2.1 Algoritma BFS (Breadth-First Search) ................................................................................. 5 2.2 Algoritma Bactracking .......................................................................................................... 6

2.3 Algoritma DFS (Depth-First Search) .................................................................................... 6 Bab 3 Analisis Pemecahan Masalah ............................................................................................... 8 Bab 4 Implementasi dan Pengujian................................................................................................. 9

4.1 Spesifikasi Teknis Program .................................................................................................. 9 4.2 Capture Layar...................................................................................................................... 12 4.3 Analisis Hasil Pengujian ..................................................................................................... 14

Bab 5 Kesimpulan dan Saran ........................................................................................................ 16 Bab 6 Daftar Pustaka .................................................................................................................... 16

Bab 7 Lampiran............................................................................................................................. 16 7.1 Pembagian Kerja dalam Kelompok .................................................................................... 16


Bab 1 Deskripsi Utama

1.1 Deskripsi Umum

Pentomino adalah polyomino yang terdiri dari lima buah persegi yang berukuran sama yang

terhubung sepanjang tepi mereka (koneksi orthogonal) menciptakan 12 bentuk yang berbeda

yang digunakan sebagai potongan teka-teki dalam matematika rekreasi (Sumber kutipan:

Wikipedia).

Biasanya, pentomino diperoleh dari refleksi atau rotasi pentomino yang tidak dihitung sebagai

pentomino yang berbeda. F, L, N, P, Y, dan Z adalah pentomino chiral dalam dua dimensi;

dengan menambahkan refleksi mereka (F ', J, N', Q, Y ', S) menghasilkan jumlah pentomino

menajdi 18. Yang lain, berhuruf I, T, U, V, W, dan X, setara dengan beberapa rotasi gambar

cermin mereka. (Sumber kutipan: Wikipedia).

Masing-masing dari dua belas pentomino dapat diubinkan untuk mengisi sebuah bidang datar.

Selain itu, setiap pentomino chiral dapat diubinkan tanpa menggunakan refleksi (Sumber

kutipan: Wikipedia).

Gambar 1. Perbandingan skema pelabelan pentomino. Yang pertama adalah konvensi penamaan yang

digunakan dalam artikel ini. Metode kedua adalah Conway (Sumber: Wikipedia)


Sebuah teka-teki pentomino standar adalah mengubinkan kotak persegi panjang dengan

pentamino, yaitu menutupinya tanpa tumpang tindih dan tanpa celah. Masing-masing dari 12

pentamino memiliki luas 5 unit kuadrat, sehingga kotak harus memiliki area seluas 60 unit.

Kemungkinan ukuran yang lain adalah 6 × 10, 5 × 12, 4 × 15 dan 3 × 20. (Sumber kutipan:

Wikipedia).

Gambar 2. Dua belas pentamino sudah dubinkan pada kotak berukuran 6 × 10, 5 × 12, 4 × 15 dan 3 × 20

(Sumber: Wikipedia)

Bila diselesaikan dengan tangan mungkin membutuhkan waktu beberapa jam, namun jika

diselesaikan dengan komputer akan membutuhkan pencarian dengan backtracking.

Keterangan: Semua gambar dan bahan tulisan diambil dari laman ini:

http://en.wikipedia.org/wiki/Pentamino

1.2 Mode Permainan

Ada tiga mode permainan di dalam permainan ini:

1. Mode komputer BFS

Pada mode ini, permainan akan disimulasikan oleh komputer. Komputer akan mencoba

melakukan solving pada puzzle pentomino dengan menggunakan algoritma BFS.

2. Mode komputer bactracking berbasis DFS

Pada mode ini, permainan akan disimulasikan oleh komputer. Komputer akan mencoba

melakukan solving pada puzzle pentomino dengan menggunakan algoritma bactracking

berbasis DFS.

3. Mode pemain

Pada mode ini, permainan akan dimainkan oleh pemain sendiri. Pemain harus meletakkan

pentomino pada board yang tersedia dengan bantuan tetikus. Permainan selesai ketika

semua potongan pentomino telah dimasukkan ke dalam board.

http://en.wikipedia.org/wiki/Pentamino


Bab 2 Dasar Teori

2.1 Algoritma BFS (Breadth-First Search)

Algoritma BFS (Breadth-First Search) merupakan salah satu algoritma yang digunakan dalam

pencarian graf. Konsep algoritma BFS adalah melakukan pencarian untuk node saat ini, lalu

melakukan pencarian untuk semua node tetangga yang belum pernah dikunjungi secara

berurutan. Algoritma ini menyimpan daftar node tetangga yang akan dikunjungi dengan

menggunakan struktur data queue.

Proses kerja algoritma BFS adalah sebagai berikut:

1. Masukkan node akar ke queue.

2. Keluarkan node yang ada di head dari queue. Jika node yang dikeluarkan adalah solusi

dari persoalan, berhenti dan kembalikan node tersebut. Jika tidak, masukkan semua node

tetangga yang belum pernah diperiksa ke dalam queue.

3. Jika queue kosong, maka semua node sudah diperiksa. Hentikan pencarian dan

kembalikan nilai null.

4. Jika queue tidak kosong, ulangi langkah 2.

Berikut adalah pseudocode dari algoritma runut balik. G merupakan sebuah graf, dan s

merupakan akar dari graf G.

BFS(G,s)

for each vertex u ∈ V [G] − {s} do

state[u] = “undiscovered”

p[u] = nil, i.e. no parent is in the BFS tree

state[s] = “discovered”

p[s] = nil

Q = {s}

while Q != ∅ do

u = dequeue[Q]

process vertex u as desired

for each v ∈ Adj[u] do

ocess edge (u,v) as desired

if state[v] = “undiscovered” then

state[v] = “discovered”

p[v] = u

enqueue[Q,v]

state[u] = “processed”


2.2 Algoritma Bactracking

Algoritma bactracking (atau disebut juga algoritma runut balik) merupakan salah satu dari

banyak algoritma yang digunakan untuk pencarian solusi dari permasalahan komputasi. Konsep

dari algoritma ini adalah membentuk kandidat solusi parsial secara bertahap hingga mencapai

solusi akhir, dan membuang kandidat solusi parsial tertentu (melakukan “backtrack”) ketika

kandidat tersebut dianggap tidak akan mencapai solusi.

Pada algoritma runut balik terdapat lima fungsi utama:

1. root(P): mengembalikan kandidat solusi parsial pada akar dari pohon pencarian. 2. reject(P,c): mengembalikan nilai true jika kandidat c dianggap tidak akan

memberikan solusi akhir.

3. accept(P,c): mengembalikan nilai true jika kandidat c merupakan solusi dari P. Selain

itu, fungsi ini akan mengeluarkan nilai false.

4. first(P,c): Membuat kandidat solusi parsial lanjutan pertama dari kandidat c.

5. next(P,s): Membuat kandidat solusi parsial lanjutan selanjutnya setelah kandidat s.

Berikut merupakan pseudocode dari algoritma runut balik yang dilakukan secara rekursif.

procedure bt(c)

if reject(P,c) then return

if accept(P,c) then output(P,c)

s ← first(P,c)

while s ≠ Λ do

bt(s)

s ← next(P,s)

2.3 Algoritma DFS (Depth-First Search)

Algoritma DFS (Depth-First Search) merupakan salah satu algoritma yang digunakan dalam

pencarian graf. Konsep algoritma DFS adalah melakukan pencarian melakukan pencarian pada

suatu node, lalu melakukan pencarian pada node pertama yang belum pernah dikunjungi hingga

solusi ditemukan atau tidak ada node tetangga yang belum dikunjungi. Algoritma ini menyimpan

daftar node tetangga yang akan dikunjungi dengan menggunakan struktur data stack. Dari sini

dapat dilihat bahwa algoritma DFS merupakan bentuk khusus dari algoritma backtracking.

Proses kerja algoritma DFS adalah sebagai berikut:

1. Masukkan node akar ke stack.

2. Keluarkan node yang ada di top dari stack. Jika node yang dikeluarkan adalah solusi dari

persoalan, berhenti dan kembalikan node tersebut. Jika tidak, masukkan semua node

tetangga yang belum pernah diperiksa ke dalam stack.

3. Jika stack kosong, maka semua node sudah diperiksa. Hentikan pencarian dan

kembalikan nilai null.

4. Jika stack tidak kosong, ulangi langkah 2.

Proses kerja algoritma DFS di atas adalah algoritma DFS yang dilakukan secara iteratif.


Berikut merupakan pseudocode dari algoritma DFS yang dilakukan secara iteratif.

procedure DFS-iterative(G,v):

label v as discovered

let S be a stack

S.push(v)

while S is not empty

t ← S.peek()

if t is what we're looking for:

return t

for all edges e in G.adjacentEdges(t) do

if edge e is already labelled

continue with the next edge

w ← G.adjacentVertex(t,e)

if vertex w is not discovered and not explored

label e as tree-edge

label w as discovered

S.push(w)

continue else if vertex w is discovered

label e as back-edge

else // vertex w is explored

label e as forward- or cross-edge

label t as explored

S.pop()

Berikut merupakan pseudocode dari algoritma DFS yang dilakukan secara rekursif.

DFS(G,u)

state[u] = “discovered”

process vertex u if desired

entry[u] = time

time = time + 1

for each v ∈ Adj[u] do

process edge (u,v) if desired

if state[v] = “undiscovered” then

p[v] = u

DFS(G,v)

state[u] = “processed”

exit[u] = time

time = time + 1


Bab 3 Analisis Pemecahan Masalah

Proses jalan algoritma yang digunakan di aplikasi ini mirip dengan algoritma BFS dan DFS yang

sudah ada. Pada bab ini hanya akan dijelaskan tentang strategi peletakan pentomino ke papan.

Pengisian papan pentomino dilakukan dengan melihat sel kosong pertama yang ditemukan di

papan pentomino. Ada dua cara penentuan sel kosong pertama, yaitu penentuan berdasarkan

kolom dan penentuan berdasarkan baris. Penentuan sel kosong berdasarkan baris dilakukan

ketika jumlah kolom lebih kecil atau sama dengan jumlah baris. Penentuan sel kosong

berdasarkan kolom dilakukan ketika jumlah baris lebih kecil daripada jumlah kolom.

Setelah penentuan sel kosong, potongan pentomino akan dicoba diletakkan ke papan. Sel kosong

akan menjadi patokan bagaimana pentomino diletakkan ke dalam papan. Ada dua patokan yang

digunakan dalam penempatan pentomino, yaitu patokan kiri dan patokan atas. Penempatan

pentomino dengan patokan kiri dilakukan dengan cara meletakkan bagian pentomino yang

ditemui pertama kali pada sumbu x ke sel kosong. Penenmpatan pentomino dengan patokan atas

dilakukan dengan cara meletakkan bagian pentomino yang ditemui pertama kali pada sumbu y

ke sel kosong. Program akan memprioritaskan peletakan pentomino dengan patokan kiri terlebih

dahulu sebelum melakukan peletakan pentomino dengan patokan atas.

Jika pentomino bisa dimasukkan ke papan, simpan keadaan dari papan ke queue (jika

menggunakan algoritma BFS) atau stack (jika menggunakan algoritma DFS). Jika pentomino

tidak bisa dimasukkan ke papan, lakukan pemutaran/pencerminan pentomino (jika bisa),

kemudian coba lakukan pemasukan pentomino ke papan. Jika masih tidak bisa (untuk semua

kemungkinan keadaan pentomino), ganti dengan pentomino lain.


Bab 4 Implementasi dan Pengujian

4.1 Spesifikasi Teknis Program

Program memiliki kelas Pentomino, Board, dan Solver dengan struktur data sebagai berikut:

class Piece { public int[,] pieceBoard; // The matrix of occupied spaces public int iTurns; // The number of turns public bool flippable; // Is the piece flippable? public int maxRotate; // Maximum number of rotations of a piece before // returning to current form (not including // flipped ones) public int pieceId; // Pentomino piece ID (0 to 11) public int firstX; // First pentomino part found in x axis public int firstY; // First pentomino part found in y axis /* * Creates a pentomino piece according to the input code. */ public Piece(int pieceType); /* * Fill the piece board according to the input code. */ public void CreatePiece(int iPieceType); /* * Rotates the piece 90 degrees counterclockwise. */ public void RotatePiece(); /* * Flips the pentomino piece. */ public void FlipPiece(); /* * Returns the string representation of pentomino piece. */ public override string ToString(); }

class Board { public int[,] board; // Matrix for the board itself // Note : Each cell has a code : // -2 : Cannot be filled // -1 : Empty // 0..n : Filled with piece corresponding to the // code public int width; // Width of the board


public int height; // Height of the board public int numOfPieces; // Number of pieces that can be used public Piece[] pieces; // Pieces that will be used for the board public bool[] usedPieces; // Pieces that have been used public int nextAvailableX; // The first x coordinate available public int nextAvailableY; // The first y coordinate available public List<Action> lastActions;// List of pieces used and the position it // is applied. Piece on the end of the list is // the last piece used. /* * Creates a Board with standard pentominoes count (12) and standard * Pentomino Board (rectangle-shaped). */ public Board(int width, int height); /* * Creates a Board with custom pentominoes count and custom * Pentomino Board. The information about the pentominoes * and the board are contained in a text file. */ public Board(string filename); /* * This method will try to put pentomino piece "piece" inside * the board on position x of "x" and position y of "y". * Returns true when putting the piece this way is possible and the piece * fills the first empty cell found. * Otherwise, returns false. */ public bool PutPiece(int positionX, int positionY, Piece piece, int numOfRotate, int numOfFlip); /* * Returns true when putting X piece in position x and y with the left part * as the base is possible. */ public bool PutXPieceLeft (int positionX, int positionY, Piece piece); /* * Returns true when putting X piece in position x and y with the upper part * as the base is possible. */ public bool PutXPieceUp (int positionX, int positionY, Piece piece); /* * Returns true when putting X piece in position x and y with the right part * as the base is possible. */ public bool PutXPieceRight(int positionX, int positionY, Piece piece); /* * Returns true when putting X piece in position x and y with the lower part * as the base is possible. */ public bool PutXPieceDown(int positionX, int positionY, Piece piece);


/* * Finds the first empty cell available in the board. * This method can find the first cell by searching per row * or searching per column, depending on the circumstances. */ public void NextEmptyCell(); /* * Removes last piece used. Returns true when succeed. * Otherwise returns false. */ public bool RemoveLastPiece(); /* * Do actions in action list to this board. */ public void DoActions(List<Action> actionList); /* * Returns string representation of the pentomino board. */ public override string ToString(); /* * Returns a clone of object p. */ public static T Copy<T> (T obj);

class Solver { public Board solutionBoard; // The solution board for the puzzle /* * Solve the pentomino puzzle with bactracking algorithm * based of DFS. Returns true when a solution is found. */ public bool SolveDFS(Board root); /* * The recursive part of the algorithm. Returns true when a solution is * found. */ public bool SolveDFSRecursive(Board root); /* * Solve the pentomino puzzle with pure BFS method (takes a long time). */ public bool SolveBFS(Board root); /* * Returns true when current board state is a solution. * A board state is considered a solution when all the board cells * are filled with pentominos. */ public bool isSolution(Board b);


4.2 Capture Layar

User interface (anatrmuka) yang digunakan di aplikasi ini ada dua macam, yaitu GUI (graphic-

based interface) dan CLI (command line interface). GUI digunakan untuk antarmuka utama.

Sedangkan CLI digunakan untuk validasi algoritma serta perbandingan langsung.

Berikut merupakan beberapa screen capture Player Mode.

Gambar 3. Capture layar GUI DFS mode Gambar 4. Capture layar GUI DFS mode solved

Gambar 5. Capture layar GUI Player mode Gambar 6. Capture layar GUI BFS mode solved


Berikut merupakan beberapa screen capture CLI untuk pembandingan algoritma BFS dan DFS

Gambar 7. Contoh eksekusi aplikasi untuk papan berukuran 3 x 20. Gambar kiri merupakan

solusi yang dibuat oleh algoritma runut balik. Gambar kanan merupakan solusi yang dibuat oleh

algoritma BFS.



algoritma BFS.




algoritma BFS.



algoritma BFS.

4.3 Analisis Hasil Pengujian

Dari gambar 3, 4, 5, dan 6 pada upabab sebelumnya, dapat dilihat bahwa waktu eksekusi

algoritma BFS sangat fluaktuatif, sedangkan waktu eksekusi algoritma DFS cenderung stabil.

Pada awal algoritma BFS, dilakukan pemilihan acak untuk pentomino yang akan dicoba

untuk dimasukkan ke papan pertama kali. Algoritma BFS juga harus menyimpan keadaan

papan ke queue karena algoritma BFS hanya bisa dilakukan dengan cara iterasi. Kedua hal

inilah yang menyebabkan waktu eksekusi algoritma BFS sangat fluktuatif.


Algoritma DFS cenderung cepat karena algoritma ini tidak melakukan penyimpanan keadaan

papan, sehingga menggunakan memori dan waktu yang jauh lebih sedikit dibandingkan

algoritma BFS. Algoritma DFS juga menggunakan pentomino acak pertama kali pada saat

percobaan pertama. Namun, pemilihan acak ini tidak terlalu memengaruhi waktu eksekusi

algoritma DFS, karena secara umum waktu eksekusinya sudah cepat.


Bab 5 Kesimpulan dan Saran

Kesimpulan

Algoritma DFS dan bactracking secara umum lebih efektif dalam pencarian solusi pertama dari

suatu permasalahan komputasi.

Saran

Fungsi peletakan pentomino masih belum bisa meletakkan pentomino untuk beberapa papan

dengan bentuk yang unik. Sejauh ini masalah ini baru ditemukan pada papan berbentuk jajaran

genjang berukuran 3x20. Sebaiknya fungsi peletakan ini diperbaiki agar bisa mengakomodasi

peletakan di papan yang unik.

Algoritma BFS sangat lambat dan membutuhkan banyak memori. Sebaiknya digunakan search

pruning untuk meningkatkan performansi algoritma BFS.

Bab 6 Daftar Pustaka 1. Munir, Dr. Ir. Rinaldi. 2009. Diktat Kuliah IF2211 Strategi Algoritma. Program Studi

Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung.

2. Skiena, Steven S.. 2008. The Algorithm Design Manual, Second Edition. Springer.

3. Levitin, Anany. 2011. Introduction to the Design and Analysis of Algorithms, Third Edition.

Addison-Wesley.

4. http://en.wikipedia.org/wiki/Breadth-first_search, diakses pada tanggal 4 November 2013

@08:24.

5. http://en.wikipedia.org/wiki/Depth-first_search, diakses pada tanggal 4 November 2013

@08:27.

6. http://en.wikipedia.org/wiki/Backtracking, diakses pada tanggal 4 November 2013 @08:32.

Bab 7 Lampiran

7.1 Pembagian Kerja dalam Kelompok

Nama Bagian

Arief Rahman Membuat kelas Pentomino, Board, Solver (BFS dan DFS),

dan Laporan

Mohamad Rivai Ramandhani Membuat kelas Pentomino, Board, Solver (BFS), dan GUI

Pandu Kartika Putra Membuat GUI, Laporan, dan Solver (DFS)

http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Backtracking

tubes stima 2 2013

Documents