01/10/2018, 15:05

Vấn đề Đệ Quy Quay Lui

  • Đây là một khái niệm và vấn đề khá mới mẻ với mình, thật sự thấy cũng khá thú vị khi nhìn đọc vào những dòng khái niệm hay đoạn code nói tới nó.
  • Tuy nhiên, sau một ngày tìm hiểu mình mới cảm thấu được độ phức tạp của nó, mình thấy để hiểu được và viết được thuật giải QUAY LUI thì cần phải suy nghĩ và có tư duy nhiều.
  • Cảm thấy khó là vậy, nhưng mình vẫn rất muốn theo đuổi nó, vì mình có thể nhìn được tiềm năng của loại thuật này.
  • Bạn nào có ý tốt, có thể chia sẻ kinh nghiêm cũng như tài liệu về vấn đề trên để mình và mn có thể tham khảo được không
Nguyễn Phú Thành viết 17:10 ngày 01/10/2018

thực ra đệ quy giúp giải bài toán dễ hơn và ko phức tạp lắm đâu,bài tập về b-cây sẽ cho bạn rất nhiều kiến thức về đệ quy đấy và hầu như bài nào cũng dùng đệ quy cả ? có thể duyệt cây = cách ko dùng đệ quy nhưng nó phức tạp hơn nhiều,

HelloWorld viết 17:19 ngày 01/10/2018

mình có thể nhìn được tiềm năng của loại thuật này

Theo mình
quay lui vét cạn là thuật toán duyệt trâu (trâu bò)
mà người ta thường nói ngu như bò
quay lui vét cạn không có tiềm năng với không gian trạng thái hoặc không gian bài toán lớn. Nếu như không sử dụng nhánh cận, các heuristic thì backtracking không có tiềm năng gì cả. Chỉ thử rồi quay lại thử cái chưa thử cho đến khi tìm ra nghiệm cần tìm hoặc tìm ra tất cả các nghiệm thôi.

Hello World viết 17:10 ngày 01/10/2018

Đúng là v, nhưng theo mình nghĩ nếu hiểu đc vấn đề này thì sau này các bài toán đòi hỏi độ trừu tượng cao ta sẽ dễ viết thuật hơn …

Hello World viết 17:12 ngày 01/10/2018

@hell6w9rld bn add face mình được không
Chung tên kìa ^^

HelloWorld viết 17:07 ngày 01/10/2018

Mình mới ngừng dùng fb xong. Hồi trước có dùng vì bảng tin toàn là tin người mình quen biết. Giờ bảng tin cứ hiển thị tào lao đâu đâu, quảng cáo, rồi tin của bạn bè của bạn bè. Thấy rác quá nên không dùng nữa

Hello World viết 17:09 ngày 01/10/2018

Oh tiếc ghê

Mai Anh Dũng viết 17:05 ngày 01/10/2018

Đệ quy hay mà, sao lại nó ngu như bò :’(

HelloWorld viết 17:10 ngày 01/10/2018

bạn ấy đang bàn về quay lui vét cạn sử dụng đệ quy ấy anh, còn đệ quy thì e biết hay ở chỗ giúp làm đơn giản hóa bài toán
nếu quay lui vét cạn mà không có dùng thêm cái gì thì là phương án tệ nhất nên e ví là ngu như bò ấy ạ mà nó cũng mang tiếng là duyệt trâu mà anh

Hello World viết 17:06 ngày 01/10/2018

@ltd vấn đề này hấp dẫn mà khó code quá anh ^^

Tao Không Ngu. viết 17:19 ngày 01/10/2018

Hi Hello World.
Bạn chỉ cần hiểu hai điểm quan trọng là đệ quy và quay lui là được.

#include <iostream>
#include <string>

#define MAX_COUNT 8

char src[MAX_COUNT] = {'t', 'b', 'k', 'd', 'n', 'h', 'g', 'u'};
char permutation[MAX_COUNT];
int state[MAX_COUNT] = {0, 0, 0, 0, 0, 0, 0, 0}; //Gia trị khởi tạo.

void Permutation(int key) { //Hàm đệ quy.
	if(key == MAX_COUNT) { //Điều kiện suy biến của hàm đệ quy.
		for(int index = 0; index < MAX_COUNT; index++) {
			std::cout << permutation[index];
		}
		std::cout << std::endl;
		return;
	}
	for(int index = 0; index < MAX_COUNT; index++) { //Đê xuất một khả năng.
		if(!state[index]) {
			state[index] = 1; //Cập nhật trạng thái.
			permutation[key] = src[index]; //Cập nhật trạng thái.
			Permutation(key + 1); //Gọi đệ quy.
			state[index] = 0; //Khôi phục lại trạng thái - Quy lui.
		}
	}
}

int main(int argc, char **argv) {
	Permutation(0);
return 0;
}
Hello World viết 17:05 ngày 01/10/2018

thks bn nhiều nha

Bài liên quan
0