Daftar Isi:
Definisi - Apa yang dimaksud dengan Backtracking?
Backtracking adalah algoritma untuk menangkap beberapa atau semua solusi untuk masalah komputasi tertentu, terutama untuk masalah kepuasan kendala. Algoritme hanya dapat digunakan untuk masalah yang dapat menerima konsep "solusi kandidat parsial" dan memungkinkan tes cepat untuk melihat apakah solusi kandidat dapat menjadi solusi yang lengkap. Mundur dianggap sebagai teknik penting untuk memecahkan masalah dan teka-teki kepuasan kendala. Ini juga dianggap teknik yang bagus untuk parsing dan juga membentuk dasar dari banyak bahasa pemrograman logika.
Techopedia menjelaskan Backtracking
Mengulangi membantu memecahkan masalah secara keseluruhan dengan menemukan solusi untuk sub-masalah pertama dan kemudian secara rekursif berusaha menyelesaikan sub-masalah lainnya berdasarkan pada solusi dari masalah pertama. Jika masalah saat ini tidak dapat diselesaikan, langkah ini mundur dan solusi berikutnya yang mungkin diterapkan untuk langkah-langkah sebelumnya, dan kemudian melanjutkan. Faktanya, salah satu hal kunci dalam backtracking adalah rekursi. Ini juga dianggap sebagai metode pencarian lengkap menggunakan divide and conquer. Algoritma backtracking berakhir ketika tidak ada lagi solusi untuk sub-masalah pertama.
Backtracking adalah suatu algoritma yang dapat membantu mencapai implementasi nondeterminisme. Dibutuhkan pencarian mendalam-pertama dari ruang masalah yang diberikan. Ini digunakan sebagian besar dalam bahasa pemrograman logika seperti Prolog. Di mana pun backtracking dapat diterapkan, itu lebih cepat daripada teknik brute force, karena menghilangkan sejumlah besar kandidat dengan tes tunggal.
