Python - Các lớp thuật toán

Các thuật toán là các bước rõ ràng sẽ cung cấp cho chúng ta một đầu ra được xác định rõ ràng bằng cách xử lý không hoặc nhiều đầu vào. Điều này dẫn đến nhiều cách tiếp cận trong việc thiết kế và viết các thuật toán. Người ta quan sát thấy rằng hầu hết các thuật toán có thể được phân loại thành các loại sau.

Thuật toán tham lam

Các thuật toán tham lam cố gắng tìm một giải pháp tối ưu được bản địa hóa, điều này cuối cùng có thể dẫn đến các giải pháp được tối ưu hóa toàn cầu. Tuy nhiên, các thuật toán tham lam nói chung không cung cấp các giải pháp tối ưu hóa toàn cầu.

Vì vậy, các thuật toán tham lam tìm kiếm một giải pháp dễ dàng tại thời điểm đó mà không xem xét nó tác động như thế nào đến các bước trong tương lai. Nó tương tự như cách con người giải quyết vấn đề mà không cần xem qua chi tiết đầy đủ của các đầu vào được cung cấp.

Hầu hết các thuật toán mạng sử dụng cách tiếp cận tham lam. Đây là danh sách một vài trong số họ -

Vấn đề nhân viên bán hàng đi du lịch
Thuật toán cây kéo dài tối thiểu của Prim
Thuật toán cây kéo dài tối thiểu của Kruskal
Thuật toán cây kéo dài tối thiểu của Dijkstra

Phân chia và chinh phục

Loại thuật toán này liên quan đến việc chia bài toán đã cho thành các bài toán con nhỏ hơn và sau đó giải quyết từng bài toán con một cách độc lập. Khi vấn đề không thể được chia nhỏ hơn nữa, chúng tôi bắt đầu hợp nhất giải pháp cho từng vấn đề phụ để đi đến giải pháp cho vấn đề lớn hơn.

Các ví dụ quan trọng của thuật toán chia và thu là:

Hợp nhất Sắp xếp
Sắp xếp nhanh chóng
Thuật toán cây kéo dài tối thiểu của Kruskal
Tìm kiếm nhị phân

Lập trình năng động

Lập trình động liên quan đến việc chia vấn đề lớn hơn thành những vấn đề nhỏ hơn nhưng không giống như chia và chinh phục, nó không liên quan đến việc giải quyết từng vấn đề con một cách độc lập. Thay vào đó, kết quả của các bài toán con nhỏ hơn được ghi nhớ và sử dụng cho các bài toán con tương tự hoặc chồng chéo. Hầu hết, các thuật toán này được sử dụng để tối ưu hóa. Trước khi giải bài toán con trong tay, thuật toán động sẽ cố gắng kiểm tra kết quả của các bài toán con đã giải trước đó.

các thuật toán động được thúc đẩy để tối ưu hóa tổng thể vấn đề chứ không phải tối ưu hóa cục bộ.

Các ví dụ quan trọng của thuật toán lập trình động là:

Chuỗi số Fibonacci
Knapsack vấn đề
Tháp Hà Nội