Giải thích BFS và DFS về backtracking

Question

Wikipedia về Depth First Search: tìm kiếm

Depth-first (DFS) là một thuật toán để vượt qua hoặc tìm kiếm một cây, cấu trúc cây, hoặc biểu đồ. Một bắt đầu từ gốc (chọn một số nút làm gốc trong trường hợp biểu đồ) và khám phá hết mức có thể dọc theo mỗi nhánh trước khi quay lại.

Vì vậy, tìm kiếm đầu tiên là gì?

"một thuật toán mà chọn một nút khởi động, kiểm tra tất cả các nút backtracks, chọn con đường ngắn nhất, chọn hàng xóm các nút backtracks, chọn con đường ngắn nhất, cuối cùng tìm thấy con đường tối ưu bởi vì của đi qua từng con đường do liên tục quay lui.

Regex 012.'s cắt tỉa - backtracking?

Thuật ngữ backtracking gây nhầm lẫn do sự đa dạng của việc sử dụng. UNIX của find cắt tỉa một SO-người dùng giải thích với backtracking. Regex Buddy sử dụng thuật ngữ "backtracking thảm họa" nếu bạn không giới hạn phạm vi của Regexes của bạn. Nó có vẻ là một chiếc ô được sử dụng rộng rãi. Vì vậy:

1. Làm thế nào để bạn xác định "backtracking" đặc biệt cho Lý thuyết đồ thị?
2. "Quay lại" trong Tìm kiếm đầu tiên và Tìm kiếm đầu tiên chiều sâu là gì?

[Added]

định nghĩa tốt về backtracking và các ví dụ

1. The Brute-force method
2. Stallman (?) Phát minh ra thuật ngữ "dependency-directed backtracking"
3. backtracking và regex dụ
4. Depth First Search definition.

Answer 1

Sự rắc rối do thỏa thuận hợp vì quay lui là cái gì đó xảy ra trong tìm kiếm, nhưng nó cũng đề cập đến một kỹ thuật giải quyết vấn đề cụ thể mà rất nhiều tùy ý được thực hiện. Các chương trình như vậy được gọi là backtrackers.

Hình ảnh lái xe vào một vùng lân cận, luôn đi theo lượt đầu tiên bạn thấy (giả sử không có vòng lặp) cho đến khi bạn chạm vào một ngõ cụt, tại thời điểm đó bạn quay trở lại giao lộ của con phố tiếp theo. Đây là loại "backtracking" đầu tiên, và nó tương đương với cách sử dụng thông tục của từ đó.

Cách sử dụng cụ thể hơn đề cập đến chiến lược giải quyết vấn đề tương tự như tìm kiếm theo chiều sâu nhưng ngược lại khi nhận ra rằng nó không đáng tiếp tục xuống một số cây con.

Đặt một cách khác - một DFS ngây thơ mù quáng truy cập từng nút cho đến khi đạt được mục tiêu. Có, nó "backtracks" trên các nút lá. Nhưng backtracker cũng có nhạc nền trên các nhánh vô dụng. Một ví dụ là tìm kiếm một bảng Boggle cho các từ. Mỗi viên gạch được bao quanh bởi 8 người khác, vì vậy cây là rất lớn, và DFS ngây thơ có thể mất quá nhiều thời gian. Nhưng khi chúng ta thấy sự kết hợp như "ZZQ", chúng ta có thể dừng tìm kiếm một cách an toàn từ thời điểm này, vì việc thêm nhiều chữ cái hơn sẽ không tạo ra một từ đó.

Tôi thích những bài giảng này của Giáo sư Julie Zelenski. Cô giải quyết 8 queens, một câu đố sudoku, và một câu đố thay thế số bằng cách sử dụng backtracking, và tất cả mọi thứ là độc đáo hoạt hình. Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11

Cây là biểu đồ trong đó có hai đỉnh chỉ có một đường đi giữa chúng. Điều này giúp loại bỏ khả năng của chu kỳ. Khi bạn đang tìm kiếm một biểu đồ, bạn thường sẽ có một số logic để loại bỏ các chu kỳ, do đó, hành vi là như nhau. Ngoài ra, với đồ thị có hướng, bạn không thể theo các cạnh theo hướng "sai".

Từ những gì tôi có thể nói, trong bài báo Stallman, họ đã phát triển một hệ thống logic không chỉ nói "có" hoặc "không" trên truy vấn mà thực sự đề xuất sửa lỗi cho các truy vấn không chính xác bằng cách thực hiện số thay đổi nhỏ nhất. Bạn có thể thấy nơi định nghĩa đầu tiên của backtracking có thể đi vào hoạt động.