Thuật toán tối ưu cho tìm kiếm đường dẫn trong ma trận không khớp hoàn toàn với bộ nhớ

Question

Tôi đang gặp phải vấn đề khó khăn:

Hãy tưởng tượng tôi có bản đồ của một quốc gia, được biểu diễn bằng một ma trận lớn của Ô. Mỗi ô đại diện cho 1 mét vuông lãnh thổ. Mỗi ô được thể hiện dưới dạng giá trị double giữa 0 và 1 thể hiện chi phí di chuyển ngang qua ô.

Bản đồ rõ ràng không phải là fittable trong bộ nhớ.

Tôi đang cố gắng bọc tâm trí của mình một cách để tính toán đường dẫn tối ưu cho rô bốt, từ điểm bắt đầu đến vị trí kết thúc. Ý tưởng đầu tiên mà tôi có là tạo một cửa sổ chuyển động giống như TCP, với một bản đồ thực sự xung quanh con robot đang di chuyển và thực hiện thuật toán A * bên trong, nhưng tôi đang gặp phải một số vấn đề với bản đồ pathfinding, vv ...

Tôi đang tìm kiếm các tài liệu về thuật toán giống như A * và tôi không thể hình dung được gần đúng về những gì sẽ là một giải pháp tốt cho vấn đề này.

Tôi tự hỏi liệu có ai đó đã gặp phải sự cố tương tự hoặc có thể giúp đưa ra ý tưởng về giải pháp khả thi không!

Cảm ơn trước :)

Answer 1

Vì tôi không biết chính xác dữ liệu, đây là một số thông tin có thể có ích:

• Một con đường một phần của một con đường ngắn nhất là bản thân một con đường ngắn nhất. I E. bạn có thể chia ma trận của bạn thành các bảng con và tìm (tất cả) các đường đi ngắn nhất trong đó. Lưu ý rằng bạn không phải lưu trữ tất cả các kết quả: Bạn ví dụ: có thể tiết kiệm bộ nhớ bằng cách không lưu một đường dẫn đầy đủ mà chỉ là thông tin: Đường dẫn đi từ A đến B. Các nút trung gian có thể được tính toán lại sau hoặc được lưu trữ trong một tệp để sử dụng sau này. Bạn thậm chí có thể tính toán trước một số đường đi ngắn nhất cho các khu vực nhất định.

• Một cách tiếp cận khác là bạn có thể nén ma trận của mình theo một cách nào đó. I E. nếu bạn có khu vực rộng lớn chỉ bao gồm một và cùng một số, nó có thể là tốt để lưu trữ chỉ số đó và kích thước của khu vực đó.

• Một cách tiếp cận khác (liên quan đến tính toán trước một số đường đi ngắn nhất) là tạo các cấp độ chi tiết khác nhau cho bản đồ của bạn. Xem xét một bản đồ của Hoa Kỳ, điều này có thể trông như sau: Mức độ chi tiết nhất chỉ chứa các thành phố New York, Los Angeles, Chicago, Dallas, Philadelphia, Houston und Phoenix. Các cấp càng tốt, càng có nhiều thành phố, nhưng - mặt khác - khu vực nhỏ hơn trong toàn bộ bản đồ của bạn được hiển thị bởi chúng.

Answer 2

Vấn đề của bạn có bất kỳ cấu trúc đặc biệt nào không, ví dụ: giữ sự bất bình đẳng tam giác/bạn có thể đảm bảo rằng đường đi ngắn nhất không chạy lại qua lại không? Bạn có muốn thực hiện truy vấn nhiều lần không? (Nếu như vậy bạn có thể thực hiện xử lý trước mà sẽ phân bổ theo nhiều truy vấn.) Bạn có cần giải pháp tối thiểu chính xác không, hoặc liệu cái gì đó trong một yếu tố epsilon có được không?

Một ý nghĩ là bạn có thể coarsen ma trận - hình thành 100 mét bởi 100 mét vuông, và xác định khoảng cách đường đi ngắn nhất thông qua 100 \ lần 100 ô vuông. Bây giờ điều này sẽ phù hợp trong bộ nhớ (khoảng 1 Gigabyte), bạn có thể chạy Dijkstra, và sau đó mở rộng từng bước thông qua 100 \ 100 lần vuông.

Ngoài ra, bạn đã thử chạy phiên bản chuyển tiếp về phía trước của thuật toán Dijkstra chưa? I E., mở rộng từ nguồn và tìm kiếm bồn rửa chén cùng một lúc và dừng lại khi có giao lộ.

Ngẫu nhiên, tại sao bạn cần mức độ chi tiết cao như vậy?

Answer 3

Dưới đây là một số ý tưởng có thể hoạt động

Bạn có thể lập mô hình đường đi của mình dưới dạng đường cong tuyến tính từng phần. Nếu bạn có 31 đoạn đường thì đường cong của bạn được mô tả đầy đủ bằng 60 số. Mỗi phòng trong số các đường cong có thể có chi phí, vì vậy chi phí là một chức năng về hình thức sau

chi phí (x1, x2, x3 ..... x60)

Bây giờ vấn đề của bạn là để tìm ra tối ưu toàn cầu của một hàm của 60 biến. Bạn có thể sử dụng các phương pháp tiêu chuẩn để làm điều này. Một ý tưởng là sử dụng các thuật toán di truyền. ý tưởng khác là sử dụng một phương pháp Carlo monte như song song luyện

http://en.wikipedia.org/wiki/Parallel_tempering

Bất cứ khi nào bạn có một con đường đầy hứa hẹn sau đó bạn có thể sử dụng nó như là một điểm khởi đầu để tìm một địa phương tối thiểu của hàm chi phí. Có lẽ bạn có thể sử dụng một số nội suy để làm cho hàm chi phí của bạn có thể khác biệt. Sau đó, bạn có thể sử dụng phương thức Newton (hay đúng hơn là BFGS) để tìm hàm mimima cục bộ của hàm chi phí.

http://en.wikipedia.org/wiki/Local_minimum

http://en.wikipedia.org/wiki/BFGS

Vấn đề của bạn là hơi tương tự như vấn đề của việc tìm kiếm con đường phản ứng trong hệ thống hóa học. Có lẽ bạn có thể tìm thấy một số nguồn cảm hứng trong cuốn sách "Phong cảnh năng lượng" của Davis Wales.

Nhưng tôi cũng có một số câu hỏi sau:

• Có cần thiết cho bạn để tìm ra con đường tối ưu, hoặc là bạn chỉ cần tìm kiếm một con đường đó là OK?
• Bạn có bao nhiêu thời gian và sức mạnh của máy tính?
• Robot có thể thực hiện các vòng quay sắc nét hay bạn cần thêm mô hình vật lý để cải thiện chức năng chi phí?