Algoritma Pencarian Tidak Berinformasi

  • Post
    Algoritma Pencarian Tidak Berinformasi

    Pencarian tanpa informasi adalah kelas algoritma pencarian tujuan umum yang beroperasi secara brute force. Algoritme pencarian tanpa informasi tidak memiliki informasi tambahan tentang status atau ruang pencarian selain cara melintasi pohon, sehingga disebut juga pencarian buta.

    Berikut ini adalah berbagai jenis algoritma pencarian yang tidak diinformasikan:

    1. Pencarian luas-pertama
    2. Pencarian Kedalaman-pertama
    3. Penelusuran dengan kedalaman terbatas
    4. Deep-first search pendalaman berulang
    5. Pencarian biaya seragam
    6. Pencarian dua arah
    1. Pencarian Breadth-first:
    • Pencarian luas-pertama adalah strategi pencarian paling umum untuk melintasi pohon atau grafik. Algoritme ini menelusuri secara luas di pohon atau grafik, sehingga disebut penelusuran luas-pertama.
    • Algoritma BFS mulai mencari dari simpul akar pohon dan memperluas semua simpul penerus pada tingkat saat ini sebelum pindah ke simpul pada tingkat berikutnya.
    • Algoritme penelusuran luas-pertama adalah contoh algoritme penelusuran grafik umum.
    • Pencarian luas pertama diimplementasikan menggunakan struktur data antrian FIFO.

    Keuntungan:

    • BFS akan memberikan solusi jika ada solusi.
    • Jika ada lebih dari satu solusi untuk masalah tertentu, maka BFS akan memberikan solusi minimal yang memerlukan langkah paling sedikit.

    Kekurangan:

    • Ini membutuhkan banyak memori karena setiap level pohon harus disimpan ke dalam memori untuk memperluas level berikutnya.
    • BFS membutuhkan banyak waktu jika solusinya jauh dari node root.

    Contoh:

    Pada struktur pohon di bawah ini, kami telah menunjukkan melintasi pohon menggunakan algoritma BFS dari simpul akar S ke simpul tujuan K. Algoritma pencarian BFS melintasi dalam lapisan, sehingga akan mengikuti jalur yang ditunjukkan oleh panah bertitik, dan jalur yang akan dilalui akan menjadi:

    1. S —> A —> B —-> C —> D —-> G —> H —> E —-> F —-> I —-> K.

    Kompleksitas Waktu: Kompleksitas Waktu dari algoritma BFS dapat diperoleh dari jumlah node yang dilintasi BFS hingga Node yang paling dangkal. Di mana d = kedalaman solusi paling dangkal dan b adalah node di setiap status.

    T (b) = 1 + b 2 + b 3 + ……. + b d = O (b d )

    Kompleksitas Ruang: Kompleksitas ruang dari algoritma BFS diberikan oleh ukuran Memori dari frontier yaitu O (b d ).

    Kelengkapan: BFS selesai, yang berarti jika node tujuan paling dangkal berada pada kedalaman yang terbatas, maka BFS akan menemukan solusi.

    Optimalitas: BFS optimal jika biaya jalur adalah fungsi non-penurunan dari kedalaman node.

    1. Pencarian Kedalaman-pertama
    • Pencarian Depth-first adalah algoritma rekursif untuk melintasi struktur data pohon atau grafik.
    • Ini disebut pencarian kedalaman pertama karena dimulai dari simpul akar dan mengikuti setiap jalur ke simpul kedalaman terbesar sebelum pindah ke jalur berikutnya.
    • DFS menggunakan struktur data stack untuk implementasinya.
    • Proses algoritma DFS mirip dengan algoritma BFS.

    Catatan: Backtracking adalah teknik algoritma untuk menemukan semua solusi yang mungkin menggunakan rekursi.

    Keuntungan:

    • DFS membutuhkan lebih sedikit memori karena hanya perlu menyimpan tumpukan node di jalur dari node root ke node saat ini.
    • Dibutuhkan lebih sedikit waktu untuk mencapai node tujuan daripada algoritma BFS (jika melintasi jalur yang benar).

    Kerugian:

    • Ada kemungkinan bahwa banyak negara terus terulang kembali, dan tidak ada jaminan untuk menemukan solusinya.
    • Algoritma DFS digunakan untuk pencarian yang lebih dalam dan kadang-kadang mungkin pergi ke loop tak terbatas.

    Contoh:

    Pada pohon pencarian di bawah ini, kami telah menunjukkan aliran pencarian kedalaman-pertama, dan itu akan mengikuti urutan sebagai:

    Node root —> Node kiri —-> node kanan.

    Ini akan mulai mencari dari simpul akar S, dan melintasi A, lalu B, lalu D dan E, setelah melintasi E, ia akan mundur ke pohon karena E tidak memiliki penerus lain dan simpul tujuan tetap tidak ditemukan. Setelah mundur, ia akan melintasi simpul C dan kemudian G, dan di sini ia akan berhenti ketika ia menemukan simpul tujuan.

    Kelengkapan: Algoritma pencarian DFS selesai dalam ruang keadaan terbatas karena akan memperluas setiap node dalam pohon pencarian terbatas.

    Kompleksitas Waktu: Kompleksitas waktu DFS akan setara dengan node yang dilintasi oleh algoritme. Itu diberikan oleh:

    T (n) = 1+ n 2 + n 3 + ……… + n m = O (n m )

    Dimana, m = kedalaman maksimum dari setiap node dan ini bisa lebih besar dari d (Kedalaman solusi paling dangkal)

    Kompleksitas Ruang: Algoritma DFS hanya perlu menyimpan jalur tunggal dari simpul akar, oleh karena itu kompleksitas ruang DFS setara dengan ukuran himpunan pinggiran, yaitu O (bm) .

    Optimal: Algoritme pencarian DFS tidak optimal, karena dapat menghasilkan banyak langkah atau biaya tinggi untuk mencapai node tujuan.

    1. Algoritma Pencarian Terbatas Kedalaman:

    Algoritme pencarian dengan batas kedalaman mirip dengan pencarian kedalaman pertama dengan batas yang telah ditentukan sebelumnya. Pencarian dengan kedalaman terbatas dapat menyelesaikan kekurangan dari jalur tanpa batas di pencarian Kedalaman-pertama. Dalam algoritme ini, node pada batas kedalaman akan diperlakukan karena tidak ada node penerus lebih lanjut.

    Pencarian dengan kedalaman terbatas dapat diakhiri dengan dua Kondisi kegagalan:

    • Nilai kegagalan standar: Ini menunjukkan bahwa masalah tidak memiliki solusi apa pun.
    • Nilai kegagalan batas: Ini tidak menentukan solusi untuk masalah dalam batas kedalaman tertentu.

    Keuntungan:

    Pencarian dengan kedalaman terbatas adalah Memori yang efisien.

    Kekurangan:

    • Pencarian dengan kedalaman terbatas juga memiliki kelemahan yaitu ketidaklengkapan.
    • Mungkin tidak optimal jika masalah memiliki lebih dari satu solusi.

    Contoh:

    Kelengkapan: Algoritma pencarian DLS selesai jika solusinya di atas batas kedalaman.

    Kompleksitas Waktu: Kompleksitas waktu dari algoritma DLS adalah O (b  ) .

    Kompleksitas Ruang: Kompleksitas ruang pada algoritma DLS adalah O (b × ℓ) .

    Optimal: Pencarian dengan kedalaman terbatas dapat dilihat sebagai kasus khusus DFS, dan juga tidak optimal meskipun ℓ> d.

    1. Algoritma Pencarian Biaya Seragam:

    Pencarian biaya seragam adalah algoritma pencarian yang digunakan untuk melintasi pohon atau grafik berbobot. Algoritme ini mulai berlaku ketika biaya yang berbeda tersedia untuk setiap sisi. Tujuan utama dari pencarian biaya seragam adalah untuk menemukan jalur ke node tujuan yang memiliki biaya kumulatif terendah. Pencarian biaya seragam memperluas node sesuai dengan biaya jalurnya dari node root. Ini dapat digunakan untuk menyelesaikan grafik / pohon apa pun yang membutuhkan biaya optimal. Algoritma pencarian biaya seragam diimplementasikan oleh antrian prioritas. Ini memberikan prioritas maksimum pada biaya kumulatif terendah. Pencarian biaya seragam setara dengan algoritma BFS jika biaya jalur semua sisi sama.

    Keuntungan:

    • Pencarian biaya seragam adalah optimal karena di setiap negara bagian dipilih jalur dengan biaya terendah.

    Kekurangan:

    • Itu tidak peduli tentang jumlah langkah yang terlibat dalam pencarian dan hanya peduli tentang biaya jalur. Karena itu, algoritme ini mungkin terjebak dalam putaran tak terbatas.

    Contoh:

    Kelengkapan:

    Pencarian biaya seragam selesai, seperti jika ada solusi, UCS akan menemukannya.

    Kompleksitas Waktu:

    Misalkan C * adalah Biaya dari solusi optimal , dan ε adalah setiap langkah untuk mendekati node tujuan. Maka banyaknya langkahnya adalah = C * / ε + 1. Di sini kita telah mengambil +1, karena kita mulai dari keadaan 0 dan berakhir ke C * / ε.

    Oleh karena itu, kompleksitas waktu kasus terburuk dari pencarian Uniform-cost adalah O (b 1 + [C * / ε] ) / .

    Kompleksitas Ruang:

    Logika yang sama adalah untuk kompleksitas ruang jadi, kompleksitas ruang kasus terburuk dari pencarian biaya Uniform adalah O (b 1 + [C * / ε] ) .

    Optimal:

    Pencarian biaya seragam selalu optimal karena hanya memilih jalur dengan biaya jalur terendah.

    5.Perdalaman berulang-ulang Pencarian Mendalam:

    Algoritma pendalaman iteratif merupakan kombinasi dari algoritma DFS dan BFS. Algoritme pencarian ini menemukan batas kedalaman terbaik dan melakukannya dengan meningkatkan batas secara bertahap hingga tujuan ditemukan.

    Algoritme ini melakukan penelusuran pertama kedalaman hingga “batas kedalaman” tertentu, dan terus meningkatkan batas kedalaman setelah setiap iterasi hingga node tujuan ditemukan.

    Algoritme Pencarian ini menggabungkan manfaat dari pencarian cepat Breadth-first search dan efisiensi memori pencarian depth-first.

    Algoritma pencarian berulang berguna untuk pencarian tanpa informasi ketika ruang pencarian besar, dan kedalaman node tujuan tidak diketahui.

    Keuntungan:

    • Ini menggabungkan keuntungan dari algoritma pencarian BFS dan DFS dalam hal pencarian cepat dan efisiensi memori.

    Kekurangan:

    • Kelemahan utama IDDFS adalah mengulang semua pekerjaan dari fase sebelumnya.

    Contoh:

    Struktur pohon berikut menunjukkan penelusuran mendalam-pertama yang berulang-ulang. Algoritma IDDFS melakukan berbagai iterasi hingga tidak menemukan node tujuan. Iterasi yang dilakukan oleh algoritma diberikan sebagai:

    Iterasi ke-1 —–>
    Iterasi ke-2 —-> A, B, C
    Iterasi ke-3 ——> A, B, D, E, C, F, G
    4 Iterasi ——> A, B, D, H, I, E, C, F, K, G
    Pada iterasi keempat, algoritma akan mencari node tujuan.

    Kelengkapan:

    Algoritma ini selesai jika faktor percabangannya terbatas.

    Kompleksitas Waktu:

    Misalkan b adalah faktor percabangan dan kedalaman adalah d maka kompleksitas waktu kasus terburuk adalah O (b d ) .

    Kompleksitas Ruang:

    Kompleksitas ruang IDDFS adalah O (bd) .

    Optimal:

    Algoritma IDDFS optimal jika biaya jalur adalah fungsi non-penurunan dari kedalaman node.

    1. Algoritma Pencarian Dua Arah:

    Algoritma pencarian dua arah menjalankan dua pencarian secara bersamaan, satu bentuk keadaan awal disebut pencarian maju dan lainnya dari node tujuan disebut pencarian mundur, untuk menemukan node tujuan. Pencarian dua arah menggantikan satu grafik pencarian tunggal dengan dua subgrafik kecil di mana satu memulai pencarian dari simpul awal dan lainnya dimulai dari simpul tujuan. Pencarian berhenti ketika dua grafik ini berpotongan satu sama lain.

    Pencarian dua arah dapat menggunakan teknik pencarian seperti BFS, DFS, DLS, dll.

    Keuntungan:

    • Pencarian dua arah cepat.
    • Pencarian dua arah membutuhkan lebih sedikit memori

    Kekurangan:

    • Penerapan pohon pencarian dua arah itu sulit.
    • Dalam pencarian dua arah, seseorang harus mengetahui keadaan tujuan terlebih dahulu.

    Contoh:

    Pada pohon pencarian di bawah ini, algoritma pencarian dua arah diterapkan. Algoritma ini membagi satu grafik / pohon menjadi dua sub-grafik. Ini mulai melintasi dari simpul 1 ke arah depan dan mulai dari simpul tujuan 16 ke arah belakang.

    Algoritme berakhir di node 9 di mana dua pencarian bertemu.

    Kelengkapan: Pencarian Dua Arah selesai jika kita menggunakan BFS di kedua pencarian.

    Kompleksitas Waktu: Kompleksitas waktu pencarian dua arah menggunakan BFS adalah O (b d ) .

    Kompleksitas Ruang: Kompleksitas ruang pencarian dua arah adalah O (b d ) .

    Optimal: Pencarian dua arah adalah Optimal.

     

     

     

    credit. javatpoint

     

Tagged: 

  • You must be logged in to reply to this topic.