TÌM ĐƯỜNG ĐI BẰNG THUẬT TOÁN AKT

TÌM ĐƯỜNG ĐI BẰNG THUẬT TOÁN AKT

• I. Mô tả thuật toán

B1: Khởi tạo ma trận ánh xạ bảng đồ với các giá trị

• 0: Giá trị mặc định
• 1: Điểm có vật chắn
• 2: Điểm đã đi qua

Tạo struct Diem gồm các giá trị

• x,y tọa độ điểm trên bản đồ
• g tổng độ dài từ điểm bắt đầu đến điểm hiện tại
• h tổng độ dài từ điểm hiện tại đến điểm đích
• Tạo độ điểm sinh (tọa độ của điểm trước điểm hiện tại )

Với h và g tính theo công thức (x₁-x₂)²+(y₁-y₂)²

B2: Khởi tạo 2 list là Open: Các điểm đã mở và Close: các điểm đã đi

B3: Mọi điểm, cũng như các hàm g, h, f chưa biết.

 Mở điểm đầu tiên Start, add điểm Start vào Open , gán g(S) = 0

 Sử dụng tri thức bổ sung để ước tính hàm h(Start)

 Tính f(Start) = g(Start) + h(Start)

B4: Chọn điểm có f nhỏ nhất trong list Open, gọi là điểm N

• Nếu N là đích: dừng chuyển sang Bước 6
• Nếu không tồn tại điểm nào trong Open: thông báo không tồn tại đường đi
• Nếu có 2 điểm có chung giá trị f nhỏ nhất thì chọn ngẫu nhiên 1 trong 2

B5: Chuyển  N vào tập Close, mở các điểm tiếp theo sau N, gọi là S tính các giá trị:

• g(S)=g(N)+g(N -> S)
• h(S)
• tọa độ điểm sinh S = tọa độ điểm N

Add các điểm S vào Open, quay lại bước 4

B6: Thực hiện tra vết ngược lại từ điểm đích đến điểm bắt đầu trong list Close thông qua tạo độ điểm sinh tạo đường đi từ điểm bắt đầu đến điểm đích

• II. Demo thuật toán

Tạo điểm bắt đầu kết thúc bằng chuột phải

Tạo điểm chắn bằng điểm kết thúc

Click button Tạo Bản Đồ để lưu lại bản đồ và click next để bắt đầu từng bước tìm đường cho đến khi tới đích hoặc không tìm được đường đi nữa

Click button tạo đường để có đường đi đúng nhất từ điểm bắt đầu đến điểm kết thúc

Kết thúc quá trình tìm đường