Một số phương pháp thiết kế
Trên cơ sở lý thuyết máy Turing, ta chia được các bài toán thành 2 lớp không giao nhau : Lớp giải được bằng thuật toán , và lớp không giải được bằng thuật toán. Đối với lớp các bài toán giải được bằng thuật toán, dựa vào ...
Trên cơ sở lý thuyết máy Turing, ta chia được các bài toán thành 2 lớp không giao nhau : Lớp giải được bằng thuật toán , và lớp không giải được bằng thuật toán.
Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của quá trình thiết kế của thuật toán, ta có thể chỉ ra một số các phương pháp thiết kế thuật toán cơ bản sau đây :
Ý tưởng là : Chia dữ liệu thành từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả lại .
Chẳng hạn như thuật toán Quicksort.
Ý tưởng là: Tìm kiếm theo ưu tiên. Đối với mỗi bước thuật toán, ưu tiên theo độ rộng hay chiều sâu để tìm kiếm.
Chẳng hạn thuật toán giải bài toán 8 hậu.
Ý tưởng là : Xác định trật tự xử lý để có lợi nhất, Sắp xếp dữ liệu theo trật tự
đó, rồi xử lý dữ liệu theo trật tự đã nêu. Công sức bỏ ra là tìm ra trật tự đó.
Chẳng hạn thuật toán tìm cây bao trùm nhỏ nhất (Shortest spanning Trees).
Phương pháp quy hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của Bellman :
- Nếu lời giải của bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu. Phương pháp này tổ chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các bài toán con nhỏ và đơn giản nhất, tổ hợp các lời giải của chúng để có lời giải của bài toán con lớn hơn...và cứ như thế cuối cùng được lời giải của bài toán ban đầu.
Chẳng hạn thuật toán “chiếc túi xách” (Knapsack).
