Hiểu đường dẫn minimax/maximin (Floyd-Warshall)

Question

Tôi đã triển khai Thuật toán Floyd-Warshall-Algorithm để giải quyết vấn đề đường đi ngắn nhất Tất cả các cặp. Bây giờ tôi phát hiện ra tôi cũng có thể tính toán đường dẫn minimax hoặc maximin với các sửa đổi dễ dàng. Nhưng tôi không hiểu ý nghĩa của kết quả (đường dẫn minimax là gì). Tôi tìm thấy một số explanations trên web, nhưng chúng làm tôi bối rối.

Minimax - Minimax trong các vấn đề về đồ thị liên quan đến việc tìm đường đi giữa hai nút giảm thiểu chi phí tối đa dọc theo đường dẫn.

Maximin - cách khác xung quanh từ Minimax - ở đây bạn có vấn đề nơi bạn cần phải tìm đường dẫn tối đa hóa chi phí tối thiểu dọc theo một con đường.

Ai đó có thể cố gắng đưa ra giải thích khác hoặc ví dụ?

Answer 1

Để hiểu đường dẫn tối đa (thường được gọi là đường dẫn nút cổ chai) trong biểu đồ, hãy xem xét vấn đề sau. Bạn có bản đồ đường của một quốc gia làm biểu đồ trong đó mỗi nút đại diện cho giao lộ và mỗi cạnh đại diện cho một con đường. Mỗi con đường có giới hạn trọng lượng và nếu bạn lái xe tải vượt quá giới hạn trên con đường đó thì đường sẽ bị phá vỡ. Bạn có một chiếc xe tải mà bạn muốn lái xe từ một số vị trí bắt đầu đến một số vị trí kết thúc, và bạn muốn đặt số lượng tối đa có thể có trọng lượng trên đó. Cho điều này, những gì bạn nên lái xe đường dẫn để gửi trọng lượng tối đa có thể? Nếu bạn nghĩ về vấn đề này, đối với bất kỳ đường dẫn nào bạn đưa vào biểu đồ, trọng lượng tối đa bạn có thể gửi dọc theo đường dẫn đó sẽ được xác định bởi cạnh trên đường dẫn có dung lượng tối thiểu. Kết quả là, bạn muốn tìm đường đi từ đầu đến đích có cạnh dung lượng tối thiểu được phóng to. Đường dẫn với thuộc tính này được gọi là đường dẫn maximin hoặc đường dẫn cổ chai, và có thể được tìm thấy với một tập hợp các sửa đổi đơn giản thành một thuật toán đường ngắn nhất.

Đường dẫn minimax đại diện cho ý tưởng ngược lại - đường dẫn giữa hai điểm giảm thiểu khả năng cạnh tối đa.

Hy vọng điều này sẽ hữu ích!