Một tùy chọn là sử dụng biểu đồ cảm ứng, là cách chức năng đại diện và làm việc với các cấu trúc đồ thị tùy ý. Chúng được cung cấp bởi thư viện fgl của Haskell và được mô tả trong "Inductive Graphs and Funtional Graph Algorithms" bởi Martin Erwig.
Để có giới thiệu nhẹ nhàng hơn (với hình minh họa!), Hãy xem bài đăng trên blog của tôi Generating Mazes with Inductive Graphs.
Bí quyết với đồ thị quy nạp là chúng cho phép bạn đối sánh mẫu trên biểu đồ. Các thành ngữ chức năng thông thường để làm việc với danh sách là để phân hủy chúng thành một yếu tố đầu và phần còn lại của danh sách, sau đó recurse trên rằng:
map f [] = []
map f (x:xs) = f x : map f xs
đồ thị cảm ứng cho phép bạn làm điều tương tự, nhưng đối với đồ thị. Bạn có thể phân hủy một đồ thị quy nạp thành một nút, các cạnh của nó và phần còn lại của biểu đồ.
pattern matching on a node http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/match1.png
Ở đây chúng ta phù hợp vào nút 1 và tất cả các cạnh của nó (đánh dấu màu xanh), tách biệt với phần còn lại của đồ thị.
Điều này cho phép chúng tôi viết một map cho đồ thị (trong giả Haskellish có thể được thực hiện với các từ đồng nghĩa mẫu):
gmap f Empty = Empty
gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest
Các thiếu sót chính của phương pháp này như trái ngược với danh sách là đồ thị không có một cách tự nhiên duy nhất để phân hủy: cùng một đồ thị có thể được xây dựng theo nhiều cách. Mã bản đồ ở trên sẽ truy cập tất cả các đỉnh, nhưng theo thứ tự tùy ý (thực hiện phụ thuộc).
Để khắc phục điều này, chúng tôi thêm một cấu trúc khác: một hàm match có một nút cụ thể. Nếu nút đó nằm trong biểu đồ của chúng tôi, chúng tôi sẽ có được kết quả thành công giống như trên; nếu không, toàn bộ trận đấu không thành công.
Cấu trúc này đủ để viết DFS hoặc BFS — với mã trang nhã trông gần như giống hệt nhau cho cả hai!
Thay vì đánh dấu các nút theo cách thủ công, chúng tôi chỉ recurse trên phần còn lại của biểu đồ ngoại trừ nút mà chúng ta đang thấy bây giờ: ở mỗi bước, chúng tôi đang làm việc với một phần nhỏ hơn và nhỏ hơn của biểu đồ gốc . Nếu chúng ta cố gắng truy cập một nút mà chúng ta đã thấy với match, nó sẽ không nằm trong biểu đồ còn lại và nhánh đó sẽ thất bại. Điều này cho phép mã xử lý đồ thị của chúng tôi trông giống như các hàm đệ quy bình thường của chúng tôi trong danh sách.
Đây là DFS cho loại biểu đồ này. Nó giữ ngăn xếp các nút để truy cập dưới dạng danh sách (biên giới) và bắt đầu biên giới ban đầu. Đầu ra là danh sách các nút được duyệt qua theo thứ tự. (Mã chính xác ở đây không thể được viết trực tiếp với thư viện mà không có một số từ đồng nghĩa mẫu tùy chỉnh.)
dfs _frontier Empty = []
dfs [] _graph = []
dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
dfs (neighbors' ctx ++ ns) rest
dfs (n:ns) graph = -- visited n
dfs ns graph
Chức năng đệ quy khá đơn giản. Để biến nó thành một tìm kiếm theo chiều rộng, tất cả chúng ta phải làm là thay thế chồng biên giới của chúng tôi với một hàng đợi: thay vì đưa những người hàng xóm trên trước của danh sách, chúng tôi đặt chúng trên lại:
bfs _frontier Empty = []
bfs [] _graph = []
bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
bfs (ns ++ neighbors' ctx) rest
bfs (n:ns) graph = -- visited n
bfs ns graph
Vâng, đó là tất cả những gì chúng tôi cần! Chúng tôi không phải làm bất cứ điều gì đặc biệt để theo dõi các nút mà chúng tôi đã truy cập khi chúng tôi kiểm tra lại biểu đồ, giống như chúng tôi không phải theo dõi các ô danh sách mà chúng tôi đã truy cập: mỗi lần chúng tôi kiểm tra lại, chúng tôi ' chỉ nhận được một phần của biểu đồ, chúng tôi chưa xem được.
Trong Python, bạn có thể tạo một 'bộ' các nút đã truy cập, thực hiện tra cứu' O (1) 'thay vì' O (n) '. – jonrsharpe
Tôi đặt cược, * monads * có thể xử lý nó .. –
Làm thế nào là sử dụng một cấu trúc dữ liệu thích hợp * không * mục đích của trò chơi? – chepner