Thuật Toán Tìm Chu Trình Hamilton
Hế lô các bạn, mình đã quay trở lại rồi đây. Cũng
lâu rồi không đăng về thuật toán nhờ, nhân tiện mấy hôm bảo trì blog xem lại
một vài thuật toán được học trong môn Cấu Trúc Dữ Liệu Và Thuật Toán,
để trở lại đăng bài cho anh em xem liền.
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
imageanchor="1"
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhAf1JZrwqsh3OwFlW4G1ywJu5BqHBg7oTyMLCwujxxaI5lIoHnKupEjEmHrMWbVZgM2Iqv7rx9KmYbC-OtHlNkJS5WRb68I7ewmBxRF-vQyKBcCuXcmgkebUb3g6HEho32HM3phbVnPDs/s16000/Hamilton.png"
/>
Thuật Toán Tìm Chu Trình Hamilton Trong Đồ Thị Vô Hướng
Như các bạn đã thấy ở tiêu đề bài viết, thuật toán mà mình muốn chia sẻ ngày
hôm nay là thuật toán tìm chu trình Hamilton trong đồ thị vô hướng. Chúng ta
sẽ tìm hiểu kĩ hơn về thuật toán ở bên dưới nhé!
Tìm Hiểu Thuật Toán
Tại Sao Lại Gọi Là Chu Trình Hamilton?
Chu trình Hamilton hay đường đi Hamilton có nguồn gốc từ bài
toán: "Xuất phát từ một đỉnh của khối thập nhị diện đều hãy đi dọc
theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh khác, mỗi đỉnh
đúng một lần sau đó quay về đỉnh xuất phát.
Đường đi được gọi theo tên của William Rowan Hamilton phát biểu vào
năm 1859.
Mô Tả Thuật Toán:
Thuật toán tìm chu trình Hamilton được giải theo đệ quy quay
lui và bằng ngôn ngữ C++.
Đầu vào đồ thị vô hướng có n đỉnh và m cạnh. Danh sách đỉnh
kề adj được khai báo dưới dạng vector<list> với
adj[i] là danh sách đỉnh kề của đỉnh i.
vector<bool> mark để đánh dấu các đỉnh là true nếu đã
đi qua và false nếu ngược lại.
vector<int> x là mô hình hóa của chu trình Hamilton.
Thuật toán được bắt đầu từ một đỉnh được chọn làm
đỉnh xuất phát x[1] sau đó gọi hàm quay lui TRY(k) để tìm
tiếp các đỉnh tiếp theo trong chu trình.
- Hàm đệ quy quay lui được mô tả như sau:
Với mỗi hàm TRY(k) ta sẽ xét lần lượt các đỉnh e thuộc danh
sách kề của x[k - 1].
Nếu mark[e] = false ta chọn x[k] = e và đánh dấu
mark[e] = true.
Nếu x[k] thỏa mãn điều kiện k = n và x[k] thuộc danh
sách đỉnh kề của x[1] thì ghi nhận chu trình Hamilton.
- Nếu k < n, ta tiếp tục xét TRY(k + 1).
Sau khi thực hiện xong hàm TRY(k + 1) ta đánh dấu e là chưa được
xét (mark[e] = false) rồi tiếp tục xét tới các điểm tiếp theo trong
danh sách đỉnh kề của x[k - 1].
Mã Nguồn:
Mình code dựa trên mô tả thuật toán ở bên trên, nếu các bạn đọc phần mô tả
thuật toán mà chưa hiểu rõ thì có thể xem thêm phần code để hiểu hơn nhé!
Ví Dụ:
Đồ Thị:
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZibO0Q56QC6SGS1I6EMiisti582HY_Tu7KGRrqlQ7Ni8F8lqlCvoFVypZhvXOVHpePdKPxmdcFa2UUAKJ_PVwDunCrJ6GVgaJuiWhTXQcARO7YyQ4djyTywuDl-j7uTHTrsX8XTELs_I/s16000/Hamilton1.png"
/>
Input:
Dòng đầu là n đỉnh mà m cạnh, và m dòng tiếp theo là mô hình hóa của các cạnh.
- 7 12
- 1 3
- 1 6
- 2 4
- 2 5
- 2 6
- 2 7
- 3 4
- 3 6
- 3 7
- 4 5
- 4 7
- 6 7
Output:
- 1 3 4 5 2 7 6 1
- 1 3 7 4 5 2 6 1
- 1 6 2 5 4 7 3 1
- 1 6 7 2 5 4 3 1
Lời Kết
Trên đây là những chia sẻ của mình về cách tìm chu trình Hamilton. Tất cả chỉ
dựa trên những gì mình học và mình hiểu, nếu có bất kì sai sót ở đâu các bạn
hãy để lại comment ở bên dưới để mình biết và sửa lại nhé!
Copyright ©
Phạm Văn Linh