Sự khác biệt giữa thuật toán ngẫu nhiên và thuật toán heuristic

Question

Mở rộng question of streetparade, tôi muốn hỏi sự khác biệt, nếu có, giữa thuật toán ngẫu nhiên và thuật toán heuristic.

Có thể nói rằng thuật toán ngẫu nhiên thực sự là một loại heuristic?

cách tiếp cận

Answer 1

TTBOMK, "ngẫu nhiên thuật toán" không phải là một thuật ngữ tiêu chuẩn. "Thuật toán ngẫu nhiên" là, tuy nhiên, và nó có lẽ là những gì có nghĩa là ở đây.

Ngẫu nhiên: Sử dụng ngẫu nhiên bằng cách nào đó. Có hai hương vị: Thuật toán Monte Carlo luôn kết thúc trong thời gian giới hạn, nhưng không đảm bảo giải pháp tối ưu, trong khi các thuật toán Las Vegas không nhất thiết được đảm bảo hoàn thành trong bất kỳ thời gian hữu hạn nào, nhưng hứa sẽ tìm giải pháp tối ưu . (Thông thường, chúng cũng được yêu cầu có thời gian hoạt động là hữu hạn dự kiến ​​.) Ví dụ về các thuật toán phổ biến của Monte Carlo: MCMC, mô phỏng ủ và thử nghiệm nguyên thủy Miller-Rabin. Quicksort với sự lựa chọn trục ngẫu nhiên là một thuật toán Las Vegas luôn luôn kết thúc trong thời gian hữu hạn. Thuật toán không sử dụng bất kỳ ngẫu nhiên nào là xác định.

Heuristic: Không được đảm bảo để tìm câu trả lời đúng. Một thuật toán không phải là heuristic là chính xác.

Nhiều phỏng đoán rất nhạy cảm với các thuộc tính "ngẫu nhiên" của đầu vào không ảnh hưởng đến giải pháp thực, chẳng hạn như các mục đặt hàng được xem xét trong phỏng đoán đầu tiên cho vấn đề Bin Packing. Trong trường hợp này, chúng có thể được coi là thuật toán ngẫu nhiên của Monte Carlo: bạn có thể hoán đổi ngẫu nhiên các đầu vào và chạy lại chúng, luôn giữ câu trả lời tốt nhất mà bạn tìm thấy.OTOH, các chẩn đoán khác không có thuộc tính này - ví dụ: Phương pháp heuristic đầu tiên-giảm-giảm là xác định, vì nó luôn luôn sắp xếp các mục theo thứ tự giảm kích thước.

Nếu tập hợp đầu ra có thể có của một thuật toán ngẫu nhiên đặc biệt là hữu hạn và chứa câu trả lời đúng, sau đó chạy nó đủ lâu là "thực tế được bảo đảm" để cuối cùng tìm thấy nó (theo nghĩa là xác suất không tìm thấy nó có thể được thực hiện tùy ý nhỏ, nhưng không bao giờ 0). Lưu ý rằng nó không tự động khi một số hoán vị của các đầu vào cho heuristic sẽ dẫn đến câu trả lời chính xác - trong trường hợp của First-Fit, nó chỉ ra rằng là đúng, nhưng điều này chỉ được chứng minh trong năm 2009 Đôi khi các câu lệnh mạnh hơn về sự hội tụ của các thuật toán ngẫu nhiên có thể được thực hiện: chúng thường nằm dọc theo dòng "Đối với bất kỳ ngưỡng nhỏ nào d, sau bước t, chúng tôi sẽ nằm trong d của giải pháp tối ưu với xác suất f (t, d) ", với f (t, d) hàm tăng t và d.

Answer 2

Booth thường được sử dụng để tăng tốc độ genere và thử nghiệm giải pháp cho NP vấn đề hoàn

1. thuật toán Stochastic sử dụng ngẫu nhiên

   Họ sử dụng tất cả các kết hợp nhưng không theo thứ tự nhưng thay vào đó họ sử dụng những cái ngẫu nhiên từ toàn bộ các khả năng hy vọng sẽ đạt được giải pháp sớm hơn. Thực hiện là nhanh chóng lặp dễ dàng và đơn cũng nhanh (thời gian liên tục)

2. Heuristics thuật toán

   Họ nhặt kết hợp không ngẫu nhiên nhưng dựa trên một số kiến ​​thức về quá trình sử dụng, dữ liệu đầu vào, hoặc sử dụng để thay thế. Vì vậy, họ giảm số lượng các kết hợp đáng kể để chỉ những người họ có lẽ là giải pháp và chỉ sử dụng những người đó nhưng thường là tất cả trong số họ cho đến khi giải pháp được tìm thấy.

   Độ phức tạp thực hiện phụ thuộc vào vấn đề, lặp lại đơn thường chậm hơn nhiều so với cách tiếp cận ngẫu nhiên (thời gian không đổi) để chẩn đoán chỉ được sử dụng nếu số khả năng được hạ xuống đủ để tăng tốc thực tế. dựa trên kinh nghiệm thường là thấp hơn nhiều đôi khi hằng số thời gian là đủ lớn để mặc mọi thứ chậm lại ... (về thời gian chạy)

Booth phương pháp tiếp cận có thể được kết hợp với nhau