ALGORITMA BACKTRACKING

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.

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.

Baca juga: Apa Itu Search Engine Optimizer