Mục lục:
Định nghĩa - Thuật toán không xác định nghĩa là gì?
Một thuật toán không xác định có thể cung cấp các đầu ra khác nhau cho cùng một đầu vào trên các lần thực hiện khác nhau. Không giống như một thuật toán xác định chỉ tạo ra một đầu ra cho cùng một đầu vào ngay cả trên các lần chạy khác nhau, thuật toán không xác định di chuyển theo các tuyến khác nhau để đi đến các kết quả khác nhau.
Các thuật toán không xác định rất hữu ích cho việc tìm các giải pháp gần đúng, khi một giải pháp chính xác rất khó hoặc tốn kém để sử dụng thuật toán xác định.
Techopedia giải thích thuật toán không xác định
Một ví dụ về thuật toán không xác định là việc thực hiện các thuật toán đồng thời với các điều kiện chủng tộc, có thể thể hiện các đầu ra khác nhau trên các lần chạy khác nhau. Không giống như một thuật toán xác định di chuyển một đường dẫn duy nhất từ đầu vào đến đầu ra, một thuật toán không xác định có thể có nhiều đường dẫn, với một số đến cùng một đầu ra và các thuật toán khác đến các đầu ra khác nhau. Tính năng này được sử dụng một cách toán học trong các mô hình tính toán không xác định như tự động hữu hạn không xác định.
Một thuật toán không xác định có khả năng thực thi trên một máy tính xác định có số lượng bộ xử lý song song không giới hạn. Một thuật toán không xác định thường có hai giai đoạn và các bước đầu ra. Giai đoạn đầu tiên là giai đoạn đoán, sử dụng các ký tự tùy ý để chạy vấn đề.
Pha thứ hai là pha xác minh, trả về giá trị đúng hoặc sai cho chuỗi đã chọn. Có nhiều vấn đề có thể được khái niệm hóa với sự trợ giúp của các thuật toán không xác định bao gồm cả vấn đề chưa được giải quyết của P vs NP trong lý thuyết điện toán.
Các thuật toán không xác định được sử dụng để giải quyết các vấn đề cho phép nhiều kết quả. Mọi kết quả mà thuật toán không xác định tạo ra là hợp lệ, bất kể các lựa chọn của thuật toán trong quá trình thực thi.
