Nguyên lý Bellman
Bài viết này không có hoặc có quá ít liên kết đến các bài viết Wikipedia khác. (tháng 4 năm 2013) |
Bài viết này là một bài mồ côi vì không có bài viết khác liên kết đến nó. Vui lòng tạo liên kết đến bài này từ các bài viết liên quan; có thể thử dùng công cụ tìm liên kết. (tháng 4 năm 2013) |
Bài viết hoặc đoạn này cần người am hiểu về chủ đề này trợ giúp biên tập mở rộng hoặc cải thiện. |
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
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
sửa- 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
sửaTham khảo
sửaLiên kết ngoài
sửa- 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