.:: CODE SNIPPET ::.

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

Áp dụng giải thuật A* cho bài toán Tacanh


Để áp dụng giải thuật A* cho bài toán Tacanh trước tiên cần nắm rõ về giải thuật A* đã nhá.

Một trình trạng nào đó của trò chơi Tacanh thì có thể đi đến đích hay là không. Nó phụ thuộc vào chuyện mình chọn đích cho nó. Đích của một tình trạng có thể là một trong hai trường hợp sau:

Đích I



Đích II

Ở đây, mình chọn đích là trường hợp II.

+ Xác định đích
Để biết một trạng thái sẽ dẫn đến đích hay không, mình dùng công thức sau:
N = Tổng số ô số nhỏ hơn giá trị ô hiện tại và đứng sau nó.
Khi đó xét giá trị của N:
+ Nếu N lẻ thì trạng thái đích của ô Tacanh hiện tại là trạng thái I.
+ Nếu N chẳn thì trạng thái đích của ô Tacanh hiện tại là trạng thái II.

Ví dụ:
Ta có bài toán Tacanh như sau:

-Xét ô 1: có tổng số 1 ô có giá trị nhỏ hơn giá trị của ô hiện tại đang xét là 2.
-Xét ô 2: có 6 ô có giá trị nhỏ hơn 8.
-Xét ô thứ 3: có 1 ô.
…..
-Xét ô 9: có 0 ô.
Như vậy: N = 1 + 6 + 1 + 0 + 2 + 0 + 1 + 0 = 12
Vậy trạng thái cuối cùng của ô số Tacanh này là II.
Chương trình dùng một mảng hai chiều để lưu một trạng thái của trò chơi. Mỗi trạng thái đó sẽ còn có các thuộc tính khác như:
• Chi phí đi từ trạng thái khởi đầu đến trạng thái hiện tại.
• Chỉ số ước lượng Heuristic, là chi phí để đi đến đích từ trạng thái đó.
• Chỉ số f là tổng hai chi phí bên trên.
• Và trạng thái cha của trạng thái hiện tại.
Khi một trạng thái được tạo ra thì các chỉ số phía trên cũng được tính toán là gán vào cho trạng thái. Bên cạnh đó, thì khi trạng thái thay đổi, thì các chỉ số cũng được tính toán hoặc xử lý lại cho phù hợp.
Chương trình xây dựng lớp PuzzlGame để xử lý trò chơi và đưa ra một danh sách chứa các trạng thái để trò chơi có thể đi đến đích.
Quan trọng nhất của chương trình là hàm xử lý thuật toán A*.

public int GenerateNext() {
			int g = 0;
			int stop = 0;

			while (lstOPEN.size() > 0) {
				stop++;
				int smallestPos = getTheSmallestElement();
				if (smallestPos == -1) {
					return 0;
				}
				StatusElement s0 = lstOPEN.get(smallestPos);
				lstOPEN.remove(smallestPos);
				g = s0.getG();

				if (isExistStatusCLOSE(s0) == -1)
					lstCLOSE.add(s0);
				if (s0.getH() == 0) {
					System.out.print("H=0=> ket thuc");
					break;
				}
				if (_numCols % 2 == 1) {
					if (N(s0.getArrNumber()) % 2 == 1) {
						WriteText("Trang thai ko di duoc den dich", 1);
						return 0;
					}
				}
				if (stop == maxStep) {

					WriteText("Tim duong qua lau", 1);
					TraceBack();
					return 0;
				}
				if (isWin(s0)) {
					return 1;
				}
				g++;
				// WriteText("Cac trang thai co the di", 1);
				for (int i = 0; i < s0.getArrNumber().length; i++) {
					if (s0.isValidMove(i)) {
						Integer[] tamArray = new Integer[s0.getArrNumber().length];
						System.arraycopy(s0.getArrNumber(), 0, tamArray, 0,
								s0.getArrNumber().length);
						swapPieces(tamArray, i);
						StatusElement nextSE = new StatusElement(tamArray, g,
								s0);
						int posO = isExistStatusOPEN(nextSE);
						int posC = isExistStatusCLOSE(nextSE);
						if (posO == -1 && posC == -1) {
							this.InsertIntoOPEN(nextSE);
						}
					}
				}
			}
			TraceBack();//Lần lại các bước đi trong danh sách CLOSE
			WriteText("So buoc di chuyen:" + lstEND.size(), 1);
			isPlaying = 1;
			return 1;
		}
	}
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: