Công cụ Kiểm tra Đường đi Hamilton

Giới thiệu về Công cụ Kiểm tra Đường đi Hamilton

Công cụ kiểm tra Đường đi Hamilton xác định xem một đồ thị có chứa đường đi Hamilton — một trình tự đi qua mọi đỉnh đúng một lần — hay chu trình Hamilton, trình tự này bổ sung thêm việc quay lại đỉnh bắt đầu. Công cụ kết hợp các bước kiểm tra trước về cấu trúc nhanh (tính liên thông, các điều kiện tiên quyết về bậc, định lý Dirac, định lý Ore) với tìm kiếm quay lui được điều chỉnh bằng thuật toán Warnsdorff, và trực quan hóa đường đi chứng thực bằng ảnh động từng bước.

Đường đi Hamilton là gì?

Cho một đồ thị G = (V, E) với n đỉnh, một đường đi Hamilton là một trình tự có thứ tự v₁, v₂, …, v_n của tất cả các đỉnh sao cho mỗi cặp liên tiếp (v_i, v_i+1) là một cạnh của G, và mọi đỉnh xuất hiện đúng một lần. Nếu thêm vào đó (v_n, v₁) là một cạnh, thì trình tự đó là một chu trình Hamilton.

Bài toán này được đặt theo tên của William Rowan Hamilton, người vào năm 1857 đã phát minh ra trò chơi Icosian — một câu đố yêu cầu người giải tìm một chu trình đi qua mọi đỉnh của một hình thập nhị diện đều đúng một lần.

Tại sao bài toán này khó: NP-Đầy đủ

Cả bài toán quyết định đường đi Hamilton và bài toán quyết định chu trình Hamilton đều là các bài toán NP-đầy đủ (Karp, 1972). Trừ khi P = NP, không tồn tại thuật toán thời gian đa thức nào giải được mọi trường hợp. Trong trường hợp xấu nhất, quay lui phải khám phá một cây tìm kiếm có kích thước lên tới (n−1)! cho một chu trình. Đây là lý do tại sao máy tính giới hạn đầu vào ở mức 20 đỉnh — một sự gia tăng đa thức nhỏ trong n sẽ tạo ra sự gia tăng bùng nổ về thời gian chạy.

Trong thực tế, thuật toán Warnsdorff (ban đầu được Heinrich Warnsdorff nghĩ ra vào năm 1823 cho bài toán mã đi tuần) giúp quá trình tìm kiếm nhanh hơn đáng kể trên các đồ thị có cấu trúc: ở mỗi bước, thuật toán mở rộng đường đi hiện tại sang đỉnh hàng xóm chưa thăm có số lượng hàng xóm chưa thăm ít nhất. Quy tắc tham lam này giúp quá trình tìm kiếm không tự đưa mình vào ngõ cụt và thường tìm thấy hành trình Hamilton mà không cần quay lui chút nào trên các đồ thị có tính chất tốt.

Điều kiện cần — Loại bỏ nhanh

Trước khi chạy một tìm kiếm tốn kém, máy tính sẽ loại bỏ các đồ thị chắc chắn không thể chứa đường đi Hamilton:

• Tính liên thông. Một đường đi Hamilton phải đi qua mọi đỉnh, vì vậy đồ thị phải có đúng một thành phần liên thông. Đối với đồ thị có hướng, yêu cầu tính liên thông yếu (bỏ qua hướng mũi tên).
• Bậc (vô hướng). Tối đa hai đỉnh có thể có bậc 1 — đó là những ứng cử viên duy nhất cho các điểm đầu cuối của đường đi. Đối với một chu trình Hamilton, mọi đỉnh phải có bậc ít nhất là 2.
• Bậc (có hướng). Đối với một đường đi Hamilton, tối đa một đỉnh có thể có bán bậc vào bằng 0 (điểm bắt đầu) và tối đa một đỉnh có thể có bán bậc ra bằng 0 (điểm kết thúc). Đối với một chu trình Hamilton, mọi đỉnh phải có cả bán bậc vào ≥ 1 và bán bậc ra ≥ 1.

Các quy tắc này loại bỏ nhiều đầu vào vô vọng trong thời gian tuyến tính, tránh lãng phí nỗ lực quay lui.

Điều kiện đủ — Định lý cổ điển

Một số định lý cổ điển đưa ra các điều kiện đủ (nhưng không phải là điều kiện cần) đảm bảo một chu trình Hamilton trong các đồ thị đơn vô hướng. Nếu bất kỳ định lý nào trong số này áp dụng được, máy tính sẽ đánh dấu kết quả là "ĐẢM BẢO" mà không cần chạy tìm kiếm — mặc dù nó vẫn hiển thị một chu trình chứng thực.

Định lý Dirac (1952)

Nếu G là một đồ thị vô hướng đơn có n ≥ 3 đỉnh và mọi đỉnh có bậc ít nhất n / 2, thì G có một chu trình Hamilton.

Định lý Ore (1960)

Nếu đối với mỗi cặp đỉnh không kề nhau u và v, chúng ta có deg(u) + deg(v) ≥ n, thì G có một chu trình Hamilton. Điều kiện của Ore yếu hơn của Dirac một cách chặt chẽ, vì vậy Ore bao hàm cả Dirac.

Việc không thỏa mãn điều kiện Dirac hoặc Ore không có nghĩa là đồ thị thiếu chu trình Hamilton — nhiều đồ thị không thỏa mãn cả hai nhưng vẫn chứa một chu trình (ví dụ: một chu trình n đơn giản có bậc tối thiểu là 2, thấp hơn nhiều so với n/2 đối với n lớn).

Thuật toán tìm kiếm bên trong

Khi các bước kiểm tra trước không giải quyết được vấn đề, máy tính sẽ chạy tìm kiếm quay lui trên biểu diễn kề của đồ thị. Các chiến thuật chính:

1. Bitmask cho tập hợp đã thăm. Các đỉnh đã thăm được lưu trữ dưới dạng bitmask (kiểm tra thành viên O(1) nhanh chóng cho tối đa 20 đỉnh).
2. Thuật toán Warnsdorff. Tại mỗi lần mở rộng, các đỉnh hàng xóm được thử theo thứ tự bậc chưa thăm còn lại của chúng (nhỏ nhất trước), mô phỏng thứ tự "ít nhánh" nhất.
3. Lựa chọn gốc. Đối với chu trình Hamilton, chỉ cần một đỉnh bắt đầu (chu trình có tính bất biến quay). Đối với đường đi Hamilton, các điểm bắt đầu được thử theo thứ tự tăng dần của bán bậc ra — các vị trí hiếm nhất trước.
4. Ngân sách bước. Một giới hạn cứng giúp ngăn các trường hợp bệnh lý chạy vô tận; giao diện người dùng sẽ báo cáo kết quả là "quá thời gian" nếu ngân sách bị cạn kiệt.

Hamilton so với Euler

Rất dễ nhầm lẫn giữa các bài toán Hamilton và Euler — chúng nghe có vẻ giống nhau nhưng về cơ bản là khác nhau:

Các định dạng đầu vào được hỗ trợ

Danh sách cạnh

Mỗi cạnh trên một dòng, hoặc phân tách bằng dấu phẩy. Các dấu phân cách được hỗ trợ: A-B, A B, A,B, A--B, A->B, A<-B. Sử dụng -> để ép buộc hiểu theo hướng có hướng.

Ma trận kề

Ma trận vuông chứa các giá trị 0/1, mỗi hàng trên một dòng, phân tách bằng khoảng trắng hoặc dấu phẩy. Cung cấp nhãn tùy chọn trong trường Nhãn ma trận; nếu không, A, B, C… sẽ được sử dụng tự động.

Cách sử dụng trình kiểm tra này

1. Chọn định dạng đầu vào — Danh sách cạnh cho các đồ thị nhỏ tự viết, Ma trận kề cho việc dán từ mã nguồn hoặc sách giáo khoa.
2. Dán đồ thị của bạn vào vùng văn bản. Đối với đầu vào ma trận, tùy chọn cung cấp nhãn đỉnh.
3. Chọn nội dung cần kiểm tra: Chỉ đường đi, Chỉ chu trình, hoặc Cả hai trong một lần chạy.
4. Chọn loại đồ thị — Tự động phát hiện sẽ suy luận tính chất có hướng từ kiểu mũi tên (->) hoặc tính đối xứng của ma trận.
5. Nhấp vào Kiểm tra Hamilton. Trang kết quả hiển thị tiêu đề kết luận, kiểm tra trước điều kiện cần, các bài kiểm tra điều kiện đủ Dirac / Ore, đường đi chứng thực (nếu có) và trực quan hóa tương tác.
6. Phát lại chứng thực bằng các nút điều khiển Phát / Từng bước. Xem đường đi sáng lên từng cạnh trên đồ thị.

Ví dụ thực tế — Đồ thị Petersen

Đồ thị Petersen nổi tiếng (10 đỉnh, 15 cạnh, bậc 3 đều) là một ví dụ kinh điển trong sách giáo khoa về một đồ thị có đường đi Hamilton nhưng không có chu trình Hamilton. Dán nội dung này vào trường danh sách cạnh và nhấp Kiểm tra:

Trình kiểm tra xác nhận: Tìm thấy đường đi Hamilton (ví dụ: 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), nhưng tìm kiếm toàn diện không tìm thấy cách nào để đóng vòng lặp trở lại — một kết quả được chứng minh lần đầu tiên vào những năm 1890.

Các ứng dụng phổ biến

• Định tuyến và Bài toán người bán hàng rong (TSP) — mọi hành trình TSP là một chu trình Hamilton trong đồ thị đầy đủ có trọng số.
• Lắp ráp bộ gen — tái tạo một trình tự DNA từ các đoạn đọc chồng chéo có thể được mô hình hóa như một đường đi Hamilton trong đồ thị chồng chéo.
• Bố cục mạch điện — sắp xếp các chân cắm trên PCB để có chiều dài dây tối thiểu.
• AI trò chơi và giải đố — mã đi tuần trên bàn cờ, trò chơi Icosian.
• Lập lịch — sắp xếp trình tự các nhiệm vụ sao cho mỗi nhiệm vụ có thể chuyển tiếp khả thi sang nhiệm vụ tiếp theo.
• Giảng dạy tổ hợp — minh họa tính NP-đầy đủ bằng các ví dụ nhỏ có thể giải bằng tay.

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

Đường đi Hamilton là gì?

Đường đi Hamilton là một đường đi trong đồ thị đi qua mỗi đỉnh đúng một lần. Nó được đặt theo tên của William Rowan Hamilton, người đã nghiên cứu vấn đề này trên đồ thị thập nhị diện vào năm 1857. Việc quyết định xem một đường đi như vậy có tồn tại hay không là một bài toán NP-đầy đủ, vì vậy không có thuật toán nào được biết đến có thể giải nó trong thời gian đa thức cho mọi đồ thị.

Chu trình Hamilton khác với đường đi Hamilton như thế nào?

Chu trình Hamilton là một đường đi Hamilton quay trở lại đỉnh bắt đầu của nó, tạo thành một vòng khép kín đi qua mỗi đỉnh đúng một lần. Mọi chu trình Hamilton đều chứa một đường đi Hamilton (chỉ cần bỏ cạnh đóng), nhưng điều ngược lại thì không đúng: nhiều đồ thị có đường đi Hamilton nhưng không có chu trình Hamilton.

Định lý Dirac nói gì?

Định lý Dirac (1952) phát biểu rằng bất kỳ đồ thị vô hướng đơn nào có n ≥ 3 đỉnh, trong đó mỗi đỉnh có bậc ít nhất n/2, đều chứa một chu trình Hamilton. Đó là một điều kiện đủ nhưng không phải là điều kiện cần: nhiều đồ thị không đạt ngưỡng Dirac vẫn có chu trình Hamilton.

Định lý Ore nói gì?

Định lý Ore (1960) phát biểu rằng nếu, đối với mọi cặp đỉnh không kề nhau u và v trong một đồ thị đơn có n ≥ 3 đỉnh, tổng các bậc của chúng ít nhất là n, thì đồ thị đó có một chu trình Hamilton. Điều kiện của Ore yếu hơn của Dirac, vì vậy định lý Ore áp dụng được bất cứ khi nào định lý Dirac áp dụng được.

Tại sao việc tìm kiếm bị giới hạn ở 20 đỉnh?

Các bài toán quyết định đường đi và chu trình Hamilton là NP-đầy đủ. Thời gian chạy trong trường hợp xấu nhất tăng theo cấp số nhân với số đỉnh. Với việc cắt tỉa và thuật toán Warnsdorff, máy tính xử lý nhanh chóng nhiều đồ thị nhỏ lên đến 20 đỉnh, nhưng các trường hợp khó hơn có thể bị quá thời gian. Ngoài 20 đỉnh, bạn nên sử dụng các trình giải chuyên dụng như Concorde hoặc các công thức lập trình nguyên.

Thuật toán Warnsdorff là gì?

Quy tắc Warnsdorff, được đề xuất vào năm 1823 cho bài toán mã đi tuần, nói rằng ở mỗi bước bạn nên thăm đỉnh tiếp theo có ít hàng xóm chưa thăm nhất. Quy tắc có vẻ tham lam này thực tế giúp cắt tỉa đáng kể cây quay lui và thường tìm thấy đường đi Hamilton mà không cần quay lui chút nào trên các đồ thị chính quy.

Công cụ này có tìm thấy tất cả các đường đi Hamilton không?

Không — nó tìm thấy một đường đi hoặc chu trình chứng thực duy nhất khi có tồn tại. Việc đếm tổng số đường đi Hamilton bản thân nó là một bài toán #P-đầy đủ và khó hơn nhiều so với bài toán quyết định. Để liệt kê, các công cụ chuyên dụng hoặc trình giải lập trình nguyên sẽ phù hợp hơn.

Đọc thêm

• Đường đi Hamilton — Wikipedia
• Bài toán đường đi Hamilton — Wikipedia
• Định lý Dirac về chu trình Hamilton — Wikipedia
• Định lý Ore — Wikipedia
• Quy tắc Warnsdorff — Wikipedia

Phép toán toán học nâng cao:

• Máy Tính Antilog
• Máy tính hàm Beta
• Máy tính hệ số nhị thức
• Máy tính phân phối xác suất nhị thức
• Máy tính Bitwise Nổi bật
• Máy tính Định lý Giới hạn Trung tâm
• Máy tính kết hợp
• Máy tính hàm lỗi bổ sung
• Máy tính số phức
• Máy tính Entropy
• Máy tính chức năng lỗi
• Máy tính giảm dần theo cấp số nhân
• Máy tính tăng trưởng theo cấp số nhân
• Máy tính Tích phân Lũy thừa
• Máy Tính Số Mũ (Độ Chính Xác Cao) Nổi bật
• Máy tính giai thừa Nổi bật
• Máy tính Hàm Gamma
• Máy tính tỷ lệ vàng
• Máy tính Nửa đời
• Máy tính phần trăm tăng trưởng
• Máy tính hoán vị
• Máy tính Phân phối Poisson
• Máy tính căn bậc của đa thức với các bước chi tiết
• Máy tính xác suất
• Máy tính phân bố xác suất
• Máy tính Tỷ lệ thức
• Máy tính công thức bậc hai
• Máy Tính Khoa Học
• Máy tính ký hiệu khoa học
• Máy Tính Chữ Số Có Nghĩa Mới
• Máy tính tổng khối
• Máy tính tổng các số liên tiếp
• Máy tính Tổng Bình phương
• Công cụ tạo bảng chân trị
• Máy tính lý thuyết tập hợp
• Công cụ tạo Biểu đồ Venn (3 Tập hợp)
• Máy tính Định lý Số dư Trung Quốc
• Máy tính Hàm Phi Euler
• Máy tính Thuật toán Euclid Mở rộng
• Máy tính Nghịch đảo Nhân theo Mô-đun
• Máy tính Phân số liên tục
• Máy tính Đường đi Ngắn nhất Dijkstra
• Máy tính Cây khung nhỏ nhất
• Trình xác thực dãy bậc đồ thị
• Máy tính Hoán vị lệch (Giai thừa phụ)
• Máy tính số Stirling
• Máy tính Nguyên lý Chuồng bồ câu
• Máy tính Phân phối Dừng Chuỗi Markov
• Máy Tính Làm Tròn Mới
• Máy Tính Phân Phối Nhị Thức Âm Mới
• Máy tính Hoán vị Có lặp Mới
• Máy Tính Lũy Thừa Modular Mới
• Máy Tính Căn Nguyên Thủy
• Công Cụ Rút Gọn Đại Số Boolean Mới
• Công cụ Giải Bản đồ Karnaugh (K-Map) Mới
• Máy Tính Tô Màu Đồ Thị Mới
• Máy Tính Sắp Xếp Topo Mới
• Máy Tính Ma Trận Kề Mới
• Máy tính Bao hàm - Loại trừ Mới
• Công cụ Giải Quy hoạch Tuyến tính Mới
• Trình Giải Bài Toán Người Du Hành (TSP) Mới
• Công cụ Kiểm tra Đường đi Hamilton Mới
• Trình Kiểm Tra Đồ Thị Phẳng Mới
• Máy Tính Luồng Mạng (Luồng Cực Đại) Mới
• Trình giải Bài toán Hôn nhân Ổn định Mới
• Máy Tính Bậc Lý Thuyết Nhóm Mới
• Máy tính Vành và Trường Mới