Trang chủLập trìnhCTDL & Thuật toánTìm hiểu thuật toán vét cạn trong lập trình

Tìm hiểu thuật toán vét cạn trong lập trình

Vét cạn là một trong những thuật toán được áp dụng tương đối nhiều trong các bài toán thực tế, vậy thuật toán vét cạn là gì, khi nào cần dùng, làm sao áp dụng thì chúng ta sẽ cùng tìm hiểu trong bài viết này.

Thuật toán vét cạn

Ý tưởng của vét cạn là tạo ra hết tất cả các lời giải có thể có của một bài toán, và sau đó lựa chọn một giải pháp tốt nhất hoặc đếm số lượng lời giải phụ thuộc vào từng bài toán cụ thể.

Tìm kiếm vét cạn là một kỹ thuật tốt nếu dữ liệu đầu vào không quá lớn và đủ thời gian để đi qua hết tất cả các lời giải mà không tốn quá nhiều thời gian xử lý, vì việc tìm kiếm thường dễ để thực thi và nó luôn cho ra lời giải chính xác. Nếu tìm kiếm vét cạn là quá chậm, thì lúc đó ta sẽ nghĩ tới các thuật toán tham lam hoặc quy hoạch động.

Và thông thường các bài toán vét cạn sẽ sử dụng quay lui (backtracking) để vét được toàn bộ những lời giải có thể sảy ra. Mình có một bài viết riêng về backtracking, bạn đọc thăm khảo thêm nhé: Tìm hiểu về Thuật toán quay lui (Backtracking).

Nói tóm lại, thì vét cạn chính là việc ta đi tìm tất cả lời giải của một bài toán. Lý thuyết là vậy, bây giờ cùng đi vào một số bài toán ví dụ cụ thể nhé.

Xét bài toán cụ thể

Bài toán liệt kê dãy nhị phân độ dài n

Bài toán liệt kê dãy nhị phân độ dài n, có nghĩa là ta đi liệt kê hết tất cả các dãy nhị phân từ 000..0(n số 0) cho tới 111..1(n số 1). Ví dụ liệt kê dãy nhị phân độ dài 3.

000, 001, 010, 011, 100, 101, 110, 111

Đây là một bài toán điển hình cho phương pháp vét cạn, và chúng ta sẽ sử dụng thuật toán quay lui để thực hiện.

Ta viết code như sau:

#include <iostream>
using namespace std;
int n = 3; //Ta gắn n = 3
int a[100];

//Hàm hiển thị dãy nhị phân
void show(){
    for(int i = 0; i<n; i++){
        cout<<a[i];
    }
    cout<<"\n";
}
 
 //Hàm quay lui để thực hiện vét cạn
void Backtracking(int k){
    for(int i = 0; i<= 1; i++)
    {
        a[k] = i;
        if(k == n-1){
            show(); //Nếu độ dài nhị phân = n ta in ra dãy nhị phân
        }
        else{
            Backtracking(k+1); //Đô dài chưa bằng n tiếp tục thực hiện quay lui
        }
    }
}
 
int main()
{
    Backtracking(0);
}

Kết quả khi thực hiện chương trình.

Tìm hiểu thuật toán vét cạn trong lập trình

Như vậy ta đã liệt kê được hết các dãy nhị phân có độ dài là n, như vậy chính là vét cạn đó ạ.

Tìm đường đi dài nhất – Duyệt đồ thị

Tìm đường đi dài nhất trong đồ thị, đây cũng là một bài toán áp dụng phương pháp vét cạn. Với bài toán này, chúng ta sẽ duyệt và tìm kiếm tất cả các đường đi có thể của đồ thị, sau đó so sánh từng đường đi và tìm ra đường đi dài nhất của đồ thị đã cho.

Mình sẽ làm một ví dụ cụ thể, ta sẽ nhập vào ma trận đồ thị, và 2 đỉnh u v. Sau đó tìm đường đi dài nhất từ u tới v.

#include <iostream>
#include <algorithm>
using namespace std;
bool dd[1000], tt = 0; //Mảng đánh dấu tối đa  1000 đỉnh
int dem=1,dem2, n;// dem sử dụng để đếm số bước đi của  đường đi hiện tai, dem2 để lưu số bước của đường đi dài nhát trước đó
int a[1000][1000]; //Mảng để lưu mảng đồ thị
int b[1000], c[1000]; //Mảng c để lưu đường đi dài nhất tìm được tạm thời, mảng b sử dụng trong qua trình tìm 1 đường đi
int u,v; //2 đỉnh u và v

//Hàm tìm đường đi dài nhất
void duongdidainhat(int i)
{
	dd[i]=1; //Đánh dấu đỉnh i đã đi qua

//Nếu đinh i chính bằng v  tức là từ đỉnh u ta đã đi tới v
	if(i==v)
	{
		tt=1;
    //Phần này chính là vét cạn đó, ta tìm tất cả đường đi rồi so sánh lấy được đường đi dài nhất
      //Nếu đường đi hiện tại tìm được lớn hơn đường đi dài nhất ban đầu
		if(dem > dem2)
		{
          //Gắn đường đi dài nhất bằng đường đi tìm được, gắn lại biến đếm
			for(int j=0;j<dem;j++) c[j]=b[j]; dem2 = dem;
		}
	}
//Nếu chưa tới đỉnh v ta tiếp tục duyệt các đỉnh chưa đi qua
	else for(int j=0;j<n;j++) 
	{
		if(a[i][j] != 0 && dd[j]==0)//Kiểm tra xem giữa 2 đỉnh có tồn tại đường đi không, và đỉnh đó đã đi qua trước đó chưa
		{
			b[dem++] = j; //Tăng biến đếm bước đi lên 1, đồng thời gắn đường đi tại đỉnh j
			duongdidainhat(j); //tiếp tục quay lui 
			dem--; dd[j]=0;//Thoát khỏi hàm quay lui, lúc này hàm quay lui sẽ lùi về 1 bước phía trước, và tìm kiếm 1 đường đi khác có thể sảy ra.....ta trừ đi biến đếm 1 đơn vị và gắn lại đỉnh đó là chưa đi qua
		}
	}
}

//Hàm hiển thị đường đi
void induongdi()
{
	for(int i = 0;i<dem2; i++) cout<<c[i]<<" ";
}
int main()
{
  cout<<"nhap so dinh: "; cin>>n;
	cout<<"Nhap ma tran do thi: \n";
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			 cin>>a[i][j];
 	cout<<"Ma tran do thi: \n";
	for(int i=0;i<n;i++)
	{
	 for(int j=0;j<n;j++)
	 cout<<a[i][j]<<"  "; cout<<endl;
	}
	cout<<"Nhap dinh u "; cin>>u;
	cout<<"Nhap dinh v "; cin>>v;
	b[0]=u;
	duongdidainhat(u);
	if(tt) induongdi(); else cout<<"Kg ton tai duong di tu u toi v";
	
}

Bạn tự chạy thử chương trình để xem kết quả nhé, và có thể bạn sẽ quên ma trận đồ thị là thế nào thì xem lại bảng bên dưới này nhé!.

Tìm hiểu thuật toán vét cạn trong lập trình

Cảm ơn bạn đã đọc bài viết chúc bạn học tốt!

[Xem tất cả bài viết chủ đề C/C++ tại đây]

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x