Tìm kiếm theo chiều sâu (DFS)
Tìm kiếm theo chiều sâu (Depth-First Search, DFS) làm ngược với BFS: luôn đi sâu nhất có thể vào một nhánh trước, chỉ quay lui khi gặp ngõ cụt. Cấu trúc dữ liệu tự nhiên cho "sâu nhất trước" là ngăn xếp LIFO (vào sau, ra trước).
Hãy hình dung bạn đi trong một mê cung. BFS giống như bạn cử nhiều người dò song song, mỗi ngã rẽ tách một nhánh, tất cả tiến đều nhau từng bước một. DFS thì ngược lại: bạn đi một mình, gặp ngã rẽ nào cứ chọn một hướng và bước tới tận cùng, chỉ khi đụng tường mới quay lại ngã rẽ gần nhất và thử hướng khác chưa đi. Cách này chỉ cần nhớ con đường mình đang đứng trên đó, không cần nhớ mọi ngả rẽ của cả mê cung, nên rất tiết kiệm bộ nhớ. Cái giá phải trả là bạn có thể lao rất sâu vào một hành lang cụt trước khi biết mình đi sai, và con đường đầu tiên tìm thấy chưa chắc là con đường ngắn nhất.
Đặt vấn đề: cái giá của trí nhớ
Bài trước kết thúc bằng một tin xấu. BFS đẹp về lý thuyết, đầy đủ và tối ưu, nhưng nó phải giữ
trọn một tầng của không gian trạng thái trong hàng đợi, tức O(b^d) ô nhớ. Với hệ số phân
nhánh b = 10 và độ sâu d = 12, con số đó vượt xa mọi máy tính ta có. BFS không chết vì
chậm, nó chết vì hết bộ nhớ.
Vậy câu hỏi tự nhiên là: có cách duyệt nào không cần nhớ cả một tầng hay không. Hãy quay
lại hình ảnh mê cung. Người dò theo kiểu BFS phải ghi lại vị trí của tất cả các nhóm đang tiến
song song, và số nhóm đó nhân lên theo cấp số nhân mỗi khi đi sâu thêm một bước. Nhưng người
dò theo kiểu DFS chỉ đi một mình. Cái anh ta cần nhớ chỉ là con đường từ cửa vào tới chỗ
mình đang đứng, cộng với, ở mỗi ngã rẽ trên con đường ấy, danh sách các hướng chưa thử. Con
đường dài tối đa m, mỗi ngã rẽ có tối đa b hướng, nên tổng bộ nhớ chỉ O(b·m), tuyến
tính theo độ sâu chứ không phải hàm mũ.
Đó là toàn bộ lý do DFS tồn tại. Nó không nhanh hơn BFS, không thông minh hơn BFS, và về chất lượng lời giải thì kém hơn hẳn. Cái nó mua được, và mua được rất rẻ, là khả năng chạy trên không gian mà BFS không thể đặt chân vào. Phần còn lại của bài này là câu chuyện về cái giá phải trả cho món hời đó, và về cách trả giá ít nhất có thể.
Thử ngay: DFS lao sâu vào một nhánh
Cùng đồ thị với bài BFS, nhưng để ý DFS lao sâu vào một nhánh thay vì lan theo tầng. Widget chạy thật thuật toán, nên bạn đổi đỉnh xuất phát hay đích là nó tính lại từ đầu. Thử chuyển sang BFS trên cùng đồ thị để thấy hai bên đi khác nhau ra sao.
1def dfs(do_thi, bat_dau, dich):2 bien = [bat_dau] # ngăn xếp LIFO3 da_tham = set()4 while bien:5 nut = bien.pop() # lấy nút trên cùng6 if nut == dich:7 return "tim thay"8 if nut not in da_tham:9 da_tham.add(nut)10 for ke in do_thi[nut]:11 if ke not in da_tham:12 bien.append(ke) # chỉ đẩy nút kề CHƯA thăm13 return None
Ý tưởng cốt lõi
- Lấy nút ở đỉnh ngăn xếp ra, đẩy các nút kề của nó vào đỉnh ngăn xếp.
- Nút đẩy vào sau cùng sẽ được lấy ra trước, nên DFS lao sâu theo một nhánh.
- Ưu điểm lớn: bộ nhớ chỉ
O(b·m)(chỉ giữ một nhánh đang đi), nhẹ hơn BFS rất nhiều. - Nhược điểm: không tối ưu (có thể trả về đường dài), và có thể lạc sâu vào nhánh vô ích.
Điểm mấu chốt nằm ở tính chất vào sau ra trước của ngăn xếp. Khi mở rộng một nút, ta đẩy tất cả nút kề của nó lên đỉnh. Ngay vòng lặp sau, ta lại lấy chính nút vừa đẩy gần nhất ra, tức là một nút con của nút hiện tại, chứ không phải một nút "anh em" cùng tầng. Nhờ vậy độ sâu tăng lên liên tục theo một nhánh cho tới khi nhánh đó cạn kiệt. Đối chiếu với BFS: BFS dùng hàng đợi FIFO nên nút lấy ra luôn là nút vào sớm nhất, tức nút nông nhất, khiến việc dò lan đều theo tầng. Chỉ khác nhau ở cấu trúc dữ liệu quản lý biên (ngăn xếp so với hàng đợi) mà toàn bộ hành vi duyệt đã đảo ngược.
Ký hiệu quen dùng khi phân tích: b là hệ số phân nhánh (số nút kề trung bình của
một nút), m là độ sâu lớn nhất của không gian trạng thái, d là độ sâu của lời
giải nông nhất. Với DFS, m mới là con số đáng lo, vì thuật toán sẵn sàng đi tới đáy
sâu nhất trước khi quay lui.
Mã nguồn Python
def dfs(do_thi, bat_dau, dich):
bien = [bat_dau] # ngăn xếp LIFO
da_tham = set()
cha = {bat_dau: None}
while bien:
nut = bien.pop() # lấy nút trên cùng ngăn xếp
if nut == dich:
return lan_nguoc(cha, dich)
if nut not in da_tham:
da_tham.add(nut)
for ke in do_thi[nut]:
if ke not in da_tham:
cha[ke] = nut
bien.append(ke) # đẩy nút kề vào ngăn xếp
return None
Hãy đọc kỹ ba biến trạng thái. bien là ngăn xếp, khởi tạo chỉ chứa nút gốc. Lệnh
bien.pop() không có tham số nên lấy phần tử cuối danh sách, đúng ngữ nghĩa LIFO.
da_tham chặn việc quay lại nút đã xử lý, tránh lặp vô hạn trên đồ thị có chu trình.
cha ghi lại nút nào đã đưa ta tới mỗi nút, để khi chạm đích còn lần ngược dựng lại
đường đi. Chú ý ta chỉ đánh dấu da_tham lúc lấy nút ra, chứ không phải lúc đẩy
vào, nên một nút có thể nằm nhiều lần trong ngăn xếp; kiểm tra if nut not in da_tham
đảm bảo mỗi nút chỉ được mở rộng đúng một lần.
Đệ quy: ngăn xếp ẩn của hệ thống
DFS còn một cách viết gọn hơn bằng đệ quy, không cần khai báo ngăn xếp tường minh:
def dfs_de_quy(do_thi, nut, dich, da_tham=None):
# The system call stack plays the role of the explicit LIFO stack
if da_tham is None:
da_tham = set()
if nut == dich:
return True
da_tham.add(nut)
for ke in do_thi[nut]:
if ke not in da_tham:
if dfs_de_quy(do_thi, ke, dich, da_tham):
return True
return False
Ở đây ngăn xếp lời gọi hàm của hệ thống chính là cái ngăn xếp LIFO mà bản lặp phải
tự quản. Mỗi lời gọi dfs_de_quy lồng nhau tương ứng một mức sâu hơn; khi hàm trả về
là lúc thuật toán "quay lui" lên mức trên. Cách viết này rất tự nhiên và ngắn, nhưng có
một rủi ro: nếu nhánh sâu quá, chuỗi lời gọi lồng nhau có thể làm tràn ngăn xếp
(stack overflow). Khi độ sâu lớn hoặc không kiểm soát được, bản lặp với ngăn xếp
tường minh an toàn hơn vì ta chủ động cấp phát bộ nhớ trên vùng heap.
DFS so với BFS
| Tiêu chí | BFS | DFS |
|---|---|---|
| Cấu trúc | hàng đợi FIFO | ngăn xếp LIFO |
| Cách đi | lan theo tầng | lao sâu một nhánh |
| Bộ nhớ | O(b^d) (nặng) | O(b·m) (nhẹ) |
| Tối ưu | có (chi phí bằng nhau) | không |
| Đầy đủ | có (b hữu hạn) | không, nếu nhánh sâu vô hạn |
DFS đánh đổi tính tối ưu để lấy bộ nhớ cực nhẹ: chỉ cần giữ nhánh đang đi, không phải toàn bộ biên như BFS. Khi không gian trạng thái khổng lồ, đây là khác biệt sống còn. Mục "Chặn độ sâu: từ DLS tới IDS" ngay dưới đây trình bày tìm kiếm sâu dần (IDS), thuật toán kết hợp ưu điểm của cả hai: bộ nhớ nhẹ của DFS và tính tối ưu của BFS.
Độ phức tạp và các tính chất
Xét bốn tiêu chí kinh điển dùng để đánh giá một chiến lược tìm kiếm.
- Độ phức tạp thời gian:
O(b^m)trong trường hợp xấu nhất, vì DFS có thể phải sinh mọi nút tới độ sâum. Nếu đích nằm nông mà DFS lại lỡ đi vào nhánh sâu trước, nó vẫn phải dò cạn nhánh đó rồi mới quay lui, nên rất phí công. - Độ phức tạp bộ nhớ:
O(b·m), ưu điểm nổi bật nhất. Tại mỗi mức trên nhánh đang đi, ta chỉ cần lưu nút hiện tại cùng các nút kề chưa duyệt, cộng lại theo chiều sâu cho ra tíchb·m. Đây là con số tuyến tính theo độ sâu, trong khi BFS phình theo cấp số nhân. - Tính đầy đủ (completeness): DFS không đầy đủ nếu không gian trạng thái có
nhánh sâu vô hạn hoặc có chu trình mà ta không đánh dấu nút đã thăm. Nó có thể lao
mãi xuống một nhánh vô tận và không bao giờ chạm đích, dù đích thực ra nằm ở nhánh
khác. Trên đồ thị hữu hạn có kiểm soát
da_thamthì DFS đầy đủ. - Tính tối ưu (optimality): DFS không tối ưu. Nó trả về lời giải đầu tiên gặp được theo thứ tự duyệt, chứ không phải lời giải rẻ nhất hay nông nhất.
Vì sao DFS không đầy đủ
Hãy tách bạch hai tình huống, vì sinh viên rất hay gộp chúng làm một.
Không gian hữu hạn có tập đã thăm. Ở đây DFS đầy đủ. Mỗi trạng thái chỉ được mở rộng đúng một lần, số trạng thái là hữu hạn, nên sớm muộn DFS cũng quét hết và tìm ra đích nếu đích tồn tại. Đồ thị trong hình minh họa ở trên thuộc loại này.
Không gian vô hạn hoặc rất sâu. Đây mới là chỗ DFS gãy. Nhiều bài toán có không gian trạng thái không bị chặn về độ sâu: một tác tử trong lưới vô hạn có thể đi sang phải mãi mãi, một bài toán sinh chuỗi có thể thêm ký tự mãi mãi. DFS lao xuống nhánh đầu tiên và đi mãi, không bao giờ quay lui, vì nhánh đó không bao giờ cạn để mà quay lui. Đích có thể nằm ngay bên cạnh nút gốc, chỉ cách hai bước, ở nhánh thứ hai; DFS sẽ không bao giờ nhìn thấy nó. Thuật toán không sai, nó chỉ đơn giản là không dừng.
Điểm cần khắc cốt: tính không đầy đủ của DFS không phải do chu trình (chu trình đã có tập đã thăm lo), mà do độ sâu không bị chặn. Đó là lý do lời giải cho vấn đề này, như ta sắp thấy, là chặn độ sâu lại.
Vì sao DFS không tối ưu
Nguyên nhân nằm ở chỗ DFS không hề nhìn vào độ sâu khi quyết định trả về lời giải. Nó dừng ở nút đích đầu tiên nó vấp phải, mà nút đó nằm trên nhánh nào thì hoàn toàn do thứ tự liệt kê các nút kề quyết định, một chi tiết cài đặt tùy tiện chứ không mang ý nghĩa gì về chất lượng lời giải.
Ví dụ nhỏ nhất: nút gốc A có hai nút kề, B và đích G. Nếu danh sách kề của A là [G, B] thì
bien.append đẩy G rồi B, khiến B nằm trên đỉnh ngăn xếp và được lấy ra trước. DFS chui vào
nhánh B, có thể đi qua hai chục nút, rồi vòng về G bằng một đường dài. Nó trả về đường dài đó
và tuyên bố đã xong, dù có một cạnh trực tiếp từ A tới G nằm ngay đó. Chỉ cần đảo thứ tự danh
sách kề thành [B, G] là kết quả đổi hẳn. Một thuật toán mà chất lượng lời giải phụ thuộc vào
thứ tự ta tình cờ liệt kê nút kề thì không thể gọi là tối ưu.
Chặn độ sâu: từ DLS tới IDS
Ta vừa thấy điểm gãy của DFS là độ sâu không bị chặn. Vậy hãy chặn nó lại.
Tìm kiếm giới hạn độ sâu (DLS)
Tìm kiếm giới hạn độ sâu (Depth-Limited Search, DLS) chỉ là DFS cộng thêm một luật: không
đi sâu quá mức L cho trước. Nút ở độ sâu đúng bằng L được coi như không có nút kề, nên DFS
buộc phải quay lui. Nhờ vậy DLS luôn dừng, kể cả trên không gian vô hạn.
Nhưng ta vừa đổi một vấn đề lấy một vấn đề khác. Chọn L bao nhiêu đây? Nếu L < d (giới hạn
nông hơn lời giải), DLS quay về tay không dù lời giải có tồn tại: nó không đầy đủ. Nếu L
lớn hơn d nhiều, ta lại phí công dò những tầng sâu vô ích, và mất luôn tính tối ưu. Trong đa
số bài toán ta không biết trước d, nên việc chọn L là đoán mò.
Đôi khi bản chất bài toán cho ta một giới hạn tự nhiên. Chẳng hạn bài 8-puzzle có đúng
181440 trạng thái tới được (bằng 9!/2, vì phép hoán vị chỉ chia không gian thành hai lớp
không thông nhau), nên mọi lời giải đều nằm trong độ sâu hữu hạn và ta có thể suy ra một cận
trên. Nhưng đó là ngoại lệ, không phải thông lệ.
Tìm kiếm sâu dần (IDS)
Nếu không biết chọn L nào, hãy thử tất cả, từ nhỏ tới lớn. Đó là tìm kiếm lặp sâu dần
(Iterative Deepening Search, IDS): chạy DLS với L = 0, thất bại thì chạy lại với L = 1,
rồi L = 2, cứ thế cho tới khi tìm ra lời giải.
def ids(do_thi, bat_dau, dich, gioi_han_toi_da=50):
# Try every depth limit from 0 upward until a solution appears
for L in range(gioi_han_toi_da + 1):
ket_qua = dls(do_thi, bat_dau, dich, L)
if ket_qua is not None:
return ket_qua
return None
def dls(do_thi, nut, dich, con_lai, duong=None):
# Depth-limited DFS: refuse to expand beyond the remaining budget
if duong is None:
duong = [nut]
if nut == dich:
return duong
if con_lai == 0:
return None
for ke in do_thi[nut]:
if ke not in duong: # avoid cycles along the current path
ket_qua = dls(do_thi, ke, dich, con_lai - 1, duong + [ke])
if ket_qua is not None:
return ket_qua
return None
Phản ứng đầu tiên của hầu hết mọi người là "phí quá, mỗi vòng lặp lại duyệt lại từ đầu". Phản ứng đó sai, và hiểu vì sao nó sai là một trong những bài học đẹp nhất của môn này.
Chìa khóa nằm ở chỗ trong một cây phân nhánh, số nút ở tầng cuối áp đảo tổng số nút của mọi
tầng trước cộng lại. Tầng d có b^d nút, còn tất cả các tầng từ 0 tới d-1 cộng lại chỉ
cỡ b^(d-1) nhân với một hằng số nhỏ. Vậy nên việc duyệt lại các tầng nông nhiều lần chỉ làm
phồng thêm phần rẻ nhất của công việc.
Cụ thể: tầng 1 bị duyệt lại d lần, tầng 2 bị duyệt d-1 lần, còn tầng sâu nhất d chỉ
được duyệt đúng một lần. Với b = 10 và d = 5, IDS sinh ra 5·10 + 4·100 + 3·1000 + 2·10000 + 1·100000 = 123450 nút, trong khi BFS sinh 10 + 100 + 1000 + 10000 + 100000 = 111110 nút. Chênh lệch chỉ khoảng 11 phần trăm. Ta trả thêm một phần mười công sinh nút,
và đổi lại được toàn bộ lợi thế bộ nhớ của DFS.
Kết quả là IDS gộp được ưu điểm của cả hai họ thuật toán.
| Tiêu chí | BFS | DFS | IDS |
|---|---|---|---|
| Bộ nhớ | O(b^d) | O(b·m) | O(b·d) |
| Thời gian | O(b^d) | O(b^m) | O(b^d) |
| Đầy đủ | có | không (nhánh vô hạn) | có |
| Tối ưu (chi phí đều) | có | không | có |
IDS đầy đủ vì với L đủ lớn nó chắc chắn chạm tới lời giải, và tối ưu khi chi phí bước
đều vì nó thử các giới hạn từ nhỏ tới lớn nên lời giải đầu tiên tìm được nằm ở độ sâu nhỏ
nhất. Bộ nhớ chỉ O(b·d) vì tại mỗi thời điểm nó vẫn chỉ là một DFS. Vì thế IDS là lựa chọn
mặc định cho tìm kiếm không thông tin trên không gian trạng thái lớn khi ta không biết trước
độ sâu lời giải.
IDS dạy một nguyên tắc vượt ra ngoài môn tìm kiếm: khi chi phí tăng theo cấp số nhân theo một tham số, việc lặp lại phần việc ứng với giá trị nhỏ của tham số đó gần như miễn phí. Đừng ngại tính lại từ đầu nếu phần tính lại nằm ở vùng rẻ của đường cong chi phí.
Ứng dụng: quay lui
DFS là bộ khung của họ thuật toán quay lui (backtracking), nền tảng để giải rất nhiều bài toán tổ hợp và ràng buộc. Ý tưởng chung: xây lời giải từng bước như đi sâu vào một cây các lựa chọn; mỗi khi thêm một lựa chọn mà vi phạm ràng buộc thì lập tức "cắt nhánh" và quay lui thử lựa chọn khác. Nhờ cắt sớm, ta tránh duyệt những nhánh chắc chắn hỏng.
- Xếp hậu (
n-queens): mỗi cột đặt một quân hậu, đi sâu theo cột; đặt được thì sang cột kế, không đặt được ô nào hợp lệ thì quay lui cột trước. - Tô màu đồ thị và Sudoku: gán giá trị cho một ô hay một đỉnh, kiểm tra ràng buộc, hợp lệ thì đi tiếp, kẹt thì lùi.
- Sinh hoán vị, tổ hợp, tập con: duyệt cây quyết định "chọn hay không chọn".
- Kiểm tra tính liên thông, phát hiện chu trình, sắp thứ tự tôpô trên đồ thị.
- Tưởng DFS tìm ra đường ngắn nhất. Không. DFS chỉ đảm bảo tìm được một đường, không đảm bảo ngắn. Muốn ngắn nhất trên đồ thị không trọng số, hãy dùng BFS.
- Quên đánh dấu
da_tham. Trên đồ thị có chu trình, thiếu tập này DFS sẽ quay vòng vô tận giữa vài nút.da_thamlà điều bắt buộc, không phải tùy chọn. - Nhầm
bien.pop()vớibien.pop(0).pop()lấy cuối danh sách (LIFO, đúng DFS), cònpop(0)lấy đầu danh sách (FIFO), biến thuật toán thành BFS mà không hay biết. - Lo tràn ngăn xếp ở bản đệ quy khi độ sâu lớn. Với cây rất sâu, hãy chuyển sang bản lặp dùng ngăn xếp tường minh.
Bài tập thực hành
Bài tập 1: thứ tự thăm nếu đổi thứ tự nút kề
Nếu danh sách kề của A là ["C", "B"] (đảo lại) thay vì ["B", "C"], DFS sẽ thăm các
nút theo thứ tự nào?
Gợi ý
Đẩy C rồi B vào, nên B nằm trên cùng và được lấy trước. DFS sẽ đi vào nhánh B: thứ tự thăm A, B, rồi nút kề của B (E hoặc D, tùy thứ tự), dẫn tới một đường đi khác. Thứ tự nút kề quyết định DFS chọn nhánh nào trước.
Bài tập 2: DFS đệ quy
Viết lại DFS dưới dạng đệ quy thay vì dùng ngăn xếp tường minh.
Gợi ý
Hàm dfs(nut) đánh dấu nut đã thăm, kiểm tra đích, rồi gọi đệ quy dfs(ke) cho mỗi
nút kề chưa thăm. Ngăn xếp lời gọi của hệ thống đóng vai trò chính cái ngăn xếp LIFO mà
phiên bản lặp dùng tường minh.
Bài tập 3: phát hiện DFS không tối ưu
Hãy tạo một đồ thị nhỏ mà trên đó DFS trả về đường đi dài hơn đường ngắn nhất, để minh họa DFS không tối ưu.
Gợi ý
Cho đích nằm gần gốc qua một cạnh trực tiếp, nhưng đặt một nhánh dài được DFS xét trước (do thứ tự nút kề). DFS sẽ đi hết nhánh dài rồi mới tới đích, trả về đường vòng dài hơn cạnh trực tiếp.
Tự kiểm tra
Vì sao DFS tiết kiệm bộ nhớ hơn BFS rất nhiều?
Vì DFS chỉ cần giữ nhánh đang đi (sâu tối đa m, mỗi mức vài nút kề), tức O(b·m).
BFS phải giữ toàn bộ biên của một tầng, lên tới O(b^d). Trên không gian lớn, biên
của BFS phình theo cấp số nhân còn DFS thì không.
IDS duyệt lại các tầng nông rất nhiều lần. Vì sao nó vẫn không chậm hơn BFS đáng kể?
Vì trong cây phân nhánh, tầng cuối áp đảo mọi tầng trước cộng lại. Tầng d có b^d nút,
còn tổng các tầng nông hơn chỉ cỡ b^(d-1) nhân hằng số nhỏ. IDS duyệt lại nhiều lần đúng cái
phần rẻ nhất của công việc, còn tầng đắt nhất thì nó chỉ duyệt một lần.
Cụ thể với b = 10, d = 5: IDS sinh 5·10 + 4·100 + 3·1000 + 2·10000 + 1·100000 = 123450
nút, BFS sinh 111110 nút, chênh khoảng 11 phần trăm. Đổi lại, bộ nhớ tụt từ O(b^d) xuống
O(b·d). Một món hời rõ ràng.
DFS không đầy đủ. Nguyên nhân gốc là chu trình trong đồ thị hay là độ sâu không bị chặn?
Là độ sâu không bị chặn. Chu trình đã có tập da_tham xử lý gọn: đánh dấu nút đã mở rộng
thì DFS không quay vòng nữa, và trên đồ thị hữu hạn có tập đã thăm thì DFS đầy đủ.
Cái giết DFS là không gian trạng thái không bị chặn về độ sâu, ví dụ lưới vô hạn hay bài toán sinh chuỗi không giới hạn độ dài. Ở đó nhánh đầu tiên không bao giờ cạn, nên DFS lao xuống mãi và không bao giờ quay lui để thử nhánh chứa đích, dù đích chỉ cách gốc vài bước. Thuật toán không sai, nó chỉ không dừng. Chính vì nguyên nhân gốc là độ sâu nên lời chữa cũng nằm ở độ sâu: chặn nó lại (DLS), rồi nới dần giới hạn (IDS).
Câu hỏi tự kiểm
- 1Độ phức tạp bộ nhớ của DFS là bao nhiêu?
- 2Nguyên nhân gốc khiến DFS không đầy đủ là gì?
- 3Vì sao IDS không chậm hơn BFS đáng kể dù duyệt lại các tầng nông nhiều lần?
- 4Trong bản DFS lặp, bien.pop() làm gì, và đổi thành bien.pop(0) sẽ ra sao?
Tóm tắt
DFS đảo đúng một chi tiết của BFS: thay hàng đợi FIFO bằng ngăn xếp LIFO. Chỉ một thay đổi ấy mà toàn bộ hành vi lật ngược, từ lan đều theo tầng thành lao sâu theo một nhánh, và toàn bộ hồ sơ chi phí cũng lật theo.
Món hời DFS mua được là bộ nhớ O(b·m), tuyến tính theo độ sâu thay vì hàm mũ, vì nó chỉ
cần nhớ nhánh đang đi cùng các nút kề chưa duyệt dọc nhánh đó. Đây là thứ cho phép DFS chạy trên
những không gian mà BFS thậm chí không đặt chân vào được. Cái giá là DFS không tối ưu (lời
giải trả về phụ thuộc thứ tự liệt kê nút kề, một chi tiết tùy tiện) và không đầy đủ khi độ
sâu không bị chặn (nó lao mãi xuống một nhánh vô tận). Cần phân biệt rõ: chu trình đã có tập đã
thăm lo, nguyên nhân gốc của tính không đầy đủ là độ sâu vô hạn.
Vì nguyên nhân nằm ở độ sâu nên cách chữa cũng nằm ở đó. DLS chặn cứng độ sâu tại L để
bảo đảm thuật toán dừng, nhưng lại đẩy ta vào thế phải đoán L. IDS giải quyết bằng cách
thử mọi L từ nhỏ tới lớn, và nhờ tầng cuối áp đảo mọi tầng trước cộng lại, phần việc lặp lại
chỉ tốn thêm cỡ mười phần trăm. Kết quả là IDS đầy đủ và tối ưu như BFS, nhẹ bộ nhớ như DFS, và
xứng đáng là lựa chọn mặc định cho tìm kiếm không thông tin.
Cuối cùng, đừng quên DFS còn một đời sống thứ hai ngoài việc tìm đường: nó là bộ khung của họ thuật toán quay lui, nền tảng để giải xếp hậu, Sudoku, tô màu đồ thị và vô số bài toán ràng buộc khác.
DFS dùng ngăn xếp LIFO để lao sâu một nhánh trước. Rất nhẹ về bộ nhớ
O(b·m), nhưng không tối ưu và có thể lạc sâu. Đối lập trực tiếp với BFS về cả
cấu trúc lẫn hành vi.