확률 적 알고리즘과 휴리스틱 알고리즘의 차이

Question

question of streetparade을 확장하여 확률 적 알고리즘과 경험적 알고리즘 간의 차이점이 무엇인지 질문하고 싶습니다.

확률 적 알고리즘이 사실은 휴리스틱의 한 유형이라고 말할 수 있습니까?

Answer 1

TTBOMK, "확률 적 알고리즘은"아니다 함께 결합 될 수있다 접근 표준 용어. 그러나 "무작위 알고리즘"은 아마도 여기에있는 의미 일 것입니다.

무작위 : 어떻게 든 임의성을 사용합니다. 몬테카를로 알고리즘은 항상 한정된 시간 내에 끝나지 만 최적의 솔루션을 보장하지는 않지만 라스베가스 알고리즘은 유한 시간 내에 끝나도록 보장 할 필요는 없지만 최적의 솔루션을 찾을 것을 약속합니다. . (일반적으로 그들은 또한 의 실행 시간이 일 필요가 있습니다.) 일반적인 몬테카를로 알고리즘의 예 : MCMC, 시뮬레이션 어닐링 및 밀러 - 라빈 소수 테스트. 무작위 피벗 선택이있는 Quicksort는 항상 유한 시간으로 끝나는 라스베가스 알고리즘입니다. 임의성을 사용하지 않는 알고리즘은 결정적입니다.

지능형 : 정답을 찾지 못할 수도 있습니다. 지능형이 아닌 알고리즘은 exact입니다.

많은 휴리스틱은 실제 솔루션에 영향을주지 않는 입력의 "부수적 인"속성에 민감합니다. 예를 들어 Bin Packing 문제에 대한 First-Fit 경험적 방법으로 고려됩니다. 이 경우에는 몬테카를로 무작위 알고리즘으로 생각할 수 있습니다. 입력을 무작위로 바꾸어서 다시 실행하여 최상의 결과를 얻을 수 있습니다.OTOH, 다른 휴리스틱 스에는이 속성이 없습니다. First-Fit-Decreasing 휴리스틱은 항상 크기가 축소 된 항목을 먼저 정렬하기 때문에 결정적입니다.

특정 무작위 알고리즘의 가능 출력의 세트는 유한하고 의미에서 (결국 그것을 찾을 충분히 긴 "실질적으로 보장"되는 실행, 진정한 해답 포함되어있는 경우 그 하지의 확률 그것을 발견하면 임의로 작게 만들 수 있지만 결코 0이 아니다. 휴리스틱에 대한 입력의 순열이 정확한 답을 얻는 결과를 가져 오는 경우는 자동으로 발생하지 않습니다. First-Fit의 경우이 은이 사실이지만 이것이 2009 년에만 입증되었습니다

무작위 알고리즘의 수렴에 대한 더 강력한 진술을 할 수 있습니다. 일반적으로 "주어진 임의의 작은 임계 값 d, t 단계 이후에 우리는 확률 f (t, d (f (t, d))는 t와 d의 증가 함수이다.

Answer 2

부스 접근 방식은 일반적으로

1. 확률 알고리즘 그들은 않기 위해 대신 모든 조합을 사용하지만 임의성을

   를 사용 NP 완전 문제에 genere 및 테스트 속도를 솔루션을 사용하는 사람들 솔루션을 빨리 치기를 희망하는 모든 가능성을 무작위로 사용하십시오. 구현 (일정 시간)

2. 휴리스틱 알고리즘

   그들은하지 무작위로 대신 사용 방법, 입력 데이터 세트 또는 사용에 대한 약간의 지식을 바탕으로 조합을 선택 빠르고, 쉽고 단일 반복도 빠르고입니다. 따라서 조합의 수를 아마도 솔루션의 수로 크게 낮추고 솔루션 만 발견 될 때까지는 일반적으로 모든 조합을 사용합니다.

   구현 복잡도는 일반적으로 확률 론적 접근법 (일정 시간)보다 훨씬 느리고 확률 적 접근법 (일정 시간)이므로 가능한 속도가 실제 속도 향상만큼 충분히 낮아진 경우에만 휴리스틱이 사용됩니다. 왜냐하면 알고리즘 복잡성이 휴리스틱은 때때로 일정 시간이 충분한 크기를 일반적으로 훨씬 낮은 아래로 ... (실행 기준)도 느린 것을

부스

이