Bài tập lớn mô tả thuật toán tìm kiếm nhánh cận

Đây là ngôn ngữ lập trình đa năng được tạo ra bởi Bjarne Stroustrup như một phần mở rộng của ngôn ngữ lập trình C, hoặc "C với các lớp Class", Ngôn ngữ đã được mở rộng đáng kể theo thời

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

KHOA CÔNG NGHỆ THÔNG TIN

-🙡🙡🙡 -BÀI TẬP LỚN

MÔ TẢ THUẬT TOÁN TÌM KIẾM NHÁNH CẬN

Tên môn học: Trí tuệ nhân tạo

Nhóm sinh viên thực hiện: 1 Vũ Minh Hiếu

2 Nguyễn Thu Hương

3 Phạm Duy Đức

4 Đàm Duy Khanh

Lớp: CNTT K18D

Thái Nguyên, tháng 3 năm 2022

CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ NGÔN NGỮ

C++

1.1 C++ là gì?

C++ (C Plus Plus) là một loại ngôn ngữ lập trình bậc trung (middle-level)

Đây là ngôn ngữ lập trình đa năng được tạo ra bởi Bjarne Stroustrup như một phần

mở rộng của ngôn ngữ lập trình C, hoặc "C với các lớp Class", Ngôn ngữ đã được

mở rộng đáng kể theo thời gian

C ++ hiện đại có các tính năng: lập trình tổng quát, lập trình hướng đối tượng, lập trình thủ tục, ngôn ngữ đa mẫu hình tự do có kiểu tĩnh, dữ liệu trừu tượng, và lập trình đa hình, ngoài ra còn có thêm các tính năng, công cụ để thao tác với bộ nhớ cấp thấp Từ thập niên 1990, C++ đã trở thành một trong những ngôn ngữ thương mại ưa thích và phổ biến của lập trình viên

C++ được thiết kế hướng tới lập trình hệ thống máy tính và phần mềm

nhúng trên các mạch vi xử lý, bao gồm cả hệ thống có tài nguyên hạn chế và tài nguyên khổng lồ, với ưu điểm vượt trội về hiệu suất, hiệu quả và tính linh hoạt cao

C ++ có thể tìm thấy ở mọi nơi, với những điểm mạnh là cơ sở hạ tầng phần mềm và các ứng dụng bị hạn chế tài nguyên bao gồm: phần mềm ứng dụng máy tính cá nhân, trò chơi điện tử, các hệ thống máy chủ (ví dụ: phần mềm thương mại điện tử, cỗ máy tìm kiếm trên web hoặc máy chủ SQL) và các ứng dụng ưu tiên về hiệu suất (ví dụ: tổng đài thông tin liên lạc hoặc thiết bị thăm dò không gian)

C++ hầu hết được thực thi dưới dạng là một ngôn ngữ biên dịch, có thể chạy trên nhiều nền tảng khác nhau như Windows, Mac OS, Linux, các phiên bản Unix Nhiều nhà cung cấp cung cấp các trình biên dịch C ++, bao gồm Tổ chức Phần mềm Tự do, Microsoft, Intel và IBM

1.2 Khái quát về lịch sử

1.2.1 Lịch sử C++

Stroustrup đã bắt đầu làm việc với khái niệm lớp trong 1979 Ý tưởng tạo ra một ngôn ngữ mới bắt nguồn từ kinh nghiệm lập trình khi mà ông viết luận án tiến

sĩ Stroustrup nhận ra rằng Simula có nhiều tính năng hữu dụng cho việc phát triển một phần mềm lớn nhưng nó đã quá chậm trong ứng dụng thực tế, trong khi

đó, BCPL lại nhanh nhưng ở cấp quá thấp và không tiện cho việc phát triển phần mềm lớn Đến khi làm việc ở Bell Labs, thì ông gặp phải vấn đề trong việc phân tích nhân Unix với việc tính toán phân tán Dùng lại kinh nghiệm lúc làm luận án

tiến sĩ, Stroustrup cài thêm các tính năng giống như Simula vào trong C để nâng cao C được chọn là vì đó là ngôn ngữ tổng quát, nhanh và năng động Lần đầu tiên, các chức năng như là lớp, lớp dẫn xuất, kiểm tra kiểu mạnh, nội tuyến

( inline ), và đối số mặc định đã được thêm vào trong C Lần xuất bản đầu tiên vào thị trường xảy ra trong tháng 11/1985

Năm 1983, thì tên C với các lớp được đổi thành C++ các chức năng mới

được thêm vào bao gồm hàm ảo, quá tải hàm và toán tử, tham chiếu, hằng, khả năng kiểm soát bộ nhớ của lưu trữ tự do, nâng cao việc kiểm soát kiểu, và lệnh chú giải kiểu ( // )

Năm 1985, tác phẩm The C++ Programming Language được xuất bản lần

đầu tiên, cung cấp một tài liệu tham khảo quan trọng cho ngôn ngữ nhưng đó chưa

là một tiêu chuẩn chính thức

Năm 1989 phiên bản C++ 2.0 phát hành Các tính năng mới bao gồm đa kế thừa, lớp trừu tượng, hàm tĩnh, hàm thành viên hằng, và thành viên bảo tồn

Năm 1990, cuốn The Annotated C++ Reference Manual được xuất bản cung cấp

nền tảng cho tiêu chuẩn tương lai

Phiên bản xuất bản sau đó có thêm các chức năng tiêu bản, ngoại lệ, không gian tên, chuyển kiểu cho toán tử  new , và kiểu  Boolean

Khi C++ hình thành, thì thư viện chuẩn hoàn thiện với nó Thư viện C++ đầu tiên thêm vào là  iostream.h  cung cấp cơ sở để thay thế các hàm C truyền thống như là  printf  và  scanf Sàu này, trong những thư viện chuẩn quan trọng nhất được thêm vào là Thư viện Tiêu bản Chuẩn

Sau nhiều năm làm việc, có sự cộng tác giữa ANSI và hội đồng tiêu chuẩn

hoá C++ của ISO để soạn thảo tiêu chuẩn ISO/IEC 14882:1998 Phiên bản tiêu

chuẩn này được phát hành năm 1989, hội đồng tiếp tục xử lý các báo cáo trục trặc,

và ấn hành một phiên bản sửa sai của chuẩn C++ trong năm 2003

Không ai là chủ nhân của ngôn ngữ C++, nó hoàn toàn miễn phí khi dùng

1.2.2 Sự phát triển trong tương lai

C++ tiếp tục phát triển để thỏa mãn các nhu cầu tương lai Đặc biệt

nhóm Boost.org, làm việc trên hầu hết các dạng và các khuyến cáo trong C++ cho Hội đồng Tiêu chuẩn C++ về các chức năng hoạt động tốt và các chức năng cần được cải thiện Công việc hiện tại cho thấy bản năng đa mẫu hình của C++ sẽ

ngày càng nhiều Chuẩn C++ không đề cập về sự thiết lập của mã hóa tên (name

decoration), xử lý ngoại lệ và sự thiết lập các tính năng đặc biệt khác, tạo mã đối

tượng mà nó được làm ra từ những trình biên dịch không tương thích khác Dù vậy, vẫn có những tiêu chuẩn khác từ các nhà sản xuất dùng cho những máy hay

OS riêng biệt nhằm tiêu chuẩn hóa các trình biên dịch trên các nền tảng đó

Các trình biên dịch cho đến gần đây (2004) vẫn lưỡng lự khi hỗ trợ toàn bộ chuẩn C++, đặc biệt là trong những lãnh vực của tiêu bản (đây là phần ngôn ngữ đã được công nhận hoàn toàn từ hội đồng tiêu chuẩn Trình biên dịch đầu tiên thiết kế kiểu này là Comeau C++, đầu năm 2003 ; trong năm 2004, phiên bản beta trình biên dịch của Borland C++ Builder X cũng hỗ trợ dùng  export Cả hai trình biên dịch đó dựa trên phần tương tác ngoại vi (front-end) của EDG C++ Cũng cần lưu

ý rằng nhiều sách cung cấp mã

Nhiều vấn đề về tiêu bản bao gồm các xây dựng như đặc biệt hóa tiêu bản từng phần, mà đã được hỗ trợ một cách nghèo nàn trong nhiều năm sau khi chuẩn C++ đã ra đời

1.3 Cấu trúc chương trình C++

Một chương trình C++ cơ bản sẽ gồm 3 thành phần sau:

 Các câu lệnh và biểu thức (Statements and expressions)

 Hàm (Functions)

 Thư viện chuẩn C++

1.3.1 Câu lệnh và biểu thức

 Các câu lệnh và biểu thức là thành phần nhỏ nhất để cấu thành lên một chương trình

 Một chương trình có thể gồm rất nhiều câu lệnh nhưng cũng có thể không có câu lệnh nào (phần này mình sẽ nói sau)

 Mỗi một câu lệnh sẽ yêu cầu chương trình thực hiện một nhiệm vụ nhất định

 Câu lệnh phải kết thúc bằng dấu chấm phẩy “ ; ”

Ví dụ:

1

2

3

int x;

x = 5 * 2;

cout << "Xin chao cac ban!";

Phân tích ví dụ:

Dòng 1: Câu lệnh khai báo biến có tên là x.

Dòng 2: Là câu lệnh gán giá trị cho biến x Ở đây biến x được gán giá trị bằng kết quả của biểu thức 5 * 2;

Dòng 3: Câu lệnh có nhiệm vụ đưa dữ liệu lên màn hình

1.3.2 Hàm (functions)

 Hàm là một nhóm các câu lệnh được tập hợp lại để thực hiện một nhiệm vụ nào đó

 Với bất cứ một chương trình C++ nào cũng đều phải có ít nhất là một hàm

main().

1.3.3 Thư viện chuẩn C++

Thư viện là một tập hợp các mã được biên dịch sẵn, được đóng gói lại để lập trình viên sử dụng, mà không cần phải viết lại Chẳng hạn: bạn viết một chương trình tính toán, bạn có thể include thư viện toán học…

Ví dụ:

1

2

3

#include <iostream>

#include <math.h>

#include <fstream>

Phân tích :

Dòng 1: Khai báo thư viện có tên iostream Thư viện này cung cấp cho chúng ta khả năng nhập xuất dữ liệu cơ bản với chương trình

Dòng 2: Khai báo thư viện toán học Khi chúng ta cần dùng đến căn bậc 2 hay bình phương… Thư viện này sẽ giúp chúng ta làm được điều đó

Dòng 3: Khai báo thư viện fstream Giúp chúng ta có thể làm việc với các file nằm ngoài chương trình

Thư viện là một phần không thể thiếu với người lập trình Có thư viện công việc của các bạn sẽ trở nên dễ dàng hơn

1.4 C++ các chức năng hướng đối tượng

C++ dẫn nhập thêm một số chức năng hướng đối tượng (OO) lên C Nó cung cấp các lớp mà có 4 chức năng thông dụng trong các ngôn ngữ OO: tính trừu tượng, tính đóng gói, tính đa hình, và tính kế thừa

1.4.1.Tính đóng gói

C++ xây dựng tính đóng bằng cách cho phép mọi thành viên của một lớp có thể được khai báo bằng các từ khoá  public ,  private  hay  protected Một thành viên  private  chỉ có thể được truy cập từ các phương pháp (hàm nội tại) là thành viên của chính lớp đó hay được truy cập từ các hàm và các lớp được đặc biệt cho phép sử dụng bằng cách dùng từ khóa  friend Một thành viên  protected  của một lớp sẽ có thể truy cập được từ các thành viên (nào đó) của các lớp có tính kế thừa của nó hay cũng có thể truy cập được từ các thành viện của chính lớp đó và của mọi thành viên  friend

Nguyên lý của OOP là mọi và chỉ có các hàm là có thể truy cập được đến các giá trị nội tại của cùng lớp thì nên có tính đóng C++ có hỗ trợ đặc tính này (qua các hàm thành viên và các hàm  friend ), nhưng C++ lại không là yêu cầu bắt buộc: người lập trình có thể khai báo các phần hay tất cả các giá trị nội tại là công

cộng (public), và cũng cho phép làm cho toàn bộ lớp trở thành công cộng Lý do là

vì C++ hỗ trợ không chỉ lập trình hướng đối tượng mà còn hỗ trợ các mẫu hình yếu hơn như là lập trình module

Một thói quen tốt cần có trong thực hành là khai báo mọi dữ liệu đều là riêng

tư (private), hay ít nhất ở dạng bảo tồn, và sau đó, tạo ra một giao diện nhỏ (thông

qua các phương pháp) cho người dùng của lớp này dấu đi các chi tiết thiết lập bên trong

1.4.2 Tính đa hình

Khái niệm đa hình được dùng khá rộng rãi và là khái niệm bị lạm dụng cũng như không được định nghĩa rõ ràng

Nói chung tính đa hình trong lập trình hướng muốn nói đến 1 đoạn code nhưng trong 2 trường hợp khác nhau có thể xuất ra 2 kết quả khác nhau Vì tính chất ra nhiều kết quả khác nhau này nên nó được gọi là đa hình

Trong trường hợp của C++, khái niệm này thường được nối kết với các tên của các hàm thành viên Các hàm thành viên này có cùng tên, sự khác nhau chỉ có thể được dựa vào một hay cả hai yếu tố sau:

1 Số lượng và kiểu của các đối số (tức là nguyên mẫu của hàm) Tính chất này

gọi là đa hình tĩnh (static polymorphism)

2 Kiểu lớp mà thực thể thực sự thuộc vào Tính chất này được dùng khi hàm

thành viên được định nghĩa là hàm ảo qua từ khóa  virtual , tính chất này gọi

là đa hình động (dynamic polymorphism)

Khi được gọi thì chương trình sẽ tùy theo hai yếu tố trên để xác định chính xác hàm nào phải được thực thi trong số các hàm cùng tên

C++ còn cung cấp hai tính năng độc đáo cho đa hình là:

 Nạp chồng toán tử (overloading): Cho phép một toán tử hay một hàm có những ứng xử khác nhau phụ thuộc vào kiểu của các toán hạng hay các tham số tại thời điểm toán tử hay hàm được triệu gọi

 Tính ảo (virtual): Cho phép một phương thức (hàm thành viên hoặc toán tử) của lớp có ứng xử khác nhau phụ thuộc vào sự kế thừa của lớp con cháu (Xem phương thức Chao() trong ví dụ trên

Hai tính năng trên cho phép chương trình định ra nhiều sự thiết lập khác nhau của một hàm để sử dụng ứng với các kiểu (khác nhau) của các đối tượng

1.4.3 Tính kế thừa

Kế thừa từ một lớp cơ sở có thể được khai báo thông qua các đặc tính công cộng, bảo tồn, hay riêng tư Những đặc tính này cho phép xác định khi nào các lớp dẫn xuất hay không liên quan có thể sử dụng các thành viên công cộng, bảo tồn, hay riêng tư của lớp cơ sở Tuy nhiên, chỉ có sự kế thừa dạng công cộng là hoàn toàn theo đúng ý nghĩa của việc "kế thừa" Hai dạng khác thì ít được dùng hơn Nếu các đặc tả này không được khai báo thì việc kế thừa được gán mặc định là dạng riêng

tư cho lớp cơ sở và dạng công cộng cho một cấu trúc cơ sở

Các lớp cơ sở có thể được khai báo là ảo (thông qua từ khóa  virtual ) Kế thừa ảo bảo đảm rằng chỉ có một thực thể của lớp cơ sở tồn tại trong đồ thị kế thừa, tránh được một số vấn đề mơ hồ của việc đa kế thừa

Đa kế thừa cũng là một tính năng có nhiều tranh cãi trong C++ Tính đa kế thừa cho phép một lớp được dẫn xuất từ nhiều hơn một lớp cơ sở; điều này có thể dẫn tới một đồ thị phức tạp của các quan hệ kế thừa Ví dụ, lớp "Buổi học" có thể kế thừa từ hai lớp "thời gian" và "bộ môn" Một số ngôn ngữ khác như Java, tiến hành cách thức tương tự bằng cách cho phép kế thừa của nhiều  giao diện  trong khi giới hạn số lượng của các lớp cơ sở (kế thừa) chỉ còn là một lớp ( giao diện , không như

lớp, không cho phép thiết lập nội dung của các thành viên và do đó không thể có thực thể)

1.5 Biên dịch chương trình C++

Để biên dịch một chương trình viết bởi ngôn ngữ C++, chúng ta cần trải qua

4 bước sau đây Các bước này được thực thi tự động trong trình biên dịch của C+

+.

1 Preprocessor (tiền xử lý)

Đây là bước đầu tiên trong quá trình biên dịch chương trình Tại đây sẽ thực

hiện các công đoạn chuẩn bị trước khi chúng ta bắt đầu xử lý chính trong chương

trình C++

Nói một cách đơn giản thì nếu việc biên dịch mã nguồn C++ là công việc nấu cơm thì tại Preprocessing (tiền xử lý) chúng ta sẽ tiến hành chuẩn bị gạo, rửa rau cắt thịt v.v trước khi bắt đầu nấu cơm vậy.Có thể kể đến một số xử lý ở

Preprocessing (tiền xử lý) trong biên dịch C++ như sau:

 Load và đọc các library cần thiết sử dụng trong chương trình

 Mở rộng các marcro được định nghĩa sau từ khóa define

 Xử lý trước các lệnh bắt đầu sau ký tự #

 Xóa comment trong mã nguồn, và biên dịch trước một số bộ phận

trong mã nguồn

2 Compiler (biên dịch)

Tiếp theo Preprocessor chính là Compiler (biên dịch) - xử lý chính trong trình biên dịch chương trình C++ Dựa vào compiler, mã nguồn được viết trong file

C++ từ ngôn ngữ bậc cao mà con người hiểu được sẽ được biên dịch sang ngôn

ngữ assembly ở dạng các mã assembly code Ngôn ngữ assembly ở đây là ngôn

ngữ bậc thấp, là ngôn ngữ trung gian giữa ngôn ngữ bậc cao và ngôn ngữ máy tính,

có tác dụng chuyển ngôn ngữ bậc cao sang dạng các chỉ thị 1 đối 1 cho máy tính Compiler ở đây theo nghĩa hẹp có nghĩa là quá trình biên dịch mã nguồn C++ sang ngôn ngữ assembly

3 Assembler (tập hợp)

Tiếp theo, trình tập hợp Assembler sẽ chuyển đổi các mã assembly code đã dịch ở Compiler ở trên thành các mã máy tính - loại ngôn ngữ mà máy tính có thể hiểu được Các mã máy tính này được biểu diễn bởi số 0 và số 1, và được tập hợp trong một file máy tính

Mặc dù tại giai đoạn này, mã nguồn của chương trình C++ đã được chuyển thành một file ở dạng mà máy tính có thể hiểu được, nhưng ở giai đoạn này do chúng ta chưa liên kết đủ đủ thông tin trong file, nên file này chưa thể thực thi một cách bình thường được

4 Linker (liên kết)

Đây là bước cuối cùng trong biên dịch chương trình trong C++ Tại đây, chúng ta sử dụng trình liên kết Linker để liên kết các thông tin còn thiếu như các thư viện (library) chẳng hạn vào file máy tính đã tạo ở Assembler Việc liên kết thông tin cuối cùng đã hoàn thành được file máy tính, và chúng ta có thể chạy file này một cách bình thường

 Các trình biên dịch trong C++

- Trình biên dịch trong Visual Studio

- Trình biên dịch MinGW

- Trình biên dịch C++ Compiler

- Trình biên dịch trong Dev C++

CHƯƠNG 2: THUẬT TOÁN TÌM KIẾM NHÁNH CẬN

2.1 Tìm hiểu về giải thuật

2.1.1 Thuật toán nhánh cận là gì?

Thuật toán nhánh cận là thuật toán sử dụng tìm kiếm leo đồi với hàm đánh giá f(u) Trong thuật toán này, tại mỗi bước khi phát triển trạng thái u, thì

ta sẽ chọn trạng thái tốt nhất v (f(v) nhỏ nhất) trong số các trạng thái kề u đề phát triển ở bước sau Đi xuống cho tới khi gặp trạng thái v là đích, hoặc gặp trạng thái v không có đỉnh kề, hoặc gặp trạng thái v mà f(v) lớn hơn độ dài đường đi tối ưu tạm thời, tức là đường đi đầy đủ ngắn nhất trong số các đường

đi đầy đủ mà ta đã tìm ra Trong các trường hợp này, ta không phát triển đỉnh v nữa, hay nói cách khác, ta cất đi các nhánh cây xuất phát từ v, và quay lên cha của v đề tiếp tục đi xuống trạng thái tốt nhất trong các trạng thái còn lại chưa được phát triển

2.1.2 Năm ra đời giải thuật và tác giả

Tên tiếng anh là : Branch and Bound algorithm Kỹ thuật này được đề xuất đầu tiên bởi Alía Land và Alison Doig thực hiện nghiên cứu tại trường kinh tế LonDon vào năm 1960 để lập trình rời rạc