Lập kế hoạch hành trình

Question

Nếu bạn có lịch trình xe buýt đầy đủ cho một quốc gia, làm thế nào bạn có thể tìm ra số người tối đa có thể mang giữa hai điểm dừng được chỉ định trong 1 ngày?

Tôi giả sử lịch trình xe buýt cung cấp cho bạn danh sách đầy đủ về thời gian khởi hành và đến đối với mỗi điểm dừng xe buýt và cũng là khả năng của mỗi xe buýt. Bạn được cung cấp điểm dừng bắt đầu và kết thúc trong câu hỏi.

Bạn có thể xác định một chuỗi các xe buýt có thời gian ngắn nhất đến đích và lấp đầy tất cả các xe buýt khởi hành đi dọc theo con đường này và sau đó mỗi xe buýt dừng lại, chỉ chuyển nhiều hành khách như có thể đến xe buýt tiếp theo sắp rời đi. Không có lý do tại sao điều này nên có khả năng tối đa tuy nhiên.

Vấn đề này nhanh nhất có thể được giải quyết là gì? Ví dụ, giả sử rằng đối với các thành phố M tôi được cấp tổng số bản ghi N; lộ trình Rᵢ chứa số Kᵢ, dung lượng Cᵢ và danh sách số thành phố K,, thời gian đến Kᵢ và thời gian khởi hành Kᵢ. (Thời gian đến đầu tiên và thời gian khởi hành cuối cùng trong Rᵢ là không liên quan.) Chương trình tìm kiếm rộng đầu tiên có giải quyết được câu hỏi trong thời gian O (M * N) không?

Answer 1

Đây không phải là một câu đố kỳ lạ; đó là câu hỏi về thuật toán. Một cách để giải quyết vấn đề này là tạo biểu đồ có hướng với một nút cho mỗi (vị trí, thời gian đến) và (vị trí, thời gian khởi hành). Mỗi nút đến có một vòng cung công suất vô hạn cho tất cả các chuyến khởi hành tại cùng một vị trí không sớm hơn. Mỗi nút khởi hành có một vòng cung cho mỗi nút đến thích hợp (theo lịch trình xe buýt), được cân bằng với khả năng của xe buýt. Sau đó, bạn có thể sử dụng thuật toán yêu thích của mình để tìm luồng tối đa từ nguồn của bạn đến bồn rửa chén.

Nút nguồn của bạn phải là nút đến tại thời điểm 0 tại vị trí bắt đầu của bạn, nút bồn rửa của bạn phải là nút khởi hành vào thời điểm kết thúc tại vị trí kết thúc của bạn.