DEFINISI ALGORITMA DAN PENCARIAN BUTA

1.1 Sejarah Ilmu Algoritma

Ditinjau dari asal usul katanya kata Algoritma sendiri mempunyai sejarah yang aneh. Orang hanya menemukan kata Algorism yang berarti proses menghitung dengan angka arab. Anda dikatakan Algorist jika anda menghitung menggunakan Angka Arab. Para ahli bahasa berusaha menemukan asal kata ini namun hasilnya kurang memuaskan. Akhirnya para ahli sejarah matematika menemukan asal kata tersebut yang berasal dari nama penulis buku arab yang terkenal yaitu Abu Ja’far Muhammad Ibnu Musa Al-Khuwarizmi. Al-Khuwarizmi dibaca orang barat menjadi Algorism. Al-Khuwarizmi menulis buku yang berjudul Kitab Al Jabar Wal-Muqabala yang artinya “Buku pemugaran dan pengurangan” (The book of restoration and reduction). Dari judul buku itu kita juga memperoleh akar kata “Aljabar” (Algebra). Perubahan kata dari Algorism menjadi Algorithm muncul karena kata Algorism sering dikelirukan dengan Arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang biasa. Maka lambat laun kata Algorithm berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam Bahasa Indonesia, kata Algorithm diserap menjadi Algoritma.

1.2. Definisi Algoritma

“Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis”. Kata Logis merupakan kata kunci dalam Algoritma. Langkah-langkah dalam Algoritma harus logis dan harus dapat ditentukan bernilai salah atau benar.

1.3. Algoritma Merupakan Jantung Ilmu Informatika

Algoritma adalah jantung ilmu komputer atau informatika. Banyak cabang ilmu komputer yang diacu dalam terminologi algoritma. Namun, jangan beranggapan algoritma selalu identik dengan ilmu komputer saja. Dalam kehidupan sehari-hari pun banyak terdapat proses yang dinyatakan dalam suatu algoritma. Cara-cara membuat kue atau masakan yang dinyatakan dalam suatu resep juga dapat disebut sebagai algoritma. Pada setiap resep selalu ada urutan langkah-lankah membuat masakan. Bila langkah-langkahnya tidak logis, tidak dapat dihasilkan masakan yang diinginkan. Ibu-ibu yang mencoba suatu resep masakan akan membaca satu per satu langkah-langkah pembuatannya lalu ia mengerjakan proses sesuai yang ia baca.

Secara umum, pihak (benda) yang mengerjakan proses disebut pemroses (processor). Pemroses tersebut dapat berupa manusia, komputer, robot atau alat-alat elektronik lainnya. Pemroses melakukan suatu proses dengan melaksanakan atau “mengeksekusi” algoritma yang menjabarkan proses tersebut. Melaksanakan Algoritma berarti mengerjakan langkah-langkah di dalam Algoritma. Pemroses mengerjakan proses sesuai dengan algoritma yang diberikan kepadanya. Juru masak membuat kue berdasarkan resep yang diberikan kepadanya, pianis memainkan lagu berdasarkan papan not balok. Karena itu suatu Algoritma harus dinyatakan dalam bentuk yang dapat dimengerti oleh pemroses. Jadi suatu pemroses harus :

1. Mengerti setiap langkah dalam Algoritma

2. Mengerjakan operasi yang bersesuaian dengan langkah tersebut.

1.4. Mekanisme Pelaksanan Algoritma Oleh Pemroses

Komputer hanyalah salah satu pemroses. Agar dapat dilaksanakan oleh komputer, algoritma harus ditulis dalam notasi bahasa pemrograman sehingga dinamakan program. Jadi program adalah perwujudan atau implementasi teknis Algoritma yang ditulis dalam bahasa pemrogaman tertentu sehingga dapat dilaksanakan oleh komputer.

1.5. Belajar Memprogram Dan Belajar Bahasa Pemrograman

Belajar memprogram tidak sama dengan belajar bahasa pemrograman. Belajar memprogram adalah belajar tentang metodologi pemecahan masalah, kemudian menuangkannya dalam suatu notasi tertentu yang mudah dibaca dan dipahami. Sedangakan belajar bahasa pemrograman berarti belajar memakai suatu bahasa aturan-aturan tata bahasanya, instruksi-instruksinya, tata cara pengoperasian compiler-nya, dan memanfaatkan instruksi-instruksi tersebut untuk membuat program yang ditulis hanya dalam bahasa itu saja. Sampai saat ini terdapat puluhan bahasa pemrogram. Yang dapat dibedakan berdasarkan tujuan dan fungsinya. 

1.6. Belajar Memprogram

1. Belajar memprogram ≠ belajar bahasa pemrograman

2. Belajar memprogram : belajar tentang strategi pemecahan masalah, metodologi dan sistematika pemecahan masalah kemudian menuliskannya dalam notasi yang disepakati bersama

3. Belajar memprogram : bersifat pemahaman persoalan, analisis dan sintesis

4. Belajar memprogram, titik berat : designer program

1.7. Belajar Bahasa Pemrograman

1. Belajar bahasa pemrograman : belajar memakai suatu bahasa pemrograman, aturan

2. sintaks, tatacara untuk memanfaatkan instruksi yang spesifik untuk setiap bahasa

3. Belajar bahasa pemrograman , titik berat : coder

1.8. Produk yang dihasilkan pemrogram :

1. Program dengan rancangan yang baik (metodologis, sistematis)

2. Dapat dieksekusi oleh mesin

3. Berfungsi dengan benar

4. Sanggup melayani segala kemungkinan masukan

5. Disertai dokumentasi

 2.1 Breadth-First Search (BFS)

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. Urutan proses searching BFS ditunjukkan dalam Gambar 2.1 adalah: A,B,C,D,E,F, ...

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada ras d+1.

Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

2.2 Cara Kerja Algoritma BFS

Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.

Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

     1.   Masukkan simpul ujung (akar) ke dalam antrian

     2.   Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi

     3.   Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

   4.   Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian

   5.   Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

     6.   Ulangi pencarian dari langkah kedua

Contoh Pencarian Lintasan Terpendek Dengan BFS

Adapun contoh untuk mencari lintasan terpendek dengan menggukan algoritma BFS adalah sebagai berkut:

Diketahui sebuah kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar kota dibentuk dengan sebuah graph terlihat dibawah:

Pertanyaan: sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal perjalanan adalah kota no. 1. Gunakan algoritma BFS!

Maka dengan menggunakan algoritma BFS, rute tercepat yang didapat adalah sebagai berikut:

1 – 2 – 3 – 4 – 5 – 6 – 7 – 8

Rute tersebut didapat dari pencarian secara melebar. Hal; tersebut dapat dijabarkan sebagai berikut:

·         Pertama-tama, pointer menunujuk pada daun yang ada sebelah kanan, yaitu no.2 (1 – 2)

·         Setelah itu, proses dilanjutkan pada tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada tetangga terdekat, yakni no.4 (1-2-3-4).

·         Pointer mencari teteangga no.4, namun karna tidak ada, maka pointer kembali ke kota no.2 dan masuk ke daun berikutnya, yakni no.5.

·         Proses diulang hingga pointer menunjuk angka 8

2.3 Depth-First search (DFS)

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi. Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah. Urutan proses searching DFS ditunjukkan dalam Gambar 1.5 adalah: A, B, E,F, G, C, ... Figure  

Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

 

2.4  Kelebihan dan Kelemahan DFS

      Kelebihan DFS adalah:
•       Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
•       Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Kelemahan DFS adalah:

•       Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
•       Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal)..

2.5. Cara Kerja DFS

Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.

Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).

Untuk memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya, berikut langkah-langkah algoritma DFS:

1.      Masukkan simpul ujung (akar) ke dalam tumpukan
2.      Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi
3.      Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.4.      Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan
5.      Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
6.      Ulangi pencarian dari langkah kedua

KESIMPULAN

1.      Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. 
2.      Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain.

 Pratiwi. P 1310128262109   
Marlena Oktarini 1310128262110       
Terima kasih kepada Dosen pengampuh mata kuliah Algoritma 3
Nama : M.Ropianto, M.Kom
NIND : 102867804
Status : Dosen Tetap Yapista / STT Ibnu Sina Batam