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_hoá 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 BULLET 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 BULLET 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 Liên_kết ngoài BULLET Sách trực_tuyến về Lý_thuyết đồ_thị BULLET Hướng_dẫn về lý_thuyết đồ_thị BULLET Bài giảng của một môn_học về các thuật_toán đồ_thị BULLET Minh_hoạ hoạt_hình về các thuật_toán đồ_thị BULLET Lần bước thuật_toán để tìm_hiểu BULLET Tóm_tắt các trang minh_hoạ thuật_toán BULLET 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_BULLET_Sưu tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập ảnh số 1 một_số mạng_lưới thực BULLET Sưu_tập các liên_kết về đồ_thị BULLET Các tạp_chí lý_thuyết đồ_thị BULLET Sách về lý_thuyết đồ_thị
Nguyên_lý Bellman