Chiến lược giải quyết bài toán tìm kiếm bằng mô hình hướng đối tượng.

1. Lời nói đầu

Sau khi kết thúc bài tập lớn AI, mình xin chia sẻ một số kinh nghiệm để giải quyết vấn đề tìm kiếm được tổng quát hơn.

2. Giới thiệu vấn đề

Bài toán tìm kiếm là một bài toán kinh điển và là một vấn đề cơ bản trong lĩnh vực trí tuệ nhân tạo (AI), để giải quyết bài toán này cho từng vấn đề cụ thể thì không khó, nhưng sẽ rất tốn nhiều thời gian nếu phải hiện thực thuật toán tìm kiếm để giải quyết nhiều vấn đề.

Thực ra thì mọi vấn đề có thể giải quyết bằng tìm kiếm trong AI đều có đặc điểm cơ bản như nhau.

Trong bài viết này mình sẽ tổng quát hoá bài toán tìm kiếm trong AI bằng mô hình hướng đối tượng, tuy nó sẽ tốn nhiều chi phí khi mình chỉ cần giải quyết một bài toán cụ thể, nhưng trong tình huống cần giải quyết nhiều bài toán, cách tiếp cận này sẽ rất hiệu quả! 😀

3. Một số vấn đề cơ bản

Bản chất của các bài toán tìm kiếm đều là từ một trạng thái làm sao sinh được các trạng thái tiếp theo và rồi lần lượt duyệt chúng, rồi lại sinh rồi lại duyệt, cho tới khi tìm được kết quả cần tìm.

Vậy ở đây chúng ta có 2 vấn đề cơ bản là:

  • làm sao để sinh được các trạng thái tiếp theo một cách tổng quát.
  • làm sao để so sánh 2 trạng thái có giống nhau hay không?

4. Vấn đề phát sinh

Ngoài ra mình gợi ý còn một số vấn đề phát sinh như sau:

  • làm sao để in trạng thái đó ra?
  • vấn đề lưu vết?
  • vấn đề tính toán hàm heuristic trong bài toán hill climbing và best-first search

Như vậy chắc cũng đủ để giải quyết các bài toán tìm kiếm cho các vấn đề thông dụng rồi 😀

5. Hiện thực

Để giải quyết và hiện thực các vấn đề trên, chúng ta sử dụng tính chất kế thừa các lớp trừu tượng (Abstract class) trong các ngôn ngữ hướng đối tượng.

public abstract class State {
	// for tracing purpose
	State parent;
	// to compare a state to another one
	public abstract boolean equals(State aState);
	// to print State
	public abstract void printState();
	// get all possible next states
	public abstract List getNextState();
	// for HillClibing and Best-first search
	public abstract int heuristic(State goal);
}

Ở đây ý tưởng tổng quát cho vấn đề sinh các trạng thái tiếp theo là nó sẽ trả về một danh sách các trạng thái tiếp theo của nó (còn cách nào khác?)

Hàm heuristic của một trạng thái thường được tính theo trạng thái đích.

Một vấn đề cụ thể như N-puzzle hay Tháp Hà Nội hay bất kì vấn đề nào khác chỉ cần kế thừa lớp State này và hiện thực đủ các hàm là có thể giải được bằng các phương pháp tìm kiếm thông dụng rồi!

Vấn đề còn lại là của thuật toán tìm kiếm, một thuật toán tìm kiếm sẽ có giao diện như sau:

public static void abcSearch(State start, State goal) {
	// 1. trạng thái hiện tại là trạng thái bắt đầu (start)
	// 2. trong khi trạng thái hiện tại có thể sinh ra các trạng thái khác, nếu không nhảy tới bước 6
	// 3. gán trạng thái hiện tại bằng một trạng thái con
	// 4. nếu trạng thái hiện tại là đích (goal) thì tìm kiếm thành công (có thể truy vết nếu cần thiết)
	// 5. quay lại bước 2 
	// 6. nếu không thể tiếp tục sinh trạng thái nữa thì bài toán tìm kiếm thât bại
}

Về vấn đề thuật toán tìm kiếm cụ thể, các bạn phải tự tìm hiểu, có thể tham khảo 2 đoạn mã giả sau trên wikipedia

1  procedure BFS(G,v) is
2      create a queue Q
3      create a vector set V
4      enqueue v onto Q
5      add v to V
6      while Q is not empty loop
7         t ← Q.dequeue()
8         if t is what we are looking for then
9            return t
10        end if
11        for all edges e in G.adjacentEdges(t) loop
12           u ← G.adjacentVertex(t,e)
13           if u is not in V then
14               add u to V
15               enqueue u onto Q
16           end if
17        end loop
18     end loop
19     return none
20 end BFS
1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v ← S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Như vậy chúng ta đã giải quyết xong một số vấn đề cơ bản và phát sinh trong bài toán tìm kiếm tổng quát, qua phần sau mình sẽ lấy một ví dụ cụ thể, để các bạn có thể dễ dàng hiểu và áp dụng hơn.

6. Ví dụ

Trong ví dụ này mình sẽ giải quyết bài toán tu sĩ và con quỷ (Missionaries and cannibals problem), chắc hẳn đây là một bài toán khá quen thuộc với một người, một phần vì nó là bài toán kinh điển, với lại chúng ta cũng đã giải bài này trong lab2 AI

public class Missionaries extends State {
	int M1, C1; // number of Missionaries and Cannibals in side 1
	int M2, C2; // number of Missionaries and Cannibals in side 2
	int boat; // side of the boat

	// initial and creating a state
	public Missionaries(int m1, int c1, int m2, int c2, int b) {
		M1 = m1;
		M2 = m2;
		C1 = c1;
		C2 = c2;
		boat = b;
	}
	// compare 2 state is equals?
	public boolean equals(State obj) {
		Missionaries aState = (Missionaries) obj;
		return aState.M1 == M1 && aState.M2 == M2 && aState.C1 == C1
				&& aState.C2 == C2 && aState.boat == boat;
	}
	public void printState() {
		// it's up to you (try to make a awesome decorations)
		System.out.println("Blah blah blah!");
	}
	// generate all possible next state
	public LinkedList getNextState() {
		LinkedList result = new LinkedList<>();
		// iterate all rule
		for (int i = 0; i < RULE_COUNT; i++)
			// check if can apply rule
			if (checkRule(i))
				result.add(move(i)); // the apply rule
		return result;
	}
	static final int _1M_FROM1TO2 = 0; // move 1 missionaries form side 1 to 2
	static final int _1C_FROM1TO2 = 1; // move 1 cannibals form side 1 to 2
	static final int _2M_FROM1TO2 = 2; //
	static final int _2C_FROM1TO2 = 3; //
	static final int _MC_FROM1TO2 = 4; //
	static final int _1M_FROM2TO1 = 5; //
	static final int _1C_FROM2TO1 = 6; //
	static final int _2M_FROM2TO1 = 7; //
	static final int _2C_FROM2TO1 = 8; //
 	static final int _MC_FROM2TO1 = 9; //
 	static final int RULE_COUNT = 10;
	// checking rule is valid?
	private boolean checkRule(int rule) {
		switch (rule) {
		case _1M_FROM1TO2:
			if (boat == 1 && ((M1 == 1) || (C1 >= 0 && M1 - 1 >= C1)))
				return true;
			break;
		case _1C_FROM1TO2:
			if (boat == 1 && (C1 >= 1 && (M2 == 0 || M2 >= C2 + 1)))
				return true;
			break;
		case _2M_FROM1TO2:
			if (boat == 1 && ((M1 == 2) || (C1 >= 0 && M1 - 2 >= C1)))
				return true;
			break;
		case _2C_FROM1TO2:
			if (boat == 1 && (C1 >= 2 && (M2 == 0 || M2 >= C2 + 2)))
				return true;
			break;
		case _MC_FROM1TO2:
			if (boat == 1 && (M1 >= 1 && C1 >= 1))
				return true;
			break;
		case _1M_FROM2TO1:
			if (boat == 2 && ((M2 == 1) || (C2 >= 0 && M2 - 1 >= C2)))
				return true;
			break;
		case _1C_FROM2TO1:
			if (boat == 2 && (C2 >= 1 && (M1 == 0 || M1 >= C1 + 1)))
				return true;
			break;
		case _2M_FROM2TO1:
			if (boat == 2 && ((M2 == 2) || (C2 >= 0 && M2 - 2 >= C2)))
				return true;
			break;
		case _2C_FROM2TO1:
			if (boat == 2 && (C2 >= 2 && (M1 == 0 || M1 >= C1 + 2)))
				return true;
			break;
		case _MC_FROM2TO1:
			if (boat == 2 && (M1 >= 2 && C1 >= 2))
				return true;
			break;
		}
		return false;
	}
	// apply rule
	private Missionaries move(int rule) {
		Missionaries nextState = new Missionaries(M1, C1, M2, C2, boat);

		switch (rule) {
		case _1M_FROM1TO2:
			nextState.M1--;
			nextState.M2++;
			nextState.boat = 2;
			break;
		case _1C_FROM1TO2:
			nextState.C1--;
			nextState.C2++;
			nextState.boat = 2;
			break;
		case _2M_FROM1TO2:
			nextState.M1 -= 2;
			nextState.M2 += 2;
			nextState.boat = 2;
			break;
		case _2C_FROM1TO2:
			nextState.C1 -= 2;
			nextState.C2 += 2;
			nextState.boat = 2;
			break;
		case _MC_FROM1TO2:
			nextState.M1--;
			nextState.M2++;
			nextState.C1--;
			nextState.C2++;
			nextState.boat = 2;
			break;
		case _1M_FROM2TO1:
			nextState.M1++;
			nextState.M2--;
			nextState.boat = 1;
			break;
		case _1C_FROM2TO1:
			nextState.C1++;
			nextState.C2--;
			nextState.boat = 1;
			break;
		case _2M_FROM2TO1:
			nextState.M1 += 2;
			nextState.M2 -= 2;
			nextState.boat = 1;
			break;
		case _2C_FROM2TO1:
			nextState.C1 += 2;
			nextState.C2 -= 2;
			nextState.boat = 1;
			break;
		case _MC_FROM2TO1:
			nextState.M1++;
			nextState.M2--;
			nextState.C1++;
			nextState.C2--;
			nextState.boat = 1;
			break;
		}
		return nextState;
	}
	public int heuristic(State goal) {
		// it's take a long time to design or re-search a admissible heuristic
		// function
		if (this.equals(goal))
			return 0;
		else
			return Integer.MAX_VALUE;
	}
}

Ở bài toán trên, mình biểu diễn các luật thành các số liên tục từ 0 tới 9 để dễ dàng áp dụng luật và đưa vào danh sách các trạng thái tiếp theo hơn.

Bây giờ nếu muốn áp dụng giải thuật tìm kiếm lên bài toán này, chỉ cần gọi:

absSearch(new Missionaries(3,3,0,0,1), new Missionaries(0,0,3,3,2));

Bây giờ thì việc áp dụng lớp State này để hiện thực các bài toán khác là một chuyện thật dễ dàng phải không nào 🙂

Lưu ý: bài toán trên chỉ mang tính ví dụ, mình chưa kiểm tra tính đúng đắn của nó và không chịu bất kì trách nhiệm nào về sai sót của nó!

7. Lưu ý

Lớp trừu tượng State chỉ mang tính chất tham khảo, có thể chưa thiết kế được tốt!

Bài viết có tham khảo một số thông tin và thuật toán trên Wikipedia, một số kỹ thuật trên Stack Overflow.

8. Kết luận

Bài toán tìm kiếm là một bài toán cơ bản và cốt lõi của AI, để giải quyết bài toán này cho nhiều vấn đề sẽ rất là khó khăn, tốn thời gian và dễ sai sót, dễ mất tính nhất quán, thống nhất của thuật toán giữa các vấn đề cần giải quyết, tốn thời gian bảo trì.

Nhưng nhờ vào tính chất thừa kế của ngôn ngữ hướng đối tượng chúng ta có thể tổng quát hoá bài toán tìm kiếm lên thành bài toán tổng quát. chỉ cần hiện thực một số phương thức chung là có thể áp dụng thuật toán tìm kiếm. Ngoài ra các thuật toán tìm kiếm chỉ cần hiện thực 1 lần cho bài toán tổng quát, tăng tính thống nhất, dễ sửa lỗi khi có sai sót…

-ANKRA-

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