8-Puzzle Problem (Bagian 2)

Bismillaah…

Menyambung postingan sebelumnya tentang 8-Puzzle Problem, kali ini akan saya lanjutkan dengan pembahasan detail mengenai metodologi yang digunakan dalam menyelesaikan permasalahan 8-Puzzle.

Di postingan sebelumnya telah disebutkan bahwa terdapat dua (2) metodologi dasar yang digunakan yaitu Blind Search dan Heuristic Search. Keduanya termasuk ke dalam jenis Pencarian atau Searching yang melibatkan pohon pencarian. Untuk yang Blind Search tidak akan saya bahas lebih lanjut karena secara prinsip cukup sederhana penalarannya. Sebagai contoh, sebut saja Depth First Search, yang termasuk ke dalam golongan Blind Search, hanya melakukan penelusuran terhadap pohon pencarian secara mendalam pada salah satu jalur pencarian hingga menemui solusi. Atau Breadth First Search yang hanya melakukan pencarian dengan menelusuri setiap level dari pohon pencarian. Untuk itu, sebelum kita melangkah ke pembahasan mengenai Heuristic Search, terlebih dahulu kita perlu tahu apa yang disebut sebagai heuristic itu sendiri.

Heuristic dalam konteks yang luas dapat didefinisikan sebagai suatu nilai informasi yang “dianggap” mendekati nilai solusi dari suatu permasalahan. Sebagai contoh, jika kita misalkan ada seseorang yang berada di Bandung hendak menuju Surabaya, lalu orang tersebut ingin mencari rute jalan darat terpendek yang dapat dilalui dari Bandung menuju Surabaya. Maka nilai heuristicnya bisa kita tentukan dari, misal jarak estimasi dari setiap titik keberangkatan menuju Surabaya berdasarkan jarak yang tertulis pada peta. Atau bisa saja nilai heuristicnya didasarkan pada jarak setiap titik keberangkatan terhadap stasiun kereta api terdekat. Yang jelas, nilai heuristic ini dapat sangat relatif berdasar penilaian masing-masing pembuat keputusan. Tapi perlu diingat, nilai heuristic ini digunakan dalam proses evaluasi setiap periode tertentu atau setiap titik evaluasi tertentu. Jadi sebisa mungkin nilai heuristic yang kita tentukan bersifat admissible atau dapat diterima secara semantik, baik karena kedekatannya dengan solusi maupun “masuk akal” dari sisi logika. Jika tidak demikian, maka bisa jadi bahwa proses pencarian yang kita lakukan malah akan menjauhkan kita dari solusi.

Pada 8-Puzzle Problem, kita juga dapat menentukan nilai heuristicnya. Namun agak berbeda dengan permasalahan bertipikal pencarian jarak terpendek, nilai heuristic pada 8-Puzzle langsung ditentukan berdasar kondisi kedekatannya dengan goal, karena kita tidak pernah tahu jarak atau langkah yang kira-kira dapat ditempuh dari state sekarang ke goalnya.

Pada berbagai referensi, ada beberapa nilai heuristic yang dapat dijadikan acuan untuk permasalahan 8-Puzzle. Salah satu yang cukup terkenal adalah Manhattan Distance. Manhattan Distance didefinisikan sebagai penjumlahan jarak masing-masing kotak 8-Puzzle terhadap posisinya yang benar pada kondisi goal. Sehingga, pada kondisi goal, heuristic pasti akan bernilai 0, karena semua kotak sudah pada posisinya masing-masing (jarak dengan posisinya yang benar = 0). Cara pendekatan seperti ini telah cukup dianggap admissible atau masuk akal. “Bagi yang mengatakan tidak masuk akal berarti akalnya belum masuk” by Jaya Setiabudi. 😀

Berikut adalah contoh perhitungan Manhattan Distance untuk suatu state terhadap kondisi goalnya.

Seperti telah dikatakan sebelumnya, bahwa penilaian heuristic ini sangat relatif berdasar cara penalaran si pembuat keputusan. Jadi, sebenarnya penilaian ini juga dapat disebut sebagai penerapan strategi untuk permasalahn 8-Puzzle. Semakin bagus strateginya, maka akan semakin mangkus jalur pencarian yang dihasilkan. Monggo… bagi yang mempunyai strategi lebih bagus daripada Manhattan Distance dapat dishare dengan saya. 🙂

Berikutnya, yang kita lakukan adalah menentukan metodologi atau algortima pencariannya. Dengan menentukan metodologi pencarian, berarti kita menentukan bagaimana proses evaluasi yang dilakukan, tentunya menggunakan penilaian heuristic yang telah kita tentukan. Ada banyak metodologi yang dapat diterapkan untuk permasalahan 8-Puzzle. Berikut ini akan saya bahas beberapa algoritma populer yang dapat diterapkan untuk mencari jalur langkah penyelesaian 8-Puzzle.

Hill Climbing
Algoritma Hill Climbing merupakan salah satu teknik optimasi matematis yang termasuk ke dalam kategori local search. Disebut local search karena hanya melakukan evaluasi terhadap kemungkinan-kemungkinan state yang saat ini sedang dihadapi. Ketika telah memilih salah satu state yang dianggap terbaik, maka Hill Climbing akan melanjutkan pencarian hanya berdasar state yang telah dipilih tersebut, hingga mencapai kondisi goalnya. Jadi, ketika telah dipilih satu jalur, maka jalur yang lain akan diabaikan. Itulah mengapa Hill Climbing sering dianggap sebagai cara pencarian heuristic yang tercepat, karena hanya melakukan simple evaluation terhadap beberapa kemungkinan state yang dianggap terbaik, lalu memilihnya, dan melupakan kemungkinan lain yang berada di luar kondisi evaluatifnya. Dengan bahasa awamnya, Hill Climbing ini adalah tipikal yang setia dalam melakukan pemilihan. 😀

Pada 8-puzzle, satu kali proses evaluasi menggunakan Hill Climbing hanya akan melibatkan maksimal 4 state untuk kondisi initial state, dan maksimal 3 state untuk kondisi state selain initial state. Sehingga state space untuk algoritma ini dapat dikatakan relatif sangat kecil. Berikut adalah contoh bagaimana algortima Hill Climbing dijalankan untuk suatu kasus state tertentu. Perlu diingat bahwa proses evaluasi yang dilakukan akan selalu mengambil nilai heuristic yang paling kecil.

Tetapi, Hill Climbing mempunyai dua (2) kelemahan:

• Plateau, kondisi ketika ada dua (2) atau lebih evaluation state yang mempunyai nilai heuristic sama besar dan juga merupakan nilai terbaik.
• Local Maxima, yaitu solusi lokal yang ditemukan dengan fungsi evaluasi. Tetapi solusi ini bukan kondisi goal yang diharapkan, dan jika dilakukan evaluasi secara terus menerus, maka akan kembali lagi ke kondisi solusi lokal itu sendiri. Karena memang fungsi evaluasi yang dilakukan menemui batasan pencarian lokal.

Untuk mengatasi kelemahan tersebut, ada strategi yang dapat diterapkan pada Hill Climbing agar solusi dapat ditemukan dengan baik. Strategi tersebut adalah:

• Untuk plateau cukup dapat diatasi dengan menerapkan aturan prioritas pergerakan kotak kosong. Misal, pergerakan kotak kosong ke atas adalah lebih diprioritaskan daripada pergerakan ke kiri, pergerakan kotak ke kiri lebih diprioritaskan daripada pergerakan ke kanan, dst.
• Sedangkan untuk local maxima, diperlukan lompatan besar (big jump) dengan memilih evaluation state yang lain ketika dalam kondisi local maxima. Big jump dapat diartikan dengan memilih state lain yang memiliki kedekatan heuristic dengan state terbaik, atau dengan cara melakukan pemilihan acak (random) terhadap state lainnya yang bukan terbaik.

Berikut adalah contoh implementasi algoritma Hill Climbing menggunakan bahasa pemrograman Java.

import java.util.Vector;
/**
 *
 * @author Andik Taufiq
 * Hill Climbing solver for 8 puzzle problem
 * March 18, 2010 - Bandung, Indonesia
 */
public class HillClimbing {
    public Vector trackNodes;
    private Node node;
    public int[] initialState;
    public int[] finalState;
    public String message = "";
    public HillClimbing(int[] initialState, int[] finalState) {
        this.initialState = initialState;
        this.finalState = finalState;
        trackNodes = new Vector();
        node = new Node(initialState, "");
        node.heuristicValue = heuristic(node.nodeState, finalState);
        trackNodes.addElement(node);
    }

    public String strArray(int[] array) {
        String temp = "[ ";
        for (int i = 0; i < array.length; i++) {
            temp = temp + Integer.toString(array[i]) + " ";
        }
        temp = temp + "]";
        return temp;
    }

    public String strSpecialArray(int[] array) {
        String temp = "+===+===+===+\n";
        String value = "";
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0)
                value = " ";
            else
                value = Integer.toString(array[i]);
            temp = temp + "| " + value + " ";
            if (i%3 == 2) {
                if (i < array.length - 1) {
                    temp = temp + "|\n+---+---+---+\n";
                } else {
                    temp = temp + "|\n";
                }
            }
        }
        temp = temp + "+===+===+===+\n";
        return temp;
    }

    private boolean hasSameElement(int[] state1, int[] state2) {
        boolean temp = true;
        int tempInt = 0;
        for (int i = 0; i < state1.length; i++) {
            if (state1[i] == state2[i])
                tempInt++;
        }
        if (tempInt == state1.length)
            temp = true;
        else
            temp = false;
        return temp;
    }

    private boolean hasSameElements(int[] state, Vector arrayOfNodes) {
        boolean temp = true;
        int i = 0;
        int counter = 0;
        Node tempNode;
        tempNode = new Node(state, "");
        for (i = 0; i < arrayOfNodes.size(); i++) {
            tempNode = (Node) arrayOfNodes.elementAt(i);
            if (!hasSameElement(state, tempNode.nodeState)) {
                counter++;
            }
        }
        if (counter == arrayOfNodes.size()) {
            temp = false;
        } else {
            temp = true;
        }
        return temp;
    }

    private int getMinVal(int[] array) {
        int tempIndex = 0;
        int tempValue = array[0];   // pre-assumed that array will never contains null value
        for (int i = 0; i  array[i]) {
                tempIndex = i;
                tempValue = array[i];
            }
        }
        return tempIndex;
    }

    private Node getTheBestNode(Vector childs) {
        int[] tempHeuristic = new int[childs.size()];
        for (int i = 0; i < childs.size(); i++) {
            tempHeuristic[i] = heuristic(((Node) childs.elementAt(i)).nodeState, finalState);
        }
        int tempIndex = getMinVal(tempHeuristic);
        return (Node) childs.elementAt(tempIndex);
    }

    public int[] moveLeft(int index, int[] state) {
        int[] tempState = new int[state.length];
        for (int i = 0; i < tempState.length; i++) {
            tempState[i] = state[i];
        }
        int temp = tempState[index-1];
        tempState[index-1] = 0;
        tempState[index] = temp;
        return tempState;
    }

    public int[] moveRight(int index, int[] state) {
        int[] tempState = new int[state.length];
        for (int i = 0; i < tempState.length; i++) {
            tempState[i] = state[i];
        }
        int temp = tempState[index+1];
        tempState[index+1] = 0;
        tempState[index] = temp;
        return tempState;
    }

    public int[] moveUp(int index, int[] state) {
        int[] tempState = new int[state.length];
        for (int i = 0; i < tempState.length; i++) {
            tempState[i] = state[i];
        }
        int temp = tempState[index-3];
        tempState[index-3] = 0;
        tempState[index] = temp;
        return tempState;
    }

    public int[] moveDown(int index, int[] state) {
        int[] tempState = new int[state.length];
        for (int i = 0; i < tempState.length; i++) {
            tempState[i] = state[i];
        }
        int temp = tempState[index+3];
        tempState[index+3] = 0;
        tempState[index] = temp;
        return tempState;
    }

    private Vector getPossibleChilds(Node parent, Node ancestor) {
        Node tempNode = new Node(parent.nodeState, "");
        Vector tempStates = new Vector();
        int[] tempState = new int[parent.nodeState.length];
        for (int i = 0; i < tempState.length; i++) {
            tempState[i] = parent.nodeState[i];
        }
        int index = 0;
        // locate the index of empty tile
        for (int i = 0; i < 9; i++) {
            if (tempState[i] == 0) {
                index = i;
            }
        }
        switch (index) {
            case 0:
                tempState = moveRight(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveLeft(index+1, tempState);
                tempState = moveDown(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 1:
                tempState = moveLeft(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveRight(index-1, tempState);
                tempState = moveRight(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveLeft(index+1, tempState);
                tempState = moveDown(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 2:
                tempState = moveLeft(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveRight(index-1, tempState);
                tempState = moveDown(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 3:
                tempState = moveUp(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveDown(index-3, tempState);
                tempState = moveRight(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveLeft(index+1, tempState);
                tempState = moveDown(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 4:
                tempState = moveUp(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveDown(index-3, tempState);
                tempState = moveLeft(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveRight(index-1, tempState);
                tempState = moveRight(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveLeft(index+1, tempState);
                tempState = moveDown(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 5:
                tempState = moveUp(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveDown(index-3, tempState);
                tempState = moveLeft(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveRight(index-1, tempState);
                tempState = moveDown(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 6:
                tempState = moveUp(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveDown(index-3, tempState);
                tempState = moveRight(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 7:
                tempState = moveUp(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveDown(index-3, tempState);
                tempState = moveLeft(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveRight(index-1, tempState);
                tempState = moveRight(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
            case 8:
                tempState = moveUp(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
                tempState = moveDown(index-3, tempState);
                tempState = moveLeft(index, tempState);
                if (!hasSameElement(tempState, ancestor.nodeState)) {
                    tempNode = new Node(tempState, "");
                    tempStates.addElement(tempNode);
                }
            break;
        }
        return tempStates;
    }

    public Node getLastNode(Vector trackNodes) {
        return (Node) trackNodes.elementAt(trackNodes.size()-1);
    }

    public void solveHillClimbing() {
        Node tempNode = new Node(initialState, "");
        Vector tempChilds = new Vector();
        tempChilds = getPossibleChilds((Node) trackNodes.elementAt(0),
                (Node) trackNodes.elementAt(0));
        tempNode = getTheBestNode(tempChilds);
        int i = 0;
        while (!hasSameElement(((Node) trackNodes.elementAt(i)).nodeState, finalState)) {
            if (hasSameElements(tempNode.nodeState, trackNodes) == false) {
                trackNodes.addElement(tempNode);
                if (!hasSameElement(tempNode.nodeState, finalState)) {
                    tempNode = new Node(tempNode.nodeState, "");
                    tempNode = getTheBestNode(getPossibleChilds((Node) trackNodes.elementAt(i+1),
                        (Node) trackNodes.elementAt(i)));
                }
                i++;
            } else {
                trackNodes.addElement(tempNode);
                message = "Local max at " + strArray(((Node) trackNodes.elementAt(i)).nodeState);
                i++;
                break;
            }
        }
    }

    private int getCol(int val) {
        return ((val/3)+1);
    }

    private int getRow(int val) {
        return ((val%3)+1);
    }

    private int stepCounter(int condition1, int condition2) {   
        return (Math.abs(getCol(condition1)-getCol(condition2)) +
                Math.abs(getRow(condition1)-getRow(condition2)));
    }

    public int heuristic(int[] currentState, int[] finalState) {
        int temp = 0;
        for (int i = 0; i < currentState.length; i++) {
            for (int j = 0; j < finalState.length; j++) {
                if (currentState[i] != 0) {
                    if (currentState[i] == finalState[j]) {
                        temp = temp + stepCounter(i, j);
                    }
                }
            }
        }
        return temp;
    }
}

Keterangan Kode Program:

• Kode program di atas membutuhkan kelas Node seperti yang telah saya tuliskan pada postingan sebelumnya.
• Komponen masukan untuk penyelesaian dalam algoritma adalah berupa atribut initalState dan finalState.
• Penghitungan nilai heuristic diterapkan pada method heuristic().
• Langkah penyelesaian diimplementaskan pada method solveHillClimbing().
• Sehingga diperoleh hasil solusi yang ditampung pada trackNodes. Isi dari trackNodes ini dapat digunakan, baik untuk ditampilkan dengan GUI maupun dengan text mode.

Untuk program drivernya, saya berikan kebebasan bagi Anda untuk berkreasi. 😀

bersambung…