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ố

[sửa | sửa mã nguồn]

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 {c1,c2,..,cn}
  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ố cici+1, và giữa c1cn cũng có đường nối trực tiếp, thuật toán kết thúc với kết quả ; 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.

Tham khảo

[sửa | sửa mã nguồn]
Chúng tôi bán
Bài viết liên quan
Vài câu tỏ tình hàng tuyển
Vài câu tỏ tình hàng tuyển
Những lời tỏ tình với đôi chút lãn mạn và một bầu trời yêu thương
Tải Game Dra+Koi - Long Ái Việt hóa
Tải Game Dra+Koi - Long Ái Việt hóa
Dra+Koi là một trò chơi điện tử thuộc thể loại nhập vai (RPG) kết hợp với yếu tố chiến thuật và nuôi dưỡng sinh vật
Evil Does Not Exist: ở nơi đâu cái ác không tồn tại?
Evil Does Not Exist: ở nơi đâu cái ác không tồn tại?
Lòng tốt có tồn tại, tình yêu có tồn tại, lòng vị tha có tồn tại, nhưng cái ác lại không tồn tại.
[Review] Visual Novel Steins;Gate Zero – Lời hứa phục sinh
[Review] Visual Novel Steins;Gate Zero – Lời hứa phục sinh
Steins;Gate nằm trong series Sci-fi của Nitroplus với chủ đề du hành thời gian. Sau sự thành công vang dội ở cả mặt Visual Novel và anime