tailieunhanh - Giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p5

Tham khảo tài liệu 'giáo trình hình thành hệ thống ứng dụng nguyên lý điều khiển luồng theo tiến trình biểu diễn số p5', kỹ năng mềm, kỹ năng tư duy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | luôn được duy trì ở đây n là số lượng nút trong graph e là số cạnh được lựa chọn tính cho tới thời điểm xét và c là số lượng thành phần trong graph tính cho tới thời điểm xét. Ở cuối thuật toán e bằng n trừ đi số thành phần trong graph gốc nếu graph gốc là liên thông chúng ta sẽ tìm được một cây có n-1 cạnh. Như đã giải thích ở trên Dfs sẽ tìm ra một rừng bắc cầu. Tuy nhiên chúng ta thường không tìm được cây bắc cầu có tổng độ dài tối thiểu. Thuật toán háu ăn Một cách tiếp cận khả dĩ để tìm một cây có tổng độ dài tối thiểu là ở mỗi giai đoạn của thuật toán lựa chọn cạnh ngắn nhất có thể. Thuật toán đó gọi là thuật toán háu ăn . Thuật toán này có tính chất thiển cận nghĩa là không lường trước được các kết quả cuối cùng do các quyết định mà chúng đưa ra ở mỗi bước gây ra. Thay vào đó chúng chỉ đưa ra cách chọn tốt nhất cho mỗi quá trình lựa chọn. Nói chung thuật toán háu ăn không tìm được lời giải tối ưu cho một bài toán. Thực tế thuật toán thậm chí còn không tìm được một lời giải khả thi ngay cả khi lời giải đó tồn tại. Tuy nhiên chúng hiệu quả và dễ thực hiện. Chính vì vậy chúng được sử dụng rộng rãi. Các thuật toán này cũng thường tạo cơ sở cho các thuật toán có tính hiệu quả và phức tạp hơn. Vì thế câu hỏi đầu tiên đặt ra khi xem xét việc ứng dụng một thuật toán để giải quyết một bài toán là liệu bài toán ấy có hay không cấu trúc nào đó đảm bảo cho thuật toán hoạt động tốt. Hy vọng rằng thuật toán ít ra cũng đảm bảo được một lời giải khả thi nếu lời giải đó tồn tại. Khi đó nó sẽ đảm bảo tính tối ưu và đảm bảo yêu cầu nào đó về thời gian thực hiện. Bài toán tìm các cây bắc cầu tối thiểu thực sự có một cấu trúc mạnh cho phép thuật toán háu ăn đảm bảo cả tính tối ưu cũng như đảm bảo độ phức tạp tính toán ở mức độ vừa phải. Dạng chung của thuật toán háu ăn là Bắt đầu bằng một lời giải rỗng s. T rong khi vẫn còn có các phần tử cần xét Tìm e phần tử tốt nhất vẫn chưa xét Nếu việc thêm e vào s là khả thi thì e được thêm vào s nếu việc thêm đó không khả thi thì loại bỏ .