TÌM ĐƯỜNG ĐI CHO KIẾN TRONG MÊ CUNG

Đề tài : Xây dựng giải thuật hỗ trợ tìm đường đi cho một con kiến trong một mê cung. Đánh giá giải thuật.

KE HOACH LAM BAI TAP LON

KE HOACH LAM BAI TAP LON

Bài toán tìm đường đi giữa hai điểm trong mê cung được quy về bài toán tìm đường đi giữa hai điểm trong đồ thị. Mê cung được quy đổi ra một ma trận 0, 1 với quy định điểm 0 là các điểm có thể đi qua, các điểm 1 là chướng ngại vật và không thể đi qua.

Bài toán áp dụng phương pháp tìm kiếm theo chiều sâu (Depth-First Search). Trong phương pháp tìm kiếm theo chiều sâu, tại vi trí hiện hành, ta chọn một vị trí kế tiếp(trong tập các vị trí có thể biến đổi thành từ trạng thái hiện tại) làm trạng thái hiện hành cho đến lúc trạng thái hiện hành là trạng thái đích. Trong trường hợp tại trạng thái hiện hành, ta không thể biến đổi thành trạng thái kế tiếp thì ta sẽ quay lui(back-tracking) lại trạng thái trước trạng thái hiện hành (trạng thái biến đổi thành trạng thái hiện hành) để chọn đường khác. Nếu ở trạng thái trước này mà cũng không thể biến đổi được nữa thì ta quay lui lại trạng thái trước nữa và cứ thế. Nếu đã quay lui đến trạng thái khởi đầu mà vẫn thất bại thì kết luận là không có lời giải.

Khi điểm hiện hành chính là điểm cần đến thì dừng dfs và ta thực hiện duyệt ngược trở lại từ điểm hiện hành đến điểm bắt đầu để tìm ra đường đi là kết quả cuối cùng cho bài toán.

CHƯƠNG TRÌNH được viết = C++ và được tải lên trong file đính kèm.

8 Responses to “TÌM ĐƯỜNG ĐI CHO KIẾN TRONG MÊ CUNG”

  1. nhoclolem Says:

    anh có thể giải bài tìm đường đi trong mê cung bằng phương pháp đệ quy ko ạ? help em với!!!

  2. doremi nguyễn huyền Says:

    cám ơn anh vs bài viết này ah, e đang cần cái bài này, ah, nếu có thể a cho e xin code vs demo C# luôn được ko ah, e cám ơn

  3. trong Says:

    sao em down về ko đươc anh, link die rùi anh, anh share len cho em down vs, em đang cần tài liệu này lắm
    tks anh ạ

  4. deimosvn Says:

    anh vào thăm chú này,have a nice day!!!:D


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

%d bloggers like this: