MAKALAH ALGORITMA BACK TRACKING

BAB I
PENDAHULUAN

1.1  LATAR BELAKANG

Di dalam kehidupannya, manusia selalu menemui masalah atau persoalan. Hal ini mungkin didasarkan dari sifat dasar manusia itu sendiri yang selalu ingin tahu segala sesuatu.

Dalam menghadapi permasalahan, untuk menyelesaikannya manusia memerlukan langkah-langkah yang benar sehingga permasalah tersebut dapat terselesaikan. Urutan langkah-langkah untuk memecahkan suatu masalah tersebutlah yang dinamakan dengan algoritma. Definisi lain dari algoritma adalah deretan langkah-langkah komputasi yang mentranformasikan data masukan menjadi keluaran.

Dalam menentukan langkah-langkah tersebut diperlukan suatu strategi agar langkah-langkah yang dipakai tersebut dapat menyelesaikan permasalahan secara mangkus (efisien). Strategi menurut kamus besar bahasa indonesia adalah rencana yang cermat mengenai kegiatan untuk mencapai sasaran khusus. Rencana itu sendiri dapat berisi suatu metode atau teknik yang digunakan untuk mencapai sasaran khusus tersebut.

Dengan pengertian algoritma dan strategi tersebut, kita dapat mendefinisikan strategi algoritmik sebagai kumpulan metode atau teknik untuk memecahkan masalah guna mencapai tujuan yang ditentukan, yang dalam hal ini deskripsi metode atau teknik tersebut dinyatakan dalam suatu urutan langkah-langkah penyelesaian.

Secara umum, strategi pemecahan masalah dapat dikelompokan menjadi:

1.      Strategi solusi langsung, metode yang termasuk ke dalam strategi ini adalah: Algoritma Brute Force dan Algoritma Greedy

2.      Strategi berbasis pencarian pada ruang status, metode yang termasuk ke dalam strategi ini adalah: Algoritma Backtracking dan Algoritma Brach and Bound

3.      Strategi solusi atas-bawah, metode yang termasuk ke dalam strategi ini adalah Algoritma Divide and Conquer.

4.      Strategi solusi bawah-atas, metode yang termasuk ke dalam strategi ini adalah Dynamic Programming.

Strategi yang akan dibahas pada makalah ini adalah strategi berbasis pencarian pada ruang status. Secara spesifik, metode yang dibahas adalah Algoritma runut balik (backtracking). Permasalahan ini akan dibahas lebih lanjut dalam bab selanjutnya.

1.2  RUMUSAN MASALAH

Dari latar belakang yang telah diuraikan, maka timbul beberapa pertanyaan yang merupakan rumusan masalah, yakni sebagai berikut:

1.      Bagaimana prosedur penyelesaian algoritma backtracking?

2.      Bagaimana implementasi dari algoritma backtracking?

3.      Bagaimana kompleksitas dari algoritma backtracking?

1.3  TUJUAN

Adapun tujuan dari dibuatnya makalah ini adalah :

1.      Menganalisis kompleksitas yang dimiliki oleh algoritma runut balik (backtracking).

2.      Menganalisis prosedur algoritma dalam algoritma runut balik (backtracking).

3.      Menganalisis implementasi algoritma runut balik (backtracking).

1.4  MANFAAT

Adapun maanfaat dari dibuatnya makalah ini adalah:

1.         Lebih  mengetahui tentang algoritma backtraking

2.         Dapat menganalisa kompleksitas waktu dari algoritma backtraking

3.         Mengetahui implementasi dari algoritma backtraking

BAB II
LANDASAN TEORI

2.1 Algoritma Backtraking

Algoritma backtracking merupakan salah satu metode pemecahan masalah yang termasuk dalam strategi yang berbasis pencarian pada ruang status. Algoritma backtracking bekerja secara rekursif dan melakukan pencarian solusi persoalan secara sistematis pada semua kemungkinan solusi yang ada. Oleh karena algoritma ini berbasis pada algoritma Depth-First Search (DFS), maka pencarian solusi dilakukan dengan menelusuri struktur berbentuk pohon berakar secara preorder. Algoritma backtracking merupakan bentuk tipikal  dari algoritma rekursif.Saat ini algoritma backtracking banyak diterapkan untuk program games (seperti permainan tic-tac-toe, menemukan jalan keluar dalam sebuah labirin, catur, dll) dan masalah-masalah  pada bidang kecerdasan buatan (artificial intelligence).

2.2 Algoritma Depth-First Search (DFS)

Algoritma Depth First Search (DFS) adalah salah satu algoritma pencarian solusi yang digunakan di dalam kecerdasan buatan. Algoritma ini termasuk salah satu jenis uninformed algorithm yaitu algoritma yang melakukan pencarian dalam urutan tertentu tetapi tidak memiliki informasi apa-apa sebagai dasar pencarian kecuali hanya mengikuti pola yang diberikan. Di dalam DFS, pencarian dilakukan pada suatu struktur pohon yaitu kumpulan semua kondisi yang mungkin yang diimplementasikan dalam sebuah struktur pohon. Paling atas adalah akar (root) yang berisi kondisi awal pencarian (initial state) dan di bawahnya adalah kondisi-kondisi berikutnya sampai kepada kondisi tujuan (goal state).

BAB III
PEMBAHASAN SOAL

3.1 Properti Umum Metode runut balik (Backtracking)

            Untuk menerapkan metode runut-balik, properti berikut didefinisikan:

1.      Solusi persoalan.

Solusi dinyatakan sebagai vektor n-tuple:

X=(x1, x2, ..., xn), xi anggota himpunan berhingga Si .

Mungkin saja S1 = S2 = ... = Sn.

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.

3.2 Pengorganisasian Solusi

Semua kemungkinan solusi dari persoalan disebut ruang solusi (solution space).

Jika x_i Î S_i, maka  S₁ ´ S₂ ´ … ´ S_n  disebut ruang solusi. Jumlah anggota di dalam ruang solusi adalah | S₁| × | S₂| × … × | S_n |. Tinjau persoalan Knapsack 0/1 untuk n = 3. Solusi persoalan dinyatakan sebagai vektor (x₁, x₂, x₃) dengan x_i Î {0,1}.  Ruang solusinya adalah

{0,1} ´ {0,1} ´ {0,1} = {(0, 0, 0),  (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1),

    (0, 1, 1), (1, 1, 1)}.    

Pada persoalan Knapsack 0/1 dengan n = 3 terdapat 2ⁿ = 2³ = 8 kemungkinan solusi,  yaitu:

(0, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 0), (1, 1, 0), (1, 0, 1), (0, 1, 1), dan (1, 1, 1).

Penyelesaian secara exhaustive search adalah dengan menguji setiap kemungkinan solusi.  Ruang solusi diorganisasikan ke dalam struktur pohon. Tiap simpul pohon menyatakan status (state) persoalan, sedangkan sisi (cabang) dilabeli dengan nilai-nilai x_i. Lintasan dari akar ke daun menyatakan solusi yang mungkin. Seluruh lintasan dari akar ke daun membentuk ruang solusi. Pengorganisasian pohon ruang solusi diacu sebagai pohon ruang status (state space tree). Tinjau kembali persoalan Knapsack 1/0 untuk n = 3. Ruang solusinya: 

Gambar  Ruang solusi untuk persoalan Knapsack 0/1 dengan n = 3

3.3 Prinsip Pencarian Solusi dengan Metode Runut Balik

      Langkah-langkah pencarian solusi dengan metode runut balik adalah sebagai berikut:

1.      Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan yang dipakai adalah mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidup dan simpul hidup yang sedang diperluas dinamakan simpul-E. Simpul dinomori dari atas ke bawah sesuai dengan kelahirannya.

2.      Jika lintasan yang diperluas yang sedang dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Simpul yang sudah mati ini tidak akan diperluas lagi.

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

4.      Pencarian dihentikan bila telah ditemukan solusi atau tidak ada lagi simpul hidup untuk runut balik (backtracking).

Tinjau persoalan Knapsack 0/1 dengan instansiasi:

            n = 3

            (w₁, w₂, w₃) = (35, 32, 25)

            (p₁, p₂, p₃) = (40, 25, 50)

            M = 30

Solusi dinyatakan sebagai X = (x₁, x₂, x₃), x_i Î {0, 1}.

Fungsi pembatas:

Gambar (a) Pohon dinamis yang dibentuk selama pencarian untuk persoalan Knapsack 0/1 dengan n = 3,

w = (35, 32, 25) dan p = (40, 25, 50)

(b) Penomoran ulang simpul-simpul sesuai urutan pembangkitannya

Solusi optimumnya adalah X = (0, 0, 1) dan F =  50.

Berikut adalah skema umum algoritma backtraking :

Jika jumlah simpul dalam pohon ruang status adalah 2ⁿ atau n!, maka untuk kasus terburuk, algoritma runut-balik membutuhkan waktu dalam O(p(n)2ⁿ) atau O(q(n)n!), dengan p(n) dan q(n) adalah polinom derajat n yang menyatakan waktu komputasi setiap simpul.

3.4  Implementasi Algoritma Backtraking

Algoritma backtracking merupakan bentuk tipikal  dari algoritma rekursif. Saat ini algoritma backtracking banyak diterapkan untuk program games seperti salah satunya adalah maze labirin. Dan pewarnaan graf.

3.4.1        Maze Labirin

Contoh (Maze problem): diberikan sebuah labirin (maze), temukan lintasan dari titik awal sampai titik akhir

Pada tiap perpotongan, anda harus memutuskan satu diantara tiga pilihan yaitu maju terus, belok kiri, belok kanan.  Anda tidak punya cukup informasi untuk memilih pilihan yang benar (yang mengarah ke titik akhir). Tiap pilihan mengarah ke sekumpulan pilihan lain. Satu atau lebih sekuens pilihan mengarah ke solusi. Backtracking (runut-balik) dapat digunakan untuk  persoalan seperti ini.

Skema algoritma backtracking

Contoh runut-balik pada sebuah labirin. Runut-balik diperlihatkan dengan garis putus-putus.

Penyelesaian dengan bactracking: Bagi lintasan menjadi sederetan langkah. Sebuah langkah terdiri dari pergerakan satu unit sel pada arah tertentu. Arah yang mungkin: lurus (straight), kiri (left), ke kanan (right). Secaara garis besar algoritmanya adalah sebagai berikut:

Jika kita menggambarkan sekuens pilihan yang kita lakukan, maka diagram berbentuk  seperti pohon.

3.2.2        Pewarnaan Graf (Graph Colouring)

Persoalan:

Diberikan sebuah graf G dengan n buah simpul dan disediakan m buah warna. Bagaimana mewarnai seluruh simpul graf G sedemikian sehingga tidak ada dua buah simpul bertetangga yang mempunyai warna sama (Perhatikan juga bahwa tidak seluruh warna harus dipakai)

Contoh aplikasi: pewarnaan peta:

Tinjau untuk n = 3 dan m = 3.

Misalkan warna dinyatakan dengan angka 1, 2, …, m dan solusi dinyatakan sebagai vektor X dengan n-tuple:
X = (x₁ , x₂ , ..., x_n ) ,    x_i Î { 1, 2, …, m}

 Algoritmanya adalah sebagai berikut :

            Kompleksitas Waktu algoritma PewarnaanGraf:

Pohon ruang status yang untuk persoalan pewarnaan graf dengan n simpul dan m warna adalah pohon m-ary dengan tinggi n + 1.

Tiap simpul pada aras i mempunyai m anak, yang bersesuaian dengan m kemungkinan pengisian  x[i], 1 £ i £ n.

BAB IV

KESIMPULAN

Algoritma backtrack sangat berguna untuk mencari solusi-solusi jumlah kombinasi jalan yang diperlukan untuk mencari solusi tersebut selalu berubah terhadap waktu ataupun respon user (dinamik). Dalam penerapannya algoritma backtrack juga mudah diimplementasikan dengan bahasa pemograman yang sudah mendukung pemanggilan fungsi atau prosedur secara rekursif. Untuk masalahmasalah yang mempunyai kemungkinan solusi yang kompleks, seperti permainan catur, sebaiknya kedalaman pohon dibatasi sehingga tidak menghabiskan waktu yang sangat lama (tentu saja batas kedalaman pohon ini relatif - bergantung pada kecepatan cycle clock prosesor yang tersedia). Secara umum, semakin dalam pohon yang ditelusuri, semakin akurat pula jalan menuju solusi (dalam hal board games maka tingkat kesulitan AI semakin bertambah). Untuk alokasi memori yang akan dipakai untuk menyimpan jalan solusi sebaiknya menggunakan dynamic array mengingat sebagian besar program yang menggunakan algoritma ini menghasilkan solusi yang tidak dapat diprediksi berhubung dengan sifat program yang akan sangat bergantung pada state program yang berubah setiap saat. Saran akhir dalam penggunaan algoritma backtrack, sebagaimana dengan algoritma-algoritma yang lain adalah kombinasikan dengan algoritma yang lain. Beberapa metoda dari exhaustive search bisa digunakan untuk menentukan apakah solusi yang sedang dijelajahi (explore) menuju ke solusi yang diharapkan