Tôi có một câu hỏi là một phần của chương trình của tôi.Tìm trung tâm của cây
Đối với cây T = (V, E), chúng ta cần phải tìm nút v trong cây giảm thiểu độ dài của đường đi dài nhất từ v đến bất kỳ nút nào khác.
vậy làm thế nào chúng ta tìm thấy trung tâm của cây? Có thể chỉ có một trung tâm trở lên không?
Nếu có ai có thể cho tôi thuật toán tốt cho điều này để tôi có thể có được ý tưởng về cách tôi có thể phù hợp với chương trình của mình.
Hãy xem xét một cây có hai nút? Đó là trung tâm? Hoặc là đủ, ergo một cây có thể có nhiều hơn một trung tâm.
Bây giờ, hãy nghĩ về ý nghĩa của nó là trung tâm. Nếu tất cả các nhánh có cùng chiều cao, trung tâm là gốc (tất cả các đường đi qua gốc). Nếu các nhánh có chiều cao khác nhau thì trung tâm phải là gốc hoặc trong nhánh có chiều cao lớn nhất nếu không thì đường lớn nhất lớn hơn chiều cao của nhánh cao nhất và gốc sẽ là lựa chọn tốt hơn. Bây giờ, chúng ta cần nhìn bao xa đến nhánh cây cao nhất? Một nửa sự khác biệt về chiều cao giữa nhánh cao nhất (từ gốc) và nhánh cao nhất tiếp theo (nếu chênh lệch lớn nhất là 1 gốc sẽ đủ). Tại sao, bởi vì khi chúng ta đi xuống nhánh cao nhất bởi một mức, chúng ta sẽ kéo dài đường dẫn đến nút sâu nhất của nhánh cao nhất tiếp theo một và giảm khoảng cách đến nút sâu nhất trong nhánh hiện tại một. Cuối cùng, chúng sẽ bằng nhau khi bạn đã vượt qua một nửa sự khác biệt về chiều sâu. Bây giờ khi chúng ta đi xuống nhánh cao nhất, chúng ta chỉ cần chọn ở mỗi cấp nhánh con cao nhất. Nếu nhiều hơn một có cùng chiều cao, chúng ta chỉ cần chọn một tùy ý. Về cơ bản, những gì bạn đang làm là tìm đường đi dài nhất trong biểu đồ, là khoảng cách giữa nhánh cao nhất của cây và nhánh cao nhất tiếp theo, sau đó tìm nút giữa trên nhánh đó. Bởi vì có thể có nhiều đường dẫn có cùng chiều dài với đường đi dài nhất và chiều dài của con đường dài nhất có thể là ngay cả, bạn có nhiều trung tâm có thể.
Thay vì làm bài tập về nhà vấn đề này cho bạn, tôi sẽ yêu cầu bạn thông qua quá trình suy nghĩ mà được câu trả lời ...
1) Bạn sẽ làm gì với abc đồ thị (ba đỉnh, hai cạnh, và chắc chắn tuần hoàn)? Hãy tưởng tượng cho một thời điểm mà bạn phải đặt một số nhãn trên một số đỉnh, bạn biết bạn sẽ nhận được tối thiểu của con đường dài nhất trên đỉnh "trung tâm". (b, với nhãn cuối cùng "1") Nhưng làm điều đó trong một bước đòi hỏi quyền hạn tâm linh. Vì vậy, hãy tự hỏi mình những gì b là 1 bước đi. Nếu con đường dài nhất để b là 1, và chúng ta vừa bước lùi một bước dọc theo con đường đó, chiều dài con đường của chúng ta cho đến nay là bao nhiêu? (đường dẫn dài nhất = 1, -1 cho lùi lại một bước. Aha: 0). Vì vậy, đó phải là nhãn cho lá.
2) Điều này đề xuất điều gì làm cắt đầu tiên cho thuật toán? Đánh dấu các lá "0", đánh dấu thượng nguồn của họ "1", đánh dấu các dòng "2" của họ và cứ tiếp tục như vậy. Diễu hành từ những chiếc lá và đếm khoảng cách khi chúng tôi đi ...
3) Umm ... Chúng tôi gặp sự cố với biểu đồ a-b-c-d. (Từ bây giờ, một đỉnh có nhãn sẽ được thay thế bằng nhãn của nó.) Ghi nhãn các lá "0" cho 0-bc-0 ... Chúng ta không thể có hai trung tâm ... Heck, chúng ta làm gì trong đơn giản hơn điều kiện 0-b-1? Chúng tôi muốn gắn nhãn b với cả "1" và "2" ... Xử lý những thứ theo thứ tự ngược lại ...
Trong 0-b-1, nếu chúng ta mở rộng đường dẫn từ b sang trái, chúng tôi nhận được Đường dẫn chiều dài 1. Nếu chúng ta mở rộng đường đi từ bên phải của b, chúng ta nhận được 2. Chúng tôi muốn theo dõi "chiều dài của đường đi dài nhất từ v đến bất kỳ nút nào khác", vì vậy chúng tôi muốn theo dõi đường dẫn dài nhất đến b. Điều đó có nghĩa là chúng ta đánh dấu b bằng dấu "2".
0-b-1 -> 0-2-1
Trong 0-b-c-0, máy tính không thực sự đồng thời cập nhật b và c. Nó cập nhật một trong số họ, cho 0-1-c-0 hoặc 0-b-1-0, và bản cập nhật tiếp theo cho 0-1-2-0 hoặc 0-2-1-0. Cả b và c là "trung tâm" của biểu đồ này vì mỗi trong số chúng đáp ứng nhu cầu "nút v trong cây giảm thiểu độ dài của đường đi dài nhất từ v đến bất kỳ nút nào khác". Điều này dẫn đến một quan sát khác: Kết quả của việc tính toán không phải là nhãn một đồ thị, nó là để tìm đỉnh cuối cùng mà chúng tôi dán nhãn và/hoặc đỉnh kết thúc bằng nhãn lớn nhất. (Có thể chúng tôi sẽ không tìm được cách tốt để đặt hàng nhãn, vì vậy chúng tôi sẽ cần phải tìm tối đa ở cuối. Hoặc có thể chúng tôi sẽ. Ai biết được.)
4) Vì vậy, bây giờ chúng tôi có giống như: Tạo hai bản sao của biểu đồ - bản sao có nhãn và bản sao ghi xuống. Việc đầu tiên sẽ lưu trữ các nhãn và đó là một trong đó sẽ có câu trả lời cuối cùng trong đó. Bản sao chép xuống sẽ nhỏ hơn và nhỏ hơn khi chúng ta xóa các đỉnh không gắn nhãn khỏi nó (để tìm các đỉnh có thể ghi nhãn mới). (Có nhiều cách khác để tổ chức này để chỉ có một bản sao của đồ thị được sử dụng Khi bạn nhận được đến hết hiểu câu trả lời này, bạn nên tìm một cách để giảm bớt sự lãng phí này..) Outline:
label = 0
while the burndown graph is nonempty
collect all the leaves in the burndown-graph into the set X
for each leaf in the set X
if the leaf does not have a label
set the leaf's label (to the current value of label)
delete the leaf from the burn-down graph (these leafs are two copies of the same leaf in the input graph)
label = label+1
find the vertex with the largest label and return it
5) Nếu bạn thực sự xem lần chạy này, bạn sẽ nhận thấy một số cơ hội để cắt ngắn. Bao gồm thay thế tìm kiếm trên dòng cuối cùng của phác thảo bằng một phương pháp nhanh hơn nhiều để nhận ra câu trả lời.
Và bây giờ là mẹo chiến lược chung cho các vấn đề về thuật toán:
* Thực hiện một vài ví dụ nhỏ bằng tay. Nếu bạn không hiểu làm thế nào để làm các trường hợp nhỏ, không có cách nào bạn có thể nhảy thẳng vào và nói với máy tính làm thế nào để làm các trường hợp lớn. * Nếu bất kỳ bước nào ở trên dường như không được kích thích hoặc hoàn toàn mờ đục, bạn sẽ cần nghiên cứu nhiều, khó hơn nhiều để làm tốt trong Khoa học Máy tính. Nó có thể là khoa học máy tính không phải dành cho bạn ...
Có hai phương pháp để làm điều này (cả hai đều chạy trong cùng một thời điểm):
Chọn bất kỳ đỉnh v1 trên cây của bạn. Chạy BFS từ đỉnh này. Đỉnh cuối cùng (v2) bạn sẽ tiếp tục sẽ là đỉnh xa nhất từ v1. Bây giờ chạy một BFS khác, lần này từ đỉnh v2 và nhận được đỉnh cuối cùng v3.
Đường dẫn từ v2 đến v3 là đường kính của cây và trung tâm của bạn nằm đâu đó trên đó. Chính xác hơn nó nằm ở giữa nó. Nếu đường dẫn có 2n + 1 điểm, sẽ chỉ có 1 trung tâm (ở vị trí n + 1). Nếu đường dẫn có 2n điểm, sẽ có hai trung tâm tại các vị trí n và n + 1.
Bạn chỉ sử dụng 2 cuộc gọi BFS chạy trong thời gian 2 * O(V).
Nếu điểm giữa chính xác không tồn tại, làm thế nào chúng ta có thể chọn? Ý tôi là, nếu con đường dài nhất là a-b-c, a-b có chiều dài 1, và b-c có chiều dài 2?Hay một ví dụ phức tạp hơn? – cnhk
Chọn một tùy ý, nếu bạn chỉ cần một nút đủ điều kiện hoặc xây dựng một tập hợp trung tâm, nếu bạn cần tất cả những điều đó đủ điều kiện. – tvanfosson