Tôi đoán tôi hơi muộn, nhưng tôi thích câu hỏi. Thay vì tạo ra một cây theo hình thức
{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}
tôi sẽ sử dụng các hình thức sau đây gọi lồng nhau, nơi mà mỗi đối số là một đứa trẻ, đại diện cho một nút
0[1[2, 3, 4], 5]
Cả hai hình thức là tương đương và có thể biến thành nhau.
Row[{
TreeForm[0[1[2, 3, 4], 5]],
TreePlot[{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}]
}]
Sau đây là cách các thuật toán hoạt động: Khi tranh luận, chúng ta cần một hàm f đó đưa ra một số ngẫu nhiên của trẻ em và được gọi khi chúng ta tạo ra một nút. Ngoài ra, chúng tôi có độ sâu d xác định độ sâu tối đa mà cây (phụ) có thể có.
[Chọn nhánh] Xác định một hàm phân nhánh f mà có thể được gọi như f[] và trả về một số ngẫu nhiên của trẻ em. Nếu bạn muốn một cây có 2 hoặc 4 trẻ em, bạn có thể sử dụng ví dụ: f[] := RandomChoice[{2, 4}]. Hàm này sẽ được gọi cho mỗi nút được tạo trong cây.
[Chọn chiều sâu cây] Chọn độ sâu tối đa d của cây. Tại thời điểm này, tôi không chắc chắn những gì bạn muốn sự ngẫu nhiên được kết hợp vào thế hệ của cây. Những gì tôi làm ở đây là khi một nút mới được tạo ra, độ sâu của cây bên dưới nó được chọn ngẫu nhiên giữa độ sâu của bố mẹ nó trừ đi một và không.
[Tạo bộ đếm ID] Tạo biến số lượt truy cập duy nhất count và đặt thành 0. Điều này sẽ cho chúng ta ngày càng tăng ID của nút. Khi tạo một nút mới, nó được tăng lên 1.
[Tạo nút] Tăng count và sử dụng nó làm nút-ID. Nếu độ sâu hiện tại d bằng 0, trả lại lá có số ID, nếu không hãy gọi số f để quyết định số lượng nút con sẽ nhận được. Đối với mỗi đứa trẻ mới chọn ngẫu nhiên độ sâu của cây con của nó có thể là 0,...,d-1 và gọi 4. cho mỗi đứa trẻ mới.Khi tất cả các cuộc gọi đệ quy đã trở lại, cây được xây dựng.
May mắn thay, trong Mathematica -code thủ tục này không phải là quá dài dòng và chỉ gồm một vài dòng. Tôi hy vọng bạn có thể tìm thấy trong mã những gì tôi đã mô tả ở trên
With[{counter = Unique[]},
generateTree[f_, d_] := (counter = 0; builder[f, d]);
builder[f_, d_] := Block[
{nodeID = counter++, childs = builder[f, #] & /@ RandomInteger[d - 1, f[]]},
nodeID @@ childs
];
builder[f_, 0] := (counter++);
]
Bây giờ bạn có thể tạo một cây ngẫu nhiên như sau
branching[] := RandomChoice[{2, 4}];
t = generateTree[branching, 6];
TreeForm[t]
Hoặc nếu bạn thích bạn có thể sử dụng tiếp theo chức năng chuyển đổi cây thành những gì được chấp nhận bởi TreePlot
transformTree[tree_] := Module[{transform},
transform[(n_Integer)[childs__]] := (Sow[
n -> # & /@ ({childs} /. h_Integer[__] :> h)];
transform /@ {childs});
[email protected]@Reap[transform[tree]
]
và sử dụng nó để tạo ra nhiều cây ngẫu nhiên
trees = Table[generateTree[branching, depth], {depth, 3, 7}, {5}];
GraphicsGrid[Map[TreePlot[transformTree[#]] &, trees, {2}]]
