Tìm đường đi ngắn nhất giữa hai điểm trên lưới, sử dụng Haskell

Question

Đây là vấn đề mà tôi có thể dễ dàng giải quyết một cách phi chức năng.

Nhưng giải quyết nó trong Haskell là cho tôi những vấn đề lớn. Tôi không có kinh nghiệm khi nói đến lập trình chức năng chắc chắn là một lý do.

Sự cố:

Tôi có trường 2D được chia thành các hình chữ nhật có kích thước bằng nhau. Một lưới đơn giản. Một số hình chữ nhật là khoảng trống (và có thể được chuyển qua) trong khi các hình chữ nhật khác là không thể vượt qua được. Đặt hình chữ nhật bắt đầu A và hình chữ nhật đích B, làm cách nào để tính đường đi ngắn nhất giữa hai hình ảnh? Phong trào chỉ có thể theo chiều dọc và chiều ngang, theo từng bước một hình chữ nhật lớn.

Làm cách nào để tôi hoàn thành việc này trong Haskell? Đoạn mã chắc chắn chào đón, nhưng cũng chắc chắn không cần thiết. Và các liên kết đến các tài nguyên khác cũng rất được hoan nghênh!

Cảm ơn!

Answer 1

Tôi muốn trình bày lưới dưới dạng danh sách các danh sách, nhập [[Bool]]. Và tôi muốn xác định một chức năng để biết nếu một yếu tố lưới là đầy đủ:

type Grid = [[Bool]] 
isFullAt :: Grid -> (Int, Int) -> Bool -- returns True for anything off-grid 

Sau đó, tôi muốn định nghĩa một hàm để tìm hàng xóm:

neighbors :: (Int, Int) -> [(Int, Int)] 

Để tìm hàng xóm không đầy point bạn có thể lọc với filter (not . isFullAt) $ neighbors point.

Tại thời điểm này, tôi muốn xác định hai cấu trúc dữ liệu:

• Bản đồ mỗi điểm đến Maybe Cost
• Lưu trữ tất cả các điểm với chi phí được biết đến trong một đống

Initialize chỉ với quảng trường bắt đầu A trong heap, với chi phí bằng không.

Sau đó, vòng lặp như sau:

• Di chuyển một hình vuông min-chi phí từ các đống.
• Nếu nó chưa có trong bản đồ hữu hạn, hãy thêm nó và chi phí của nó c và thêm tất cả hàng xóm không đầy đủ vào đống với chi phí c+1.

Khi heap trống, bạn sẽ có chi phí của tất cả các điểm có thể truy cập và có thể tra cứu B trong bản đồ hữu hạn.(Thuật toán này có thể được gọi là "thuật toán Dijkstra"; Tôi đã quên.)

Bạn có thể tìm thấy bản đồ hữu hạn trong Data.Map. Tôi cho rằng có một đống (còn gọi là hàng đợi ưu tiên) ở đâu đó trong thư viện rộng lớn, nhưng tôi không biết ở đâu.

Tôi hy vọng điều này là đủ để giúp bạn bắt đầu.

Answer 2

Vâng, các loại của bạn sẽ xác định thuật toán của bạn.

Loại dữ liệu nào bạn muốn sử dụng để thể hiện lưới? Mảng hai chiều? Một danh sách các danh sách? Một cái cây? Một đồ thị?

Nếu bạn chỉ muốn con đường ngắn nhất trong biểu đồ được chỉ dẫn, việc sử dụng thứ gì đó từ FGL (gói đồ thị chức năng) sẽ là tốt nhất.