한 거짓말 모델에서 이진 검색을 수행하는 방법

Question

질문은 다음과 같습니다. n 개의 숫자로 된 정렬 된 목록이 있습니다. x가 주어지면, 정렬 된 목록에서 x와 같은 숫자를 찾으십시오. 여기서 우리는 x가 정말로 목록에 있다고 가정합니다. 질문에 "예"또는 "아니오"로 대답 할 수있는 오라클이 있습니다 ("x> = y"여부). 일반적인 이진 검색과 달리 오라클은 질문에 한 번 거짓말 할 수 있습니다. 이 문제를 해결하는 가장 순진한 방법은 각 질문을 오라클에 두 번 묻는 것입니다. 두 답이 같으면 그 표어가 거짓말이 아니라는 것을 알게됩니다. 이 알고리즘은 2log_2 (n) 번 비교해야합니다. 그러나이 질문은 log_2 (n) + o (logn) 비교만을 사용하여 x를 찾을 수있는 알고리즘을 찾도록 요청합니다.

매우 열심히 노력했지만 실패했습니다. 아무도 나 에게이 문제를 해결하는 방법에 대한 조언을 줄 수 있습니까? 고맙습니다.

Answer 1

당신이 들어간 간격을 기억하십시오. k 개의 질문이 필요한 경우 일관성을 유지하십시오 (귀하가 정한 간격에 있는지 여부)마다 sqrt(k) 걸음을 확인하십시오. 일관성을 검사하는 동안 각 질문에 대해 두 번 물어보십시오. 불일치가 발견되면 sqrt(k) 걸음으로 되돌아갑니다. c*sqrt(k) 질문이 더 이상 표시되지 않습니다.

Answer 2

오라클에 질문하십시오 : "is x> = y?" 바이너리 검색을 반복 할 때마다 한번씩. 같은 대답을 두 번 받으면 처음 오라클이 거짓말을하지 않는다는 것을 알게됩니다.

예를 들어, x = 1을 검색하고 y = a에 대해 테스트 한 첫 번째 테스트에서는 oracle이 x<에 대답합니다. 두 번째 테스트에서는 y = b에 대해 테스트하고 oracle은 x<에 응답합니다. b. 이진 검색을 사용하고 있고 오라클이 '<'이라고 말했고 어레이가 정렬되어 있기 때문에 b <을 알고 있습니다. 따라서 x < b 일 경우 x < a라는 사실을 알고 있으며 첫 번째 대답은 거짓말이 아닙니다. 두 번째 대답이 거짓말이고 x> b 인 경우 오라클은 한 번만 거짓말을 할 수 있기 때문에 x < a는 여전히 참입니다.

답변이 다시 돌아 오지 않는 경우에도 마찬가지입니다. 예를 들어 x < a, x> = b, x < c, 이진 검색으로 C <을 알고 있으므로 X가 <이고 aacle이 아님이 틀림 없습니다. 그가 당신에게 말했을 때 거짓말.

오라클이 거짓말을하면 어떻게됩니까? 거짓말이 x < 인 경우 진실은 x> = y입니다. 따라서 이진 탐색을 계속할 때 그 시점부터 확인하는 숫자는 모두 너무 작을 것이고 이진 검색의 맨 아래에 도달 할 때까지 대답은 항상 "> ="이됩니다. 그 시점에서 오라클이 거짓말을했다면 그는 마지막으로 "> ="이외의 것을 말했을 때 거짓말을한다는 것을 깨닫습니다. 따라서 오라클이 거짓말을하고 "x < y"라고 말한 지점에서 이진 검색을 다시 시작합니다.

이것은 항상 < 2 log_2 n 비교를 사용하지만 오라클이 검색 시작 부분에있는 경우 거의 log_2 n 작업을 반복해야하므로 log_2 n + o를 얻지 못합니다 (log n) 당신이 찾고 있던 대답. 따라서 nm에 의해 제안 된 아이디어를 통합해야합니다. 같은 대답을 얻었다면 sqrt (log n) 번 연속으로 말하면 오라클이 거짓말을 한 것으로 의심되어 즉시 질문을 다시합니다. 이진 검색의 맨 아래까지 기다리는 대신 대답이 반복되기 전에 물었다. 이 전략을 따르면, 최악의 경우 질문 로그 n/sqrt (log n) 번 다시 요청할 것이며, 항상 sqrt (log n) 낭비 작업으로 거짓말을 잡아서 실행 시간을 달성하게됩니다 찾고.

Answer 3

당신은 시도에 대해 대신 배열의 2 개 diffrent 인덱스를 비교하기 위해 각각의 반복에서 오라클을 요청하는 방법이 작동하려면 고전 이진 검색을 변경할 수 있습니다 단지 1, 뭔가 같은 :

assume Oracle(x,y) returns "x>=y?", assume every division is returning floor integer. 
LyingOracleSearch(A,n,toFind) 
1. if (n==0) return not found 
2. if (A[0]==toFind) return found 
3. if (Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then 
4.      return LyingOracleSearch(A[(n/4)...(3n/4)],3n/4-n/4,toFind) 
5. if (Oracle(A[n/4],toFind) and !Oracle(toFind,A[3n/4]) then 
6.      return LyingOracleSearch(A[0...(n/4)],n/4,toFind) 
7. if (!Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then 
8.      return LyingOracleSearch(A[(3n/4)...n],n-3n/4,toFind) 
9. return LyingOracleSearch(A,n,toFind); \\orcale lied! 

나는 그것이 손톱이라고 생각한다. 틀릴 수도있다.

복잡성은 원래의 BS와 같지만 오라클에 두 번 이상 묻는 것이 좋습니다. 엘리먼트가 오라클이 거짓말을하지 않으면 두 번 비교되지 않는다는 것에주의하십시오. 따라서 k가 작은 -o (logn) 인 경우 한 번 또는 심지어 k 번 거짓이면 우린 괜찮습니다.

좋아하는 코딩 환경으로 이동하여 비교할 때마다 코드화 해보십시오. 이것과 순진한 것을 모두 시도해보고 결과를 비교해보십시오. 실수가 아니라면, 순진한 사람은 이것보다 두 배를 비교해야합니다.

주목해라. 내가 인덱스에 너무주의를 기울이지 않았다면, 인덱스를 놓치지 않았거나 실수로 인덱스를 반복하지 않았는지 확인하기 위해 몇 가지 생각을해야 할 것이다.

Answer 4

오라클이 거짓말 한 후 이진 검색이 잘못되어 사실을 사용하십시오. 그 이후로 오라클의 응답에는 아무런 변화가 없습니다 (항상 >= 또는 항상 <). log(log(n)) 단계에 대한 오라클의 대답이 변경되지 않으면 간격 일관성을 확인하십시오. 현재 간격이 일치하지 않으면 oracle을 한 번 더 물어보고 여전히 일치하지 않으면 log(log(n)) + 1 단계로 돌아가서 정상적인 이진 검색을 계속하십시오.

이 절차를 수행하려면 평균적으로 O(log(log(n))) 일관성 검사가 필요하며 추가 이진 검색 단계는 log(log(n))까지입니다.

추가 질문의 평균 개수는 c*log(log(n))이며, 추가 질문의 최대 개수는 log(n)/(log(log(n))) + log(log(n))입니다.

Answer 5

나는이 질문을 3 * log(n)에서 풀 때마다 단계별로 불평등 문제를 3 번 ​​질문하고 쉽게 결정할 수 있다고 생각합니다. 그 결정은 다수결입니다.