• Thứ Năm, 08/01/2004 11:57 (GMT+7)

    Câu hỏi :
    Hỏi: Xin hướng dẫn giải bài toán tìm hành trình bay như sau: Có N sân bay (đánh số từ 1 đến N). Khoảng cách (theo đường bay) từ sân bay i đến sân bay j là D(i, j) với D(i, i) = 0, D(i, j) = D(j, i). Một máy bay cần bay từ sân bay S đến sân bay T. Máy bay chỉ có thể bay liên tục một quãng đường là H, khi cần phải hạ cánh ở sân bay nào đó để nạp thêm nhiên liệu. Tìm một hành trình cho máy bay sao cho số lần hạ cánh để nạp thêm nhiên liệu là ít nhất. Nếu có nhiều hơn một hành trình như vậy thì chọn hành trình nào có tổng độ dài đường bay ngắn hơn. Dữ liệu vào cho bởi file PATH.INP có dạng: N D(1, 2) D(1, 3) ... D(1, N) D(2, 3) D(2, 4) ... D(2, N) ... D(N-1, N) H S T trong đó các giá trị đều là số nguyên dương, các số trên cùng một dòng cách nhau ít nhất một dấu trắng. Kết quả ghi ra file PATH.OUT gồm một dòng, bắt đầu là S, sau đó lần lượt là các số hiệu sân bay (nếu có) mà máy bay phải hạ cánh để nạp nhiên liệu, kết thúc là T. Các số ghi cách nhau ít nhất một dấu trắng. Nếu không có hành trình nào đi được từ S đến T thì ghi một số 0. Giới hạn kích thước: số sân bay N 100, các giá trị khoảng cách D(i, j) 99 (tính theo đơn vị 100 km). Thí dụ: PATH.INP PATH.OUT 5 1 4 3 5 6 5 1 3 7 8 1 9 1 5 1 3

    Trả lời :

    Đáp: Bài toán của bạn là 1 trường hợp đặc biệt của bài toán tổng quát hơn: bài toán tìm đường đi ngắn nhất giữa 2 nút trong 1 đồ thị. Tuy nhiên cách đặt bài toán của bạn chưa rõ ràng và thiếu thông tin nên khó lòng giải được. Thí dụ nếu độ dài giữa 2 sân bay lớn hơn quãng đường bay cho phép là H thì theo ràng buộc của bạn, máy bay không thể bay trực tiếp từ sân bay này sang sân bay kia mà phải đáp xuống sân bay trung gian nào đó để đổ nhiên liệu. Như vậy thông số khoảng cách giữa 2 sân bay này trong file dữ liệu nhập sẽ vô nghĩa (vì không cần thiết), tuy nhiên theo số liệu thí dụ của bạn thì bạn đã phải điền các giá trị này vào file dữ liệu nhập! Về việc giải bài toán trên, chúng tôi xin đề nghị cách giải quyết như sau:

    o Bước 1: Từ ma trận khoảng cách thực sự giữa các sân bay, bạn xây dựng ma trận khoảng cách bay được giữa các sân bay như sau: nếu khoảng cách thực giữa 2 sân bay i,j <=H thì ta điền giá trị 1 (tính theo đơn vị lần hạ cánh) vào phần tử i,j của ma trận khoảng cách bay được, ngược lại ta điền giá trị 0 để đánh dấu là không thể bay trực tiếp được.

    o Bước 2: Tìm các đường đi ngắn nhất (tính theo đơn vị lần hạ cánh) giữa 2 sân bay S và T dùng số liệu của ma trận khoảng cách bay được vừa xây dựng, dựa vào giải thuật tìm đường đi ngắn nhất trong đồ thị nào đó đã biết (thí dụ giải thuật Dijsktra).

    o Bước 3: nếu kết quả tìm được chỉ có 1 đường thì đó là kết quả của bài toán. Nếu kết quả có nhiều hơn 1 đường thì hãy tính độ dài thực của từng con đường tìm được dựa vào số liệu của ma trận khoảng cách thực sự để chọn ra đường đi vừa có số lần bay ít nhất vừa có khoảng cách vật lý ngắn nhất.

     

    Chuyên mục: Lập trình