Algoritma Pelacakan Balik

Apa itu Algoritma Backtracking?

Backtracking adalah algoritma yang mencari kemungkinan kombinasi untuk menyelesaikan masalah. masalah komputasi. Secara bertahap membangun kandidat dan menghapus kandidat yang tidak memenuhi batasan yang diberikan. Teknik ini sangat berguna dalam situasi di mana Anda harus memilih solusi yang layak di antara beberapa kemungkinan hasil.

Algoritma ini dianggap lebih baik dan lebih efisien daripada pendekatan Brute Force. Tidak seperti Bruteforce, yang mencoba semua solusi yang mungkin, Backtracking berfokus pada pencarian hanya satu solusi akhir sesuai dengan yang diberikan. kendala. Ini juga menghemat waktu dan memori dengan membatalkan langkah terakhir (mundur) dan mencoba opsi lain setelah mencapai jalan buntu. Selain itu, ini berhenti segera setelah solusi yang valid ditemukan.

Penelusuran balik merupakan teknik yang banyak digunakan karena dapat memecahkan masalah yang rumit tanpa menghabiskan banyak sumber daya. Teknik ini khususnya berguna untuk masalah yang harus memenuhi banyak kendala, seperti Sudoku, masalah n queen, dan penjadwalan. Dengan menavigasi solusi potensial secara cerdas, penelusuran balik dapat menemukan jawaban yang memenuhi semua kondisi. Hal ini membuatnya sangat berharga untuk tugas yang membutuhkan ketepatan dan efisiensi.

Bagaimana Algoritma Backtracking Bekerja?

Algoritma backtracking adalah teknik pemecahan masalah yang melibatkan pencarian solusi valid langkah demi langkah. Jika kendala suatu langkah tidak memenuhi kondisi tertentu, algoritma kembali ke langkah sebelumnya.

Kemudian dilanjutkan dengan kemungkinan kombinasi lain yang memenuhi batasan yang diberikan. Karena ada banyak kemungkinan kombinasi, maka dipilih salah satu opsi yang paling memuaskan dan memecahkan masalah secara berurutan. Teknik algoritmik ini berguna ketika Anda perlu menyelesaikan satu atau beberapa opsi yang mungkin. Penarikan berarti membatalkan pilihan Anda setiap kali muncul situasi yang tidak menghasilkan solusi yang valid.

Algoritma backtracking secara umum memiliki langkah-langkah berikut untuk menyelesaikan suatu masalah:

Langkah 1) Inisialisasi: Mulailah dengan solusi awal yang kosong/sebagian.

Langkah 2) Pemilihan: Berdasarkan kriteria dan batasan tertentu, pilih satu opsi untuk memperluas solusi saat ini.

Langkah 3) Eksplorasi: Selesaikan secara rekursif dengan mempertimbangkan kandidat yang dipilih dan bergerak maju dalam proses pemecahan masalah.

Langkah 4) Pemeriksaan Kendala: Periksa apakah solusi parsial saat ini melanggar batasan apa pun di setiap langkah. Jika ya, kembali ke langkah sebelumnya dan coba kandidat yang berbeda.

Langkah 5) Penghentian: Proses penelusuran balik berhenti ketika solusi valid ditemukan, atau semua kombinasi telah habis.

Langkah 6) Melakukan Backtracking: Jika opsi saat ini tidak menyelesaikan masalah yang diberikan, sistem akan kembali ke kondisi sebelumnya. Kemudian, sistem akan mempertimbangkan opsi baru untuk menyelesaikan masalah yang diberikan.

Langkah 7) Ulangi: Lanjutkan langkah-langkah ini hingga masalah teratasi atau semua opsi dieksplorasi.

Sifat Rekursif Algoritma Backtracking

Algoritma backtracking bersifat rekursif. Ini berarti algoritma memanggil dirinya sendiri dengan parameter yang berbeda hingga menemukan solusi atau menguji semua kemungkinan:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Istilah Umum Terkait Masalah Backtracking

Berikut ini adalah beberapa istilah dasar yang terkait dengan teknik Backtracking:

• Vektor Solusi: Mewakili solusi sebagai n-tupel, seperti (X1, X2, …, Xn).
• kendala: Aturan yang membatasi nilai X, implisit dan eksplisit.
• Ruang Solusi: Semua nilai X yang valid memenuhi batasan eksplisit.
• Pohon Ruang Negara: Mewakili ruang solusi sebagai pohon.
• Ruang Negara: Menggambarkan lintasan pada pohon ruang keadaan.
• Keadaan Masalah: Simpul pada pohon pencarian yang mewakili solusi parsial.
• Negara Solusi:Negara-negara yang membentuk tupel solusi valid dalam S.
• Jawaban Negara:Memenuhi batasan implisit dan menghasilkan solusi yang diinginkan.
• Node yang Menjanjikan:Mengarah pada solusi yang diinginkan dan tetap layak.
• Node yang Tidak Menjanjikan: Mengarah ke kondisi yang tidak dapat dilaksanakan dan tidak dieksplorasi lebih lanjut.
• Simpul Hidup:Dihasilkan dengan anak yang belum dijelajahi.
• Simpul-E: Node hidup dengan pembangkitan anak yang berkelanjutan.
• Node Mati: Tidak ada perluasan lebih lanjut dari semua anak yang dihasilkan.
• Pembuatan Node Kedalaman Pertama: Menggunakan node aktif terkini sebagai E-node berikutnya.
• Fungsi Pembatas: Memaksimalkan atau meminimalkan B(x1, x2, …, Xa) untuk optimasi.
• Pohon Statis:Formulasi pohon terlepas dari instansi permasalahan.
• Pohon Dinamis:Formulasi pohon bervariasi tergantung pada contoh masalah.

Kapan Harus Menggunakan Algoritma Backtracking?

Kita dapat memilih teknik Backtracking untuk memecahkan masalah rumit ketika:

• Ada banyak pilihan: Penelusuran balik cocok jika terdapat banyak pilihan di setiap langkah proses pemecahan masalah. Pilihan ini dapat terkait dengan pemilihan item dan gerakan.
• Tidak ada pilihan terbaik yang jelas:Ketika tidak ada cukup informasi untuk menentukan pilihan terbaik di antara opsi yang tersedia, algoritma Backtracking dapat digunakan.
• Keputusan ini menghasilkan lebih banyak pilihan: Anda dapat memilih teknik penelusuran kembali untuk meninjau pilihan secara sistematis.
• Perlu mengeksplorasi semua solusi yang mungkin: Backtracking secara sistematis mengeksplorasi semua solusi dengan membuat serangkaian keputusan yang dibangun satu sama lain.

Jenis-jenis Masalah Backtracking

Ada tiga jenis masalah dalam algoritma backtracking: masalah keputusan, masalah optimasi, dan masalah enumerasi. Mari kita pelajari tentang ketiganya di bawah ini.

1. Masalah Keputusan: Dalam jenis masalah ini, tujuannya adalah untuk menentukan apakah ada solusi yang layak. Kami memeriksa jawaban "ya" dan "tidak". Misalnya, masalah n-ratu. Ini adalah masalah keputusan yang menguji kemungkinan menempatkan n ratu pada papan catur n × n tanpa saling menyerang.
2. Masalah pengoptimalan: Dalam masalah optimasi, tujuannya adalah menemukan solusi terbaik yang memungkinkan di antara banyak pilihan. Hal ini dapat melibatkan penentuan nilai maksimum dan minimum dari fungsi atau variabel tertentu. Misalnya, perhatikan masalah ransel, di mana tujuannya adalah memaksimalkan nilai total barang di dalam tas sambil mematuhi batas beratnya.
3. Masalah Pencacahan: Tujuannya adalah menemukan semua kemungkinan solusi untuk masalah tertentu. Kami mencantumkan setiap opsi yang valid tanpa ada yang terlewat. Contohnya adalah menghasilkan semua kemungkinan kombinasi huruf dari sekumpulan karakter tertentu.

Aplikasi Backtracking dan Contohnya

Ada berbagai aplikasi Backtracking. Beberapa di antaranya dijelaskan di bawah ini dengan kode semu.

1. Sudoku Solver: Soal ini berisi subgrid 3x3 dengan angka duplikat. Teknik backtracking akan menunjukkan bahwa solusi mengembalikan nilai false, yang menunjukkan perlunya penempatan angka yang berbeda.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

2. Masalah N-Ratu: Pendekatan mundur menentukan cara menampilkan ratu pada papan catur N × N sehingga tidak ada satupun di antara mereka yang saling mengancam.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

3. Masalah Jumlah Subset: Digunakan untuk menemukan bagian himpunan angka dari himpunan tertentu yang jumlahnya mencapai jumlah target tertentu.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

4. Masalah Siklus Hamiltonian:Backtracking dapat diterapkan untuk menemukan tur tertutup dalam grafik yang mengunjungi setiap titik tepat satu kali.
5. Masalah Tikus di Labirin: Teknik backtracking digunakan untuk menemukan jalur tikus dari titik awal labirin hingga pintu keluar.

Kelebihan dan Kekurangan Algoritma Backtracking

Keuntungan Algoritma Backtracking

Teknik backtracking digunakan untuk memecahkan masalah yang kompleks. Teknik ini memiliki banyak keuntungan seperti:

• Teknik backtracking efisien untuk menangani kendala.
• Metode ini bagus untuk memecahkan masalah optimasi.
• Teknik ini dapat digunakan untuk berbagai jenis masalah.
• Prosedur ini dapat membantu meninjau semua solusi yang mungkin.
• Karena melakukan backtracking, ia menghemat lebih banyak memori daripada teknik Bruteforce.

Kekurangan Algoritma Backtracking

Teknik backtracking juga memiliki beberapa keterbatasan, seperti kompleksitas waktu. Teknik ini memiliki beberapa kelemahan berikut:

• Tidak ada solusi yang dijamin.
• Lebih lambat karena banyak kombinasi.
• Memiliki kompleksitas waktu yang tinggi karena banyaknya kemungkinan.
• Tidak cocok untuk kendala waktu nyata karena menemukan solusi terbaik mungkin memakan waktu lama.
• Efisiensi bergantung pada tingkat kerumitan masalah.

Perbedaan Antara Backtracking Dan Rekursi

Kesimpulan

Penelusuran balik merupakan strategi algoritmik yang berguna untuk memecahkan masalah kompleks dengan cara mengeksplorasi solusi yang layak secara sistematis dan menelusuri balik bila perlu. Kita dapat mengharapkan teknik penelusuran balik akan meningkat dengan peningkatan daya komputasi dan efisiensi algoritmik. Kemajuan ini akan memungkinkan mereka untuk mengatasi masalah yang lebih besar dan lebih kompleks secara efisien.

Selain itu, model pembelajaran mesin dapat memandu keputusan penelusuran kembali berdasarkan pola yang dipelajari sebelumnya.

Semua inovasi teknologi ini akan merevolusi algoritma backtracking, menjadikannya alat yang ampuh dan serbaguna untuk mengatasi masalah rumit di berbagai domain.