CON SỐ ẨN CỦA NGƯỜI BÁN HÀNG RONG BỊ DỒN VÀO GÓC

Có khai báo sử dụng AI. Trong mục “Disclosure of AI Use” (Công khai việc sử dụng AI), các tác giả cho biết họ đã dùng công cụ AI GPT-5.6 Sol Pro để chuẩn bị bài báo, đã rà soát và kiểm chứng mọi kết quả, và chịu hoàn toàn trách nhiệm về nội dung. Mã nguồn của họ được cung cấp khi có yêu cầu.

Bài toán người bán hàng rong đòi tìm hành trình ngắn nhất đi qua mỗi điểm của một tập hợp đúng một lần rồi quay về điểm xuất phát. Giờ hãy cho các điểm là ngẫu nhiên: ném n điểm một cách đều vào một hình vuông cạnh 1 và hỏi hành trình ngắn nhất dài bao nhiêu.

Năm 1959, Beardwood, Halton và Hammersley đã chứng minh một câu trả lời đáng kinh ngạc. Khi n tăng, độ dài của hành trình tốt nhất hầu chắc chắn bằng β√n, trong đó β là một hằng số phổ quát — như nhau với mọi cách rải ngẫu nhiên. Họ cũng chỉ ra rằng 0,625 ≤ β ≤ 0,9212.

Hơn sáu mươi lăm năm sau, không ai biết β. Không có công thức nào. Các thí nghiệm máy tính quy mô lớn cho giá trị khoảng 0,7124, nhưng thí nghiệm không phải là chứng minh. Cho tới nay, các cận tốt nhất đã được chứng minh là 0,6277 ≤ β ≤ 0,90367. Những hằng số như vậy quan trọng trong logistics, nơi chúng được dùng để ước tính độ dài tuyến giao hàng mà không cần tính toán chúng — đó là lý do kết quả mới đến từ Trường Kinh doanh McCombs của Đại học Texas ở Austin, do Zhuolun Dong và Junyu Cao thực hiện.

Khoảng kẹp mới

Bài báo chứng minh:

0,6421 ≤ β ≤ 0,8810

và, nhờ lấy mẫu ngẫu nhiên, chỉ ra rằng 0,6536 ≤ β ≤ 0,8749 với xác suất ít nhất 1 − 2 × 10⁻⁴. Xác suất đó liên quan đến tính ngẫu nhiên của việc lấy mẫu trên máy tính, không phải bản thân β, vốn là một con số cố định.

Từ dưới lên: cắt các cạnh dài

Để chứng minh mọi hành trình đều phải dài, các tác giả xem điều gì xảy ra nếu xóa mọi cạnh của hành trình dài hơn một độ dài r nào đó. Hành trình vỡ thành những đoạn đường, và mỗi đoạn nằm gọn trong một cụm điểm cách nhau không quá r. Một cụm cần càng nhiều đoạn đường để phủ thì hành trình càng phải có nhiều cạnh dài. Cộng điều này qua mọi giá trị r khả dĩ sẽ cho độ dài hành trình:

ℓ(H) = ∫₀^∞ N_H(r) dr,

trong đó N_H(r) đếm số cạnh dài hơn r.

Các điểm cô lập và các đầu mút đường cho số hạng cũ 5/8 = 0,625 — đúng bằng cận năm 1959. Thành phần mới là một loạt hiệu chỉnh từ các cụm nhỏ gồm 3, 4 và 5 điểm, mỗi hiệu chỉnh là một tích phân trên các vị trí khả dĩ của các điểm. Những tích phân này không thể tính chính xác, nên các tác giả chia miền của chúng thành những khối lập phương nhỏ xíu và chặn dưới từng khối, với mọi số vô tỷ được làm tròn theo hướng bất lợi để kết quả là một cận thực sự:

β ≥ 0,625 + 0,01113528859 + 0,005040573276 + 0,001015487669 > 0,6421.

Từ trên xuống: đi zíc zắc theo khối năm điểm

Một cận trên chỉ cần một hành trình tốt. Công thức cổ điển cắt hình vuông thành các dải nằm ngang và quét chúng theo kiểu zíc zắc, từ trái sang phải, rồi từ phải sang trái. Điểm mới: trong mỗi dải, các điểm được lấy theo khối năm điểm, và mỗi khối được đi qua theo thứ tự tốt nhất trong 24 thứ tự khả dĩ của nó.

Độ dài kỳ vọng của một khối là một tích phân mười một chiều — năm khoảng cách ngang giữa các điểm và sáu độ cao. Các tác giả chặn nó bằng số trên một lưới mịn, một lần nữa với các số hữu tỷ được làm tròn theo hướng an toàn, và thu được β < 0,8810.

Khoảng cách còn lại

Khoảng kẹp đã thu hẹp từ bề rộng khoảng 0,28 xuống khoảng 0,24, nhưng giá trị thực nghiệm 0,7124 vẫn nằm sâu bên trong. Lưới mịn hơn, ước lượng sắc hơn về diện tích các đĩa chồng lấn và các khối dài hơn có thể thu hẹp nó thêm. Để khép lại khoảng cách còn lại, các tác giả viết, “có thể cần những kỹ thuật mới.”