Tối ưu hóa thuật toán dựa trên Dijkstra cho bộ nhớ đệm

Question

Tôi cần phải tìm đường dẫn tối ưu kết nối hai điểm phẳng. Tôi được cung cấp một hàm xác định vận tốc trước tối đa, phụ thuộc vào cả vị trí và thời gian.

Giải pháp của tôi dựa trên thuật toán Dijkstra. Lúc đầu, tôi che máy bay bằng một mạng lưới 2D, chỉ xem xét các điểm rời rạc. Điểm được kết nối với hàng xóm của họ theo thứ tự được chỉ định, để có đủ độ phân giải hướng. Sau đó, tôi tìm thấy con đường tốt nhất bởi (loại) thuật toán Dijkstra. Tiếp theo, tôi cải thiện độ phân giải/chất lượng của đường dẫn tìm thấy. Tôi tăng mật độ mạng và thứ tự kết nối hàng xóm, cùng với việc hạn chế tìm kiếm chỉ đến các điểm đủ gần với con đường đã tìm thấy. Điều này có thể được lặp lại cho đến khi đạt được độ phân giải cần thiết.

Điều này hoạt động tốt nhưng tôi vẫn muốn cải thiện hiệu suất thuật toán tổng thể. Tôi đã thực hiện một số thủ thuật, chẳng hạn như mật độ mạng biến và thứ tự kết nối hàng xóm, dựa trên "độ mịn" của hàm giá. Tuy nhiên tôi tin rằng có một tiềm năng để cải thiện thuật toán Dijkstra chính nó (áp dụng cho đồ thị cụ thể của tôi), mà tôi chưa thể hoàn toàn nhận ra được nêu ra.

Trước tiên, hãy đồng ý với thuật ngữ. Tôi chia tất cả các điểm lưới thành 3 loại:

• - các điểm chưa được thuật toán truy cập.
• ấm - điểm được đạt tới, nhưng không được xử lý đầy đủ chưa (ví dụ: có tiềm năng để cải thiện)
• ổn định - điểm được xử lý xong.

Ở mỗi bước Thuật toán Dijkstra chọn điểm tối thiểu "rẻ nhất" ấm và sau đó cố gắng cải thiện giá của các nước láng giềng. Do bản chất của biểu đồ của tôi, tôi nhận được một loại đám mây ổn định điểm, được bao quanh bởi một lớp mỏng ấm áp điểm. Tại mỗi bước, điểm ấm áp tại chu vi đám mây được xử lý, sau đó được thêm vào đám mây ổn định và phạm vi ấm áp được mở rộng.

Vấn đề là ấm điểm được do xử lý bởi các thuật toán thường theo không gian (do đó - topology) không liên quan. Một chu vi ấm áp độc đáo bao gồm hàng trăm nghìn điểm. Tại mỗi bước, điểm ấm áp tiếp theo để xử lý là giả ngẫu nhiên (không gian), do đó hầu như không có khả năng hai điểm liên quan được xử lý cái khác.

Điều này thực sự tạo ra sự cố với việc sử dụng bộ nhớ cache CPU. Tại mỗi bước, CPU xử lý vị trí bộ nhớ giả ngẫu nhiên. Vì có số lượng lớn ấm điểm - tất cả dữ liệu có liên quan có thể không phù hợp với bộ nhớ cache CPU (thứ tự từ hàng chục đến hàng trăm MB).

Vâng, đây thực sự là hàm ý của thuật toán Dijkstra. Toàn bộ ý tưởng rõ ràng là chọn điểm ấm nhất, bất kể các thuộc tính khác.

Tuy nhiên trực giác rõ ràng là các điểm trên một bên của chu vi đám mây lớn không có ý nghĩa gì đối với các điểm ở phía bên kia (trong trường hợp cụ thể của chúng tôi), và không có vấn đề gì với hoán đổi thứ tự xử lý của chúng.

Do đó tôi mặc dù về cách "điều chỉnh" ấm điểm xử lý đơn đặt hàng, nhưng chưa ảnh hưởng đến thuật toán nói chung. Tôi nghĩ về một số ý tưởng, chẳng hạn như lặn máy bay thành các khối, và giải quyết một phần chúng một cách độc lập cho đến khi một số tiêu chí được đáp ứng, có nghĩa là giải pháp của chúng có thể bị can thiệp. Hoặc cách khác bỏ qua nhiễu và có khả năng cho phép "giải quyết lại" (tức là chuyển đổi từ ổn định trở lại ấm).

Tuy nhiên, đến nay tôi không thể tìm thấy phương pháp nghiêm ngặt.

Có ý tưởng nào về cách thực hiện việc này không? Có lẽ đó là một vấn đề, với các nghiên cứu hiện tại và (hy vọng) các giải pháp?

Xin cảm ơn trước. Và xin lỗi vì câu hỏi dài.

Answer 1

Những gì bạn đang mô tả là động lực đằng sau các A* search algorithm, một sự sửa đổi của thuật toán Dijkstra có thể cải thiện đáng kể thời gian chạy bằng cách hướng dẫn tìm kiếm theo một hướng mà có thể chọn điểm mà tục nhận được gần hơn và gần gũi hơn với các Nơi Đến. A * không bao giờ thực hiện thêm bất kỳ công việc nào hơn là việc thực hiện Dijkstra ngây thơ, và thường có xu hướng mở rộng các nút được nhóm lại trên biên giới của các nút ấm gần nút đích nhất.

Nội bộ, A * hoạt động bằng cách tăng thêm thuật toán Dijkstra với hàm heuristic ước tính khoảng cách còn lại cho nút đích. Điều này có nghĩa rằng nếu bạn nhận được một xấp xỉ thô về cách xa một nút nhất định từ đích đến, bạn có thể kết thúc bỏ qua các nút không cần xử lý để ưu tiên các nút có khả năng tốt hơn.

A * không được thiết kế như một thuật toán bộ nhớ cache tối ưu, nhưng tôi tin rằng sự gia tăng về tốc độ do

1. Mở rộng nút ít hơn (ít hơn trong bộ nhớ cache), và
2. Mở rộng nút gần gũi hơn với mục tiêu (được xử lý gần đây hơn và do đó có nhiều khả năng nằm trong bộ nhớ cache)

sẽ mang đến cho bạn hiệu suất tăng cao và hiệu suất bộ nhớ cache tốt hơn.

Hy vọng điều này sẽ hữu ích!