Giải quyết một Optimization (Tìm số tiền tối thiểu thời gian cần thiết để có được tất cả mọi người lên xuống một ngọn núi)

Question

Vấn đề đi như thế này (dịch):

Có n (n < = 25000) người ở dưới cùng của một ngọn núi, và mọi người đều muốn đi lên, sau đó xuống núi. Có 2 hướng dẫn viên: một để giúp một người đi lên núi, một để giúp một người đi xuống. Người tôi mất (i) thời gian để leo lên ngọn núi này, và xuống (i) thời gian để hạ nó xuống. Tuy nhiên, mỗi hướng dẫn chỉ có thể giúp 1 người tại một thời điểm (có nghĩa là tối đa 1 người có thể leo núi và tối đa 1 người có thể xuống núi bất kỳ lúc nào). Giả sử khi hướng dẫn "lên" đạt đến đỉnh, anh ta sẽ được dịch chuyển tức thời về phía dưới cùng với hướng dẫn "xuống". Tìm ít thời gian nhất để đưa mọi người lên và xuống núi. (Mọi người có thể tụ tập tại các đỉnh núi nếu cần thiết)

Dưới đây là một đầu vào mẫu cho vấn đề này, với chú thích của tôi:

3 persons 
person 1: up=6 minutes, down=4 minutes 
person 2: up=8 minutes, down=1 minutes 
person 3: up=2 minutes, down=3 minutes 

Output để đầu vào:

Lượng thời gian tối thiểu là 17. Điều này là bởi vì Nếu người thứ 3 đi trước, thì người thứ 1, và sau đó là người thứ 2 (và cùng thứ tự này là được sử dụng cho cả đi lên), thì tổng thời gian là 17.

Tôi đã thử đến với một vài thuật toán, nhưng đây là những gì tôi có cho đến nay:

Một O (n! * n) thuật toán: chỉ cần hoán vị bò qua tất cả các hoán vị có thể sử dụng next_permutation

Thuật toán tham lam: Tôi đã sắp xếp người bằng cách giảm thời gian giảm dần và thử đặt chúng lại với nhau, nhưng điều này không đưa ra giải pháp đúng.

suy nghĩ khác

Tôi chuyển sang lập trình năng động bây giờ, khi theo CLR, các vấn đề tối ưu hóa thường lập trình tham lam hoặc động (vấn đề này, tôi nghĩ, đáp ứng tối ưu Hạ tầng cơ sở).

Tôi đã nhận thấy rằng trong giải pháp tối thiểu, hướng dẫn "lên" sẽ không còn chỗ cho đến khi mọi người lên núi. (Vì vậy, không có khoảng trống giữa người đi lên của 1, người thứ 2 đi lên, vv ..) Có lẽ vấn đề có thể được giảm xuống chỉ để giảm thiểu khoảng cách giữa các lần gốc?

Tôi đang gặp sự cố khi hiển thị trạng thái cho vấn đề lập trình động này (tôi không nghĩ đó là một chiều, vì tôi không nghĩ rằng bạn có thể tìm ra giải pháp tối ưu cho người của tôi chỉ biết giải pháp tối ưu cho tôi -1 người).

Có ai giúp được không?

Answer 1

Vấn đề này tương đương với n vấn đề cửa hàng dòng chảy công việc 2 máy với mục tiêu makepan (n/2/F/C _{tối đa}). Johnson's algorithm tìm ra giải pháp chính xác.

Answer 2

Chỉ hướng dẫn giảm dần thời gian rảnh thực sự quan trọng. Và sau khi cho nó một số suy nghĩ, tôi nghĩ vấn đề chính ở đây là chọn người đầu tiên leo lên, bởi vì thời gian của người leo núi đầu tiên là một sự chậm trễ chắc chắn cho hướng dẫn giảm dần.

Giải pháp có thể là để chọn một với thấp nhất up(i) ra khỏi những người có down(i) > up(i) và sau đó cho leo bạn ưu tiên tất cả mọi người với down(i) > up(i), sau đó down(i) = up(i), sau đó tất cả phần còn lại. Đối với giảm dần bạn chỉ cần ưu tiên những người có thời gian dài nhất (i).

Điều này đạt được là:

1. Bạn trì hoãn việc giảm dần hướng dẫn ít nhất là ở đầu
2. Bạn giữ anh bận rộn tất cả các thời gian sau đó