저는 컴퓨터 과학 학부이며 나는 단지 결승을 위해 공부하고 있습니다. 다양한 동적 프로그래밍 유형 문제로 인해 문제가 발생했습니다. 이것을 다음과 같이 요약 해 보겠습니다.무작위 알고리즘 확률 극대화
효율적인 무작위 알고리즘 A가 제공되어 독립 세트를 반환합니다. 이 알고리즘은 확률이 최소 1/(n^3) 인 최대 독립 세트를 반환합니다. 여기서 n은 그래프의 정점 수입니다. 확률이 1/2 이상인 최대 집합을 반환하는 A를 사용하는 다른 알고리즘을 제안하십시오.
무작위 알고리즘을 연구했지만 단순한 구현 사례처럼 보입니다. A n^3 번 실행하려면 최대 독립 집합이 1에 가까울 확률을 구하십시오. 그러면 n^3/2 번 실행하면 원하는 효과가 나타납니다. 이걸 더 열심히하려고하는거야? 어떤 도움을 주셔서 감사합니다.
정확하지는 않지만 실행 중 하나가 정답을 반환 할 확률은 1/n^3 이상입니다. 즉, 한 번의 실행에서 잘못된 답을 얻을 확률은 (1-1/n^3)이며, M을 실행 한 후에 정답을 얻을 확률은 1- (1-1/n^3)^M입니다. .
e (Wikipedia link)의 공식을 생각해보십시오. n^3 번 실행하면 확률은 1-1/e가 1/2 이상이지만 (1에 가까울 정도는 아닙니다), 정확히 1/2 - (n^3) * ln (2)에 도달하는 정확한 실행 횟수.
그게 내가 찾고있는 것입니다. 고마워. 나는 확률 규칙에 약간 녹슬지. – Championcake
최대 독립 세트를 연구하지 않았으므로 너무 많은 도움을 줄 수는 없습니다. 그러나 먼저 실행 시간을 요구하기 전에 먼저 알고리즘을 작성해야합니다.
n^3 알고리즘 A를 실행하면 n^3 최대 독립 집합을 얻습니다. 그러나 최대 값을 하나만 반환해야합니다. 그 n^3 안에서 올바른 것을 어떻게 알아 내겠습니까? 여기서 질문에 누락 된 확인 알고리즘이 필요할 수 있습니다.
문제 자체 (최대 독립 세트)에 따라 O (n^3)보다 훨씬 적은 실행 횟수를 요구하는 올바른 최대 독립 세트를 찾을 수있는 충분한 정보를 가질 수 있습니다.
이 질문을 올리는 데 잘못된 사이트가 있습니다 ... –