Trình Giải Bài Toán Người Du Hành (TSP)

Tìm lộ trình ngắn nhất đi qua mọi thành phố đúng một lần và quay trở lại điểm xuất phát. Sử dụng quy hoạch động chính xác (Held-Karp) cho các trường hợp nhỏ và thuật toán tìm láng giềng gần nhất + heuristics 2-opt cho các trường hợp lớn hơn. Chấp nhận tọa độ hoặc ma trận khoảng cách và hiển thị lộ trình SVG hoạt họa.

Ví dụ nhanh:

5 thành phố hình vuông+đỉnh 8 thành phố ngẫu nhiên 8 thủ đô EU Ma trận 4×4 Điểm chuẩn 10 thành phố Hình tam giác (đường đi mở)

⌖ Tọa độ (x, y) ▦ Ma trận khoảng cách

Thành phố hoặc ma trận

Dòng tọa độ: A, 10, 20 hoặc 10 20. Hàng ma trận: 0 10 15 20 — mỗi hàng một dòng, hình vuông, không âm. Tối đa 40 thành phố.

Nhãn ma trận (tùy chọn)

Nhãn cách nhau bằng dấu phẩy hoặc khoảng trắng, mỗi nhãn cho một hàng ma trận. Mặc định là A, B, C… nếu bỏ trống.

Thuật toán

Loại lộ trình

Embed Trình Giải Bài Toán Người Du Hành (TSP) Widget

Giới thiệu về Trình Giải Bài Toán Người Du Hành (TSP)

Trình Giải Bài Toán Người Du Hành (TSP) là một công cụ tính toán thực tế và mang tính giáo dục cho bài toán kinh điển Traveling Salesman Problem (TSP): cho một tập hợp các thành phố và khoảng cách giữa từng cặp, tìm lộ trình ngắn nhất có thể đi qua mọi thành phố đúng một lần và quay trở lại điểm bắt đầu. Trình giải này chấp nhận cả tọa độ mặt phẳng hoặc ma trận khoảng cách tùy chỉnh, tự động chọn thuật toán tốt nhất dựa trên quy mô bài toán và hiển thị lộ trình kết quả dưới dạng bản đồ SVG động.

Bài toán người du hành là gì?

Về mặt hình thức, cho một đồ thị đầy đủ có trọng số G = (V, E) với tập đỉnh V = {1, 2, ..., n} và trọng số cạnh d(i, j), TSP tìm kiếm một hoán vị π của các đỉnh sao cho tối thiểu hóa:

minimize Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

Số hạng cuối cùng khép kín vòng lặp. TSP là một trong những bài toán lâu đời nhất và được nghiên cứu nhiều nhất trong tối ưu hóa tổ hợp — nó là bài toán NP-khó trong trường hợp tổng quát, nghĩa là không có thuật toán nào đã biết có thể giải mọi trường hợp trong thời gian đa thức. Mặc dù vậy, nó xuất hiện trong vô số ứng dụng thực tế: định tuyến phương tiện, khoan bảng mạch PCB, giải trình tự DNA, lộ trình lấy hàng trong kho, lịch quan sát thiên văn và thậm chí là giao thư ở nông thôn.

Trình giải này hoạt động như thế nào

Quy hoạch động Held–Karp (Chính xác)

Đối với các trường hợp nhỏ (tối đa 12 thành phố), trình giải sẽ tính toán lộ trình tối ưu có thể chứng minh được bằng thuật toán Held–Karp, được công bố độc lập bởi Richard Bellman và Michael Held & Richard Karp vào năm 1962. Công thức truy hồi chính, trong đó C(S, j) là đường đi ngắn nhất từ đỉnh 1 đến đỉnh j đi qua đúng tập con S:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

Chi phí lộ trình tối ưu sau đó là min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp chạy trong thời gian O(2ⁿ · n²) và bộ nhớ O(2ⁿ · n) — một sự cải thiện khổng lồ so với vét cạn n!, nhưng vẫn mang tính chất mũ. Khi vượt quá khoảng 20 thành phố, dung lượng bộ nhớ trở nên không khả thi.

Nearest-Neighbor + 2-opt (Heuristic)

Đối với các trường hợp lớn hơn, trình giải sử dụng một heuristic hai giai đoạn. Đầu tiên, Nearest-Neighbor xây dựng một lộ trình nhanh chóng bằng cách đi tham lam đến thành phố chưa ghé thăm gần nhất từ mỗi đỉnh xuất phát. Trình giải thử nhiều đỉnh xuất phát và giữ lại lộ trình tốt nhất. Sau đó, tìm kiếm cục bộ 2-opt cải thiện lộ trình bằng cách lặp lại việc loại bỏ hai cạnh và kết nối lại hai đường đi kết quả theo cách khả thi duy nhất còn lại:

Trước: ... a — b ... c — d ... Sau khi hoán đổi 2-opt: ... a — c ... b — d ... Nếu d(a,c) + d(b,d) < d(a,b) + d(c,d) → chấp nhận hoán đổi, đảo ngược lộ trình con b..c

Về mặt hình học, 2-opt loại bỏ mọi điểm "giao nhau" trong lộ trình: bất kỳ hai đoạn thẳng cắt nhau nào cũng luôn có thể được gỡ bỏ để có tổng chiều dài ngắn hơn. Thuật toán dừng lại ở tối ưu cục bộ nơi không có hoán đổi đơn lẻ nào giúp ích được, gọi là lộ trình 2-optimal. Trên các trường hợp Euclid thực tế, 2-opt thường tìm thấy các lộ trình trong phạm vi 2–5% so với tối ưu thực sự chỉ trong vài mili giây.

Định dạng nhập liệu

Chế độ tọa độ (x, y)

Mỗi thành phố một dòng. Mỗi dòng là nhãn, x, y — nhãn là tùy chọn. Trình giải tự động tính toán khoảng cách Euclid và trực quan hóa các thành phố tại vị trí thực của chúng.

A, 10, 20 B, 40, 70 C, 75, 30 Hà Nội: 105.83, 21.02 10 20 ← tự động dán nhãn C1

Chế độ ma trận khoảng cách

Một ma trận vuông n × n gồm các khoảng cách không âm, mỗi hàng một dòng, các giá trị cách nhau bằng khoảng trắng hoặc dấu phẩy. Ma trận có thể đối xứng hoặc không đối xứng — ma trận không đối xứng mô phỏng đường một chiều, giá vé máy bay với tính khả dụng thay đổi và hành trình phụ thuộc vào gió. Tùy chọn cung cấp nhãn trong trường Nhãn ma trận.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

So sánh thuật toán

Thuật toán	Độ phức tạp thời gian	Bộ nhớ	Chất lượng kết quả	Quy mô thực tế
Vét cạn (Brute force)	O(n!)	O(n)	Tối ưu	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	Tối ưu	n ≤ 20
Nearest-Neighbor	O(n²)	O(n)	Tệ hơn tối ưu ~25%	n ≤ hàng nghìn
NN + 2-opt	O(n² · số lần lặp)	O(n)	Tệ hơn tối ưu ~2–5%	n ≤ hàng trăm

Cách sử dụng trình giải này

Chọn chế độ nhập liệu. Tọa độ nếu thành phố của bạn có vị trí (x, y) ý nghĩa; Ma trận khoảng cách nếu chi phí của bạn không phải Euclid hoặc không đối xứng.
Dán hoặc nhập dữ liệu của bạn. Mỗi thành phố hoặc hàng một dòng. Nhấp vào nút ví dụ nhanh phía trên biểu mẫu để điền sẵn một ví dụ hợp lệ.
Chọn thuật toán. Để ở chế độ Tự động cho các mặc định phù hợp: Held–Karp khi quy mô đủ nhỏ để tối ưu có thể chứng minh, nếu không thì dùng NN + 2-opt. Buộc chọn một thuật toán cụ thể nếu bạn muốn so sánh.
Chọn khép kín hoặc mở. Một lộ trình khép kín sẽ quay lại điểm bắt đầu — TSP truyền thống. Chế độ đường đi mở giải quyết bài toán Đường đi Hamiltonian liên quan nơi người bán hàng kết thúc tại một thành phố khác.
Nhấp Giải quyết. Trang kết quả hiển thị tổng chiều dài lộ trình, hoạt ảnh SVG của tuyến đường (nhấp "Phát lại hoạt ảnh" để xem lại), trình tự thành phố đầy đủ, phân tích từng cạnh và ma trận khoảng cách với các cạnh lộ trình được đánh dấu.

Ví dụ minh họa

Xét năm thành phố — một hình chữ nhật cộng với một đỉnh: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Trình giải trả về:

Lộ trình: A → D → E → C → B → A
Chiều dài: 3 + √8 + √8 + 3 + 4 ≈ 15.66
Tối ưu? Có — Held–Karp chứng minh không tồn tại lộ trình nào ngắn hơn.
Tại sao lại theo thứ tự này? Tuyến đường đi theo bao lồi của năm điểm (A → D → E → C → B → A). Một đặc tính kinh điển của Euclidean TSP là lộ trình tối ưu sẽ ghé thăm các điểm trên bao lồi theo thứ tự vòng tròn của chúng; các điểm bên trong sẽ nằm xen kẽ giữa các hàng xóm bao lồi liền kề. Bất kỳ lộ trình nào tự cắt chính mình, như A → C → B → D → E → A (chiều dài ≈ 21.8), luôn có thể được gỡ rối bằng 2-opt để có kết quả ngắn hơn.

Ứng dụng trong thế giới thực

Logistics & giao hàng — tối ưu hóa lộ trình hàng ngày của tài xế qua 15 điểm dừng để giảm thiểu nhiên liệu và thời gian.
Sản xuất — sắp xếp thứ tự các lỗ mà máy khoan CNC phải thực hiện trên PCB để giảm thiểu việc di chuyển đầu khoan.
Lắp ráp bộ gen — sắp xếp các đoạn DNA theo độ tương đồng chồng lấp, được mã hóa dưới dạng ma trận khoảng cách.
Thiên văn học — lập lịch chuyển động của kính thiên văn giữa các ngôi sao mục tiêu để tối đa hóa thời gian quan sát.
Lấy hàng trong kho — sắp xếp trình tự các lối đi để thực hiện đơn hàng với ít bước chân nhất.
Lập kế hoạch du lịch — lập kế hoạch cho một chuyến đi qua nhiều thành phố giúp giảm thiểu thời gian di chuyển và chi phí vé.

Câu hỏi thường gặp

Bài toán người du hành là gì?

Bài toán người du hành (Traveling Salesman Problem - TSP) yêu cầu tìm lộ trình ngắn nhất có thể đi qua mọi thành phố đúng một lần và quay trở lại thành phố ban đầu. Đây là một trong những bài toán nổi tiếng nhất trong tối ưu hóa tổ hợp và là bài toán NP-khó trong trường hợp tổng quát, nghĩa là không có thuật toán nào đã biết có thể giải mọi trường hợp trong thời gian đa thức.

Thuật toán Held–Karp là gì?

Held–Karp là một thuật toán quy hoạch động giải TSP một cách chính xác trong thời gian O(2ⁿ · n²) và bộ nhớ O(2ⁿ · n). Nó nhanh hơn đáng kể so với vét cạn (n giai thừa) nhưng vẫn có tính chất mũ, vì vậy trên thực tế nó chỉ được sử dụng cho các trường hợp tối đa khoảng 20 thành phố. Trình giải này sử dụng Held–Karp khi có từ 12 thành phố trở xuống.

2-opt là gì và tại sao nó được sử dụng?

2-opt là một heuristic tìm kiếm cục bộ liên tục loại bỏ hai cạnh khỏi lộ trình hiện tại và kết nối lại hai đường đi kết quả theo cách khả thi khác. Khi lộ trình mới ngắn hơn, việc hoán đổi sẽ được giữ lại. 2-opt chạy trong thời gian đa thức trên mỗi lần lặp và liên tục tìm thấy các lộ trình trong phạm vi vài phần trăm so với mức tối ưu, đó là lý do tại sao nó là heuristic kinh điển cho các trường hợp TSP lớn hơn.

Khi nào tôi nên sử dụng tọa độ so với ma trận khoảng cách?

Sử dụng tọa độ khi các thành phố của bạn nằm trên một mặt phẳng với khoảng cách đường thẳng — ví dụ các điểm trên bản đồ, vị trí kho hàng hoặc các lỗ khoan trên bảng mạch. Sử dụng ma trận khoảng cách khi chi phí từng cặp không phải là Euclid — ví dụ giá vé máy bay, thời gian di chuyển khi có giao thông, khoảng cách đường bộ một chiều hoặc chi phí không đối xứng. Chế độ ma trận chấp nhận bất kỳ khoảng cách không âm nào, ngay cả những khoảng cách không đối xứng.

Giải pháp 2-opt có phải là tối ưu không?

Không, 2-opt trả về một lộ trình tối ưu bậc 2, nghĩa là không có cặp cạnh đơn lẻ nào có thể được hoán đổi để tạo ra một tuyến đường ngắn hơn. Đây là một tối ưu cục bộ và thường nằm trong phạm vi vài phần trăm so với tối ưu toàn cục trên các trường hợp thông thường, nhưng nó không được đảm bảo là tốt nhất toàn cầu. Để có một lộ trình tối ưu có thể chứng minh được trên các trường hợp nhỏ, hãy chọn Held–Karp.

Công cụ này có hỗ trợ ma trận khoảng cách không đối xứng không?

Có. Trong chế độ Ma trận khoảng cách, bạn có thể nhập bất kỳ ma trận vuông không âm nào, bao gồm cả các ma trận không đối xứng trong đó D[i][j] khác với D[j][i]. Held–Karp và 2-opt đều xử lý chính xác các ma trận không đối xứng. Điều này hữu ích cho các bài toán định tuyến trong thế giới thực với đường một chiều, giao thông hoặc chi phí chuyến bay phụ thuộc vào gió.

Đọc thêm

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Trình Giải Bài Toán Người Du Hành (TSP)" tại https://MiniWebtool.com/vi/trinh-giai-bai-toan-nguoi-du-hanh-tsp/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 21 tháng 4, 2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.