Lập trình đồ thị động

Error

Trong các giải pháp sử dụng lập trình động, thứ tự tính toán động lực học là rất quan trọng (điều cần thiết là các giá trị mà giá trị hiện tại phụ thuộc phải được tính toán trước).
Do đó, nếu cần sử dụng quy hoạch động trên các đồ thị tuần hoàn có hướng, trước tiên cần xây dựng một sắp xếp tô pô của đồ thị. Sau đó, tính toán động lực bằng cách sắp xếp qua các đỉnh theo thứ tự sắp xếp tô pô đã xây dựng (tùy thuộc vào vấn đề, thứ tự duyệt có thể là từ nguồn đến phần chìm hoặc ngược lại).
 
 

Nếu biểu đồ chứa các chu trình (không có sắp xếp tô pô), thì hai thủ thuật có thể hữu ích:

1) Tính động lực học n lần, trong đó n là số đỉnh của đồ thị (tương tự với thuật toán Ford-Bellman). Nhưng điều này làm tăng các tiệm cận và nói chung hiếm khi hiệu quả.

2) Dựng đồ thị cô đọng. Đối với mỗi thành phần liên thông mạnh của đồ thị ban đầu, hãy giải bài toán một cách riêng biệt. Biểu đồ cô đặc là một biểu đồ theo chu kỳ và đối với nó, bạn có thể sử dụng phương pháp tiêu chuẩn với sắp xếp tô pô, đồng thời sử dụng làm giá trị đỉnh, giá trị được tính toán cho các thành phần được kết nối mạnh. Phương pháp này được sử dụng chủ yếu.