Algoritma greedy dan Algoritma Brute force

Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah local maximum. Pada kebanyakan kasus, algoritma greedy tidak akan menghasilkan solusi paling optimal, begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Sebagai contoh dari penyelesaian masalah dengan algoritma greedy, mari kita lihat sebuah masalah klasik yang sering dijumpai dalam kehidupan sehari-hari: mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta:

Jalur dari Titik A ke B

Dari peta yang ditampilkan di atas, dapat dilihat bahwa terdapat beberapa jalur dari titik A ke titik B. Sistem peta pada gambar secara otomatis telah memilih jalur terpendek (berwarna biru). Kita akan mencoba mencari jalur terpendek juga, dengan menggunakan algoritma greedy.

Langkah pertama yang harus kita lakukan tentunya adalah memilih struktur data yang tepat untuk digunakan dalam merepresentasikan peta. Jika dilihat kembali, sebuah peta seperti pada gambar di atas pada dasarnya hanya menunjukkan titik-titik yang saling berhubungan, dengan jarak tertentu pada masing-masing titik tersebut. Misalnya, peta di atas dapat direpresentasikan dengan titik-titik penghubung seperti berikut:

Graph Sederhana dari Titik A ke B

Dari gambar di atas, kita dapat melihat bagaimana sebuah peta jalur perjalanan dapat direpresentasikan dengan menggunakan graph, spesifiknya Directed Graph (graph berarah). Maka dari itu, untuk menyelesaikan permasalahan jarak terpendek ini kita akan menggunakan struktur data graph untuk merepresentasikan peta. Berikut adalah graph yang akan digunakan:

Graph Berarah dari Titik A ke B

Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:

1. Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.
2. Cari local maximum ke titik selanjutnya.
3. Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan.
4. Kembali ke langkah 1 sampai titik tujuan didapatkan.

Jika mengapliikasikan langkah-langkah di atas pada graph A ke B sebelumnya maka kita akan mendapatkan pergerakan seperti berikut:

1. Mulai dari titik awal (A). Ambil seluruh titik yang dapat dikunjungi.

Langkah Pertama Greedy

2. Local maximum adalah ke C, karena jarak ke C adalah yang paling dekat.
3. Tandai A sebagai titik yang telah dikunjungi, dan pindah ke C.
4. Ambil seluruh titik yang dapat dikunjungi dari C.

Langkah Kedua Greedy

5. Local maximum adaah ke D, dengan jarak 6.
6. Tandai C sebagai titik yang telah dikunjungi, dan pindah ke D.

Langkah Ketiga Greedy

7. (Langkah selanjutnya diserahkan kepada pembaca sebagai latihan).

Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximumpada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma greedy dapat memberikan solusi yang kurang optimal:

Solusi Kurang Optimal dari Greedy

Tetapi ingat bahwa untuk kasus umum, kerap kali algoritma greedy memberikan hasil yang cukup baik dengan kompleksitas waktu yang cepat. Hal ini mengakibatkan algoritma greedy sering digunakan untuk menyelesaikan permasalahan kompleks yang memerlukan kecepatan jawaban, bukan solusi optimal, misalnya pada game.

Implementasi Algoritma Greedy

Untuk memperdalam pengertian algoritma greedy, kita akan mengimplementasikan algoritma yang telah dijelaskan pada bagian sebelumnya ke dalam kode program. Seperti biasa, contoh kode program akan diberikan dalam bahasa pemrograman python. Sebagai langkah awal, tentunya kita terlebih dahulu harus merepresentasikan graph. Pada implementasi yang kita lakukan, graph direpresentasikan dengan menggunakan dictionary di dalam dictionary, seperti berikut:

DAG = {'A': {'C': 4, 'G': 9}, 'G': {'E': 6}, 'C': {'D': 6, 'H': 12}, 'D': {'E': 7}, 'H': {'F': 15}, 'E': {'F': 8}, 'F': {'B': 5}}

# Hasil Representasi:

{'A': {'C': 4, 'G': 9},

 'C': {'D': 6, 'H': 12},

 'D': {'E': 7},

 'E': {'F': 8},

 'F': {'B': 5},

 'G': {'E': 6},

 'H': {'F': 15}}

Selanjutnya kita akan membuat fungsi yang mencari jarak terpendek dari graph yang dibangun, dengan menggunakan algoritma greedy. Definisi dari fungsi tersebut sangat sederhana, hanya sebuah fungsi yang mengambil graph, titik awal, dan titik akhir sebagai argumennya:

def shortest_path(graph, source, dest):

Jarak terpendek yang didapatkan akan dibangun langkah demi langkah, seperti pada algoritma greedy yang mengambil nilai local maximum pada setiap langkahnya. Untuk hal ini, tentunya kita akan perlu menyimpan jarak terpendek ke dalam sebuah variabel, dengan source sebagai isi awal variabel tersebut. Jarak terpendek kita simpan ke dalam sebuah list, untuk menyederhanakan proses penambahan nilai.

result = []

result.append(source)

Penelusuran graph sendiri akan kita lakukan melalui result, karena variabel ini merepresentasikan seluruh node yang telah kita kunjungi dari keseluruhan graph. Variabel result pada dasarnya merupakan hasil implementasi dari langkah 3 algoritma (“Tandai graph sekarang sebagai graph yang telah dikunjungi”). Titik awal dari rute tentunya secara otomatis ditandai sebagai node yang telah dikunjungi.

Selanjutnya, kita akan menelusuri graph sampai titik tujuan ditemukan, dengan menggunakan iterasi:

while dest not in result:

    current_node = result[-1]

dengan mengambil node yang sekarang sedang dicari local maximum-nya dari isi terakhir result. Pencarian local maximum sendiri lebih memerlukan pengetahuan python daripada algoritma:

# Cari local maximum

local_max = min(graph[current_node].values())

# Ambil node dari local maximum,

# dan tambahkan ke result

# agar iterasi selanjutnya dimulai

# dari node sekarang.

for node, weight in graph[current_node].items():

    if weight == local_max:

        result.append(node)

Setelah seluruh graph ditelurusi sampai mendapatkan hasil, kita dapat mengembalikan result ke pemanggil fungsi:

return result

Keseluruhan fungsi yang dibangun adalah sebagai berikut:

def shortest_path(graph, source, dest):

    result = []

    result.append(source)

    while dest not in result:

        current_node = result[-1]

        local_max = min(graph[current_node].values())

        for node, weight in graph[current_node].items():

            if weight == local_max:

                result.append(node)

    return result

Perlu diingat bahwa fungsi ini masih banyak memiliki kekurangan, misalnya tidak adanya penanganan kasus jika titik tujuan tidak ditemukan, atau jika terdapat node yang memiliki nilai negatif (bergerak balik). Penanganan hal-hal tersebut tidak dibuat karena fungsi hanya bertujuan untuk mengilustrasikan cara kerja algoritma greedy, bukan untuk digunakan pada aplikasi nyata.

Kesimpulan

Algoritma greedy merupakan algoritma yang besifat heuristik, mencari nilai maksimal sementara dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan solusi cepat meskipun tidak optimal seperti sistem real-time atau game.

Dari impementasi yang kita lakukan, dapat dilihat bagaimana algoritma greedy memiliki beberapa fungsionalitas dasar, yaitu:

1. Fungsi untuk melakukan penelusuran masalah.
2. Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.
3. Fungsi untuk mengisikan nilai local maximum ke solusi keseluruhan.
4. Fungsi yang menentukan apakah solusi telah didapatkan.

Pengertian :

      Brute force adalah sebuah pendekatan yang sangat jelas(straightforward) untuk memecahkan suatu persoalan, biasanya didasarkan pada problem statement dan definisi konsep yang dilibatkan.

      Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas .

Cara kerja Algoritma Brute Force

1.       Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.

2.       Evaluasi setiap kemungkinan solusi “satu per satu” dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).

3.       Bila pencarian solusi berakhir, umumkan solusi terbaik (the winner)

Karakteristik Algoritma Brute Force

·         Algoritma brute force sebenarnya bukanlah algoritma yang “cerdas” dan mangkus(efisien), karena ia membutuhkan jumlah langkah yang besar/banyak dalam penyelesaiannya dan tentu saja membutuhkan waktu yang berbanding lurus dengan jumlah langkah penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm).

·         Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya itu, tapi kalau mencari pola2 dasar, keteraturan, atau trik-trik khusus, biasanya dapat membantu membantu untuk menemukan algoritma yang lebih cerdas dan lebih mangkus lagi.

·         Untuk persoalan2 yang kecil, kesederhanaan brute force lebih diperhitungkan daripada ketidakmangkusannya. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus.

·         Meskipun brute force bukan merupakan teknik pemecahan masalah yang mangkus, namun teknik brute force dapat diterapkan pada sebagian besar persoalan. Bayangkan..,sangat sulit menemukan masalah yang tidak dapat dipecahkan dengan teknik brute force, tapi ada masalah yang hanya dapat dipecahkan secara brute force.

Algoritma bubble sort mengimplementasikan teknik brute force dengan jelas sekali. Berikut contoh persoalan sorting yang dipecahkan dengan algoritma bubble sort:

procedure BubbleSort (input/output L : arrayOfInt, input n : integer) { Mengurutkan array L[1..N] sehingga terurut menaik dengan metode pengurutan bubble sort. Masukan : Array L yang sudah terdefenisi nilai-nilainya. Keluaran: Array L yang terurut menaik sedemikian sehingga L[1] £ L[2] £ … £ L[N]. }

Deklarasi i : integer { variabel untuk jumlah langkah } k : integer { variabel,untuk pengapungan pada setiap langkah } temp : integer { variabel untuk pertukaran }

Algoritma: for i <- 1 to n – 1 do    for j <- n downto i + 1 do {looping menurun}       if (L[j] < L[j-1]) then          {tukar L[j] dengan L[j-1]}          temp <- L[j]          L[j] <- L[j-1]          L[j-1] <- temp       endif    endfor endfor