Chaitin-Briggs Giải thích thuật toán

Question

Tôi googled nó nhưng tôi đã không tìm thấy một số tài liệu tốt về chủ đề này.

Tôi có thể tìm thêm thông tin về thuật toán tô màu đồ thị Chaitin-Briggs ở đâu? Hoặc ai đó có thể giải thích nó hoạt động như thế nào?

Answer 1

Thông tin chi tiết quan trọng về thuật toán của Chaitin được gọi là quy tắc độ < R như sau. Cho một đồ thị G có chứa một nút N có độ nhỏ hơn R, G có màu R là biểu đồ G ’, trong đó G 'là G với nút N bị loại bỏ, có màu R. Bằng chứng rõ ràng theo một hướng: nếu biểu đồ G có thể được tô màu bằng màu R thì biểu đồ G ’có thể được tạo mà không thay đổi màu. Theo một hướng khác, chúng ta có màu R của G '. Vì N có mức độ nhỏ hơn R nên phải có ít nhất một màu không được sử dụng cho nút bên cạnh N. Chúng ta có thể tô màu N với màu này.

Thuật toán như sau:

While G cannot be R-colored 
    While graph G has a node N with degree less than R 
     Remove N and its associated edges from G and push N on a stack S 
    End While 
    If the entire graph has been removed then the graph is R-colorable 
     While stack S contains a node N 
      Add N to graph G and assign it a color from the R colors 
     End While 
    Else graph G cannot be colored with R colors 
     Simplify the graph G by choosing an object to spill and remove its node N from G 
     (spill nodes are chosen based on object’s number of definitions and references) 
End While 

Sự phức tạp của thuật toán Chaitin-Briggs là O (n2) vì vấn đề của lan. Biểu đồ G sẽ không thể có màu R nếu tại một số điểm, biểu đồ giảm G ’chỉ có các nút có độ R hoặc cao hơn. Khi một đồ thị dễ dàng R-màu thì chi phí của một lần lặp đơn là O (n) bởi vì chúng tôi thực hiện hai chuyến đi qua biểu đồ và loại bỏ hoặc thêm một nút mỗi lần. Nhưng sự tràn ra mang lại sự phức tạp thêm bởi vì chúng ta có thể cần phải tràn một số lượng tùy ý các nút trước khi G trở thành R-colorable. Đối với mỗi nút chúng ta tràn chúng tôi thực hiện một chuyến du lịch thông qua các thuật toán tuyến tính

Bạn cũng có thể đi qua này Register allocation algorithm