Tiểu Luận Tìm đường đi ngắn nhất giữa 2 diểm trong 1 mê cung

MỤC LỤC:





LỜI MỞ ĐẦU 1

I.GIỚI THIỆU VỀ ĐỀ TÀI: 2

1.Nội dung đề tài : 2

2.Tìm hiểu và phân tích đề tài : 2

a.Truyền thuyết về mê cung : 2

b.Phân tích đề tài : 2

c. Tìm hiểu các giải thuât có thể giải quyết bài toán : 3

i)Thuật toán tìm kiếm theo chiều sâu (DFS) : 3

ii)Thuật toán tìm kiếm theo chiều rộng (BFS): 5

iii) So sánh giữa 2 phương pháp: 7

II.THUẬT TOÁN CƠ BẢN: 7

1.Xây dựng mê cung bằng ma trận kề: 7

2.Áp dụng thuật toán tìm kiếm theo chiều sâu để tìm đường đi trong mê cung: 8

III.CHƯƠNG TRÌNH: 12

IV.KẾT QUẢ CHẠY CHƯƠNG TRÌNH : 18

V.KẾT LUẬN: 19

TÀI LIỆU THAM KHẢO: 19



LỜI MỞ ĐẦU

Trong khoa học máy tính, cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Việc chọn cấu trúc dữ liệu thường bắt đầu từ chọn một cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu được thiết kế tốt cho phép thực hiện nhiều phép toán, sử dụng càng ít tài nguyên, thời gian xử lý và không gian bộ nhớ càng tốt. Các cấu trúc dữ liệu được triển khai bằng cách sử dụng các kiểu dữ liệu, các tham chiếu và các phép toán trên đó được cung cấp bởi một ngôn ngữ lập trình. Mỗi loại cấu trúc dữ liệu phù hợp với một vài loại ứng dụng khác nhau, một số cấu trúc dữ liệu dành cho những công việc đặc biệt.



Để có thể đi sâu và nắm vững kiến thức đã thu nhận được trong quá trình học môn Cấu Trúc Dữ Liệu, em chọn đề tài “Tìm đường đi ngắn nhất giữa 2 diểm trong 1 mê cung” để tìm hiểu và nghiên cứu.



Do kiến thức còn hạn chế, dù cố gắng hoàn thiện thật tốt nhưng chắc chắn đồ án còn nhiều thiếu sót. Em mong có được sự chỉ bảo, đóng góp ý kiến của thầy và các bạn để chúng em có thể hiểu rõ và sâu sắc hơn về các cấu trúc dữ liệu và giải thuật ứng dụng trong tin học.

Em xin chân thành cảm ơn!