휴리스틱과 알고리즘의 차이점은 무엇입니까?
답변
알고리즘은 문제 에 대한 자동화 된 솔루션에 대한 설명입니다 . 알고리즘이하는 일은 정확하게 정의됩니다. 해결책은 최선일 수도 있고 아닐 수도 있지만 처음부터 어떤 종류의 결과를 얻을 수 있는지 알고 있습니다. 당신은 구현 알고리즘을 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가 만든 대답을 편집하지 않기로 결정했습니다.
답변
사실 저는 그들 사이에 공통점이 많지 않다고 생각합니다. 일부 알고리즘은 논리에 휴리스틱을 사용합니다 (종종 더 적은 계산을 수행하거나 더 빠른 결과를 얻기 위해). 일반적으로 휴리스틱 스는 소위 탐욕스러운 알고리즘에서 사용됩니다.
휴리스틱 스는 알고리즘에서 최선의 선택을하기 위해 사용하는 것이 좋다고 가정하는 “지식”입니다 (선택을해야 할 때). 예를 들어 … 체스의 휴리스틱은 (당신이 할 수 있다면 항상 상대방의 여왕을 가져 가십시오. 이것이 더 강한 인물이라는 것을 알고 있기 때문입니다). 휴리스틱 스가 정답으로 이어질 것이라고 보장하지는 않지만 (가정이 맞다면) 훨씬 더 짧은 시간에 최고에 가까운 답을 얻을 수 있습니다.
답변
휴리스틱은 알고리즘이므로 그 의미에서 휴리스틱은 문제 해결에 ‘추측’접근 방식을 취하여 ‘가능한 최상의’솔루션을 찾는 대신 ‘충분히 좋은’답변을 산출합니다.
좋은 예는 솔루션을 원하지만 도달 할 시간이없는 매우 어려운 (NP 완료 읽기) 문제가있는 경우입니다. 따라서 다음과 같은 휴리스틱 알고리즘을 기반으로 충분한 솔루션을 사용해야합니다. 유전 알고리즘을 사용하여 여행하는 세일즈맨 문제에 대한 해결책을 찾습니다.
답변
알고리즘은 입력이 무언가 (함수)를 계산하고 결과를 출력하는 일부 연산의 시퀀스입니다.
알고리즘은 정확하거나 대략적인 값을 산출 할 수 있습니다.
또한 정확한 값에 가까운 확률이 높은 임의 값을 계산할 수도 있습니다.
휴리스틱 알고리즘은 입력 값에 대한 통찰력을 사용하고 정확한 값이 아닌 값을 계산합니다 (최적에 가까울 수 있음). 특별한 경우에 휴리스틱은 정확한 솔루션을 찾을 수 있습니다.
