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. 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) → −∞. Sách trực tuyến về Lý thuyết đồ thị Hướng dẫn về lý thuyết đồ thị Lưu trữ 2012-01-16 tại Wayback Machine Bài giảng của một môn học về các thuật toán đồ thị Lưu trữ 2005-08-31 tại Wayback Machine 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 Lưu trữ 2008-06-01 tại Wayback Machine 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) Lưu trữ 2013-05-29 tại Wayback Machine 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 Lưu trữ 2012-02-23 tại Wayback Machine Sưu tập các liên kết về đồ thị Các tạp chí lý thuyết đồ thị Lưu trữ 2013-07-04 tại Wayback Machine Sách về lý thuyết đồ thị Lưu trữ 2012-09-11 tại Wayback Machine