Sự khác biệt giữa heuristic và thuật toán là gì?

Question

Sự khác nhau giữa heuristic và thuật toán là gì?

Answer 1

Thuật toán là mô tả về giải pháp tự động cho sự cố. Thuật toán nào được định nghĩa chính xác. Giải pháp có thể hoặc không thể là giải pháp tốt nhất có thể nhưng bạn biết ngay từ đầu bạn sẽ nhận được loại kết quả nào. Bạn triển khai thuật toán sử dụng một số ngôn ngữ lập trình để nhận (một phần) một chương trình .

Hiện tại, một số vấn đề khó và bạn có thể không có được giải pháp có thể chấp nhận trong thời gian chấp nhận được. Trong những trường hợp như vậy bạn thường có thể nhận được một giải pháp không quá xấu nhanh hơn nhiều, bằng cách áp dụng một số lựa chọn tùy ý (phỏng đoán được giáo dục): đó là heuristic.

Một heuristic vẫn là một loại thuật toán, nhưng một thuật toán sẽ không khám phá tất cả các trạng thái có thể có của vấn đề, hoặc sẽ bắt đầu bằng cách khám phá những khả năng nhất.

Ví dụ điển hình là từ trò chơi. Khi viết một chương trình trò chơi cờ vua bạn có thể tưởng tượng cố gắng mọi cử động có thể ở một mức độ sâu và áp dụng một số chức năng đánh giá cho hội đồng quản trị. Một heuristic sẽ loại trừ các chi nhánh đầy đủ bắt đầu với những động thái rõ ràng là xấu.

Trong một số trường hợp, bạn không tìm kiếm giải pháp tốt nhất, nhưng đối với bất kỳ giải pháp nào phù hợp với một số hạn chế. Một heuristic tốt sẽ giúp để tìm một giải pháp trong một thời gian ngắn, nhưng cũng có thể không tìm thấy bất kỳ nếu các giải pháp duy nhất là trong các tiểu bang nó đã chọn không thử.

Answer 2

Thực ra tôi không nghĩ rằng có nhiều điểm chung giữa chúng. Một số thuật toán sử dụng các chẩn đoán trong logic của chúng (thường để tính toán ít hơn hoặc nhận được kết quả nhanh hơn). Thông thường heuristics được sử dụng trong các thuật toán tham lam được gọi là.

Heuristics là một số "kiến thức" mà chúng tôi giả định là tốt để sử dụng để có được lựa chọn tốt nhất trong thuật toán của chúng tôi (khi lựa chọn nên được thực hiện). Ví dụ ... một heuristics trong cờ vua có thể được (luôn luôn có nữ hoàng của đối thủ nếu bạn có thể, vì bạn biết đây là con số mạnh mẽ hơn). Heuristics không đảm bảo với bạn rằng sẽ dẫn bạn đến câu trả lời đúng, nhưng (nếu các giả định là chính xác) thường nhận được câu trả lời gần với tốt nhất trong thời gian ngắn hơn nhiều.

Answer 3

• Một thuật toán thường là xác định và chứng minh là mang lại một kết quả tối ưu
• Một heuristic, không có bằng chứng về tính đúng đắn, thường liên quan đến các yếu tố ngẫu nhiên, và có thể không mang lại kết quả tối ưu.

Nhiều vấn đề mà không có thuật toán hiệu quả nào tìm được giải pháp tối ưu được biết là có phương pháp tiếp cận heuristic mang lại kết quả gần như tối ưu rất nhanh.

Có một số chồng chéo: "thuật toán di truyền" là một thuật ngữ được chấp nhận, nhưng nghiêm túc nói, đó là những chẩn đoán, chứ không phải thuật toán.

Answer 4

Heuristic, tóm lại là "phỏng đoán được giáo dục". Wikipedia giải thích nó độc đáo. Cuối cùng, một phương pháp "chấp nhận chung" được lấy làm giải pháp tối ưu cho vấn đề được chỉ định.

Heuristic là một tính từ cho kỹ thuật dựa trên kinh nghiệm giúp trong giải quyết vấn đề, học tập và khám phá. Một phương pháp heuristic được sử dụng để nhanh chóng đi đến một giải pháp là hy vọng được gần với câu trả lời tốt nhất có thể là hoặc 'giải pháp tối ưu'. Điều kiện tiên quyết là "quy tắc chung", các phỏng đoán được giáo dục, phán đoán trực quan hoặc đơn giản là thông thường. Một heuristic là một cách chung để giải quyết một vấn đề. Heuristics như một danh từ là một tên khác cho các phương pháp heuristic.

Về chính xác hơn, chẩn đoán đứng cho các chiến lược sử dụng dễ dàng truy cập , mặc dù lỏng lẻo hiện hành, thông tin để kiểm soát giải quyết vấn đề trong con người và máy móc.

Trong khi thuật toán là phương pháp chứa tập hợp hữu hạn các lệnh được sử dụng để giải quyết sự cố. Phương pháp này đã được chứng minh bằng toán học hoặc khoa học để giải quyết vấn đề. Có các phương pháp và chứng minh chính thức.

Heuristic thuật toán là một thuật toán mà có thể sản xuất một giải pháp chấp nhận một vấn đề trong nhiều kịch bản thực tế, trong thời trang của một heuristic, nói chung, nhưng mà không có bằng chứng chính thức tính chính xác của nó.

Answer 5

Thuật toán là một bộ hướng dẫn được xác định rõ ràng để giải quyết vấn đề, Heuristics liên quan đến việc sử dụng phương pháp học và khám phá để đạt được giải pháp.

Vì vậy, nếu bạn biết cách giải quyết sự cố thì hãy sử dụng thuật toán. Nếu bạn cần phát triển một giải pháp thì đó là phỏng đoán.

Answer 6

Một heuristic thường là một tối ưu hóa hoặc một chiến lược thường cung cấp một câu trả lời đủ tốt, nhưng không phải luôn luôn và hiếm khi câu trả lời tốt nhất. Ví dụ, nếu bạn giải quyết vấn đề nhân viên bán hàng với lực lượng vũ phu, loại bỏ một giải pháp từng phần một khi chi phí của nó vượt quá giải pháp tốt nhất hiện tại là heuristic: đôi khi nó giúp ích, thời gian khác, và chắc chắn không t cải thiện thời gian chạy lý thuyết (big-oh notation) của thuật toán

Answer 7

Heuristics là các thuật toán, do đó, theo nghĩa đó, không có cách nào, heuristics có cách tiếp cận 'đoán' để giải quyết vấn đề, mang lại 'đủ tốt' trả lời, thay vì tìm một giải pháp 'tốt nhất có thể'.

Một ví dụ tốt là nơi bạn gặp khó khăn (đọc NP-hoàn thành) vấn đề bạn muốn một giải pháp nhưng không có thời gian để đến đó, vì vậy phải sử dụng một giải pháp đủ tốt dựa trên heuristic thuật toán, chẳng hạn như tìm giải pháp cho vấn đề người bán hàng đi du lịch bằng cách sử dụng thuật toán di truyền.

Answer 8

Thuật toán là một chuỗi các hoạt động cho đầu vào tính toán một cái gì đó (một hàm) và xuất kết quả.

Thuật toán có thể mang lại giá trị chính xác hoặc gần đúng.

Nó cũng có thể tính toán một giá trị ngẫu nhiên có xác suất cao gần với giá trị chính xác.

Thuật toán heuristic sử dụng một số thông tin chi tiết về giá trị đầu vào và tính toán không chính xác giá trị (nhưng có thể gần tối ưu). Trong một số trường hợp đặc biệt, heuristic có thể tìm ra giải pháp chính xác.

Answer 9

Tôi nghĩ rằng Heuristic là một hạn chế được sử dụng trong Mô hình dựa trên học tập trong Intelligent Intelligent vì các trạng thái giải pháp trong tương lai khó dự đoán.

Nhưng sau đó nghi ngờ của tôi sau khi đọc câu trả lời ở trên là "Làm thế nào Heuristic có thể được áp dụng thành công bằng cách sử dụng kỹ thuật tối ưu hóa Stochastic? Hoặc họ có thể hoạt động như thuật toán chính thức khi sử dụng với Stochastic Optimization?"

http://en.wikipedia.org/wiki/Stochastic_optimization

Answer 10

Họ tìm một giải pháp dưới mức tối ưu mà không cần bất kỳ sự bảo đảm như đến chất lượng của giải pháp được tìm thấy, rõ ràng là nó có ý nghĩa cho sự phát triển của công nghệ tự động chỉ đa thức. Việc áp dụng các phương pháp này phù hợp để giải quyết các vấn đề trong thế giới thực hoặc các vấn đề lớn quá khó hiểu từ quan điểm tính toán cho rằng thậm chí không có thuật toán nào có khả năng tìm ra giải pháp gần đúng trong thời gian đa thức.

Answer 11

Một trong những lời giải thích tốt nhất mà tôi đã đọc xuất phát từ cuốn sách tuyệt vời Code Complete, mà tôi bây giờ quote:

Một heuristic là một kỹ thuật giúp bạn tìm kiếm một câu trả lời. Các kết quả của nó có thể xảy ra do một heuristic chỉ cho bạn biết cách để xem, không phải những gì cần tìm. Nó không cho bạn biết làm thế nào để có được trực tiếp từ điểm A đến điểm B; nó thậm chí có thể không biết điểm A và điểm B là gì. Trong thực tế, một heuristic là một thuật toán trong một phù hợp với chú hề. Dự đoán ít khả thi hơn, vui hơn và không có bảo đảm hoàn tiền sau 30 ngày, .

Đây là thuật toán để lái xe đến nhà của một ai đó: Đi theo Quốc lộ 167 về phía nam đến Puy-allup. Đi theo lối Hill Mall Nam và lái xe 4,5 dặm lên đồi. Rẽ phải tại cửa hàng tạp hóa, rồi rẽ trái đầu tiên. Rẽ vào đường lái xe của ngôi nhà rộng lớn trên bên trái, tại 714 North Cedar.

Đây là lý do để tìm đến nhà của một ai đó: Tìm thư cuối cùng mà chúng tôi đã gửi cho bạn. Lái xe đến thị trấn trong địa chỉ trả lại. Khi bạn đến thị trấn, hãy hỏi ai đó ở đâu nhà của chúng tôi. Mọi người đều biết chúng tôi — ai đó sẽ vui lòng giúp bạn. Nếu bạn không thể tìm thấy bất kỳ ai, hãy gọi cho chúng tôi từ điện thoại công cộng và chúng tôi sẽ đến giúp bạn.

Sự khác biệt giữa thuật toán và phỏng đoán là tinh tế và một số ít nhất hai cụm từ vượt quá giới hạn. Đối với mục đích của cuốn sách này, sự khác biệt chính giữa giữa hai là mức độ gián tiếp từ giải pháp . Thuật toán cung cấp cho bạn hướng dẫn trực tiếp. A heuristic cho bạn biết cách khám phá hướng dẫn cho chính mình hoặc ít nhất là nơi để tìm kiếm chúng.

Answer 12

Một thuật toán là một bước-by-step bộ khép kín của các hoạt động được thực hiện 4, thường hiểu là một dãy hữu hạn các hướng dẫn (máy tính hay con người) để xác định một giải pháp cho một vấn đề như : có một con đường từ A đến B hay đường đi nhỏ nhất giữa A và B. Trong trường hợp thứ hai, bạn cũng có thể hài lòng với giải pháp thay thế 'hợp lý gần'.

Có một số loại thuật toán nhất định, trong đó thuật toán heuristic là một. Tùy thuộc vào các thuộc tính (đã được kiểm chứng) của thuật toán trong trường hợp này, nó rơi vào một trong ba loại (lưu ý 1):

• Exact: giải pháp được chứng minh là một tối ưu (hoặc chính xác giải pháp) cho vấn đề đầu vào
• Approximation: độ lệch của giá trị giải pháp được chứng minh là không bao giờ xa giá trị tối ưu so với một số giới hạn được xác định trước (ví dụ, không bao giờ lớn hơn 50% giá trị tối ưu))
• Heuristic: các thuật toán đã không được chứng minh là tối ưu, cũng không phải trong vòng một được xác định trước ràng buộc của giải pháp tối ưu

Chú ý rằng một thuật toán xấp xỉ cũng là một heuristic, nhưng với tài sản mạnh rằng có một đã được chứng minh ràng buộc với các giải pháp (giá trị) nó kết quả đầu ra.

Đối với một số vấn đề, không ai đã từng tìm thấy thuật toán 'hiệu quả' để tính toán các giải pháp tối ưu (lưu ý 2). Một trong những vấn đề đó là vấn đề người bán hàng du lịch nổi tiếng. Thuật toán của Christophides cho vấn đề người bán hàng du lịch, ví dụ, được sử dụng để được gọi là heuristic, vì nó đã không được chứng minh rằng nó nằm trong phạm vi 50% của giải pháp tối ưu. Vì nó đã được chứng minh, tuy nhiên, thuật toán của Christophides được gọi chính xác hơn là một thuật toán xấp xỉ.

Do hạn chế về những gì máy tính có thể làm, không phải lúc nào cũng có thể hiệu quả tìm giải pháp tốt nhất có thể. Nếu có đủ cấu trúc trong một vấn đề, có thể có một cách hiệu quả để đi qua không gian giải pháp, mặc dù không gian giải pháp là rất lớn (tức là trong vấn đề đường đi ngắn nhất).

Phương pháp chẩn đoán thường được áp dụng để cải thiện thời gian chạy các thuật toán, bằng cách thêm 'thông tin chuyên gia' hoặc 'dự đoán được giáo dục' để hướng dẫn hướng tìm kiếm. Trong thực tế, một heuristic cũng có thể là một thói quen phụ cho một thuật toán tối ưu, để xác định nơi để xem đầu tiên.

(lưu ý 1): Ngoài ra, các thuật toán được đặc trưng bởi chúng bao gồm các yếu tố ngẫu nhiên hay không xác định. Một thuật toán luôn luôn thực thi cùng một cách và tạo ra cùng một câu trả lời, được gọi là xác định.

(lưu ý 2): Điều này được gọi là vấn đề P vs NP và các vấn đề được phân loại là NP-complete và NP-hard không có thuật toán 'hiệu quả'. Chú thích; như @Kriss được đề cập trong các nhận xét, thậm chí có các loại sự cố 'tồi tệ hơn', có thể cần thời gian hoặc không gian theo thời gian để tính toán.

Có một số câu trả lời trả lời một phần câu hỏi. Tôi cho rằng chúng không đầy đủ và không đủ chính xác và quyết định không chỉnh sửa câu trả lời được chấp nhận bởi @Kriss