휴리스틱과 알고리즘의 차이점은 무엇입니까?

휴리스틱과 알고리즘의 차이점은 무엇입니까?

---

휴리스틱과 알고리즘의 차이점은 무엇입니까?

---

알고리즘은 문제 에 대한 자동화 된 솔루션에 대한 설명입니다 . 알고리즘이하는 일은 정확하게 정의됩니다. 해결책이 최선일 수도 있고 아닐 수도 있지만 처음부터 어떤 종류의 결과를 얻을 수 있는지 알고 있습니다. 당신은 구현 알고리즘을 A (의 일부) 얻기 위해 몇 가지 프로그래밍 언어를 사용하여 프로그램을 .

이제 일부 문제는 어렵고 수용 가능한 시간 내에 수용 가능한 솔루션을 얻지 못할 수 있습니다. 이러한 경우, 임의의 선택 (교육 된 추측)을 적용하여 그리 나쁘지 않은 솔루션을 훨씬 더 빨리 얻을 수 있습니다. 그것은 휴리스틱 입니다.

휴리스틱은 여전히 ​​일종의 알고리즘이지만 문제의 가능한 모든 상태를 탐색하지 않거나 가장 가능성이 높은 상태를 탐색하는 것으로 시작합니다.

전형적인 예는 게임입니다. 체스 게임 프로그램을 작성할 때 가능한 모든 동작을 어느 정도 깊이 수준에서 시도하고 일부 평가 기능을 보드에 적용하는 것을 상상할 수 있습니다. 휴리스틱은 명백하게 잘못된 동작으로 시작하는 전체 분기를 제외합니다.

어떤 경우에는 최상의 솔루션을 찾지 않고 제약 조건에 맞는 솔루션을 찾습니다. 좋은 휴리스틱은 짧은 시간에 솔루션을 찾는 데 도움이 될 수 있지만 시도하지 않기로 선택한 상태에 유일한 솔루션이있는 경우에는 찾지 못할 수도 있습니다.

---

• 알고리즘은 일반적으로 결정적이며 최적의 결과를 산출하는 것으로 입증되었습니다.
• 휴리스틱은 정확성에 대한 증거가 없으며 종종 임의의 요소를 포함하며 최적의 결과를 산출하지 못할 수 있습니다.

최적의 솔루션을 찾기위한 효율적인 알고리즘이 알려져 있지 않은 많은 문제에는 거의 최적의 결과를 매우 빠르게 생성하는 휴리스틱 접근 방식이 있습니다.

몇 가지 중복되는 부분이 있습니다. "유전 알고리즘"은 허용되는 용어이지만 엄밀히 말하면 알고리즘이 아니라 휴리스틱입니다.

---

휴리스틱은 간단히 말해서 "교육 된 추측"입니다. Wikipedia는 그것을 잘 설명합니다. 마지막으로 "일반 수용"방법이 지정된 문제에 대한 최적의 솔루션으로 간주됩니다.

휴리스틱은 문제 해결, 학습 및 발견에 도움이되는 경험 기반 기술의 형용사입니다. 휴리스틱 방법은 가능한 최선의 답변 또는 '최적 솔루션'에 가까워지기를 희망하는 솔루션을 신속하게 도출하는 데 사용됩니다. 휴리스틱은 "경험의 법칙", 교육받은 추측, 직관적 판단 또는 단순한 상식입니다. 휴리스틱은 문제를 해결하는 일반적인 방법입니다. 명사로서의 휴리스틱 스는 휴리스틱 방법의 또 다른 이름입니다.

좀 더 정확하게 말하면, 휴리스틱은 쉽게 접근 할 수있는 정보를 사용하여 인간과 기계의 문제 해결을 제어하는 ​​전략을 의미합니다.

알고리즘은 문제를 해결하는 데 사용되는 유한 한 명령 집합을 포함하는 방법입니다. 이 방법은 문제를 해결하기 위해 수학적으로 또는 과학적으로 입증되었습니다. 공식적인 방법과 증명이 있습니다.

휴리스틱 알고리즘 은 일반적인 휴리스틱 방식으로 많은 실제 시나리오에서 문제에 대한 수용 가능한 솔루션을 생성 할 수 있지만 정확성에 대한 공식적인 증거는없는 알고리즘입니다.

---

사실 저는 그들 사이에 공통점이 많지 않다고 생각합니다. 일부 알고리즘은 논리에 휴리스틱을 사용합니다 (종종 더 적은 계산을 수행하거나 더 빠른 결과를 얻기 위해). 일반적으로 휴리스틱 스는 소위 탐욕스러운 알고리즘에서 사용됩니다.

휴리스틱 스는 알고리즘에서 최선의 선택을하기 위해 사용하는 것이 좋다고 가정하는 "지식"입니다 (선택을해야 할 때). 예를 들어 ... 체스의 휴리스틱은 (당신이 할 수 있다면 항상 상대방의 여왕을 가져 가십시오. 이것이 더 강한 인물이라는 것을 알고 있기 때문입니다). 휴리스틱 스가 정답으로 이어질 것이라고 보장하지는 않지만 (가정이 맞다면) 훨씬 더 짧은 시간에 최고에 가까운 답을 얻을 수 있습니다.

---

알고리즘이 수행 될 작업 자체 포함 단계별 세트이다 4 (A)로부터의 경로가있다 : 일반적으로 문제와 같은 해결책을 결정하기 위해 (컴퓨터 또는 사람)의 지시 한정된 순서로 해석, B 또는 A와 B 사이의 가장 작은 경로입니다. 후자의 경우 '합리적으로 가까운'대체 솔루션에 만족할 수도 있습니다.

휴리스틱 알고리즘이 하나 인 특정 범주의 알고리즘이 있습니다. 이 경우 알고리즘의 (검증 된) 속성에 따라 다음 세 가지 범주 중 하나에 속합니다 (참고 1).

• 정확함 : 솔루션이입력 문제에대한 최적 (또는 정확한 솔루션)임이 입증되었습니다.
• 근사치 : 솔루션 값의 편차가 사전 정의 된 경계보다 최적 값에서 더 멀어지지 않는 것으로 입증되었습니다 (예 : 최적 값보다 50 % 이상 크지 않음).
• 휴리스틱 : 알고리즘이 최적 인 것으로 입증되지 않았거나 최적 솔루션의 사전 정의 된 범위 내에 있지 않습니다.

근사 알고리즘도 경험적이지만 출력하는 솔루션 (값)에 대한 입증 된 경계가 있다는 더 강력한 속성을 가지고 있습니다.

일부 문제의 경우 최적 솔루션을 계산하는 '효율적인'알고리즘을 발견 한 사람은 아무도 없습니다 (참고 2). 그 문제 중 하나는 잘 알려진 여행 세일즈맨 문제입니다. 예를 들어, Traveling Salesman Problem에 대한 Christophides의 알고리즘 은 최적 솔루션의 50 % 이내라는 것이 입증되지 않았기 때문에 휴리스틱 이라고 불 렸습니다 . 그러나 입증 되었기 때문에 Christophides의 알고리즘은보다 정확하게 근사 알고리즘이라고합니다.

컴퓨터가 수행 할 수있는 작업에 대한 제한으로 인해 가능한 최상의 솔루션 을 항상 효율적으로 찾을 수있는 것은 아닙니다 . 문제에 충분한 구조가있는 경우 솔루션 공간이 크더라도 (즉, 최단 경로 문제에서) 솔루션 공간을 탐색하는 효율적인 방법이있을 수 있습니다.

휴리스틱 스는 일반적으로 검색 방향을 안내하는 '전문가 정보'또는 '교육 된 추측'을 추가하여 알고리즘의 실행 시간을 개선하는 데 적용됩니다. 실제로, 휴리스틱은 어디 있는지를 결정하기 위해, 최적의 알고리즘을위한 서브 루틴 될 수있다 첫째 .

(주 1) : 또한 알고리즘은 랜덤 또는 비 결정적 요소를 포함하는지 여부를 특징으로합니다. 항상 동일한 방식으로 실행되고 동일한 답을 생성하는 알고리즘을 결정적이라고합니다.

(주 2) :이를 P vs NP 문제라고하며, NP-complete와 NP-hard로 분류되는 문제는 '효율적인'알고리즘을 가질 가능성이 낮습니다. 노트; @Kriss가 주석에서 언급했듯이 '더 나쁜'유형의 문제가있어 계산에 기하 급수적 인 시간이나 공간이 필요할 수 있습니다.

질문의 일부에 대한 답변이 몇 가지 있습니다. 나는 그것들이 덜 완전하고 정확하지 않다고 생각했고, @Kriss가 만든 대답을 편집하지 않기로 결정했습니다.

---

Heuristics are algorithms, so in that sense there is none, however, heuristics take a 'guess' approach to problem solving, yielding a 'good enough' answer, rather than finding a 'best possible' solution.

A good example is where you have a very hard (read NP-complete) problem you want a solution for but don't have the time to arrive to it, so have to use a good enough solution based on a heuristic algorithm, such as finding a solution to a travelling salesman problem using a genetic algorithm.

---

Algorithm is a sequence of some operations that given an input computes something (a function) and outputs a result.

Algorithm may yield an exact or approximate values.

It also may compute a random value that is with high probability close to the exact value.

A heuristic algorithm uses some insight on input values and computes not exact value (but may be close to optimal). In some special cases, heuristic can find exact solution.

---

An Algorithm is a clearly defined set of instructions to solve a problem, Heuristics involve utilising an approach of learning and discovery to reach a solution.

So, if you know how to solve a problem then use an algorithm. If you need to develop a solution then it's heuristics.

---

A heuristic is usually an optimization or a strategy that usually provides a good enough answer, but not always and rarely the best answer. For example, if you were to solve the traveling salesman problem with brute force, discarding a partial solution once its cost exceeds that of the current best solution is a heuristic: sometimes it helps, other times it doesn't, and it definitely doesn't improve the theoretical (big-oh notation) run time of the algorithm

---

I think Heuristic is more of a constraint used in Learning Based Model in Artificial Intelligent since the future solution states are difficult to predict.

But then my doubt after reading above answers is "How would Heuristic can be successfully applied using Stochastic Optimization Techniques? or can they function as full fledged algorithms when used with Stochastic Optimization?"

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

---

One of the best explanations I have read comes from the great book Code Complete, which I now quote:

A heuristic is a technique that helps you look for an answer. Its results are subject to chance because a heuristic tells you only how to look, not what to find. It doesn’t tell you how to get directly from point A to point B; it might not even know where point A and point B are. In effect, a heuristic is an algorithm in a clown suit. It’s less predict- able, it’s more fun, and it comes without a 30-day, money-back guarantee.

Here is an algorithm for driving to someone’s house: Take Highway 167 south to Puy-allup. Take the South Hill Mall exit and drive 4.5 miles up the hill. Turn right at the light by the grocery store, and then take the first left. Turn into the driveway of the large tan house on the left, at 714 North Cedar.

Here’s a heuristic for getting to someone’s house: Find the last letter we mailed you. Drive to the town in the return address. When you get to town, ask someone where our house is. Everyone knows us—someone will be glad to help you. If you can’t find anyone, call us from a public phone, and we’ll come get you.

The difference between an algorithm and a heuristic is subtle, and the two terms over-lap somewhat. For the purposes of this book, the main difference between the two is the level of indirection from the solution. An algorithm gives you the instructions directly. A heuristic tells you how to discover the instructions for yourself, or at least where to look for them.

---

They find a solution suboptimally without any guarantee as to the quality of solution found, it is obvious that it makes sense to the development of heuristics only polynomial. The application of these methods is suitable to solve real world problems or large problems so awkward from the computational point of view that for them there is not even an algorithm capable of finding an approximate solution in polynomial time.

참고URL : https://stackoverflow.com/questions/2334225/what-is-the-difference-between-a-heuristic-and-an-algorithm