Nguyên lý Bellman

Thêm liên kết
Bách khoa toàn thư mở Wikipedia

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:

Hình 1:
  • 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 | sửa mã nguồn]

  • 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) → −∞.
Hình 2:

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Nguyên_lý_Bellman&oldid=70697374”