Apa perbedaan antara backtracking dan depth first search?

Apa perbedaan antara backtracking dan depth first search?

Backtracking adalah algoritma tujuan yang lebih umum.

Pencarian Depth-First adalah bentuk khusus dari penelusuran mundur yang terkait dengan pencarian struktur pohon. Dari Wikipedia:

Satu dimulai dari root (memilih beberapa node sebagai root dalam kasus grafik) dan mengeksplorasi sejauh mungkin di sepanjang setiap cabang sebelum melakukan backtracking.

Ia menggunakan backtracking sebagai bagian dari cara bekerja dengan pohon, tetapi terbatas pada struktur pohon.

Namun, backtracking dapat digunakan pada semua jenis struktur di mana bagian dari domain dapat dihilangkan - apakah itu pohon logis atau tidak. Contoh Wiki menggunakan papan catur dan masalah tertentu - Anda dapat melihat gerakan tertentu, dan menghilangkannya, lalu mundur ke langkah berikutnya yang mungkin, menghilangkannya, dll.

Saya pikir jawaban untuk pertanyaan terkait lainnya ini menawarkan lebih banyak wawasan.

Bagi saya, perbedaan antara backtracking dan DFS adalah backtracking menangani pohon implisit dan DFS berurusan dengan pohon eksplisit. Ini kelihatannya sepele, tapi itu sangat berarti. Ketika ruang pencarian masalah dikunjungi oleh penelusuran mundur, pohon implisit akan dilintasi dan dipangkas di tengahnya. Namun untuk DFS, pohon / grafik yang berhubungan dengannya dibuat secara eksplisit dan kasus yang tidak dapat diterima telah dibuang, yaitu dipangkas, sebelum pencarian dilakukan.

Jadi, backtracking adalah DFS untuk pohon implisit, sedangkan DFS melakukan backtracking tanpa pemangkasan.

Backtracking biasanya diimplementasikan sebagai DFS plus pemangkasan pencarian. Anda melintasi pencarian solusi parsial pohon ruang angkasa yang pertama membangun di sepanjang jalan. Brute-force DFS dapat membuat semua hasil pencarian, bahkan yang tidak masuk akal secara praktis. Ini juga bisa sangat tidak efisien untuk membangun semua solusi (n! Atau 2 ^ n). Jadi pada kenyataannya saat Anda melakukan DFS, Anda juga perlu memangkas solusi parsial, yang tidak masuk akal dalam konteks tugas sebenarnya, dan fokus pada solusi parsial, yang dapat menghasilkan solusi optimal yang valid. Ini adalah teknik mundur yang sebenarnya - Anda membuang solusi parsial sedini mungkin, mundur selangkah dan mencoba menemukan optimal lokal lagi.

Tidak ada yang berhenti untuk melintasi pohon ruang pencarian menggunakan BFS dan menjalankan strategi pelacakan mundur di sepanjang jalan, tetapi ini tidak masuk akal dalam praktiknya karena Anda perlu menyimpan status pencarian lapis demi lapis dalam antrian, dan lebar pohon tumbuh secara eksponensial ke ketinggian, jadi kami akan membuang banyak ruang dengan sangat cepat. Itu sebabnya pohon biasanya dilintasi menggunakan DFS. Dalam kasus ini status pencarian disimpan dalam stack (call stack atau struktur eksplisit) dan tidak boleh melebihi tinggi pohon.

Biasanya, penelusuran pertama kedalaman adalah cara melakukan iterasi melalui grafik / struktur pohon aktual untuk mencari nilai, sedangkan penelusuran mundur adalah pengulangan melalui ruang masalah untuk mencari solusi. Melacak mundur adalah algoritma yang lebih umum yang bahkan tidak berhubungan dengan pohon.

Menurut saya, DFS adalah bentuk khusus dari kemunduran; backtracking adalah bentuk umum DFS.

Jika kita memperluas DFS ke masalah umum, kita bisa menyebutnya backtracking. Jika kita menggunakan backtracking ke masalah terkait pohon / grafik, kita dapat menyebutnya DFS.

Mereka mengusung ide yang sama dalam aspek algoritmik.

Menurut Donald Knuth, itu sama. Berikut adalah link pada makalahnya tentang algoritma Dancing Links, yang digunakan untuk memecahkan masalah "non-pohon" seperti N-queens dan Sudoku solver.

Melacak mundur, juga disebut penelusuran mendalam-pertama

IMHO, sebagian besar jawaban sebagian besar tidak tepat dan / atau tanpa referensi untuk memverifikasi. Jadi izinkan saya membagikan penjelasan yang sangat jelas dengan referensi .

Pertama, DFS adalah algoritma traversal grafik umum (dan pencarian). Sehingga dapat diterapkan pada grafik apapun (atau bahkan hutan). Pohon adalah jenis Grafik khusus, jadi DFS juga berfungsi untuk pohon. Intinya, mari kita berhenti mengatakan itu hanya berfungsi untuk pohon, atau sejenisnya.

Berdasarkan [1], Backtracking adalah jenis khusus DFS yang digunakan terutama untuk menghemat ruang (memori). Perbedaan yang akan saya sebutkan mungkin tampak membingungkan karena dalam algoritme Graph semacam itu, kami sudah terbiasa memiliki representasi daftar kedekatan dan menggunakan pola berulang untuk mengunjungi semua tetangga langsung ( karena pohon itu adalah anak langsung ) dari sebuah node , kita sering mengabaikan bahwa implementasi get_all_immediate_neighbours yang buruk dapat menyebabkan perbedaan dalam penggunaan memori dari algoritma yang mendasarinya.

Lebih lanjut, jika simpul graf memiliki faktor percabangan b, dan diameter h ( untuk pohon ini adalah tinggi pohon ), jika kita menyimpan semua tetangga terdekat pada setiap langkah mengunjungi simpul, kebutuhan memori akan menjadi O besar (bh) . Namun, jika kita hanya mengambil satu tetangga (langsung) pada satu waktu dan mengembangkannya, kompleksitas memori akan berkurang menjadi O besar (h) . Sementara jenis implementasi yang pertama disebut sebagai DFS , jenis yang terakhir disebut Backtracking .

Sekarang Anda lihat, jika Anda bekerja dengan bahasa tingkat tinggi, kemungkinan besar Anda benar-benar menggunakan Backtracking dalam kedok DFS. Selain itu, melacak node yang dikunjungi untuk kumpulan masalah yang sangat besar bisa sangat membutuhkan memori; memanggil desain get_all_immediate_neighbours yang cermat (atau algoritme yang dapat menangani kunjungan kembali node tanpa masuk ke loop tak terbatas).

[1] Stuart Russell dan Peter Norvig, Artificial Intelligence: A Modern Approach, Edisi ke-3

Kedalaman pertama adalah algoritma untuk melintasi atau mencari pohon. Lihat disini . Mundur adalah istilah yang jauh lebih luas yang digunakan di mana pun kandidat solusi dibentuk dan kemudian dibuang dengan mundur ke negara bagian sebelumnya. Lihat disini . Pencarian kedalaman pertama menggunakan backtracking untuk mencari cabang terlebih dahulu (kandidat solusi) dan jika tidak berhasil mencari cabang lainnya.

DFS menjelaskan cara Anda ingin menjelajahi atau melintasi grafik. Ini berfokus pada konsep melangkah sedalam mungkin mengingat pilihan.

Backtracking, meskipun biasanya diterapkan melalui DFS, lebih berfokus pada konsep pemangkasan subruang pencarian yang tidak menjanjikan sedini mungkin.

Pada pencarian pertama yang mendalam , Anda mulai dari akar pohon dan kemudian menjelajah sejauh setiap cabang, lalu Anda mundur ke setiap simpul induk berikutnya dan melintasi anak-anaknya

Melacak mundur adalah istilah umum untuk memulai di akhir tujuan, dan secara bertahap bergerak mundur, secara bertahap membangun solusi.

IMO, pada node tertentu dari backtracking, Anda mencoba untuk mendalami percabangan terlebih dahulu ke setiap anak, tetapi sebelum Anda bercabang ke salah satu node anak, Anda perlu "menghapus" status anak sebelumnya (langkah ini sama dengan kembali berjalan ke simpul orang tua). Dengan kata lain, setiap saudara kandung menyatakan tidak boleh saling mempengaruhi.

Sebaliknya, selama algoritme DFS normal, Anda biasanya tidak memiliki batasan ini, Anda tidak perlu menghapus (jalur mundur) status saudara sebelumnya untuk membuat node saudara berikutnya.

Ide - Mulai dari titik mana pun, periksa apakah itu titik akhir yang diinginkan, jika ya maka kami menemukan solusi lain pergi ke semua kemungkinan posisi berikutnya dan jika kita tidak dapat melangkah lebih jauh, kembali ke posisi sebelumnya dan cari alternatif lain yang menandai saat ini jalan tidak akan membawa kita ke solusi.

Sekarang backtracking dan DFS adalah 2 nama berbeda yang diberikan untuk ide yang sama yang diterapkan pada 2 tipe data abstrak yang berbeda.

Jika ide diterapkan pada struktur data matriks, kami menyebutnya backtracking.

Jika ide yang sama diterapkan pada pohon atau grafik maka kami menyebutnya DFS.

Klise di sini adalah bahwa matriks dapat diubah menjadi grafik dan grafik dapat diubah menjadi matriks. Jadi, kami benar-benar menerapkan idenya. Jika pada grafik maka kita menyebutnya DFS dan jika pada matriks kita menyebutnya backtracking.

Ide di kedua algoritme itu sama.

Backtracking hanyalah pencarian mendalam pertama dengan kondisi penghentian tertentu.

Pertimbangkan untuk berjalan melalui labirin di mana untuk setiap langkah Anda membuat keputusan, keputusan itu adalah panggilan ke tumpukan panggilan (yang melakukan pencarian mendalam pertama Anda) ... jika Anda mencapai akhir, Anda dapat kembali ke jalan Anda. Namun, jika Anda mencapai jalan buntu, Anda ingin kembali dari keputusan tertentu, pada dasarnya kembali dari fungsi pada tumpukan panggilan Anda.

Jadi ketika saya memikirkan mundur, saya peduli

1. Negara
2. Keputusan
3. Kasus Dasar (Ketentuan Penghentian)

Saya menjelaskannya dalam video saya tentang mundur di sini .

Analisis kode backtracking ada di bawah. Dalam kode mundur ini saya ingin semua kombinasi yang akan menghasilkan jumlah atau target tertentu. Oleh karena itu, saya memiliki 3 keputusan yang membuat panggilan ke tumpukan panggilan saya, pada setiap keputusan saya dapat memilih nomor sebagai bagian dari jalur saya untuk mencapai jumlah target, melewati nomor itu, atau mengambilnya dan mengambilnya lagi. Dan kemudian jika saya mencapai kondisi penghentian, langkah mundur saya hanyalah kembali . Kembali adalah langkah mundur karena keluar dari panggilan itu di tumpukan panggilan.

class Solution:    

"""

Approach: Backtracking 

State
    -candidates 
    -index 
    -target 

Decisions
    -pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
    -pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
    -skip one --> call func changing state: index + 1, target, path

Base Cases (Termination Conditions)
    -if target == 0 and path not in ret
        append path to ret
    -if target < 0: 
        return # backtrack 

"""

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """
    @desc find all unique combos summing to target
    @args
        @arg1 candidates, list of ints
        @arg2 target, an int
    @ret ret, list of lists 
    """
    if not candidates or min(candidates) > target: return []

    ret = []
    self.dfs(candidates, 0, target, [], ret)
    return ret 

def dfs(self, nums, index, target, path, ret):
    if target == 0 and path not in ret: 
        ret.append(path)
        return #backtracking 
    elif target < 0 or index >= len(nums): 
        return #backtracking 


    # for i in range(index, len(nums)): 
    #     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)

    pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
    pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
    skip_one = self.dfs(nums, index + 1, target, path, ret)