8-Puzzle Problem (Bagian 1)


Bismillaah…

Di tengah merebaknya “gosip” seputar paniknya pengumpulan tugas kuliah yang kian hari kian “riweuh” dan menumpuk, sepertinya baru mulai terasa bahwa kehidupan perkuliahan rupanya mengandung beban yang makin syarat serta semakin menguras waktu dan pikiran (lebay mode: ON). Untuk itu, saya berniat sedikit berbagi dengan teman-teman yang mungkin sedang sibuk-sibuknya “kejar tayang” dengan pekerjaan kantornya atau barangkali sedang “nyungsang jempalik” mengurusi masalah keluarga yang juga tidak kalah pentingnya. Sebagai “jomblowan” dan kaum “pengangguran”, saya memaklumi hal itu. Berikut adalah ulasannya. Monggo disemak!!

Ok… postingan kali ini adalah tentang tugas perkuliahan Intelejensi Buatan Tingkat Lanjut (EL5133) yang membahas mengenai permasalahan 8-puzzle (8-Puzzle Problem). Dalam dunia artificial intelligence, permasalahan-permasalahan yang sederhana seperti 8-Puzzle ini sering digunakan sebagai miniatur simulasi pencarian solusi terhadap suatu masalah. Tentang seperti apa, mengapa, dan bagaimana penerapan 8-Puzzle Problem ini, ada baiknya kita uraikan satu per satu poin-poinnya.

Definisi Singkat
8-Puzzle adalah representasi permainan teka-teki yang dapat diselesaikan dengan mengurutkan atau menyusun komponen-komponen pembentuknya sesuai dengan kondisi yang diinginkan. Komponen pada 8-Puzzle adalah berupa kotak-kotak bernomor atau bergambar (sesuai kebutuhan) yang dapat diacak sedemikian hingga menjadi suatu pola random yang dapat dicari jalan penyelesaiannya. Sesuai namanya, 8-Puzzle terdiri atas 8 kotak dan 1 tempat kosong yang dapat digerakkan dengan aturan tertentu. Aturan pergerakannya hanya berupa empat (4) arah pergerakan, yaitu: atas, bawah, kanan, dan kiri. Serta terlimitasi oleh ukuran dimensi papan yang ditempatinya. Pada 8-Puzzle, batasannya adalah ukuran 3×3. Sehingga, 8 kotak yang dimiliki hanya dapat bergerak dalam lingkup ukuran tersebut.

Tipikal Permasalahan
Tipikal permasalahan yang disajikan oleh 8-Puzzle adalah berupa pencarian langkah-langkah konkret sesuai aturan sehingga menuju kondisi akhir yang diinginkan. Oleh karena itu, pada bidang artificial intelligence, penyelesaian permasalahan 8-Puzzle ini dapat dikategorikan ke dalam metode Pencarian atau Searching. Penjelasan lebih lanjut mengenai Searching akan dibahas pada poin Metodologi.

Struktur Representasi
Karena berupa pencarian langkah-langkah menuju goal, maka permasalahan 8-Puzzle ini mungkin lebih sesuai jika direpresentasikan dalam bentuk Pohon Penyelesaian. Sehingga implementasinya akan lebih “mengena” jika menggunakan struktur pohon atau tree node dengan jumlah child sebanyak N, atau yang lebih familiar kita sebut sebagai N-ary Tree. Berikut adalah contoh implementasi N-ary Tree yang saya buat menggunakan bahasa favorit saya, JavaTM (dibacanya bukan Jawa Timuran ya… :p).

import java.util.Vector;
/**
 *
 * @author Andik Taufiq
 * Node represents element of N-ary tree
 * March 18, 2010 - Bandung, Indonesia
 */
public class Node {
    public Node parentNode = null;
    public Vector children;
    public int index = 0;
    public int[] nodeState;
    public String nodeId;
    public int level = 0;
    public int heuristicValue;
    public boolean closed;
    
    public Node(int[] state, String id) {
        this.children = new Vector();
        nodeState = new int[9];
        for (int i = 0; i < 9; i++) {
            nodeState[i] = state[i];
        }
        if (parentNode == null) {
            nodeId = id + "0";
            level = 0;
        } else {
            nodeId = parentNode.nodeId + Integer.toString(parentNode.getChildrenNum() + 1);
            level = parentNode.level + 1;
        }
        closed = false;
    }

    public void appendChild(Node node, int[] state) {
        node.parentNode = this;
        node.index = this.children.size();
        node.nodeState = new int[9];
        for (int i = 0; i < 9; i++) {
            node.nodeState[i] = state[i];
        }
        node.nodeId = node.parentNode.nodeId + Integer.toString(node.parentNode.getChildrenNum() + 1);
        node.level = this.level + 1;
        node.closed = false;
        this.children.addElement(node);
    }

    public int getChildrenNum() {
        return this.children.size();
    }

    public boolean hasChildren() {
        return this.getChildrenNum() > 0;
    }
}

Representasi di atas saya bungkus ke dalam satu kelas bernama Node yang mewakili satu node pada struktur pohon N-ary. Untuk atribut, saya sesuaikan dengan kebutuhan terkait struktur data state pada 8-Puzzle yang sepertinya lebih cocok jika direpresentasikan dalam bentuk array of integer nodeState yang beranggotakan bilangan integer dari 0 sampai 8. Bilangan 0 mewakili kotak kosong atau blank, sedangkan bilangan lainnya mewakili kotak-kotak bernomor yang bersesuaian dengan bilangan tersebut. Serta nilai informasi menuju goal yang saya simpan pada atribut heuristicValue. Pembahasan mengenai nilai informasi ini akan diuraikan lebih dalam pada poin Informed Search.

Metodologi
Cara penyelesaian masalah dalam Searching, secara garis besar dibagi menjadi dua (2) metode, yaitu:
1. Pencarian dengan tanpa nilai informasi menuju kondisi akhir, biasa disebut sebagai Uninformed Search.
2. Pencarian yang memperhitungkan nilai informasi menuju kondisi yang diinginkan dan biasa disebut sebagai Informed Search.

…bersambung…

11 thoughts on “8-Puzzle Problem (Bagian 1)

  1. waduh, terlalu ribet pendahuluannya, langsung aja ada ga algoritma yang simple buat menyelesaikan puzzle ya, klo di saya itu nama nya kecerdasan tiruan, but itu sama aja…..

    Like

  2. mau Tanya, apakah tidak perlu menggunakan package pada saat koding di java atau iya? dan di situ terdapat import java util, itu bagian mana ya yg di import.. terimakasih

    Like

    1. Package tujuannya utk merapihkan kodingan. Selain itu, biar semakin terstruktur. Walaupun kita tidak membuat package, biasanya otomatis akan ada default package yang disediakan oleh Java. Untuk import, tidak selalu yang diimport adalah kelas/lib/package dari yang kita bikin. Bisa saja yang diimport adalah kelas/lib bawaan system. Salah satunya java.util.Vector seperti yang telah saya tulis pada contoh kode program di atas.🙂

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s