Tiểu luận Ứng dụng một số nguyên tắc sáng tạo để giải quyết vấn đề bài toán trong Tin học và ứng dụng giải bài Toán 8 số trên máy tính

 ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH 
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG 
----------------- 
BÀI THU HOẠCH MÔN HỌC 
PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC 
ĐỀ TÀI 
ỨNG DỤNG MỘT SỐ NGUYÊN TẮC SÁNG TẠO ĐỂ GIẢI QUYẾT 
VẤN ĐỀ BÀI TOÁN TRONG TIN HỌC VÀ ỨNG DỤNG GIẢI BÀI 
TOÁN 8 SỐ TRÊN MÁY TÍNH 
 GVHD: GS.TSKH. Hoàng Văn Kiếm 
 Học viên thực hiện: Huỳnh Thị Mỹ Hồng 
 Mã số học viên: CH1101086 
TP.HCM, năm 2012
MỤC LỤC 
Trang 
MỞ ĐẦU ....................................................................................................... 1 
CHƯƠNG 1: VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI 
QUYẾT .......................................................................................................... 4 
1.1. Vấn đề khoa học ...................................................................................... 4 
1.1.1. Khái niệm ............................................................................................. 4 
1.1.2. Phân loại ............................................................................................... 4 
1.1.3. Các tình huống vấn đề .......................................................................... 5 
1.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế .... 7 
1.2.1. Vepol .................................................................................................... 7 
1.2.2. Phương pháp giải quyết vấn đề theo khoa học về phát minh, sáng chế . 8 
1.2.3. Một số thủ thuật, nguyên tắc về phát minh, sáng tạo ............................. 9 
CHƯƠNG 2: CÁC PHƯƠNG PHÁP NGHIÊN CỨU, GIẢI QUYẾT VẤN 
ĐỀ BÀI TOÁN TRONG TIN HỌC ............................................................. 21 
2.1. Mục đích nghiên cứu giải quyết bài toán trong tin học .......................... 21 
2.2. Các phương pháp thường dùng để giải quyết vấn đề bài toán trên máy 
tính ............................................................................................................... 21 
2.2.1. Phương pháp trực tiếp......................................................................... 21 
2.2.2. Phương pháp gián tiếp hoặc tìm kiếm lời giải ..................................... 24 
2.2.3. Các phương pháp Heuristic................................................................. 25 
2.2.4. Các phương pháp trí tuệ nhân tạo ....................................................... 25 
CHƯƠNG 3: LÝ THIẾT TRÒ CHƠI 8 SỐ .................................................. 26 
3.1. Tìm hiểu trò chơi 8 số ............................................................................ 26 
3.1.1. Mục đích giải quyết bài toán 8 số trên máy tính .................................. 26 
3.1.2. Mô tả .................................................................................................. 28 
3.1.3. Xác định trạng thái đích ...................................................................... 29 
3.2. Thuật toán tìm đáp án ............................................................................ 30 
3.2.1. Giới thiệu về A* ................................................................................. 30 
3.2.2. Chi tiết thuật toán A*.......................................................................... 32 
3.3. Cài đặt giải thuật ................................................................................... 38 
3.3.1. Cài đặt giải thuật................................................................................. 38 
3.3.2. Hướng dẩn sử dụng ............................................................................ 38 
TÀI LIỆU THAM KHẢO ............................................................................ 39
1 
MỞ ĐẦU 
Tất cả chúng ta công nhận rằng một nước muốn giàu có hùng mạnh 
không những chúng ta có nhiều tài nguyên khoáng sản, có nhiều ruộng đất, 
tiền của mà điều quan trọng là để đất nước ta phát triển ta phải có nhiều 
người tài giỏi để phát hiện ra cái hay cái mới nâng cao dần sự hoàn thiện để 
sự giàu có của con người và sự phồn vinh của xã hội. Như ta đã biết Việt Nam 
đang gia nhập với các nước trên thế giới. Nếu con ngưởi Việt Nam chỉ có cần 
cù mà không thông minh và nếu chúng ta đi theo lối mòn kế thừa những cái 
có sẵn thì chúng ta rất dễ bị lạc hậu. 
Tôi xin kể một câu chuyện như sau: 
Ngày xưa, có một anh thanh niên khỏe mạnh ít học nhưng có sức khỏe 
rất cường tráng. Một ngày nọ anh đi tìm việc làm và được một ông chủ khai 
thác gỗ nhận vào làm công việc khai thác gỗ. Anh thanh niên rất mừng rỡ. 
Anh được ông chủ phát cho một cái rìu. 
 Hôm làm việc đầu tiên, anh thanh niên hăng hái vào rừng khai thác gỗ. 
Anh khai thác được 14 góc gỗ. Ông chủ rất hài lòng và khen anh ta. Anh 
thanh niên rất vui mừng và nghỉ thầm ngày mai sẽ cố gắng hơn nữa. 
Ngày làm việc thứ hai, anh thanh niên thức sớm hơn ngày đầu và làm 
việc rất vất vả đến chiều. Anh khai thác được 12 góc gỗ. Để động viên được 
tinh thần làm việc của anh ta ông chủ vẫn khen anh ta. Anh thanh niên thấy 
được lòng tốt của ông chủ và nguyện với lòng ngày mai sẽ cố gắng hơn ngày 
hôm trước: 
Ngày làm việc thứ ba, anh thanh niên thức sớm hơn ngày làm việc thứ 
hai và làm việc cả ngày và không hề nghỉ trưa. Kết quả hôm làm việc thứ ba 
anh đã cố gắng làm việc hơn hai ngày đầu nhưng kết quả chỉ được 11 góc gỗ. 
Anh thanh niên rất buồn và nói với ông chủ rằng: 
2 
Thưa ông tôi rất cố gắng hết sức nhưng kết quả ngày càng không tăng 
mà có xu hướng giảm. 
Ông chủ trả lời: anh là một người rất chăm chỉ làm việc nhưng anh 
không biết nâng cấp dụng cụ lao động. Ví dụ cái rìu anh ngày đầu nó rất bén 
nên anh khai thác được nhiều gỗ nhưng đến một ngày nào đó nó không còn 
bèn nữa, đó là nói đến thời gian gần, nếu nói đến một thời điểm xa hơn nó 
không còn phù hợp nữa mà phải thay bằng một dụng cụ khác. Ông chủ nói 
tiếp, ngoài việc nâng cấp dụng cụ lao động anh còn phải biết sáng tạo trong 
lao động, anh phải suy nghĩ làm thế nào để tốn ít sức lao động và công việc 
đạt được nhiều hiệu quả hơn. 
Từ câu chuyện của anh thanh niên ta rút ra được bài học là nghiên cứu 
sáng tạo ra cái mới là rất cần thiết cho mỗi con người chúng ta nói riêng và sự 
phát triển của xã hội nói chung. 
Theo Gaudin, chúng ta không thể bằng lòng với vốn kiến thức quá hạn 
hẹp thu nhận được trong những năm ngồi trên ghế nhà trường, mà phải học 
suốt đời, phải có đủ vốn kiến thức về phương pháp để tự mình học tập, nghiên 
cứu suốt đời. Có người đưa ra định nghĩa về cuộc đời như sau: “Cuộc đời là 
chuỗi đề cần giải quyết và chuỗi quyết định cần phải ra”. Thật vậy mỗi ngày 
chúng ta phải đối mặt biết bao vấn đề cần giải quyết. Câu hỏi đặt ra rằng 
chúng ta phải giải quyết như thế nào để có hiệu quả nhất. Một con người khôn 
ngoan sống lúc nào họ cũng muốn tiến dần đến sự hoàn thiện vì vậy họ luôn 
đầu tư, tìm tòi ra cái hay, cái mới. 
Ngày nay, nghiên cứu khoa học là một việc làm hết sức cần thiết đối với 
mỗi chúng ta và nó trở thành một hoạt động sôi nổi trên thế giới. Tham gia 
nghiên cứu khoa học được xem là cống hiến lớn của nhân loại cho khoa học 
và xã hội vì tất cả các cơ quan nhà nước luôn luôn đãi ngộ đối với những 
người đã cống hiến chất xám mình vào nghiên cứu khoa học. Để nghiên cứu 
3 
khoa học được thành con người phải có một tri thức nhất định và nhiều tâm 
quyến để cần nghiên cứu sáng tạo. Hiện nay, công nghệ thông tin là một 
ngành mũi nhọn, nó là chìa khóa để mở cửa cho tư duy và sáng tạo của con 
người. 
Qua bài thu hoạch này, em sẽ trình bày các suy nghĩ chủ quan của mình 
về các thủ thuật, nguyên tắc về phát minh sáng tạo trong nghiên cứu khoa học 
em cảm thấy ấn tượng nhất để có thể áp dụng vào trong đời sống hằng ngày 
và trong ngành môn tin học của mình và cách giải bài toán trên máy tính. Qua 
đây, em cũng xin được gửi lời cảm ơn sâu sắc đến GS.TSKH. Hoàng Văn 
Kiếm, người đã tận tâm truyền đạt những kiến thức nền tảng cơ bản cho 
chúng em về môn học “Phương pháp nhiên cứu khoa học trong tin học”. Bên 
cạnh đó cũng không thể không nhắc đến công lao trợ giúp không mệt mỏi của 
các chuyên gia cố vấn qua mạng thuộc Trung tâm phát triển CNTT – ĐH 
Quốc gia TP.HCM và toàn thể các bạn bè học viên trong lớp. 
4 
CHƯƠNG 1 
VẤN ĐỀ KHOA HỌC VÀ CÁC PHƯƠNG PHÁP GIẢI QUYẾT 
1.1. Vấn đề khoa học 
1.1.1. Khái niệm 
Vấn đề khoa học (scientific problem) cũng được gọi là vấn đề nghiên 
cứu (research problem) hoặc câu hỏi nghiên cứu là câu hỏi được đặt ra khi 
người nghiên cứu đứng trước mâu thuẫn giữa tính hạn chế của tri thức khoa 
học hiện có với yêu cầu phát triển tri thức đó ở trình độ cao hơn. 
1.1.2. Phân loại 
Nghiên cứu khoa học luôn tồn tại hai vấn đề: 
- Vấn đề về bản chất sự vật đang tìm kiếm. 
- Vấn đề về phương pháp nghiên cứu để làm sáng tỏ về lý thuyết và thực 
tiễn nhưng vấn đề thuộc lớp thứ nhất. 
Cách giải quyết vấn đề khoa học như thế nào? 
Giải quyết vấn đề khoa học. Đây là mong muốn của những người muốn 
bước vào con đường khoa học. Như ta đã biết có rất nhiều ứng dụng vi mô từ 
phát minh sáng chế khoa học thành công trong cuộc sống. 
Một người muốn phát minh sáng tạo cần có 3 yếu tố cần thiết sau: 
- Kiến thức đủ để sáng tạo: Người phát minh sáng tạo cần có một kiến 
thức nhất định phù hợp với công trình nghiên cứu. Một người có kiến thức 
phổ thông đã biết sáng tạo khoa học nhưng mỗi người sáng tạo như thế nào? 
mức độ nào? là hoàn toàn khác nhau. 
- Môi trường đòi hỏi sáng tạo: Môi trường ảnh hưởng rất lớn đến đời 
sống của con người kể cả vấn đề sáng tạo của con người. Sống trong môi 
trường luôn đòi hỏi con người sáng tạo là môi trường luôn luôn đổi mới để 
hoàn thiện và phát triển. 
5 
- Khát vọng sáng tạo của con người: Có lẻ đây là vấn đề rất quan trọng 
để phát minh sáng tạo. Phát minh sáng tạo đòi hỏi con người phải có lòng 
ham mê, ốc sáng tạo và vượt khó, kiên trì bởi có rất nhiều nhà khoa học phát 
minh ra một cái mới họ phải thử đi thử lại rất nhiều có khi phải mất hàng chục 
năm. 
1.1.3. Các tình huống vấn đề 
Có ba tình huống: Có vấn đề, không có vấn đề, giả vấn đề được cho 
trong hình dưới đây: 
Các phương pháp phát hiện vấn đề khoa học. Có 6 phương pháp: 
1) Tìm những kẻ hở, phát hiện những vấn đề mới 
2) Tìm những bất đồng 
3) Nghĩ ngược lại quan niệm thông thường 
4) Quan sát những vướng mắc trong thực tiễn 
5) Lắng nghe lời kêu ca phàn nàn 
6) Cảm hứng: những câu hỏi bất chợt xuất hiện khi quan sát sự kiện nào 
đó. 
Một tiếp cận không gian giải quyết vấn đề. 
Ý tưởng Bài toán Mô hình Cách giải 
Bài toán P: Sau khi có ý tưởng, bài toán P được đặt ra nhằm giải quyết 
mục đích cuối cùng là gì? Trong cùng điểm nhìn, cùng một không gian, nếu ta 
P 
Bài toán P 
Điểm nhìn 
Không gian, vấn đề 
6 
thay đổi bài toán thì vấn đề cũng thay đổi nhưng chỉ thay đổi theo mục đích 
yêu cầu của bài toán. 
Ví dụ: Khi lập trình giải bài toán phương trình bậc 1 nếu cần chuyển 
sang giải phương trình bậc 2 thì bài toán lúc này có khác ta chỉ thay đổi mục 
đích yêu cầu từ bậc 1 sang bậc 2. 
Điểm  ... i đích 
Trạng thái đích có thể có 2 trường hợp có thể xảy ra: 
 và 
Với mỗi trạng thái ban đầu, chỉ tìm được 1 trạng thái đích có thể đạt tới. 
Điều đầu tiên cần phải quan tâm để giải bài toán này là xác định trạng 
thái đích. Trạng thái đích được xác định dựa trên trạng thái ban đầu. 
29 
3.1.3. Xác định trạng thái đích 
Đầu tiên hãy thử tính có bao nhiêu số bé hơn 8 ở sau ô chứa giá trị 8. 
Kết quả nhận được là 6 (những ô màu vàng) 
Làm tương tự như vậy với ô có giá trị 6. Dễ thấy trong 3 ô (4,7,5) có 2 
giá trị nhỏ 6 là 4,5. 
Làm như trên từ ô đầu tiên (2) tới ô cuối cùng (5) và cộng dồn các giá trị 
nhận được: 
N = 1+6+1+0+2+0+1+0=11 
Nếu N là số lẻ thì chúng ta chỉ có thể có đáp án là trạng thái A, ngược lại 
là trạng thái B. 
30 
Trạng thái A 
Trạng thái B 
Chúng ta đã xác định được trạng thái đích cần đạt được, bây giờ chúng 
ta bắt đầu tìm kiếm giải thuật để tìm ra đích. 
Trên thực tế có nhiều giải thuật để tìm ra đích, ở đây tôi chỉ áp dụng 
thuật toán A*. 
3.2. Thuật toán tìm đáp án 
3.2.1. Giới thiệu về A* 
A* là một thuật toán Heuristic dựa trên thuật toán Dijsktra. Thế nên phải 
tìm hiểu kỹ thuật toán Dijsktra trước khi tìm hiểu thuật toán này. 
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan 
Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất 
trong một đồ thị có hướng không có cạnh mang trọng số âm. 
a. Bài toán 
Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và 
một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến 
mỗi đỉnh của đồ thị. Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các 
thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số 
các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). 
Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra 
sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi. Trọng số không âm của 
31 
các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai 
đỉnh đầu mút của chúng. Ví dụ: với 3 đỉnh A, B, C đường đi A-B-C có thể 
ngắn hơn so với đường đi trực tiếp A-C. 
b. Chứng minh 
Ý tưởng của chứng minh như sau: 
Chúng ta sẽ chỉ ra, khi một đỉnh v được bổ sung vào tập S, thì d[v] là giá 
trị của đường đi ngắn nhất từ nguồn s đến v. 
Theo định nghĩa nhãn d, d[v] là giá trị của đường đi ngắn nhất trong các 
đường đi từ nguồn s, qua các đỉnh trong S, rồi theo một cạnh nối trực tiếp u-v 
đến v. 
Giả sử tồn tại một đường đi từ s đến v có giá trị bé hơn d[v]. Như vậy 
trong đường đi, tồn tại đỉnh giữa s và v không thuộc S. Chọn w là đỉnh đầu 
tiên như vậy. 
Đường đi của ta có dạng s - ... - w - ... - v. Nhưng do trọng số các cạnh 
không âm nên đoạn s - ... - w có độ dài không lớn hơn hơn toàn bộ đường đi, 
và do đó có giá trị bé hơn d[v]. 
Mặt khác, do cách chọn w của ta, nên độ dài của đoạn s - ... - w chính là 
d[w]. Như vậy d[w] < d[v], trái với cách chọn đỉnh v. Đây là điều mâu thuẫn. 
Vậy điều giả sử của ta là sai. Ta có điều phải chứng minh. 
Trong khoa học máy tính, A* là một lựa chọn tốt nhất đồ thị tìm kiếm 
thuật toán mà tìm thấy đường dẫn chi phí ít nhất định ban đầu từ một nút tới 
một nút mục tiêu (trong một hoặc nhiều mục tiêu có thể). Nó sử dụng một 
khoảng cách, cộng với chi phí năng Heuristic (thường được ký hiệu là f (x)) 
để xác định thứ tự tìm kiếm thăm nút trong cây. Khoảng cách + giá Heuristic 
là một tổng của hai chức năng: 
- Đường dẫn - chi phí hoạt động, đó là chi phí từ nút bắt đầu đến nút 
hiện tại (thường được ký hiệu là g (x)). 
32 
- Và một “Admissible Heuristic ước lượng” khoảng cách đến mục tiêu 
(thường được ký hiệu là h (x)). 
H(x) là một phần của f (chức năng) x phải là một Admissible Heuristic; 
có nghĩa là, nó không được đánh giá cao khoảng cách đến mục tiêu. Vì thế 
cho một ứng dụng như định tuyến, h(x) có thể đại diện cho khoảng cách 
đường thẳng đến mục tiêu, vì đó là khoảng cách nhỏ nhất có thể giữa hai 
điểm. 
Nếu h đáp ứng các điều kiện bổ sung h x d x, y h y cho cạnh 
mỗi x, y của đồ thị (d nghĩa là chiều dài của cạnh đó) sau đó được gọi là h 
không thay đổi hay nhất quán. Trong trường hợp này A* có thể được thực 
hiện hiệu quả hơn - khoảng nói, nút không cần phải được xử lý nhiều hơn một 
lần (xem đóng đặt dưới đây) - và trong thực tế, A* tương đương với chạy 
thuật toán Dijkstra's với chi phí giảm: 
d'(x, y): = d(x,y) - h(x) + h(y) 
Thuật toán này được mô tả lần đầu vào năm 1968 bởi Peter Hart, Nils 
Nilsson, và Bertram Raphael Thuật toán này đã được khái quát hóa thành một 
thuật toán tìm kiếm Heuristic hai chiều. 
A* là sự lựa chọn phổ biến nhất, bởi vì nó khá linh hoạt và có thể được 
sử dụng trong nhiều hoàn cảnh. 
A* là đồ thị như các thuật toán tìm kiếm khác nhưng khác ở chỗ nó có 
khả năng có thể tìm kiếm một khu vực rộng lớn của bản đồ. Nó giống như 
thuật toán Dijkstra trong đó nó có thể được sử dụng để tìm một con đường 
ngắn nhất. Nó giống như tham lam nhất ở chỗ nó có thể sử dụng một 
Heuristic để hướng dẫn chính nó. 
3.2.2. Chi tiết thuật toán A* 
Giả sử rằng có một người muốn đi từ điểm A tới điểm B. Giả định rằng 
một bức tường ngăn cách hai điểm. Điều này được minh họa bằng hình dưới 
33 
đây, với màu xanh lá cây là một điểm khởi đầu A, và màu đỏ là kết thúc điểm 
B và hình chữ nhật màu xanh là bức tường ở giữa (hình 3.2). 
Hình 3.2 
Ở đây chúng tôi đã phân chia khu vực tìm kiếm thành 1 lưới ô vuông 
như hình vẽ để đơn giản hóa khu vực tìm kiếm, đây là bước đầu tiên. 
Phương pháp này đặc biệt làm giảm diện tích để tìm kiếm một mảng hai 
chiều đơn giản. Mỗi mục trong mảng đó đại diện cho một trong các hình 
vuông trên khu vực tìm kiếm, và tình trạng của nó được ghi lại như di chuyển 
hoặc đứng yên. Đường đi được tìm thấy khi xuất hiện các ô vuông liên tiếp đi 
từ A đến B. 
Các ô vuông trên đường đi gọi là các “nút”. Các nút có thể được đặt ở 
bất cứ đâu trên khu vực tìm kiếm. 
a. Bắt đầu tìm kiếm 
Khi chúng ta đã đơn giản hóa khu vực tìm kiếm và quản lý được các 
“nút”, bước tiếp theo cần làm là tìm kiếm đường đi ngắn nhất từ A đến B, bắt 
đầu từ A, kiểm tra các hình vuông liền kề và tìm kiếm cho đến khi tìm thấy B. 
Bắt đầu tìm kiếm như sau: 
34 
- Bắt đầu từ A, sau đó thêm vào một danh sách mở các hình vuông liền 
kề A. Về cơ bản đây là danh sách các ô vuông cần kiểm tra để tìm ra đường đi 
đến B. 
- Tất cả các hình vuông có thể truy cập hoặc di chuyển giáp với A, hình 
3.1 hoặc các điểm không thuận lợi, thêm chúng vào danh sách mở. A là mốc 
quan trọng để theo dõi đường đi đến B. 
- Chọn 1 điểm vuông trong danh sách mở làm điểm bắt đầu tiếp theo và 
đưa vào “danh sách đóng” khi F là nhỏ nhất. 
Hình dưới đây minh họa cho công việc trên. 
Hình 3.3 
Chìa khóa xác định hình vuông để tìm ra con đường ngắn nhất là 
phương trình sau đây: 
F G H 
Trong đó: 
+ G là chi phí di chuyển để di chuyển từ A đến điểm khởi đầu cho một 
hình vuông trên khu vực tìm kiếm. 
+ H là chi phí ước tính để di chuyển, từ đó đưa ra điểm vuông trên khu 
vực tìm kiếm đến đích cuối cùng. Chúng ta thực sự không biết khoảng cách 
thực tế cho đến khi tìm thấy con đường đi đến B. 
Con đường được tìm thấy khi đi qua nhiều danh sách mở và hình vuông 
được chọn khi F là nhỏ nhất. 
35 
Trong ví dụ này, ta quy ước G=10 với di chuyển ngang, dọc và G=14 
với di chuyển chéo (ta sử dụng 10 và 14 bởi vì khoảng cách thực tế để di 
chuyển theo đường chéo là căn bậc hai của 2, hay khoảng 1,414 lần chi phí di 
chuyển theo chiều ngang hoặc theo chiều dọc). 
H có thể được tính bằng nhiều cách. Ở đây chúng tôi chọn phương pháp 
Manhattan. Với phương pháp này có thể tính được tổng số hình vuông di 
chuyển theo chiều ngang, dọc để đến đích mà không tính đến các chướng ngại 
vật, sau đó nhân tổng đó với 10. 
Hình 3.4 
Tiếp tục tìm kiếm 
Để tiếp tục tìm kiếm chúng ta chọn ra hình vuông có F nhỏ nhất trong 
danh sách mở. So với hình vuông đã chọn, ta làm như sau: 
- Đưa hình vuông được chọn từ danh sách mở vào danh sách đóng. 
- Kiểm tra tất cả các ô vuông kề bỏ qua những hình vuông có trong danh 
sách đóng hoặc không di chuyển (bức tường hình 3.2). Thêm hình vuông vào 
danh sách mở nếu như nó chưa có trong danh sách mở. 
- Nếu một hình vuông liền kề đã được vào danh sách mở, kiểm tra G cho 
hình vuông đó là thấp hơn. Nếu không, không làm bất cứ điều gì. Mặt khác, 
36 
nếu chi phí G của các đường dẫn mới là thấp hơn, thay đổi các vuông kề bên 
vuông lựa chọn. Cuối cùng, tính toán lại cả F và G điểm của hình vuông đó. 
Các bước trên được minh họa bằng hình vẽ dưới đây: 
Hình 3.5 
Hình 3.6 
37 
Hình 3.7 
Cuối cùng ta tìm ra được đường đi từ A→B theo thuật toán A* như hình 
3.8. 
Hình 3.8 
b. Tóm lược thuật toán A* 
Từ giải thích chi tiết bằng ví dụ trên ta tóm lược lại được phương pháp 
A* như sau: 
- Thêm hình vuông bắt đầu (hoặc nút) vào danh sách mở. 
38 
- Lặp lại như sau: 
+ Chọn hình vuông F chi phí thấp nhất trong danh sách mở. 
+ Chuyển nó vào danh sách đóng. 
- Đối với mỗi ô vuông 8 cạnh vuông này. 
- Nếu nó không di chuyển hoặc nếu nó nằm trong danh sách đóng cửa, 
bỏ qua nó. Nếu không làm như sau: 
+ Nếu nó không có trong danh sách mở, thêm nó vào danh sách mở 
Làm cho hiện tại khu vực tìm kiếm chính của hình vuông này bản ghi F, G, H 
và chi phí của nó. 
+ Nếu đó là trong danh sách đã được mở, kiểm tra xem đường dẫn này 
để mà vuông là tốt hơn, bằng cách sử dụng G chi phí như là thước đo... Một G 
thấp hơn chi phí có nghĩa rằng đây là một con đường tốt hơn. Nếu vậy, thay 
đổi các vuông chính của khu vực tìm kiếm vào vuông hiện tại và tính toán lại 
các G và điểm F của khu vực tìm kiếm. 
- Dừng khi: 
+ Thêm các mục tiêu vuông vào danh sách đóng cửa, trong đó đường 
dẫn trường hợp đã được tìm thấy. 
+ Không tìm thấy những vuông mục tiêu và danh sách mở trống. Trong 
trường hợp này, không có đường dẫn. 
3.3. Cài đặt giải thuật 
3.3.1. Cài đặt giải thuật 
Lập trình C# trên visual studio 2010. 
3.3.2. Hướng dẩn sử dụng 
Ứng dụng viết trên windows form nên tương đối dể sử dụng. 
39 
TÀI LIỆU THAM KHẢO 
1. Mai Tiến Dũng, Bài giảng kỹ thuật lập trình. 
2. Phan Dũng (1992), Làm thế nào để sáng tạo, Ủy ban khoa học và kỹ thuật 
Tp.Hồ Chí Minh. 
3. Phan Dũng (1994), Sổ tay sáng tao: các thủ thuật (nguyên tắc cơ bản), Sở 
khoa học – công nghệ và môi trường. 
4. Phan Dũng (1997), Phương pháp luận sáng tạo khoa học kỹ thuật (giáo 
trình sơ cấp), Sở khoa học – công nghệ và môi trường. 
5. Nguyễn Hữu Duyệt, Bài giảng môn trí tuệ nhân tạo. 
6. Vũ Cao Đàm (1996), Phương pháp luận nghiên cứu khoa học, Nhà xuất 
bản khoa học kỹ thuật. 
7. Hoàng Kiếm – Thanh Thủy – Chi Mai (1990), Đôi cánh I Ca Rơ, Nhà xuất 
bản thống kê Hà Nội. 
8. Hoàng Kiếm (2001), Giải một bài toán trên máy tính như thế nào, tập 1 và 
2, Nhà xuất bản giáo dục. 
9. Hoàng Kiếm, Bài giảng các môn nguyên lý lập trình nâng cao, các hệ cơ 
sở tri thức, phương pháp luận nghiên cứu khoa học. 
10. Các website sau: