Nguyên lý Bellman

Nguyên lý Bellman là nguyên lý tổng quát cho các bài toán tối ưu hóa rời rạc. Hầu hết các thuật toán tìm đường đi ngắn nhất đều đặt cơ sở trên nguyên lý Bellman.

Đối với trường hợp bài toán đường đi ngắn nhất thì có thể trình bày nguyên lý này như sau:

 Giả sử P là đường đi ngắn nhất từ đỉnh i đến đỉnh j và k là một đỉnh nằm trên đường đi P. Giả sử P=P1⊕P2 với P1 là đường đi con của P từ i đến k và P2 là đường đi con của P từ k đến j. Nguyên lý Bellman nói rằng P1 cũng là đường đi ngắn nhất từ i đến k, vì nếu có một đường đi khác là P1’ từ i đến k có trọng lượng nhỏ hơn hơn P1 thì P1’⊕P2 là đường đi từ i đến j mà có trọng lượng nhỏ hơn P, điều này mâu thuẫn với tính ngắn nhất của P.

Điều kiện tồn tại lời giải 

 Gọi P là một đường đi từ i đến j, giả sử P có chứa một mạch ∝. Có 2 trường hợp sau đây.
Nếu L(∝)≥0 thì có thể cải tiến đường đi P bằng cách bỏ đi mạch ∝. 
Nếu L(∝)<0 thì không tồn tại đường đi ngắn nhất từ đỉnh i đến đỉnh j vì nếu quay vòng tại ∝ càng nhiều vòng thì trọng lượng đường đi P càng nhỏ đi, tức là L(P) → −∞.

Chú thích

Tham khảo

Liên kết ngoài
 Sách trực tuyến về Lý thuyết đồ thị
 Hướng dẫn về lý thuyết đồ thị 
 Bài giảng của một môn học về các thuật toán đồ thị 
 Minh họa hoạt hình về các thuật toán đồ thị
 Lần bước thuật toán để tìm hiểu.
 Tóm tắt các trang minh họa thuật toán 
 Dữ liệu test chuẩn cho các bài toán đồ thị con đầy đủ lớn nhất (Maximum Clique), tập con độc lập lớn nhất (Maximum Independent Set), phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô màu đỉnh (Vertex Coloring) 
 Sưu tập ảnh số 1: một số mạng lưới thực
 Sưu tập ảnh số 1: một số mạng lưới thực 
 Sưu tập các liên kết về đồ thị
 Các tạp chí lý thuyết đồ thị 
 Sách về lý thuyết đồ thị