Tại sao tìm kiếm rộng đầu tiên sử dụng nhiều bộ nhớ hơn chiều sâu đầu tiên?

Question

Tôi không thể tìm thấy câu trả lời cho câu hỏi này trực tuyến, và trong các câu trả lời khác cho câu hỏi tương tự như vậy, dường như là một lợi thế của DFS là nó sử dụng ít bộ nhớ hơn DFS.

Với tôi điều này có vẻ ngược lại với những gì tôi mong đợi. BFS chỉ phải lưu trữ nút cuối cùng mà nó đã truy cập. Ví dụ, nếu chúng ta đang tìm kiếm số 7 trong cây dưới đây:

Nó sẽ tìm kiếm các nút với giá trị 8, sau đó 3, 10, 1, 6, 14, 4, sau đó finaly 7. Đối với DFS, nó sẽ tìm kiếm nút có giá trị 8, sau đó 3, 1, 6, 4, rồi cuối cùng là 7.

Nếu mỗi nút được lưu trữ trong bộ nhớ, với thông tin về giá trị của nó, con của nó và vị trí của nó trong cây sau đó một chương trình BFS sẽ chỉ cần lưu trữ thông tin về vị trí của nút cuối cùng mà nó đã truy cập, sau đó nó có thể kiểm tra cây và tìm nút tiếp theo trong cây. Một chương trình DFS phải lưu trữ nút cuối cùng, cũng như tất cả các nút mà nó đã truy cập để nó không kiểm tra lại và chỉ chu kỳ qua tất cả các nút lá sắp tắt một trong các nút thứ hai đến các nút thế hệ cuối cùng.

Vậy tại sao BFS thực sự sử dụng ít bộ nhớ hơn?

Answer 1

Hoặc phương pháp tìm kiếm có thể được viết để nó chỉ phải theo dõi nút trước đó, nhưng sau đó DFS là hiệu quả hơn so với BFS.

DFS chỉ phải di chuyển một cấp tại một thời điểm để tìm hiểu xem có nhiều nút lân cận hơn không. Nó sẽ di chuyển qua các nút theo thứ tự này để máng tìm kiếm tất cả trong số họ:

8-3-1-3-6-4-6-7-6-3-8-10-14-13-14-10-8 

Các BFS phải đi lên và xuống cây tất cả các cách để trên đầu bất cứ khi nào nó đi để nửa kia của cây. Nó sẽ di chuyển qua các nút theo thứ tự này:

8-3-8-10-8-3-1-3-6-3-8-10-14-10-8-3-1-6-4-6-7-6-3-8-10-14-13-14-10-8 

(Tôi không chắc chắn nếu điều đó hoàn tất, có lẽ thậm chí phải đi lên và xuống thêm vài lần để tìm ra rằng không còn các nút ở cấp độ cuối cùng.)

Như bạn thấy, BFS kém hiệu quả hơn nhiều nếu bạn muốn triển khai thuật toán sử dụng bộ nhớ tối thiểu.

Nếu bạn muốn sử dụng nhiều bộ nhớ hơn để làm cho các thuật toán hiệu quả hơn, thì chúng sẽ có hiệu suất gần như giống nhau, về cơ bản chỉ trải qua từng nút một lần. DFS cần ít bộ nhớ hơn vì nó chỉ phải theo dõi các nút trong một chuỗi từ trên xuống dưới, trong khi BFS phải theo dõi tất cả các nút trên cùng một mức.

Ví dụ, trong cây cân bằng với 1023 nút, DFS phải theo dõi 10 nút, trong khi BFS phải theo dõi 512 nút.

Answer 2

Nói chung, có thể hoặc có thể không phụ thuộc vào biểu đồ cụ thể.

Tìm kiếm theo chiều sâu đầu tiên sử dụng ngăn xếp, chứa các nút từ gốc đến nút đang được tìm kiếm. Vì vậy, tại hầu hết bán kính của biểu đồ.

Tìm kiếm theo chiều rộng đầu tiên sử dụng hàng đợi, chứa các nút ở phía trước tìm kiếm. Vì vậy, tối đa tất cả các nút ở khoảng cách d.

Trong đồ thị chung, tất cả những gì bạn có thể nói là nó ở hầu hết tất cả các nút trong cây trong cả hai trường hợp.

Nhưng nếu bạn có một cân bằng (hoặc hầu hết là như vậy) k cây -ary, đó là chiều sâu, tức là bán kính, sẽ chỉ có O (log (n)), trong khi lớp thấp nhất sẽ chứa O (n) các nút (n/2 cho cây nhị phân và thậm chí nhiều hơn cho các mức độ cao hơn).

tìm kiếm Vì vậy, chiều sâu-đầu tiên sẽ chỉ sử dụng O (log (n )) nhớ và tìm kiếm theo chiều rộng sẽ sử dụng O (n ). Đối với cây cân đối k; đối với các trường hợp khác, các kết quả khác nhau là có thể (nhưng đối với hầu hết các đường kính đồ thị phổ biến vẫn sẽ nhỏ hơn đáng kể so với chu vi).

Answer 3

BFS không luôn luôn sử dụng nhiều bộ nhớ hơn. Cây bạn có, đặc biệt, là một ví dụ mà không phải là.

xem xét cây này: (source)

Với BFS, tại một số sân khấu, tất cả các nút 8-15 sẽ có trong bộ nhớ.

Với DFS, bạn sẽ không bao giờ có nhiều hơn 4 nút trong bộ nhớ (tương đương với chiều cao của cây).

Sự khác biệt trở nên tệ hơn rất nhiều như cây đi lớn hơn (miễn là nó vẫn khá đầy đủ).

Cụ thể hơn, BFS sử dụng bộ nhớ O(branchingFactor^maxDepth) hoặc O(maxWidth), trong đó DFS chỉ sử dụng O(maxDepth).

Nếu maxWidth < maxDepth, BFS nên sử dụng ít bộ nhớ hơn (giả sử bạn sử dụng các biểu diễn tương tự cho cả hai), nhưng điều này hiếm khi đúng.