Giới thiệu chung

I. Đặt vấn đề:

Để tìm kiếm lời giải của một bài toán ta có nhiều phương pháp khác nhau. Nếu thể hiện bài toán dưới dạng đồ thị trong không gian trạng thái thì việc tìm lời giải cho bài toán là tìm đường đi trên bản đồ từ nút xuất phát đã cho đến một đích đích xác định.

Có nhiều thuật giải tìm kiếm trên đồ thị đã được xây dựng, từ những thuật giải vét cạn đơn giản như tìm theo chiều sâu, tìm theo chiều rộng cho đến những thuật giải cải tiến ưu việt hơn, tập trung vào những đường đi nhiều triển vọng hơn cả. Trong bản luân văn này em xin được trình bầy một trong những phương pháp đó là “phương pháp nhánh và cận”. Phương pháp nhánh cận là phương pháp tìm kiếm tối ưu mà không tốn nhiều công sức và còn hoàn thiện hơn khi được cài đặt trên “cây nhị phân”. Việc triển khai tìm kiếm trên cây nhị phân là một cấu trúc dữ liệu quen thuộc được xây dựng hoàn chỉnh sẽ là một thử nghiệm lý thú nên xem xét.

I.2 ý tưởng:

Phương pháp tìm kiếm nhánh và cận là một phương pháp tìm kiếm tối ưu, bản thân cây nhị phân là một cấu trúc dữ liệu rất quen thuộc và tìm kiếm trên đó là một việc đơn giản nhánh chóng, tìm kiếm trên cây nhị phân là phương pháp tìm kiếm nhanh nhất chưa có phương pháp nào nhanh hơn chính vì tại so ta không kếy hợp 2 phương pháp này để có thể đưa ra 1 phương pháp tìm kiếm hay hơn, nhanh hơn ,tối ưu hơn đó chính là ý tưởng để em làm bản luân văn nay.

Để có được những kết quả trong luân văn sinh viên đã nhận được sự hướng dẫn tận tình của thầyd giáo TS Nguyễn Đình Hoá - Em xin chân thành cám ơn sự hướng dẫn của thầy trong những bước đầu nhgiên cứu.

Bản luận văn này đã được hoàn thành nhưng với trình độ kiến thức và kinh nhiệm còn hạn chế nên không thể tránh khỏi những thiếu sót nên em rất mong được sự chỉ bảo của các thầy cô và đóng góp ý kiến để em có thể hoàn thiện về mặt kiến thúc và tiếp tục nghiên cứu phát triển bản luận văn này được hoàn thiện hơn.

Bản luân văn bày dài 87 trang, Ngoài phụ lục thì bao gồm ba chương. Sau đây là tóm tắt nội dung chính của luân văn.