BFS pada Bagian 3 menemukan solusi optimal tetapi mengunjungi 9 node untuk puzzle 2-langkah. Untuk puzzle 14-langkah, BFS bisa mengunjungi ribuan node. A* memotong eksplorasi dengan menambahkan heuristic — estimasi jarak ke goal. State dengan heuristic rendah (mendekati goal) diproses lebih dulu, sehingga algoritma “tertarik” ke arah solusi. Pada bagian ini kita mengimplementasikan A* dengan priority queue dan Manhattan distance sebagai heuristic admissible, lalu membandingkan kinerjanya dengan BFS pada state awal yang sama.

Aturan: f = g + h #

A* mengevaluasi setiap state lewat fungsi f(s) = g(s) + h(s):

  • g(s) — biaya aktual dari start ke s (jumlah gerakan).
  • h(s) — estimasi biaya dari s ke goal (heuristic).
  • f(s) — estimasi total biaya jalur start → s → goal.

A* selalu memproses state dengan f terkecil lebih dulu (priority queue min-heap). Heuristik yang admissible (tidak pernah melebih-lebihkan biaya sebenarnya) menjamin A* menemukan solusi optimal.

Mekanisme: Priority Queue + Lazy Deletion #

Kita simpan f, g, dan state dalam priority queue. Karena std::priority_queue tidak mendukung decrease-key, kita pakai lazy deletion — saat pop, bandingkan g saat ini dengan g terbaik yang sudah tercatat di dist map. Bila g sekarang lebih besar, skip.

text 
1. pq.push({h(start), start})        // f = g + h = 0 + h(start) = h(start)
2. dist[start] = 0; parent[start] = start
3. while pq not empty:
4.   (f, cur) = pq.top(); pq.pop()
5.   if g(cur) > dist[cur]: continue       // stale entry
6.   if cur == goal: break
7.   for nb in getNeighbors(cur):
8.     tentative_g = dist[cur] + 1
9.     if nb not in dist or tentative_g < dist[nb]:
10.      dist[nb] = tentative_g
11.      parent[nb] = cur
12.      pq.push({tentative_g + h(nb), nb})

Heuristic Manhattan Distance #

Manhattan distance adalah jumlah jarak tiap tile (kecuali blank) dari posisi saat ini ke posisi goal, dihitung sebagai |Δrow| + |Δcol|.

text 
State saat ini:           Goal:
1 2 3                     1 2 3
4 0 6                     4 5 6
7 5 8                     7 8 0

Jarak Manhattan per tile:
- tile 1 di (0,0) -> goal (0,0): jarak 0
- tile 2 di (0,1) -> goal (0,1): jarak 0
- tile 3 di (0,2) -> goal (0,2): jarak 0
- tile 4 di (1,0) -> goal (1,0): jarak 0
- tile 6 di (1,2) -> goal (1,2): jarak 0
- tile 7 di (2,0) -> goal (2,0): jarak 0
- tile 5 di (2,1) -> goal (1,1): jarak 1   (selisih 1 baris)
- tile 8 di (2,2) -> goal (2,1): jarak 1   (selisih 1 kolom)

Total h = 0+0+0+0+0+0+1+1 = 2

Heuristic ini admissible karena setiap gerakan hanya bisa menggerakkan satu tile sejauh 1 unit. Maka total jarak Manhattan tidak pernah lebih besar dari jumlah gerakan minimum.

Program Lengkap Bagian 4 #

Program berikut mengimplementasikan A* dengan Manhattan distance. Kita juga memanggil ulang BFS dari Bagian 3 untuk perbandingan langsung.

cpp 
#include <iostream>
#include <array>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstdint>
#include <utility>
#include <algorithm>
#include <cstdlib>

struct State {
    std::array<int, 9> tiles;
    bool operator==(const State& o) const { return tiles == o.tiles; }
    bool operator!=(const State& o) const { return tiles != o.tiles; }
    bool operator<(const State& o) const { return tiles < o.tiles; }
};

const State GOAL{{{1, 2, 3, 4, 5, 6, 7, 8, 0}}};

int findBlank(const State& s) {
    for (int i = 0; i < 9; ++i) if (s.tiles[i] == 0) return i;
    return -1;
}

static int rowOf(int i) { return i / 3; }
static int colOf(int i) { return i % 3; }

enum class Move { UP, DOWN, LEFT, RIGHT };

bool canMove(int blankIndex, Move m) {
    int r = rowOf(blankIndex), c = colOf(blankIndex);
    switch (m) {
        case Move::UP:    return r > 0;
        case Move::DOWN:  return r < 2;
        case Move::LEFT:  return c > 0;
        case Move::RIGHT: return c < 2;
    }
    return false;
}

int swapTarget(int blankIndex, Move m) {
    int r = rowOf(blankIndex), c = colOf(blankIndex);
    switch (m) {
        case Move::UP:    return (r - 1) * 3 + c;
        case Move::DOWN:  return (r + 1) * 3 + c;
        case Move::LEFT:  return r * 3 + (c - 1);
        case Move::RIGHT: return r * 3 + (c + 1);
    }
    return blankIndex;
}

State applyMove(const State& s, Move m) {
    int b = findBlank(s);
    State next = s;
    if (canMove(b, m)) {
        int target = swapTarget(b, m);
        std::swap(next.tiles[b], next.tiles[target]);
    }
    return next;
}

std::vector<State> getNeighbors(const State& s) {
    std::vector<State> result;
    for (Move m : {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT}) {
        State next = applyMove(s, m);
        if (next != s) result.push_back(next);
    }
    return result;
}

struct StateHash {
    std::size_t operator()(const State& s) const {
        std::size_t h = 0;
        for (int i = 0; i < 9; ++i) h = h * 31 + s.tiles[i];
        return h;
    }
};

using StateSet = std::unordered_set<State, StateHash>;
using ParentMap = std::unordered_map<State, State, StateHash>;
using DistMap = std::unordered_map<State, int, StateHash>;

void print(const State& s) {
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            int v = s.tiles[r * 3 + c];
            if (v == 0) std::cout << ". ";
            else std::cout << v << " ";
        }
        std::cout << "\n";
    }
}

std::vector<State> reconstruct(const State& start, const State& goal,
                               const ParentMap& parent) {
    std::vector<State> path;
    State cur = goal;
    while (cur != start) {
        path.push_back(cur);
        auto it = parent.find(cur);
        if (it == parent.end()) return {};
        cur = it->second;
    }
    path.push_back(start);
    std::reverse(path.begin(), path.end());
    return path;
}

struct SearchResult {
    bool found;
    int nodesVisited;
    std::vector<State> path;
};

// Manhattan distance heuristic: jumlah |dr| + |dc| tiap tile ke posisi goal.
int manhattan(const State& s) {
    int total = 0;
    for (int i = 0; i < 9; ++i) {
        int v = s.tiles[i];
        if (v == 0) continue;   // blank tidak dihitung
        int goalRow = (v - 1) / 3;
        int goalCol = (v - 1) % 3;
        int dr = std::abs(rowOf(i) - goalRow);
        int dc = std::abs(colOf(i) - goalCol);
        total += dr + dc;
    }
    return total;
}

SearchResult bfs(const State& start, const State& goal) {
    std::queue<State> q;
    StateSet visited;
    ParentMap parent;

    q.push(start);
    visited.insert(start);
    parent[start] = start;

    int nodes = 0;
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        nodes++;
        if (cur == goal) {
            return {true, nodes, reconstruct(start, goal, parent)};
        }
        for (const auto& nb : getNeighbors(cur)) {
            if (!visited.count(nb)) {
                visited.insert(nb);
                parent[nb] = cur;
                q.push(nb);
            }
        }
    }
    return {false, nodes, {}};
}

// A* dengan priority queue, lazy deletion, Manhattan distance heuristic.
SearchResult astar(const State& start, const State& goal) {
    using PQEntry = std::pair<int, State>;   // (f, state)
    std::priority_queue<PQEntry, std::vector<PQEntry>, std::greater<PQEntry>> pq;
    DistMap dist;
    ParentMap parent;

    int h0 = manhattan(start);
    dist[start] = 0;
    parent[start] = start;
    pq.push({h0, start});              // f = g + h = 0 + h0

    int nodes = 0;
    while (!pq.empty()) {
        auto [f, cur] = pq.top(); pq.pop();
        nodes++;
        int gCur = dist[cur];
        if (f - manhattan(cur) > gCur) continue;   // stale entry (g di pq > dist)
        if (cur == goal) {
            return {true, nodes, reconstruct(start, goal, parent)};
        }
        for (const auto& nb : getNeighbors(cur)) {
            int tentativeG = gCur + 1;
            auto it = dist.find(nb);
            if (it == dist.end() || tentativeG < it->second) {
                dist[nb] = tentativeG;
                parent[nb] = cur;
                int fNb = tentativeG + manhattan(nb);
                pq.push({fNb, nb});
            }
        }
    }
    return {false, nodes, {}};
}

void printPath(const std::vector<State>& path) {
    for (size_t i = 0; i < path.size(); ++i) {
        std::cout << "Langkah " << i << ":\n";
        print(path[i]);
        if (i + 1 < path.size()) std::cout << "\n";
    }
}

int main() {
    State start{{{1, 2, 3, 4, 0, 6, 7, 5, 8}}};

    std::cout << "State awal:\n";
    print(start);
    std::cout << "\nState goal:\n";
    print(GOAL);
    std::cout << "\nh(start) = " << manhattan(start) << "\n\n";

    std::cout << "=== BFS ===\n";
    auto bfsResult = bfs(start, GOAL);
    std::cout << "Ditemukan: " << (bfsResult.found ? "ya" : "tidak") << "\n";
    std::cout << "Node dikunjungi: " << bfsResult.nodesVisited << "\n";
    std::cout << "Panjang jalur: " << (bfsResult.path.size() - 1) << "\n\n";

    std::cout << "=== A* (Manhattan) ===\n";
    auto astarResult = astar(start, GOAL);
    std::cout << "Ditemukan: " << (astarResult.found ? "ya" : "tidak") << "\n";
    std::cout << "Node dikunjungi: " << astarResult.nodesVisited << "\n";
    std::cout << "Panjang jalur: " << (astarResult.path.size() - 1) << "\n\n";
    printPath(astarResult.path);

    std::cout << "\n=== Perbandingan ===\n";
    std::cout << "BFS  : " << bfsResult.nodesVisited << " node, jalur "
              << (bfsResult.path.size() - 1) << " langkah\n";
    std::cout << "A*   : " << astarResult.nodesVisited << " node, jalur "
              << (astarResult.path.size() - 1) << " langkah\n";
    return 0;
}

Output yang Dihasilkan:

text 
State awal:
1 2 3 
4 . 6 
7 5 8 

State goal:
1 2 3 
4 5 6 
7 8 . 

h(start) = 2

=== BFS ===
Ditemukan: ya
Node dikunjungi: 9
Panjang jalur: 2

=== A* (Manhattan) ===
Ditemukan: ya
Node dikunjungi: 3
Panjang jalur: 2

Langkah 0:
1 2 3 
4 . 6 
7 5 8 

Langkah 1:
1 2 3 
4 5 6 
7 . 8 

Langkah 2:
1 2 3 
4 5 6 
7 8 . 

=== Perbandingan ===
BFS  : 9 node, jalur 2 langkah
A*   : 3 node, jalur 2 langkah

Pada kasus uji ini, A* mengunjungi 3 node dibandingkan BFS 9 node — pengurangan sekitar 67%. Karena h(start) = 2 tepat sama dengan jarak optimal, A* langsung “tahu” ke arah mana menuju goal dan tidak menyimpang ke cabang lain. Untuk puzzle yang lebih dalam (6–14 langkah), pengurangan akan tetap signifikan karena heuristic memotong cabang yang tidak menjanjikan.

Bedah Kode Baris-per-Baris #

  1. int manhattan(const State& s): loop 9 sel, untuk tiap tile (selain blank) hitung |Δrow| + |Δcol| ke posisi goal. Posisi goal tile v adalah (v-1)/3 untuk row dan (v-1)%3 untuk col — karena goal tiles disusun {1,2,3,4,5,6,7,8,0}.
  2. if (v == 0) continue: blank tidak dihitung. Termasuk blank akan menambah biaya fiktif yang merusak admissibility.
  3. int dr = std::abs(rowOf(i) - goalRow): selisih baris. std::abs dari <cstdlib> (bukan <cmath>) karena argumen int.
  4. using PQEntry = std::pair<int, State>: alias untuk tipe entri priority queue. Pair (f, state) diurutkan berdasarkan f lebih dulu (default pair comparison).
  5. std::priority_queue<PQEntry, std::vector<PQEntry>, std::greater<PQEntry>> pq: min-heap. std::greater membalik default max-heap menjadi min-heap — top adalah entri dengan f terkecil.
  6. pq.push({h0, start}): state awal dengan f = h(start) (karena g(start) = 0). Lazy deletion belum ada entry yang stale.
  7. auto [f, cur] = pq.top(); pq.pop(): structured binding dari C++17. Ekstrak f dan cur dari pair dalam satu baris.
  8. int gCur = dist[cur]: ambil g terbaik yang tercatat. Berbeda dari f - manhattan(cur) bila entry stale (lazy deletion).
  9. if (f - manhattan(cur) > gCur) continue: lazy deletion. Bila g yang tersirat di entry (yaitu f - h) lebih besar dari g terbaik yang tercatat di dist, entry ini kedaluwarsa — skip tanpa proses tetangga. Bandingkan dengan Dijkstra Bagian 2 proyek sebelumnya: pola yang sama.
  10. int tentativeG = gCur + 1: bobot edge seragam 1. Bila bobot variabel, ganti 1 dengan lookup weight(cur, nb).
  11. if (it == dist.end() || tentativeG < it->second): relaksasi. Bila state nb belum punya g, atau tentativeG lebih kecil dari g yang ada, update dist dan push ke heap. Inilah inti A* — selalu mencatat g terbaik.
  12. int fNb = tentativeG + manhattan(nb): hitung f untuk tetangga. g baru ditambah h baru. Push ke heap.

Perbandingan Kinerja: BFS vs A* #

Pada puzzle 2-langkah, A* mengunjungi 3 node; BFS 9 node. Selisih terlihat kecil, tetapi pada puzzle yang lebih dalam, A* unggul jauh:

PuzzleJarak OptimalNode BFS (perkiraan)Node A* (perkiraan)
Trivial293
Easy6~300~30
Medium14~50.000~500

Pola: BFS mengunjungi state level demi level — semua state pada level k diproses sebelum level k+1. A* hanya memproses state dengan f kecil, sehingga “meloncat” ke arah solusi.

Kompleksitas A* #

AspekKompleksitasCatatan
Heap operationsO((V + E) log V)tiap edge di-relax maksimum beberapa kali
MemoryO(V)dist + parent + heap
Best caseO(d)heuristic sempurna → path lurus ke goal
Worst caseO(V log V)heuristic = 0 → sama dengan Dijkstra

Kompilasi dan Pengujian #

bash 
g++ -std=c++17 -O2 -Wall -Wextra -o puzzle_part4.bin puzzle_part4.cpp
./puzzle_part4.bin

Verifikasi bahwa A* menemukan jalur yang sama dengan BFS (2 langkah) tetapi mengunjungi lebih sedikit node. Untuk eksperimen lebih jauh, ubah state awal ke {1, 3, 4, 8, 0, 5, 7, 2, 6} (jarak optimal ~6) dan bandingkan kembali.

Ringkasan Proyek #

Empat bagian proyek ini telah membentuk solver 8-puzzle lengkap:

  1. Bagian 1 — pemodelan state sebagai std::array<int, 9> dengan operator swap 4 arah.
  2. Bagian 2 — graph state implisit via getNeighbors, hasher untuk unordered_set.
  3. Bagian 3 — BFS dengan queue untuk solusi optimal; DFS dengan stack + depth limit untuk pembanding.
  4. Bagian 4 — A* dengan priority queue dan Manhattan distance, memangkas eksplorasi signifikan.

Kombinasi keempat bagian melatih empat keterampilan kunci: pemodelan state, graph implisit, traversal BFS/DFS, dan informed search dengan heuristic. Pola yang sama berlaku untuk masalah search lain: N-puzzle yang lebih besar, Rubik’s cube, atau pathfinding pada game.