.:: CODE SNIPPET ::.

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

Category Archives: Algorithm

Searching algorithm DFS


Depth first search (DFS) is a searching algorithm used in searching maze.
Prerequisites:
A maze is also a graph with: a vertex equals a intersection, and edge is passage. (So, we should have some basic knowledge about graph, this will is be stored in some next posts)
The goal of using this algorithm in maze is explore all the connected intersections with a start point in the maze.
Algorithm for DFS:
+ Mark the visited intersection by a nut on the string.
+ Enter any passage related with that intersection that have never visit before and unroll the ball of string to mark that passage.
+ Retrace steps when no unvisited options.
Read more of this post

Giải quyết bài 8 quân hậu bằng giải thuật Min-Max


1. Giải thuật
Ứng dụng giải thuật Min-Max
Thuật toán Minmax hay còn gọi là Minimax là một thuật toán dùng trong tìm kiếm có đối thủ. Cải tiến của thuật toán này là thuật toán cắt tỉa Alpha-Beta (Alpha – Beta Pruning) rất hay được sử dụng làm chiến lược cho tìm kiếm nước đi trong không gian tìm kiếm của trò chơi có tính chất đối kháng (vd cờ Tướng, cờ Vua, cờ caro… ). Nói một cách dễ hiểu, thì ý nghĩa của thuật toán này bạn có thể hiểu một cách đơn giản như sau: Giả sử bạn đang đánh cờ với máy, thì cả bàn cờ sẽ được biểu diễn trong một cái gọi là không gian trạng thái (KGTT) – bạn có thể hình dung KGTT chính là cách mà máy tính biểu diễn bàn cờ thực lên bộ nhớ máy tính. Với mỗi nước đi (mỗi thay đổi) sẽ làm cho KGTT của bàn cờ thay đổi thành một KGTT mới. Như vậy, đến nước đi của máy. Chiến lược tìm kiếm nước đi Minimax sẽ được sử dụng để làm sao tìm ra nước đi tốt nhất cho máy. Để có được nước đi tốt thì cần có một sự lượng giá tốt – là kết quả từ một hàm lượng giá (tức là cách đánh giá, như lúc mình tính ở trong đầu í == độ uyên thâm). Độ sâu (depth) là số nước mà máy sẽ tính trước. Như vậy giả sử với độ sâu là 4 thì sẽ tìm với tầm nhìn là 4 nước đi. Nút có kết quả lượng giá cao nhất ở mức gốc (mức 0) sẽ được chọn để đi (trong hình ở mức 0 chỉ có 1nút thôi, nên bạn hình dung là như vậy).


Mức 0, 2, 4 là lượt đi của máy – mức MAX (kết quả lượng giá càng lớn càng tốt).
Mức 1, 3 là lượt đi của người – mức MIN (kết quả lượng giá càng nhỏ càng tốt).
2. Áp dụng giải thuật Minmax vào bài toán 8 quân hậu
Read more of this post

Á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 Read more of this post

Áp dụng giải thuật AKT vào bài toán tháp Hà Nội


Chương trình áp dụng giải thuật AKT, mội trạng thái được mô tả bằng mảng hai chiều. Để ước lượng đối với trạng thái của trò chơi, ta sẽ tính trạng thái của cột thứ ba. Tại một trạng thái, thì số bước để đưa cột thứ ba về đúng như trạng thái đích là bao nhiêu? Ta thấy tại một trạng thái của cột thứ ba thì có một số đĩa nằm đúng vị trí của nó, và cũng có một số đĩa không nằm đúng vị trí của nó. Số lượt để ta có thể đưa cột thứ ba về đúng trạng thái đích bằng tổng số lượt mang những đĩa không đúng vị trí ra khỏi cột thứ ba cộng với số lượt mang những đĩa còn lại vào cho đúng vị trí của nó trong cột thứ ba.
Một số hàm chính trong chương trình:

 int GetNumberOfDiskOfPillar(Integer[] pPillar) Tính tổng số đĩa hiện có trong một cột nào đó.
 int GetRightPositions(Integer[] pPillar) Tính số đĩa nằm đúng vị trí trong một cột nào đó
 void H() // Là hàm tri thức bổ sung có giá trị bằng số vị trí sai trên cột thứ 3.
 Void Generate() Tính toán các bước đi cho bài toán Áp dụng giải thuật AKT

Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó.
Mặc dù không biết được chính xác cần bao nhiêu lần di chuyển, có thể có một vài kết quả tiệm cận. Có một “lời giải được coi như tối ưu” có thể áp dụng một cách đệ quy để tìm một lời giải–xem giải thích cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer. Read more of this post

Á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


Read more of this post

%d bloggers like this: