.:: CODE SNIPPET ::.

"Your time is limited, so don't waste it living someone else's life"

Áp dụng tìm kiếm Heuristic vào bài toán Mã Đi Tuần


Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau:Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất)
Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người.Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau:
+ Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
+ Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
+ Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.
Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Đó là các hàm đánh già thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải.
Hàm ước lượng trong thuật toán Heuristic

/**
	 * Hàm ước lượng xem nên lựa chọn vị trí nào để đi tiếp theo từ vị trí
	 * hiện tại (qO) Hàm được tính như sau:
	 * B1:Từ vị trí hiện tại ta xác
	 * định các vị trí có thể đi đến của quân mã các vị trí này được lưu
	 * trong mảng avaiPos[]
	 * B2:Xét lần lượt các vị trí đã có trong B1 tính
	 * số ô phải bỏ qua của vị trí từng vị trí đó vị trí nào có số ô phải bỏ
	 * qua ít nhất sẽ là vị trí được chọn để đi Hàm trả về -1 khi không xác
	 * định được vị trí nào để đi tiếp
	 */
	private int BestNextStep(OneSquare qO) {
		int avaiPos[];
		avaiPos = qO.GetAvailablePositions();
		int k = 8;
		int idx = -1;
		int e = 0;
		for (int i = 0; i < avaiPos.length; i++) {
			if (this.sq[avaiPos[i]].visited)
				continue;
			e = NumOfOmitedSquare(this.sq[avaiPos[i]], avaiPos[i]);
			if ((e > 0) && (e < k)) {
				k = e;
				idx = i;
			}
		}
		if (idx == -1)
			return idx;
		else
			return avaiPos[idx];
	}

Và một hàm quan trọng là hàm tìm đường đi cho quân hậu trong thuật toán

int[] FindTheWay(int startSquare) {
		int i = 0;
		int path[];
		path = new int[64];
		for (i = 0; i < 64; i++){
			sq[i].visited = false;
		}
		sq[startSquare - 1].visited = true;
		int nxt[];
		int n = -1;
		int moves = 0;
		int currentSquare = startSquare - 1;
		path[currentSquare] = moves + 1;
		// Tìm đường đi theo thứ tự 1,2,... lưu vào mảng path[]
		for (i = 0; i < 64; i++) {
			n = BestNextStep(sq[currentSquare]);
			if (n < 0)
				break;
			sq[n].visited = true;
			moves++;
			currentSquare = n;
			path[currentSquare] = moves + 1;
		}
		// Tìm đến những ô chưa được đi đến (unvisited)
		int nUnvisited = 0;
		int unvisited = -1;
		for (i = 0; i < 64; i++) {
			if (!sq[i].visited) {
				unvisited = i;
				nUnvisited++;
			}
		}
		if (nUnvisited == 1) {
			nxt = sq[currentSquare].GetAvailablePositions();
			for (i = 0; i < nxt.length; i++) {
				if (nxt[i] == unvisited) {
					path[unvisited] = moves + 2;
					break;
				}
			}
		} else {
			return null;
		}
		return path;
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: