Làm thế nào để bạn sử dụng BFS hai chiều để tìm đường đi ngắn nhất?

Question

Làm thế nào để bạn sử dụng BFS hai chiều để tìm đường đi ngắn nhất? Giả sử có một lưới 6x6. Điểm bắt đầu nằm trong (0,5) và điểm cuối là (4,1). Con đường ngắn nhất sử dụng bfs hai chiều là gì? Không có chi phí đường dẫn. Và nó là vô hướng.

Answer 1

BFS hai hướng hoạt động như thế nào?

Đồng thời chạy hai BFS từ cả hai đỉnh nguồn và đích, chấm dứt một khi một đỉnh chung cho cả hai lần chạy được phát hiện. Đỉnh này sẽ nằm giữa nguồn và đích.

Tại sao nó tốt hơn BFS?

BFS hai chiều sẽ mang lại kết quả tốt hơn nhiều so với BFS đơn giản trong hầu hết các trường hợp. Giả sử khoảng cách giữa nguồn và đích là k và hệ số phân nhánh là B (mỗi đỉnh có cạnh B trung bình).

• BFS sẽ đi ngang 1 + B + B^2 + ... + B^k đỉnh.
• BFS hai hướng sẽ đi ngang 2 + 2B^2 + ... + 2B^(k/2) đỉnh.

Đối với lớn B và k, thứ hai rõ ràng là nhanh hơn đầu tiên.

---

Trong trường hợp của bạn:

Để đơn giản tôi sẽ giả định rằng không có trở ngại trong ma trận. Đây là những gì sẽ xảy ra:

iteration 0 (init): 
front1 = { (0,5) } 
front2 = { (4,1) } 

iteration 1: 
front1 = { (0,4), (1,5) } 
front2 = { (4,0), (4,2), (3,1), (5,1) } 

iteration 2: 
front1 = { (0,3), (1,4), (2,5) } 
front2 = { (3,0), (5,0), (4,3), (5,2), (3,2), (2,1) } 

iteration 3: 
front1 = { (0,2), (1,3), (2,4), (3,5) } 
front2 = { (2,0), (4,4), (3,3), (5,3), (2,2), (1,1), } 

iteration 4: 
front1 = { (0,1), (1,2), .... } 
front2 = { (1,2) , .... } 

Bây giờ, chúng tôi đã phát hiện ra rằng mặt trận giao nhau tại (1,2), cùng với những con đường đưa đến đạt được điều đó từ nguồn và mục tiêu đỉnh:

path1: (0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) 
path2: (4,1) -> (3,1) -> (2,1) -> (1,1) -> (1,2) 

Bây giờ chúng ta chỉ cần đảo ngược đường dẫn 2 và nối nó vào đường 1 (loại bỏ một trong các đỉnh giao nhau chung), để cho chúng ta đường dẫn đầy đủ của chúng tôi:

(0,5) -> (0,4) -> (0,3) -> (0,2) -> (1,2) -> (1,1) -> (2,1) -> (3,1) -> (4,1)