무작위 알고리즘에 대한 Wikipedia 에서
예상되는 실행 시간이나 메모리 사용량을 줄이기 위해 임의의 입력을 사용하는 알고리즘 을 구분 해야하지만 항상 제한된 시간 내에 올바른 결과로 종료해야하며
확률 적 알고리즘 은 임의의 입력에 따라 기회가 있습니다 실패를 알리거나 종료하지 않음으로써 잘못된 결과 (Monte Carlo 알고리즘)를 생성하거나 결과 (Las Vegas 알고리즘)를 생성하지 못하는
- “첫 번째 종류의 알고리즘 이 임의의 입력을 사용하여 예상 실행 시간이나 메모리 사용량을 줄이는 방법이 궁금 하지만 항상 제한된 시간 내에 올바른 결과로 종료됩니까?
- 결과를 얻지 못할 수있는 Las Vegas 알고리즘과 차이점은 무엇입니까?
- 내가 올바르게 이해하면 확률 알고리즘과 무작위 알고리즘은 같은 개념이 아닙니다. 확률 알고리즘은 랜덤 알고리즘의 한 종류 일 뿐이며, 다른 알고리즘은 랜덤 입력을 사용하여 예상 실행 시간이나 메모리 사용량을 줄이지 만 항상 제한된 시간 내에 올바른 결과로 종료됩니까?
답변
-
영형(엔2)
영형(엔로그엔)
영형(엔2)
영형(엔로그엔)
-
이것은 Las Vegas 알고리즘의 하위 집합을 제공합니다. 라스 베이거스 알고리즘은 (낮은 확률로) 전혀 더 이상 종료되지 않을 가능성을 허용합니다.
-
이것들은 실제로 몬테카를로 알고리즘의 한 유형일뿐입니다. 대답은 틀릴 수 있습니다 (낮은 확률로). 적어도 개념적으로는 대답하지 않을 수도 있습니다.
물론 남은 세부 사항이 많이 있습니다. 복잡한 아이디어 ZPP, RP 및 BPP를 찾아보고 이러한 아이디어를 공식화 할 수 있습니다.
답변
무작위 알고리즘 과 확률 알고리즘 이라는 두 용어 는 서로 다른 두 가지 상황에서 사용됩니다. 무작위 알고리즘 은 결정 론적 알고리즘 과 달리 무작위성을 사용 하는 알고리즘 입니다. 확률 알고리즘 , 예를 들어 우선 성 테스트를위한 확률 알고리즘은 임의성을 사용하고 약간의 희망이 있으면 오류를 일으킬 수있는 알고리즘입니다.
Monte Carlo 알고리즘 과 Las Vegas 알고리즘 간에 중요한 차이점이 있습니다 . Las Vegas 알고리즘은 항상 정답을 반환하는 무작위 알고리즘이지만 실행 시간은 동전 던지기에 따라 다릅니다. 예를 들어 정수 인수 분해 알고리즘 – 항상 올바른 인수를 반환하지만 실행 시간은 임의성에 따라 다릅니다. Las Vegas 알고리즘의 실행 시간 (인수 분해 알고리즘)을 명시 할 때 실제로 예상 실행 시간을 명시합니다 . 운이 좋지 않으면 알고리즘이 더 오래 실행될 수 있습니다.
반면에 Monte Carlo 알고리즘은 실행 시간이 미리 설정된 무작위 알고리즘입니다. 이러한 알고리즘은 실수를 할 수 있지만 일반적으로 오류 확률은 매우 낮습니다. 좋은 예는 확률 론적 원시성 테스트입니다. 이 알고리즘은 매우 빠르지 만 오류가 발생할 수 있습니다. 그러나 오류 확률은 느리므로 실제로는 실수하지 않습니다.
모든 Las Vegas 알고리즘은 오랜 시간이 지난 후에 실행을 중지하여 Monte Carlo 알고리즘으로 변환 할 수 있으므로 Las Vegas 알고리즘은 Monte Carlo 알고리즘보다 “더 나은”의미를 갖습니다.