Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 25
Một công ty vận tải cần giao hàng đến tất cả các thành phố A, B, C, D, E (hình vẽ bên dưới). Chi phí di chuyển giữa các thành phố được mô tả trên hình. Xe giao hàng của công ty xuất phát từ một thành phố trong năm thành phố trên đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố ban đầu. Tìm chi phí thấp nhất của xe giao hàng.
Xem lời giải
Lời giải
Đường đi Tổng số chi phí
$A\to B\to C\to E\to D\to A$ $9+14+12+14+11=60$
$A\to B\to E\to C\to D\to A$ $9+8+12+13+11=53$
$A\to E\to B\to C\to D\to A$ $10+8+14+13+11=56$
$A\to E\to D\to C\to B\to A$ $10+14+13+14+9=60$
$A\to D\to C\to E\to B\to A$ $11+13+12+8+9=53$
$A\to D\to E\to C\to B\to A$ $11+14+12+14+9=60$
Do đó, tổng chi phí của đường đi nhận giá trị nhỏ nhất là 53.
