Đăng ký Đăng nhập
Trang chủ Công nghệ thông tin Cơ sở dữ liệu Báo cáo thực hành trí tuệ nhân tạo...

Tài liệu Báo cáo thực hành trí tuệ nhân tạo

.DOCX
24
1200
100

Mô tả:

Báo cáo thực hành trí tuệ nhân tạo
ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA CÔNG NGHỆ THÔNG TIN ---------- BÁO CÁO THỰC HÀNH TRÍ TUỆ NHÂN TẠO Giáo viên hướng dẫn : Võ Đức Hoàng Đà Nẵng, 11/2014 MỤC LỤC I. Nội dung buổi 2..............................................................................................................................3 1. Bài 1...........................................................................................................................................3 2. Bài 2...........................................................................................................................................5 3. Bài 3...........................................................................................................................................6 4. Bài 4...........................................................................................................................................8 5. Bài 5...........................................................................................................................................9 6. Bài 6.........................................................................................................................................10 7. Bài 7.........................................................................................................................................13 8. Bài 8.........................................................................................................................................14 9. Bài 9.........................................................................................................................................16 10. II. Bài 10....................................................................................................................................18 Nội dung buổi 3............................................................................................................................19 1. Đề tài và giới thiệu....................................................................................................................19 2. Chữ kí tự động..........................................................................................................................20 a. Thu thâp dữ liệu về tiến trình................................................................................................20 b. Trích chọn đặt trưng..............................................................................................................21 c. Đăng kí chữ ký mẫu..............................................................................................................21 d. So khớp.................................................................................................................................22 3. 4. Thuật toán DTW.......................................................................................................................22 a) Mô tả kí kiệu.........................................................................................................................22 b) Xây dựng ma trận DTW........................................................................................................23 Tìm warp-path nhỏ nhất............................................................................................................23 GVHD: Võ Đức Hoàng I. Nội dung buổi 2 1. Bài 1  Đề bài: Trò chơi 8 quân cờ (Cờ ta canh) Tám (8) quân cờ được chỉ ra trong hình, gồm một bảng kích thước 3x3 với 8 quân cờ dược đánh số từ 1 đến 8 và một ô trống. Một quân cờ đứng cạnh ô trống có thể đi vào ô trống. Mục tiêu là luôn luôn tiến tới vị trí các quân cờ như ở trong hình bên phải (trạng thái đích). Trạng thái đầu Trạng thái đích 1 2 3 4 5 6 7 8 Hãy trình bày thuật toán và viết chương trình demo để di chuyển các quân cờ sao cho số bước di chuyển là thấp nhất (tối ưu). Dữ liệu được đọc từ file là ma trận vuông 3x3.  Thuật toán - Dùng thuật toán A* để giải quyết bài toán 8 quân cờ nêu trên.Thuật toán A* sẽ đảm bảo lời giải phát hiện ra có chi phí thấp nhất nếu ước lượng các đỉnh đang xét đến đích nhỏ hơn khoảng cách thực - Thuật toán A* sẽ sử dụng khoảng cách từ đỉnh xuất phát đến đỉnh x đang xét: g(x) và khoảng cách ước lượng từ đỉnh x đang xét đến đích: h’(X) - Các bước của thuật toán A* như sau:  1. Cho đỉnh xuất phát vào open  2. Nếu open rỗng thì tìm kiếm thất bại, kết thúc việc tìm kiếm  3. Lấy đỉnh đầu trong open ra và gọi đó là O. Cho O vào closed  4. Nếu O là đỉnh đích thì tìm kiếm thành công, keeys thúc việc tìm kiếm  5. Tìm tất cả các đỉnh con của O không thuộc open và closed cho vào open theo thứ tự tăng dần đối với hàm f(x)=g(x)+ h’(x)  6. Trở lại bước 2. - Để áp dụng được thuật toán A* vào bài toán 8 quân cờ, ta cần xác định hàm heuristic để ước lượng giá trị của mỗi trạng thái ở bảng số.Ta sử dụng thuật toán Manhattan để xây dựng hàm đánh giá chi phí, khi đó giá trị của hàm heuristic sẽ bằng tổng số ô chênh lệch của ô số ở trạng thái hiện tại so với trạng thái đích của nó. Manhattan đo khoảng cách chênh lệch bằng cách đếm các hướng ngang học sao cho đường đi từ vị trí đang xét với vị trí đúng là ngắn nhất. Tọa độ đúng của ô có địa chỉ ID trên ma trận vuông kích thước nxn ta sử dụng công thức sau: RowID=ID/n, ColID=ID%n TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 3 GVHD: Võ Đức Hoàng - Khi đó chi phí từ vị trí hiện tại có tọa độ (x2,y2) đến vị trí đích có tọa độ (x1,y1) là: h=| x1-x2 | + | y1-y2 |  Demo - Các bước di chuyển : Bước 0 Bước 2 TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Bước 1 Bước 3 Trang 4 GVHD: Võ Đức Hoàng Bước 4 Bước 5 2. Bài 2  Đề bài: Trò chơi viết số Hai người chơi với nhau trò chơi như sau: với 1 số a đang có sẵn, đến lượt mình chơi, người đó sẽ viết số a+1 hay 2a với điều kiện số mới viết này không vượt qua số nguyên dương N cho trước. Với số bắt đầu là 1, ai viết được số N trước thì xem như thắng. Xem như máy là người đi sau. Trình bày thuật toán và viết chương trình mô tả trò chơi sao cho khả năng thắng của máy cao. Dữ liệu được đọc từ bàn phím.  Thuật toán - Dùng thuật toán MiniMax để giải quyết bài toán nêu trên - Giả sử cả các người chơi đều lựa chọn chiến thuật chơi tối ưu, thì khi một người viết số x, ta có thể biết người đó sẽ chắc chắn thắng hay thua. - Với N không quá lớn thì có thể lập 1 bảng các trạng thái của trò chơi này. - Thuật toán như sau:  Mảng A[] với A[i] sẽ có các giá trị là 0 hoặc 1 để biểu diễn các trạng thái của bài toán, với A[i]=0 là trạng thái chắc chắn thua và A[i]=1 là trạng thái chắc chắn thắng  Khởi tạo A[n]=1 : thắng  Tại một điểm i nào đó với x=2*i hoặc x=i+1, và nếu A[x]=1 thì A[i]=0 , ngược lại thì A[i]=1. Vì nếu người đi hiện tại để người đi sau mình cộng 1 hoặc nhân 2 đụng tới điểm chắc chắn thắng thì người đó sẽ thua.  Sau khi có được bảng các trạng thái thì có thể áp dụng thuật toán MiniMax để tìm kiếm để khả năng thắng của máy là cao nhất - Giả sử như với n=10, ta sẽ có bảng trạng thái như sau:  A[10]=1  A[9]=0 vì A[9+1]=1  A[8]=1 vì A[8+1]=0  A[7]=0 vì A[7+1]=1  A[6]=1 vì A[6+1]=0  A[5]=0 vì A[5*2]=1  A[4]=0 vì A[4*2]=1  A[3]=0 vì A[3*2]=1  A[2]=1 vì A[2+1]=0  A[1]=0 vì A[1+1]=1  Demo TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 5 GVHD: Võ Đức Hoàng Nếu Bấm +1 tiếp tục thì máy sẽ thắng - Trường hợp nhìn bảng trạng thái ở trên, có thể biết mình thắng hay thua 3. Bài 3  Đề bài: Bài toán phân việc Có n chi tiết máy J1, J2, ..., Jn cần gia công lần lượt trên 3 máy A, B, C với thời gian hoàn thành tương ứng của 1 chi tiết là TA, TB, TC. Các chi tiết từ J1, J2, ..., Jn có thể gia công theo thứ tự bất kỳ tuy nhiên một chi tiết J i phải được gia công lần lượt theo thứ tự trên máy A  máy B  máy C. TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 6 GVHD: Võ Đức Hoàng Trình bày thuật toán và viết chương trình mô tả sao cho tổng thời gian gia công hoàn thành n chi tiết là thấp nhất (tối ưu). Dữ liệu được đọc từ file có dạng như sau: DULIEU.INP n //số chi tiết cần gia công J1A, J2A,...., JnA //thời gian gia công các chi tiết trên máy A J1B, J2B,...., JnB //thời gian gia công các chi tiết trên máy B J1C, J2C,...., JnC //thời gian gia công các chi tiết trên máy C Kết quả xuất ra là thứ tự các công việc  Thuật toán - Sử dụng thuật toán Johnson để giải quyết bài toán trên. - Thuật toán lập lịch Johnson đối với 2 máy A,B như sau:  Chia các chi tiết thành 2 nhóm: nhóm N1: gồm các chi tiết Di thoả mãn a1< b1, tức là min(ai,bi) = ai và nhóm N2 gồm các chi tiết Di thoả mãn ai>bi tức là min(ai,bi)=bi. Các chi tiết Di thoả mãn ai =bi xếp vào nhóm nào cũng được.  Sắp xếp các chi tiết trong N1 theo chiều tăng của các ai và sắp xếp các chi tiết trong N2 theo chiều giảm của các bi  Nối N2 vào đuôi N1, dãy thu được (đọc từ trái sang phải) sẽ là lịch gia công. - Thuật toán lập lịch Johnson đối với 3 chi tiết máy theo thứ tự A,B,C phải có điều kiện ràng buộc max bi ≤ min ai hoặc max bi ≤ min ci - Lịch gia công tối ưu trên 3 máy sẽ trùng với lịch gia công tối ưu trên 2 máy: máy thứ nhất với thời gian ai + bi và máy thứ hai với thời gian bi + ci.  Demo 4. Bài 4  Đề bài: Bài toán người du lịch Một người khách du lịch muốn đi thăm n thành phố được đánh số từ 1 n và quay lại thành phố xuất phát. Mạng lưới giao thông giữa n thành phố này là hai TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 7 GVHD: Võ Đức Hoàng chiều và được cho bởi ma trận A[i,j] trong đó A[i,j]=1 nếu có đường đi từ thành phố i đến thành phố j, A[i,j]=0 trong trường hợp ngược lại. Hãy thiết lập lộ trình cho người khách hay thông báo không tồn tại lời giải. Dữ liệu được đọc từ file có dạng như sau: DULIEU.INP Dòng 1: Ghi số nguyên n (n<=20). Dòng i+1 (1<=i<=n) ghi n số nguyên không âm (0 hoặc 1). Kết quả xuất ra chu trình đường đi. (Chu trình HAMILTON)  Thuật toán - Sử dụng chu trình Hamilton để giải quyết bài toán trên - Chu trình Hamilton:  Cho đồ thị G=(V, E) có n đỉnh  Chu trình (x 1 , x 2 , …, x n , x 1 ) được gọi là Chu trình Hamilton nếu x i <>x j với 1<=ix j với 1<=i=2 và i<=n.  Chọn tất cả các đỉnh j để tìm đỉnh thứ i X[i] kề với X[i-1] và chưa bị đi qua o Nếu tìm thấy đỉnh j thỏa mãn điều kiện trên thì gán X[i] = j . o Nếu i < n thì:  Đánh dấu đỉnh j là đã đi qua để cho các bước tiếp theo không chọn j nữa.  Sau đó chọn đỉnh thứ i+1 trong hành trình  Thử phương án khác cho X[i] nên sẽ bỏ đánh dấu đỉnh vừa thử o Ngược lại , nếu đã thử chọn đến X[n] thì kiểm tra nếu X[n] lại kề với X[1] thì ta có chu trình Hamilton  Demo TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 8 GVHD: Võ Đức Hoàng 5. Bài 5  Đề bài: Bài toán hệ thống dây điện Một công ty cần thay toàn bộ hệ thống dây điện cho N phòng làm việc. Cho biết sơ đồ mạng lưới điện hiện có của n căn phòng được biểu diễn bằng ma trận A[i,j] trong đó A[i,j] chính là độ dài của dây điện nối giữa 2 phòng i và j (A[i,j]=A[j,i], A[i,j]=0 nếu không có (không thể) dây nối giữa phòng i và j). Hãy lập trình tính độ dài của dây dẫn cần sử dụng sao cho cả N phòng dều có điện và số lượng này là ít nhất. Dữ liệu được đọc từ file có N+1 dòng dạng như sau: DULIEU.INP Dòng 1: Ghi số nguyên N. Dòng i+1 (1<=i<=N) ghi N số nguyên A[i,1] A[i,2] .........A[i,N]. Các số ghi trên 1 dòng cách nhau ít nhất 1 dấu cách. Kết quả xuất ra màn hình cách nối và tổng độ dài nhỏ nhất  Thuật toán - Sử dụng thuật toán Prim để giải quyết bài toán trên. - Thuật toán Prim như sau:  Dữ liệu vào: Một đồ thị có trọng số liên thông với tập hợp đỉnh V và tập hợp cạnh E (trọng số có thể âm). Đồng thời cũng dùng V và E để kí hiệu số đỉnh và số cạnh của đồ thị.  Khởi tạo: Vmới = {x}, trong đó x là một đỉnh bất kì (đỉnh bắt đầu) trong V, Emới = {}  Lặp lại cho tới khi Vmới = V: TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 9 GVHD: Võ Đức Hoàng -  Chọn cạnh (u, v) có trọng số nhỏ nhất thỏa mãn u thuộc Vmới và v không thuộc Vmới (nếu có nhiều cạnh như vậy thì chọn một cạnh bất kì trong chúng)  Thêm v vào Vmới, và thêm cạnh (u, v) vào Emới  Dữ liệu ra: Vmới và Emới là tập hợp đỉnh và tập hợp cạnh của một cây bao trùm nhỏ nhất. Coi mỗi phòng là một đỉnh của đồ thị. Chiều dài dây điện cần để nối giữa phòng i và phòng j chính là trọng số cạnh (i , j). A[i,j] chính là độ dài đoạn dây điện nối giữa hai phòng i và j. Nếu không thể nối dây thì A[i,j]=∞ Độ dài đường dây dẫn cần nối sao cho tất cả các phòng đều có điện và số lượng là ít nhất chính là độ dài cây khung nhỏ nhất của đồ thị A.  Demo 6. Bài 6  Đề bài: Trò chơi đoán số Cậu bé nghĩ ra 1 số (Gọi là S) gồm bỗn chữ số (không nhất thiết khác nhau) trong sáu chữ số từu 1 đến 6. Để tìm số đó máy lần lượt đưa ra các số dự đoán (gọi là M), mỗi số gồm 4 chữ số không nhất thiết khác nhau. Với mỗi lần dự đoán, máy nhận được 2 câu trả lời của cậ bé cho 2 câu hỏi sau. + Có bao nhiêu chữ số trong M là chữ số trong S nhưng vị trí xuất hiện của mỗi chữ số đó là sai? + Có bao nhiêu chữ số trong M là chữ số trong S và đồng thời vị trí xuất hiện của mỗi chữ số đều đúng? Yêu cầu: Hãy hiện lên màn hình các số máy dự đoán và nói mỗi số đó nhận 2 câu trả lời từ bàn phím của cậu bé cho đến khi được số đúng như cậu bé nghĩ. (Số lần dự đoán không quá 6 lần). Ví dụ: Số cần tìm là 5436 TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 10 GVHD: Võ Đức Hoàng 1234 Đúng số - Đúng vị trí : 1 Đúng số - Sai vị trí : 1 2156 Đúng số - Đúng vị trí : 1 Đúng số - Sai vị trí : 1 1416 Đúng số - Đúng vị trí : 2 Đúng số - Sai vị trí : 0 5436 Đúng số - Đúng vị trí : 4 Đúng số - Sai vị trí : 0 Chọn đúng số  Thuật toán - Sử dụng mảng save[2000][6] để lưu các tập số lọc ra từ câu trả lời của người chơi Begin Đưa ra 1 2 3 4 cho người chơi chọn và lưu 2 kết quả trả lời a1, b1 Đưa ra 2 1 5 6 cho người chơi chọn và lưu 2 kết quả trả lời a2, b2 //Lọc từ tập hợp các số từ 1 1 1 1 đến 6 6 6 6 từ câu trả lời thứ a1 For i = 1 1 1 1 to 6 6 6 6 do If (i và 1 2 3 4 có a1 số chung vị trí) và (i và 2 1 5 6 có a2 số chung vị trí) If các chữ số còn lại có b1 số giống nhau hoặc b2 số giống nhau Lưu i vào save EndIf Endif EndFor While số lần đoán < 7 Chọn ngẫu nhiên 1 số k trong save và đưa ta cho người chơi chọn lưu kết quả vào a1, b1 If đúng số thì dừng For i trong tập Save If (i và k không có a1 số chung vị trí) If các số chữ số còn lại có không có b1 số giống nhau Loại i khỏi save EndIf TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 11 GVHD: Võ Đức Hoàng Endif EndFor EndWhile  Demo - Ví dụ số nghĩ là : 2514. Quá trình đoán số như sau: Đưa ra số dự đoán đầu tiên Đưa ra số dự đoán thứ 2 Đưa ra số dự đoán thứ 3 TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 12 GVHD: Võ Đức Hoàng Đưa ra số dự đoán thứ 4 và chính xác 7. Bài 7  Đề bài : Chia quà Trong ngày sinh nhật Tom và Jerry nhận được N đồ chơi (N<=40). Trên đồ chơi i có giá tiền là X i. Hai anh em quyết định mỗi người phải có trách nhiệm bảo quản 1 phần số quà và phân chia sao cho chênh lệch tổng giá trị tiền đồ chơi mà mỗi người phải bảo quản là ít nhất. Hãy giúp Tom bà Jerry phân chia trách nhiệm. Dữ liệu đọc từ file text có dạng sau: Dòng 1 : ghi số nguyên dương N. Dòng 2 : Ghi N số nguyên dương tương ứng với giá trị N đồ vật.  Thuật toán: - Sử dụng thuật toán tham lam để giải quyết bài toán trên - Ý tưởng của thuật toán:  Đọc tất cả các dữ liệu đầu vào trong mảng 1 chiều  Sắp xếp mảng đó theo giá trị giảm dần của giá trị các quà  Lần lượt đưa các phần quà vào cho Tom và Jerry sao cho hiệu của tổng các giá trị phần quà của Tom và Jerry nhỏ nhất  Công việc tiếp tục quá trình trên cho đến khi nào các phần quà được chia hết cho Tom và Jerry. - Các thuộc tính cần thiết phục vụ cho chương trình: soqua: chứa số phần quà, giatien[] là mảng 1 chiều chứa các giá trị của các phần quà, tom[] là mảng sẽ chứa các phần quà chia cho Tom, tongtom: tổng các phần quà mà Tom được chia, jerry[] là mảng chứa các phần quà của jerry, tongjerry: chứa tổng các phần quà mà jerry được chia. - Để cài đặt cho bài toán trên, ta xây dựng các các phương thức cần thiết để giải quyết bài toán:  Phương thức docfile() để đọc dữ liệu đầu vào của bài toán: bao gồm số phần quà và 1 mảng các giá trị của phần quà  Các phương thức docso() và isnumber() sẽ hỗ trợ cho phương thức docfile() trong việc đọc các dữ liệu đầu vào  Phương thức sapxep() có nhiệm vụ sắp xếp mảng các giá trị của phần quà theo thứ tự giảm dần  Phương thức show() để in kết quả chia quà ra màn hình TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 13 GVHD: Võ Đức Hoàng  Phương thức chia_qua() là hàm xử lý chính của chương trình, có nhiệm vụ chia quà cho Tom và Jerrry. Hàm sẽ xử lý như sau: ban đầu cho tongtom=0 và tongjerry=0. Cho vòng lặp thực thiện : nếu tongtom<= tongjerry thì chia phần quà đó cho Tom, ngược lại sẽ chia cho jerry. Thực hiện tương tự cho đến khi hết quà.  Demo 8. Bài 8  Đề bài : Tô màu bản đồ Có 1 bản đồ có N nước. Mỗi nước được tô 1 màu để phân biệt. Các nước liền kề nhau không được tô cùng màu với nhau. Hãy xác định số màu tối thiểu để tô bản đồ sao cho các miền kề nhau không được tô cùng màu.  File dữ liê uê đầu vào: GRAPH.INP có cấu trúc n m (n đỉnh:1,2,...,n; m là số cạnh) x1 y1 (danh sách m cạnh) x2 y2 .... xm ym ................  File kết quả: COLOR.OUT VERTEX: 1 2 ... n COLOR: c1 c2 ... cn  Ví dụ: GRAPH.INP COLOR.OUT 10 18 VERTEX: 1 2 3 4 5 67 8 9 10 1 2 COLOR: 2 3 2 1 1 12 3 2 3 1 4 1 5 1 8 2 3 2 5 2 6 TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 14 GVHD: Võ Đức Hoàng 3 5 3 6 3 8 4 7 5 7 5 8 5 9 6 9 6 10 8 9 9 10 --------------5 5 VERTEX: 1 2 3 4 5 1 2 COLOR: 1 2 1 2 3 2 3 3 4 4 5 5 1  Thuật toán - Sử dụng thuật toán tham lam để giải quyết bài toán nêu trên - Ý tưởng của thuật toán là:  Cho vòng lặp đi từ nước đầu tiên đến nước cuối cùng.  Với mỗi nước ta sẽ tô cùng một màu cho các nước không liền kề với nước đang xét, không được tô màu cho các nước liền kề.  Lặp lại quá trình cho đến khi tất cả các nước được tô màu xong - Các thuộc tính cần thiết cho bài toán bao gồm: sodinh: số đỉnh, socanh: số cạnh, matrix[][] : mảng 2 chiều lưu trữ dữ liệu đầu vào. - Để giải quyết bài toán trên, ta sẽ xây dựng các phương thức phục vụ cho bài toán  Phương thức docfile() dùng để đọc dữ liệu đầu vào của bài toán từ file, lưu lại số đỉnh, số cạnh và ma trận, với quy ước: matrix[u] [v]=1 nếu hai đỉnh u và v liền kề với nhau, ngược lại matrix[u] [v]=0.  Phương thức ghifile() dùng để ghi kết quả của bài toán ra file trên đĩa cứng.  Phương thức docso() và isnumber() là 2 phương thức phụ hỗ trợ cho việc đọc dữ liệu từ file.  Phương thức color() là phương thức xử lý chính của chương trình, áp dụng giải thuật tham lam để giải quyết bài toán. Bắt đầu từ đỉnh 1, và color=1 để gán cho đỉnh 1 và các đỉnh không liền kề với đỉnh 1, tiếp theo tăng color lên và sẽ tiếp tục tô cho các đỉnh còn lại, cho đến khi nào hết thì dừng lại  Demo TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 15 GVHD: Võ Đức Hoàng 9. Bài 9  Đề bài: Người lái đò Viết chương trình mô phỏng bài toán người lái đò (có thể có giao diện đồ họa). Bài toán phát biểu như sau: Tại bến sông nọ có bắp cải, sói và dê muốn bác lái đò chở qua sông. Biết rằng tại một thời điểm thuyền của bác lái đò chỉ chở tối đa được 2 khách. Nếu sói và dê đứng riêng với nhau (không có mặt bác lái đò và bắp cải) thì sói sẽ ăn thịt dê. Nếu dê và bắp cải đứng riêng với nhau (không có mặt bác lái đò và sói) thì dê sẽ ăn bắp cải. Ký hiệu bờ sông mà sói, dê, bắp cải và bác lái đò đang đứng là 1, bờ sông bên kia là 2. Hãy viết chương trình giải quyết bài toán trên.  Thuật toán - Sử dụng thuật toán tìm kiếm sâu để giải quyết bài toán nếu trên. Tìm kiếm sâu là phương pháp tìm kếm mà ưu tiên tìm kiếm những đỉnh xa với đỉnh xuất phát. - Thuật toán tìm kiếm sâu:  1.Cho đỉnh xuất phát vào open  2.Nếu open rỗng thì tìm kiếm thất bại, kết thúc việc tìm kiếm.  3.Lấy đỉnh đầu trong open ra và gọi nó là O. Cho O vào closed.  4.Nếu O là đỉnh đích thì tìm kiếm thành công, kết thúc việc tìm kiếm  5. Tìm tất cả đỉnh con của O không thuộc open và closed cho vào đầu của open  6.Trở lại bước 2 TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 16 GVHD: Võ Đức Hoàng - Áp dụng cho bài toán trên, ta sẽ xây dựng các lớp để lưu trữ dữ liệu của bài toán.  Lớp State lưu trữ các đối tượng trong bài toán. Các đối tượng trong bài toán gồm có: sói, dê, bắp cải, bác lái đò, thuyền. Hàm construct của lớp sẽ bao gồm tất cả các đối tượng trên: State(bắp cải, sói, dê, lái đò, thuyền ). Lớp State xây dựng phương thức getChildren() để lưu tất cả các trạng thái con có thể có của trạng thái hiện tại, phương thức checkOk() để kiếm tra xem trạng thái có phù hợp với bài toán hay không?  Lớp Operator bao gồm các trường hợp di chuyển các đối tượng trong bài toán sao cho phù hợp với yêu cầu của bài toán. Có 4 trường hợp có thể có khi di chuyển các đối tượng trong bài toán: bắp cải và bác lái đò qua sông, sói và bác lái đó qua sông, dê và bác lái đò qua sông, bác lái đò qua sông. ứng với mỗi trường hợp sẽ trả về trạng thái mới phù hợp  Lớp nguoilaido là lớp xử lý chính của bài toán, bao gồm 2 List là open và closed để phù hợp với thuật toán tìm kiếm sâu. Xác định trạng thái bắt đầu và trạng thái kết thúc của bài toán. Trạng thái bắt đầu sẽ là State(1,1,1,1,0) tương ứng với 1 bắp cải, 1 sói, 1 dê, 1 bác lái đò và thuyền đang ở bờ bên trái. Trạng thái kết thúc sẽ là State(1,1,1,1,1) tương ứng với 1 bắp cải, 1 sói , 1 dê, 1 bác lái đò và thuyền đang ở bờ bên phải.  Cuối cùng áp dụng chính xác các bước trong giải thuật tìm kiếm sâu để giải quyết bài toán trên, kết quả in ra các bước di chuyển đối tượng.  Demo 10. Bài 10  Đề bài : Qua sông TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 17 GVHD: Võ Đức Hoàng Viết chương trình mô phỏng bài toán qua sông (có thể có giao diện đồ họa). Bài toán phát biểu như sau: Tại bến sông nọ có 3 thầy tu và 3 con quỷ muốn qua sông. Biết rằng tại một thời điểm thuyền chỉ chở tối đa được 2 khách. Nếu bất cứ ở trên bờ nào, bên này hoặc bên kia thì số con quỷ phải bé hơn hoặc bằng số thầy tu, ngược lại quỷ sẽ ăn thịt thầy tu. Hãy viết chương trình giải quyết bài toán trên.  Thuật toán - Sử dụng thuật toán tìm kiếm sâu để giải quyết bài toán nếu trên. Tìm kiếm sâu là phương pháp tìm kếm mà ưu tiên tìm kiếm những đỉnh xa với đỉnh xuất phát. - Thuật toán tìm kiếm sâu:  1.Cho đỉnh xuất phát vào open  2.Nếu open rỗng thì tìm kiếm thất bại, kết thúc việc tìm kiếm.  3.Lấy đỉnh đầu trong open ra và gọi nó là O. Cho O vào closed.  4.Nếu O là đỉnh đích thì tìm kiếm thành công, kết thúc việc tìm kiếm  5. Tìm tất cả đỉnh con của O không thuộc open và closed cho vào đầu của open  6.Trở lại bước 2 - Áp dụng cho bài toán trên, ta sẽ xây dựng các lớp để lưu trữ dữ liệu của bài toán.  Lớp State sẽ lưu trữ trạng thái của 1 bờ bên sông, bao gồm các tham số : State(số_người, số_quỷ,trạng_thái_thuyền). Lớp còn có phương thức getChildren() để phục vụ cho việc tìm kiếm và lưu trữ các trạng thái con có thể có của trạng thái hiện tại, phương thức checkOk() để kiểm tra xem trạng thái hiện tại có thỏa mãn với yêu cầu của bài toán hay không?  Lớp Operator bao gồm các trường hợp có thể có để di chuyển người và quỷ, bao gồm 5 trường hợp cụ thể như sau: 2 người qua sông, 2 quỷ qua sông, 1 người 1 quỷ qua sông, 1 người qua sông, 1 quỷ qua sông. Nếu trường hợp nào thỏa mãn thì sẽ trả về trạng thái mới phù hợp.  Lớp Search là lớp xử lý chính của bài toán, sẽ xác định trạng thái bắt đầu và trạng thái kết thúc của trò chơi. Trạng thái bắt đầu sẽ là State(3,3,0): 3 người 3 quỷ và thuyền ở bờ bên trái. Trạng thái kết thúc là State(3,3,1): 3 người 3 quỷ và thuyền ở bờ bên phải. Lớp Search còn xây dựng các List là open và closed để phục vụ cho thuật toán kìm kiếm sâu.  Cuối cùng áp dụng từng bước của thuật toán tìm kiếm sâu để giải quyết bài toán trên, và kết quả sẽ in ra các bước để đưa được 3 người và 3 quỷ sang sông.  Demo: TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 18 GVHD: Võ Đức Hoàng II. Nội dung buổi 3 1. Đề tài và giới thiệu  Đề tài : Ứng dụng DTW xác thực trong chữ ký tự động  Giới thiệu: - Vào năm 1983, Joseph Kruskal và Mark Liberman đã giới thiệu một kỹ thuật mới cho phép tìm đường chuẩn hóa tối ưu dựa trên việc so sánh hai mẫu dữ liệu được vector hóa đắc trưng (tức là khoảng cách giữa chúng). Kỹ thuật này được gọi là Time Warping, có thể so khớp hai vector có đặc trưng khác nhau về thời gian và tốc độ. Ví dụ, có thể so sánh dựa vào dáng đi của một người đi chậm và người khác đi nhanh hơn hay thậm chí có sự tăng, giảm tốc độ quan sát đối tượng dọc đường đi. Một trong những đặc điểm của DTW rất hữu ích trong lĩnh vực nhận dạng chữ ký là khả xử lý những đường chữ ký có độ dài không bằng nhau (tức là đường cong có một số lượng các điểm tọa độ x,y khác nhau). Điều này cho phép so sánh mà không cần phải lấy lại mẫu. Bởi việc lấy lại mẫu thường xóa bớt thông tin hay thêm thông tin sai (đường cong bao gồm nhiều điểm chứa đựng nhiều thông tin hơn những đường cong ít điểm, vì vậy - việc lấy mẫu là không cần thiết), cho nên tốt hơn là không sử dung. Kruskal và Liberman đã đề nghị sử dụng kỹ thuật này trong nhận dạng giọng nói, bởi đặc điểm giọng nói là chuỗi tín hiệu biến thiên liên tục TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 19 GVHD: Võ Đức Hoàng theo thời gian. Ngoài ra kỹ thuật này cho thấy khá hữu ích trong nhiều ứng dụng khác như nhận dạng dáng đi, người máy, khai thác dữ kiệu và xác thực chữ ký tự động. Và đề tài này ta sử dụng DTW để xác thực chữ ký tự động. 2. Chữ kí tự động  Hệ thống xác thực chữ lý tự động như sau: a. Thu thâp dữ liệu về tiến trình - Việc thu nhận trực tuyến các hàm thời gian của chữ ký tay có thể được thực hiện bằng các thiết bị số hóa hay màn hình cảm ứng,hoăc những thiết bị được tích hợp trong Tablet PCs và PDAs. Những thiết bị thu - nhận này cung cấp thông tin về tọa độ, về áp lực của bút,…. Sau khi được thu nhận từ các thiết bị điện tử thì chữ ký đươc tiền xử lý trước khi nó được chuyển đến tiến trình chọn đặc trưng. Một số bước tiền xử lý quan trọng đó là lọc nhiễu và tái tạo mẫu. b. Trích chọn đặt trưng - Để trích chọn ra những đặc trưng cơ bản trong chữ ký tự động, người ta sử dụng 2 phương thức cơ bản, đó là feature-based (dựa trên tính năng) và function-based(dựa trên chức năng). o Phương thức feature-based là phương thức mà từ quỹ đạo của chữ ký có thể xây dựng được một vector đại diện bao gồm những đặc trưng chung của nó o Phương thức function-based là phương thức mà trong đó chuỗi thời gian mô tả các đặc trưng cục bộ của chữ ký được sử dụng để nhận dạng TH PHÂN TÍCH VÀ THIẾT HỆ THỐNG NHÓM 11B Trang 20
- Xem thêm -

Tài liệu liên quan