Làm thế nào để tìm ra con đường ngắn nhất trong loại mê cung

Question

Red Dot - Represents the initial location 
Black Dot - Already occupied 
Green - Free to occupy 
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8] 

Ví dụ:

Các red dot có thể đặt bản thân chỉ có một di chuyển tại một thời điểm và có thể di chuyển trong một màu xanh lá cây Sáu vòng tròn được gắn vào nó. Phương pháp nhanh nhất để tính đường đi ngắn nhất trong loại mê cung này là gì.

Answer 1

Trước hết, bạn không cần Dijkstra, bởi vì tất cả các giá trị của các cạnh đều giống nhau. Bạn có thể sử dụng thuật toán đơn giản BFS hoặc DFS. Trường hợp phức tạp tồi tệ nhất là như nhau nhưng tôi sẽ sử dụng BFS vì nó có độ phức tạp trung bình tốt hơn. Tuy nhiên, O (| V | + | E |) là nhanh nhất bạn có thể nhận được ở đây và nó đã được chứng minh.

Làm cách nào để biểu đồ của bạn được thể hiện? Cách tốt nhất là giữ một danh sách các hàng xóm cho mỗi Node. Dấu chấm đen từ ví dụ của bạn không được tính là hàng xóm. Vì vậy, trong ví dụ của bạn, mỗi nút sẽ có 0 (được bao phủ bởi các dấu chấm đen) cho 6 người hàng xóm. Sau đó, bạn có thể đến bất cứ nơi nào bạn có thể nhận được từ bất kỳ điểm nút nào thông qua các danh sách này.

Thuật toán BFS có thuộc tính mà nó gán cho mỗi nút một lớp, có nghĩa là nó cách xa nút khởi đầu. Bạn bắt đầu từ điểm bắt đầu của bạn và lớp hiện tại của bạn sẽ là 0. Sau đó, bạn chỉ cần làm theo tất cả các nút từ một lớp hiện tại (thường được giữ ở hàng đợi) và cố gắng tìm hàng xóm của nó (từ danh sách những người hàng xóm), không có lớp được chỉ định và bạn gán cho họ +1 lớp cao hơn.Một khi bạn tìm thấy nút của bạn, (mà vẫn có thể có x, y làm thuộc tính để kiểm tra đường viền (hoặc đường viền bool thuộc tính)), ở biên giới mê cung của bạn, bạn biết nó ở xa giá trị lớp của bạn. Nếu bạn muốn in một cách chính xác, bạn chỉ phải tìm cách quay trở lại (thông qua danh sách các hàng xóm của bạn) mà đáp ứng các điều kiện mà mỗi bước là ở lớp -1 thấp hơn. Điều này sẽ in theo cách từ đầu đến cuối, nhưng tôi chắc chắn bạn sẽ nhận được kết quả của mình với một chút trợ giúp từ cấu trúc dữ liệu Stack :)

Answer 2

Điều bạn gặp phải là vấn đề đồ thị "đơn giản". Kết nối đồ thị là những động thái hợp pháp mà bạn có. Nút bắt đầu là chấm đỏ của bạn. Để có được một nút đầu cuối đơn, hãy tạo thêm một vòng tròn bên ngoài mê cung đã cho; kết nối tất cả các nút thoát thực với vòng kết nối mới với chi phí bằng 0.

Bây giờ, hãy áp dụng thuật toán Dijkstra. Làm xong.

---

Một cách khác để xem vấn đề là đệ quy. Di chuyển chấm đỏ, đánh dấu vị trí cũ màu đen. Tái xuất từ ​​vị trí mới. Quay trở lại khi bạn thoát (trả về chiều dài đường dẫn 1) hoặc không có động thái hợp pháp (chiều dài đường dẫn trả về vô hạn). Giữ đường dẫn ngắn nhất được biết.

Làm những điều đó khiến bạn không bị kẹt?

Answer 3

A * tìm kiếm thuật toán

(từ: https://en.wikipedia.org/wiki/A*_search_algorithm)

Các giả sau đây mô tả các thuật toán [đáng ngờ - thảo luận]:

function A*(start,goal) 
    ClosedSet := {}  // The set of nodes already evaluated. 
    OpenSet := {start} // The set of tentative nodes to be evaluated, initially containing the start node 
    Came_From := the empty map // The map of navigated nodes. 


    g_score := map with default value of Infinity 
    g_score[start] := 0 // Cost from start along best known path. 
    // Estimated total cost from start to goal through y. 
    f_score := map with default value of Infinity 
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal) 

    while OpenSet is not empty 
     current := the node in OpenSet having the lowest f_score[] value 
     if current = goal 
      return reconstruct_path(Came_From, goal) 

     OpenSet.Remove(current) 
     ClosedSet.Add(current) 
     for each neighbor of current 
      if neighbor in ClosedSet 
       continue  // Ignore the neighbor which is already evaluated. 
     tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path. 
     if neighbor not in OpenSet // Discover a new node 
      OpenSet.Add(neighbor) 
     else if tentative_g_score >= g_score[neighbor] 
      continue  // This is not a better path. 

     // This path is the best until now. Record it! 
     Came_From[neighbor] := current 
     g_score[neighbor] := tentative_g_score 
     f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal) 

return failure 

function reconstruct_path(Came_From,current) 
    total_path := [current] 
    while current in Came_From.Keys: 
     current := Came_From[current] 
     total_path.append(current) 
    return total_path 

như vậy, như xa như Tôi hiểu - bạn có thể đặt nút bắt đầu tại vị trí dấu chấm màu đỏ \ vị trí trung tâm và nút mục tiêu là x = 0 hoặc y = 0 hoặc x = 8 hoặc y = 8 (bạn có thể thực hiện 4 cuộc gọi chức năng và tối thiểu)

cho giá trị heuristic cho nút - chỉ cần đặt các nút bị chặn đen rất cao, điều này sẽ khiến chúng không thể truy cập được, vì vậy thuật toán sẽ vượt qua chúng.