JavaScript is required

Cho mạng quang có 5 nút (A, B, C, D và E) với 4 liên kết (AB, BC, CD, DE). Mỗi liên kết có thể có 3 bước sóng. Giả sử các yêu cầu tuyến quang (lightpath) là: {A, C}, {A, B}, {D, E}, {C, E}, {B, D}, {C, D}. Kết quả nào sau đây là sai khi các bước sóng được gán theo giải thuật First-fit:

A.

Bước sóng thứ nhất: {A, C}, {D, E}, {C, D}

B.

Bước sóng thứ hai: {A, B}, {D, E}

C.

Bươc sóng thứ ba: {B, D}

D.

Cả 3 đáp án sai

Trả lời:

Đáp án đúng: B


Để giải quyết bài toán này, chúng ta cần áp dụng giải thuật First-fit để gán bước sóng cho các lightpath đã cho và sau đó kiểm tra xem kết quả nào là sai. Giải thuật First-fit gán bước sóng đầu tiên có sẵn cho một lightpath. Các lightpath được xem xét theo thứ tự được liệt kê. 1. **{A, C}:** Tuyến này đi qua các liên kết AB và BC. Gán bước sóng thứ nhất. 2. **{A, B}:** Tuyến này đi qua liên kết AB. Liên kết AB đã được sử dụng bởi {A, C} trên bước sóng thứ nhất, nhưng {A, B} chỉ sử dụng AB, vì vậy chúng ta có thể gán bước sóng thứ hai cho nó. 3. **{D, E}:** Tuyến này đi qua liên kết DE. Gán bước sóng thứ nhất. 4. **{C, E}:** Tuyến này đi qua các liên kết CD và DE. Liên kết DE đã được sử dụng bởi {D, E} trên bước sóng thứ nhất, nên ta không thể dùng bước sóng thứ nhất. Vậy ta gán bước sóng thứ hai cho {C, E}. 5. **{B, D}:** Tuyến này đi qua các liên kết BC và CD. Gán bước sóng thứ ba cho {B, D}. 6. **{C, D}:** Tuyến này đi qua liên kết CD. Bước sóng thứ nhất có thể được sử dụng vì CD chưa được sử dụng bởi lightpath nào trên bước sóng thứ nhất. Vậy, kết quả là: - Bước sóng thứ nhất: {A, C}, {D, E}, {C, D} - Bước sóng thứ hai: {A, B}, {C, E} - Bước sóng thứ ba: {B, D} So sánh với các đáp án: - Đáp án 1: Đúng. - Đáp án 2: Sai. {C, E} phải dùng bước sóng thứ 2 thay vì {D, E}. - Đáp án 3: Đúng. Vậy đáp án sai là đáp án 2.

Câu hỏi liên quan