Contoh Makalah Yang Benar Tentang Algoritma Pencarian DFS BFS Dan Heuristik

Contoh Makalah Yang Benar Tentang Algoritma Pencarian DFS BFS Dan Heuristik | Pada kesempatan kali ini yang akan kami bahas yaitu Makalah Tentang Algoritma Pencarian. Didalam makalah tersebut dibahas secara legkap dan jelas mengenai Algoritma Pencarian. Untuk lebih jelasnya silahkan download makalah tersebut yang telah kami sediakan di bawah ini. Makalah tersebut berbentuk dokumen dengan format .docx.

Silahkan download melalui link di bawah ini , semoga bermanfaat : 

Download Contoh Makalah Yang Benar Tentang Algoritma Pencarian DFS BFS Dan Heuristik

Isi makalah yang anda download sebagai berikut :

BAB I

PENDAHULUAN

1.1  Latar Belakang

Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian, sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian. Adapun dalam metode pencarian blind atau buta digunakan karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. Algoritma Pencarian ini menggunakan Metode BFS, DFS, dll.

1.2  Batasan Masalah

Makalah ini membahas tentang Algoritma Pencarian hanya pada Metode Pemecahan Masalah yaitu Breadth-first Search (BFS), Depth-first Search (DFS) dan Metode Pencarian Heuristik.

1.3  Tujuan

Tujuan dari Pembuatan Makalah ini, antara lain agar :

1.      Mahasiswa mampu memahami apa itu DFS, BFS dan Heuristik

2.      Mahasiswa mampu membedakan DFS, BFS dan Heuristik

1.4  Metode

Metode yang digunakan penulis dalam pembuatan Makalah ini adalah dengan mencari referensi di internet.

BAB II

PEMBAHASAN

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, ...

Figure 1.6: Diagram pohon dari BFS.

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.1.1.      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

Contohnya terlihat dibawah ini:

Maka penyelesaiannya adalah:

Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.

Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1

Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

2.1.2.      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.1.3.      Penerapan BFS dalam Algoritma

Adapun penerapan BFS pada algoritma adalah sebagai berikut:

2.2.   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  

Figure 2.3 : Diagram pohon dari DFS.

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.2.1. 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).

Gambar 2.4 Penelusuran Depth First Search untuk Water Jug Problem.

2.2.2. 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

2.3. Pencarian Heuristik

Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.

George Poyla (dalam Kristanto. A, 2003) mendefinisikan heuristik sebagai ”studi tentang sebuah metode dan aturan discovery serta invention” dalam pencarian state space, heuristik didefinisikan sebagai aturan untuk memilih cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima .

Pemecahan masalah AI menggunakan heuristik dalam dua situasi dasar (Setiawan. S, 1993), yaitu :

1.    Permasalahan yang mungkin tidak mempunyai solusi yang pasti disebabkan oleh ambiguitas (keraguan/ketidakpastian) mendasar dalam pernyataan permasalahan atau data yang tersedia, contohnya diagnosa kedokteran.

2.    Permasalahan yang boleh jadi memiliki solusi pasti, tetapi biaya komputasinya untuk mendapatkan solusi tersebut mungkin sangat tinggi. Dalam banyak problema (misalnya saja catur), pertumbuhan state space adalah secara kombinatorial eksplosif dengan bayak state yang mungkin meningkat secara eksponensial atau faktorial dengan kedalaman pencarian. Dalam hal ini, exhaustive, yakni teknik pencarian brute force seperti pencarian mendalam pertama dan pencarian meluas pertama mungkin gagal menemukan solusi sehingga heuristik akan menangani kerumitan permasalahan ini dengan panduan pencarian pada sepanjang lintasan yang memeberi harapan melewati state. Dengan mengeliminasi state yang tidak memberi harapan dan turunannya dari ruang tersebut maka algoritma heuristik dapat mengalahkan ledakan kombinatorial dan menemukan penyelesaian yang dapat diterima.

Pencarian terbimbing (heuristic search) dibutuhkan karena pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. Dalam pencarian ruang keadaan, heuristik dinyatakan sebagai aturan untuk melakukan pemilihan cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima.

Heuristik dapat digunakan pada beberapa kondisi berikut ini (Siswanto, 2010):

1.      Mengatasi combinatorial explosion.

Ada masalah yang kemungkinan arah penyelesaiannya berkembang pesat (bersifat faktorial) sehingga menimbulkan combinatorial explosion. Heuristik merupakan cara untuk menentukan kemungkinan arah penyelesaian masalah secara efisien.

2.      Solusi paling optimal mungkin tidak diperlukan.

Dalam suatu keadaan, mungkin lebih baik mendapatkan solusi yang mendekati optimal dalam waktu yang singkat daripada solusi yang paling optimal dalam waktu yang lama.

3.      Pada umumnya hasilnya cukup baik.

Sekalipun tidak optimal, tetapi biasanya mendekati optimal.  Membantu pemahaman bagi orang yang menyelesaikan persoalan.

4.      Banyak alternatif heuristik yang dapat diterapkan dalam suatu percobaan. Orang yang menyelesaikan persoalan tersebut akan lebih mengerti persoalannya jika mencoba heuristik yang diterapkannya.

Salah satu contoh dari heuristik yang baik untuk tujuan umum yang berguna untuk beragam kombinasi permasalahan adalah the nearest neighbour heuristic, yang bekerja dengan cara menyeleksi alternatif yang paling tinggi secara lokal pada setiap langkahnya. Untuk permasalahan perjalanan salesman, prosedur-prosedur yang harus dilakukan adalah sebagai berikut :

1.      Memilih sebuah kota awal (starting cities)

2.      Melihat kota berikutnya, kemudian melihat semua kota yang belum dikunjungi dan memilih salah satu kota yang paling dekat dengan kota yang dipilih pada saat itu.

3.      Ulangi langkah 2 sampai semua kota dikunjungi.

Sebuah fungsi heuristik mengevaluasi keadaan permasalahan tersendiri dan menentukan bagaimana diperlukan fungsi ini dalam memecahkan suatu permasalahan. Sebuah fungsi heuristik adalah sebuah fungsi yang memetakan keadaan permasalahan, yang mendeskripsikan daya tarik dan digambarkan dalam sebuah angka (Pearl, 1984).

Fungsi heuristik yang dirancang dengan baik dapat berperan dalam sebuah bagian yang penting untuk memandu secara efisien proses pencarian menuju ke sebuah solusi. Tabel 2.1 menunjukkan beberapa fungsi heuristik sederhana untuk beberapa permasalahan.

Kadang kala sebuah nilai tinggi dari fungsi heuristik mengindikasikan sebuah posisi yang baik secara relatif (terlihat pada catur dan tic tac toe), di lain waktu sebuah nilai rendah mengindikasikan sebuah situasi yang menguntungkan (terlihat pada perjalanan salesman). Program yang menggunakan nilai (value) dari fungsi dapat mengusahakan minimal atau maksimal secara tepat.

Tujuan dari sebuah fungsi heuristik adalah untuk memandu proses pencarian tujuan yang menguntungkan dengan menganjurkan jalur yang mana yang diikuti pertama kali ketika tersedia lebih dari satu tujuan. Setelah proses berlangsung, akan bisa dihitung sebuah fungsi heuristik yang sempurna dengan cara melakukan sebuah pencarian yang lengkap dari simpul dalam pertanyaan dan menentukan apakah fungsi ini menuju ke sebuah solusi yang baik.

Sayangnya, seperti semua kaidah penemuan lainnya, heuristik juga dapat salah. Heuristik hanyalah panduan informasi untuk menebak langkah berikutnya yang harus diambil dalam menyelesaikan suatu permasalahan, dan sering dilakukan berdasarkan eksperimen/percobaan atau secara intuisi. Oleh karena menggunakan informasi yang terbatas, heuristik jarang dapat memprediksi tingkah laku yang eksak dari ruang keadaan saat dilakukan pencarian. Heuristik dapat membimbing algoritma pencarian untuk mendapatkan solusi suboptimal atau gagal menemukan solusi apapun, karena tidak ada solusi yang dapat menuju keadaan akhir.

Heuristik dan perancangan algoritma untuk mengimplementasikan pencarian heuristik telah menjadi inti permasalahan penelitian AI. Game playing dan pemecahan teorema (theorem solving) adalah dua aplikasi paling tua dari AI, kedua-duanya memerlukan heuristik untuk memangkas ruang dari solusi yang mungkin.

BAB 3

PENUTUP

3.1. Kesimpulan

 Dari pembahasan diatas dapat ditarik kesimpulan yaitu :

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.

3.      Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.

DAFTAR PUSTAKA

dir.unikom.ac.id/s1-final-project/...dan.../6-12.unik-2.pdf

MakalahSTMIK2007-081

bahasa Indonesia, ensiklopedia bebas

www.google.com

Itulah tadi makalah tentang Algoritma pencaria. Anda dapat mendownloadnya melalui link di bawah ini :

Download Contoh Makalah Yang Benar Tentang Algoritma Pencarian DFS BFS Dan Heuristik

Semoga apa yang kami sampaikan dapat bermanfaat bagi anda yang sedang emebutuhkannya. 

Contoh Makalah