Thuật toán không đơn định

Trong lý thuyết tính toán, một thuật toán không đơn định là một thuật toán có một hoặc nhiều điểm lựa chọn, mà tại đó có nhiều hướng đi tiếp khác nhau mà không được chỉ rõ hướng nào sẽ được chọn. Mỗi thực thi cụ thể của một thuật toán như vậy chọn lấy một hướng mỗi khi gặp một điểm lựa chọn. Do đó, khi áp dụng cho cùng một dữ liệu đầu vào và trạng thái khởi tạo, có thể có các đường thực thi khác nhau của thuật toán đó, và khi kết thúc, các đường thực thi này thường cho kết quả là các dữ liệu ra khác nhau hoặc kết thúc tại các trạng thái cuối cùng khác nhau.

Ví dụ: Tour du lịch qua n thành phố

Bài toán: cho n thành phố và một số tuyến đường nối một số cặp hai thành phố. Câu hỏi là có hay không một tour đi qua n thành phố và quay lại chỗ cũ mà không đi qua thành phố nào quá 1 lần.

Dưới đây là một ví dụ về một thuật toán không đơn định dùng để kiểm tra xem có tồn tại một tour như trên hay không.

1. Chọn một hoán vị của n thành phố. Giả sử ta được {c₁,c₂,..,c_n}
2. Nếu với mọi i từ 1 đến n, ta có tuyến đường trực tiếp giữa hai thành phố c_i và c_i+1, và giữa c₁ và c_n cũng có đường nối trực tiếp, thuật toán kết thúc với kết quả có; nếu không, thuật toán kết thúc với kết quả không biết.

Ta thấy rằng thuật toán này không phải lúc nào cũng cho ra một kết quả hữu ích, nhưng nó không bao giờ đưa ra câu trả lời sai. Ngoài ra, nó có thể (đôi khi) đưa ra câu trả lời đúng và có ích một cách nhanh chóng hơn bất kỳ thuật toán đơn định nào cho bài toán này.

Xem thêm

• Máy Turing không đơn định (Non-deterministic Turing machine)
• Ôtômát hữu hạn không đơn định (Nondeterministic finite state machine)