Tìm tâm điểm tối ưu cho hệ thống mạng có dây

[NguNhuheo]

Dùng một bài toán, mất phân nửa thời gian thi để giải là kiểu thi tốt nghiệp thời thập niên 60's về trước.
Nó thiên vị cách học mua sách bài tập (thường có bài giải sẵn) về tập cả đống.

Tương tự vậy, cho điểm cao một bài toán mẹo là ưu tiên cho những người quen tập làm toán mẹo.

Quản trị mạng:
Cái bạn nói là tình trạng lý tưởng cho những buổi mini meeting (xảy ra vào buổi sáng sớm, một tuần 2-3 ngày).
Trên thực tế, cứ vào mấy cái quép sai chuyên kỹ thuật của VN sẽ thấy họ than vãn "bên phòng IT dửng dưng không chịu giải quyết". Rõ ràng ví dụ của bạn cũng đặt nặng phần "báo cáo kỹ thuật", tức là chỉ chú trọng bề trên. Chứ chả thấy phần "mức độ hài lòng của thân chủ (tức users), cấp ngang hàng thì thây kệ.

Chú thích về cách ra đề thi Toán ngày xưa:
Tôi nhìn nhận rằng cách này lọc ra được những tay rất giỏi về Toán.
Nhưng tôi cũng đồng ý với các nhà giáo dục "đổi mới" (thời ấy) rằng cách ấy sẽ bỏ sót nhiều tài năng Toán phát triển theo hướng khác.

[Monre]

Tôi không quan tâm chuyện nay mai
Người biết chuyện thập niên 60's chắc thế giới này không còn ai

https://vi.wikipedia.org/wiki/Th%E1%BA%ADp_ni%C3%AAn
...
..
.

[khoaph]

Đề bài. Giữa hai điểm, có thể vẽ được vô số đường truyền, với độ dài không nhất thiết bằng nhau. Một đường truyền là một đường gấp khúc mà mỗi đoạn của nó đều song song với một trục tọa độ. Trong mặt phẳng tọa độ, hãy tìm điểm X làm cực tiểu tổng độ dài N đường truyền ngắn nhất khả dĩ nối điểm X với N điểm đã cho trước.

Bối cảnh. Khi thiết kế một mạng có dây có N điểm để cắm thiết bị (máy vi tính, điện thoại), cần tìm chỗ đặt thiết bị trung tâm (switch, tổng đài) tối ưu về vật liệu (dây cáp truyền dẫn tín hiệu).

Đây là một trong các bài tập mình nghĩ ra để giúp một bạn tuyển dụng nhân viên quản trị hệ thống và mạng máy tính. Khi giải bằng giấy bút thì đề ra bằng bản vẽ, với N nhỏ (không quá 10). Mình đã đưa vài đồng nghiệp của mình làm thử ai cũng giải được dễ dàng. Họ đều là kỹ sư ngoài ngành CNTT, thậm chí ngoài mọi ngành có thể liên quan như điện, nước,.. Dễ hiểu thôi: bài toán này dành cho học sinh cấp II bình thường.

Nhưng đáng tiếc, khi dùng trong đề thi tuyển dụng, không có ứng viên nào giải được.

Bên trên chứng minh rồi, nhưng hơi khó hiểu, nên chứng minh lại
Xét các đường gấp khúc giữa 2 điểm A, B có các đoạn song song trục tọa độ
Độ dài các đường gấp khúc sẽ đạt min bằng |xA - xB| + |yA - yB|
Min đạt được khi các đoạn của đường gấp khúc đều hướng về phía gần điểm đích B (*)
Hình 1 biểu hiện 1 trường hợp đạt min, có vô số trường hợp đạt min
Hình 2 biểu hiện 1 trường hợp không đạt min, đoạn thứ 3 của đường gk CD hướng về phía xa D, nếu độ dài đoạn này là x, độ dài đgk CD sẽ = |xC - xD| + |yC - yD| + 2 * x
Giá trị min được đề cập bên trên có thể tính được dựa vào tính chất 2 cạnh đối của hình bình hành thì bằng nhau
Đường gấp khúc ngắn nhất giữa 2 điểm vậy là đã tìm được
Gọi I(x0, y0) là điểm trung tâm
Giả sử có n = 4 điểm trạm, trạm thứ i có tọa độ (X[i], Y[i])
Tổng độ dài các đường truyền theo phương trục hoành là xx = |x0 - X[1]| + |x0 - X[2]| + |x0 - X[3]| + |x0 - X[4]|
ta có bất đẳng thức sau |a| + |b| >= |a + b|, dấu = xảy ra khi a, b cùng dấu.
Áp dụng, |x0 - X[i]| + |x0 - X[j]| = |x0 - X[i]| + |X[j] - x0| >= |X[j] - x0 + x0 - X[i]| = |X[j] - X[i]|
dấu = xảy ra khi x0 nằm giữa hoặc trùng với X[i], X[j]
như vậy ta có thể nhóm như sau (|x0 - X[1]| + |x0 - X[2]|) + (|x0 - X[3]| + |x0 - X[4]|)
>= |X[2] - X[1]| + |X[4] - X[3]|
dấu = xảy ra khi x0 nằm giữa hoặc trùng X[1], X[2] và x0 nằm giữa hoặc trùng X[3], X[4]
nhưng không có gì bảo đảm 2 điều kiện trên đồng thời thỏa mãn, kết quả dấu = của biểu thức xx không xảy ra, tức là chưa tìm được giá trị nhỏ nhất
để dấu = có thể xảy ra, ta phải tính toán thêm
đó là ta phải sắp xếp X[i], gọi dãy x[i] là dãy X[i] sau khi đã sắp xếp tăng dần
nghĩa là x[1] <= x[2] <= x[3] <= x[4]
khi đó xx = |x0 - x[1]| + |x0 - x[2]| + |x0 - x[3]| + |x0 - x[4]|
= (|x0 - x[1]| + |x0 - x[4]|) + (|x0 - x[2]| + |x0 - x[3])
>= x[4] - x[1] + x[3] - x[2]
dấu = xảy ra khi x[1] <= x0 <= x[4] và x[2] <= x0 <= x[3],
giao 2 điều kiện với nhau ta được x[2] <= x0 <= x[3]
đối với trường hợp tổng quát n trạm với n chẵn ta sẽ nhóm tương tự
xx = (|x0 - x[1]| + |x0 - x[n]|) + (|x0 - x[2]| + |x0 - x[n - 1]|) +...
>= x[n] - x[1] + x[n - 1] - x[2] +... + x[n / 2 + 1] - x[n / 2]
dấu = xảy ra khi x[n / 2] <= x0 <= x [n / 2 + 1], đây là 2 phần tử nằm chính giữa dãy x[i]
vậy là đã tìm được min của xx trong trường hợp n chẵn, min của tổng độ dài đường truyền theo phương trục tung tính tương tự
giả sử n = 5, nhóm như sau
xx = (|x0 - x[1] + |x0 - x[5]|) + (|x0 - x[2]| + |x0 - x[4]|) + |x0 - x[3]|
>= x[5] - x[1] + x[4] - x[2] + 0
dấu = xảy ra khi x[1] <= x0 <= x[5], x[2] <= x0 <= x[4], x0 = x[3]
giao lại với nhau được x0 = x[3]
trong trường hợp tổng quát n trạm với n lẻ
min(xx) = x[n] - x[1] + x[n - 1] - x[2] + ... x[n / 2 + 2] - x[n / 2]
đạt được khi x0 = x[n / 2 + 1], đây chính là phần tử chính giữa dãy x[i]

[Ada]

Giải bằng giao các điều kiện (các khoảng số thực) là chặt chẽ rồi. Nhưng mình nghĩ sẽ trực quan hơn, có thể ngắn gọn hơn, nếu theo phương pháp thông dụng của học sinh cấp 2, là khảo sát và vẽ đồ thị hàm số, và đi thẳng đến đáp số tổng quát bằng một phương pháp nữa, cũng của học sinh cấp 2, là quy nạp toán học.