Giải toán hiện đại bằng Excel: bài toán Manhattan

[LearnExcel]

Đây là bài tóan về vận trù, gợi ý là tìm phướng án tối ưu, tuy nhiên thuật tóan liệt kê tìm đường đi thì tôi chưa nghĩ ra.
Xin mời tham gia thảo luận!

 

[OverAC]

Em xin phép dịch đề bài tí nhé.

Ở Midtown Mahattan, có 12 tòa nhà được nối với nhau bằng 17 con đường, mỗi con đường dài 1Km. Mỗi đêm các con đường phải được rửa bằng xe rửa đường. Để có thể rửa tất cả các con đường xe rửa đường phải đi qua vài còn đường nhiều hơn 1 lần. Câu hỏi là cách đi nào để chiều dài con đường đi là ngắn nhất để xe có thể rửa được tất cả các con đường

ý kiến của em,
bài toán này liên quan đến lý thuyết kẻ đường 1 nét (quên tên là gì rồi). Đại ý là trong hình được xét phải tính toán số đỉnh chẳn và đỉnh lẻ. Đỉnh chẳn là đỉnh có số con đường nối với nó là số chẳn và tương tự đỉnh lẻ là đĩnh có số con đường nôi với nó là đĩnh lẻ.
1. Nếu số đỉnh lẻ là 2 thì con đường 1 nét nếu có thể phải bắt đầu ở đỉnh lẻ này và kết thúc ở đỉnh lẻ còn lại.
2. Nếu số đỉnh lẻ nhiều hơn 2 thì không thể kẻ đường một nét mà có thể đi qua tất cả các đường.
3. Số lượng đỉnh lẻ luôn là một số chẳn

Nếu đường ngắn nhất có thể đi qua tất cả các con đường phải là con đường bắt đầu từ các đỉnh lẻ và kết thúc ở các đỉnh lẻ. Ở giai đoạn chuyển tiếp từ nhóm 2 đỉnh lẻ này sang nhóm 2 đỉnh kẻ kia phải là con đường ngắn nhất. Trong bài này có tổng cộng 6 đỉnh lẻ. Có nghĩa là có 2 lần chuyển tiếp, vậy mỗi lần chuyển tiếp tối thiểu đường đi bị lặp lại là 1Km.

Vậy về mặt lý thuyết. Tối thiểu con đường mà xe rửa đường phải đi qua là 17+2= 19

nhưng em chưa tìm được lối đi . Lối đi ngắn nhất mà em tìm được là 20, thêm 1 điều nữa là không hết liên quan 1 tí nào tới Excel.

 

[LearnExcel]

thêm 1 điều nữa là không hết liên quan 1 tí nào tới Excel.

Hi hi, vì chót yêu quí Excel quá mà bát nó mang nhiều việc.
Nhưng theo tôi, Solver + VBA + Circular Reference của Exl cũng làm được nhiều việc đó chứ!