무차별 검색

Brute-force search
이 기사는 컴퓨터 과학의 문제 해결 기술에 관한 것이다.다른 분야에서도 유사한 이름의 방법은 Brute force(동음이의)를 참조하십시오.

컴퓨터 과학에서, 생성과 테스트라고도 알려진, 브루트 포스 검색 또는 완전 검색은 매우 일반적인 문제 해결 기법이자 알고리즘 패러다임으로, 해결책에 대한 모든 가능한 후보들을 체계적으로 열거하고 각 후보들이 문제의 진술을 충족하는지 확인하는 것으로 구성됩니다.

자연수 n의 제수를 찾는 브루트포스 알고리즘은 1 ~n의 모든 정수를 열거하고 각각n을 나머지 없이 분할하는지 여부를 체크합니다.8개의 퀸 퍼즐에 대한 무차별적인 접근은 64개의 정사각형 체스판에 8개의 조각을 가능한 모든 배열로 검사하고 각 배열에 대해 각 퀸 조각이 [1]다른 조각을 공격할 수 있는지 여부를 검사합니다.

무차별적인 검색은 구현이 간단하며 솔루션이 존재하는 경우 항상 해결책을 찾게 되지만 구현 비용은 후보 솔루션의 수에 비례합니다.많은 실제 문제에서는 문제의 규모가 커짐에 따라 매우 빠르게 증가하는 경향이 있습니다(★[2]따라서 일반적으로 brute-force 검색은 문제 크기가 제한되거나 후보 솔루션 세트를 관리 가능한 크기로 줄이기 위해 사용할 수 있는 문제별 휴리스틱이 있을 때 사용됩니다.이 방법은 속도보다 구현의 단순성이 더 중요한 경우에도 사용됩니다.

예를 들어 알고리즘의 오류가 매우 심각한 결과를 초래할 수 있는 중요한 응용 프로그램이나 수학적 정리를 증명하기 위해 컴퓨터를 사용하는 경우에 해당됩니다.브루트포스 검색은 다른 알고리즘이나 메타휴리스틱을 벤치마킹할 때 기준 방법으로도 유용합니다.사실, 무차별적인 검색은 가장 단순한 메타 휴리스틱으로 볼 수 있습니다.(위의 8대 여왕 문제에 대한 교과서적인 컴퓨터 솔루션에서와 같이) 명시적으로 열거되지 않고 대규모 솔루션 세트를 폐기할 수 있는 역추적과 혼동해서는 안 된다.테이블 내의 아이템을 찾기 위한 brute-force 메서드, 즉 후자의 모든 엔트리를 순차적으로 체크하는 방법을 선형 검색이라고 합니다.

브루트 포스 검색 구현

기본 알고리즘

현재 1 c 다음에 P 후보가 되기 위해서.

  1. valid (P, c): 후보 c가 P의 솔루션인지 확인합니다.
  2. output (P, c): 용도에 따라 P의 솔루션 c를 사용합니다.

다음 절차에서는 인스턴스 P의 후보가 현재1 c 뒤에 없을 때도 통지해야 합니다.이를 위한 편리한 방법은 "null 후보"를 반환하는 것입니다. 이 값은 실제 후보와 구별되는 기존의 데이터 값 δ입니다.마찬가지로 인스턴스 P의 후보가 전혀 없는 경우 첫 번째 순서는 λ를 반환해야 합니다.다음으로 brute-force 메서드는 알고리즘에 의해 표현됩니다.

c ← first(P)인 반면 c ≠ λ λ if 、 valid(P,c)인 경우 실행한 후 출력(P,c) c ← next(P,c)인 경우 종료합니다.

예를 들어 정수 n의 제수를 구할 때 인스턴스 데이터 P는 숫자 n이다.n이 1이면 정수 1을 반환하고, 그렇지 않으면 정수 1을 반환하고, c가 n < n이면 c + 1을 반환하고, 그렇지 않으면 valid(n,c)가 true를 반환하는 것은 c가 n의 약수일 경우뿐입니다.(실제로 λ이 n + 1이 되도록 선택한 경우)위의 브루트포스 검색 알고리즘은 특정 인스턴스 P의 솔루션인 모든 후보 출력을 호출합니다.알고리즘은 첫 번째 솔루션 또는 지정된 수의 솔루션을 찾은 후, 또는 지정된 수의 후보를 테스트한 후 또는 지정된 CPU 시간을 소비한 후 중지하도록 쉽게 변경할 수 있습니다.

조합 폭발

브루트포스 방식의 가장 큰 단점은 많은 실제 문제에서 자연 후보자의 수가 엄청나게 많다는 것입니다.예를 들어 위에서 설명한 숫자의 제수를 찾으면 테스트된 후보의 수는 주어진 숫자 n이 됩니다.따라서 예를 들어, n이 16자리 소수점 이하일 경우, 검색에서는 적어도15 10개의 컴퓨터 명령을 실행해야 합니다.이것은 일반적인 PC에서는 며칠 걸립니다.n이 랜덤 64비트 자연수이고 평균 소수점 약 19자리일 경우 검색에는 약 10년이 소요됩니다.데이터의 크기가 커짐에 따라 후보자의 수가 급격히 증가하는 것은 모든 종류의 문제에서 발생합니다.예를 들어 10글자의 특정 재배열을 원하는 경우 10! = 3,628,800명의 후보자를 고려해야 합니다. 이는 일반적인 PC가 1초 이내에 생성하고 테스트할 수 있습니다.단, 1글자를 추가하면 (데이터 사이즈가 10% 증가하는데 그친다) 후보 수가 1000% 증가한 11이 됩니다.20글자의 경우, 후보자는 20!으로 약 2.4×1018, 2.4조, 수색에는 약 10년이 소요됩니다.이 반갑지 않은 현상은 흔히 조합 폭발 또는 차원성의 저주라고 불립니다.

조합의 복잡성이 해결성의 한계로 이어지는 경우의 한 예는 체스를 푸는 것이다.체스는 해결된 게임이 아니다.2005년에는 6피스 이하의 체스 게임 엔딩이 모두 해결되어 각 포지션의 결과가 완벽하게 나왔다.체스 한 마디가 더해져 테이블 베이스를 완성하는 데 10년이 더 걸렸고, 따라서 7개의 테이블 베이스를 완성했다.체스 엔딩에 한 피스를 추가하는 것(따라서 8피스의 테이블 베이스를 만드는 것)은 추가된 조합 [3][4]복잡성 때문에 다루기 어려운 것으로 간주됩니다.

브루트 포스 검색 속도 향상

브루트포스 알고리즘을 고속화하는 방법 중 하나는 문제 클래스에 고유한 휴리스틱스를 사용하여 검색 공간, 즉 후보 솔루션 세트를 줄이는 것입니다.예를 들어, 8개의 여왕 문제에서는 여왕이 다른 여왕을 공격하지 않도록 8개의 여왕을 하나의 표준 체스판에 배치하는 것이 과제입니다.각 퀸은 64개의 정사각형 중 하나에 배치할 수 있으므로, 원칙적으로 64 = 281,474,976,710,656개의 가능성을 고려해야8 한다.그러나 여왕은 모두 비슷하고 두 여왕을 같은 정사각형에 배치할 수 없기 때문에 후보들은 모두 64개의 정사각형 집합에서 8개의 정사각형 집합을 선택할 수 있습니다. 즉, 64개는 8 = 64!/(56!*8!) = 4,426,136,368개의 후보 해를 선택합니다. 이는 이전 추정치의 약 60,000분의 1입니다.또한 같은 행 또는 같은 열에 두 개의 여왕이 있는 배열은 해결책이 될 수 없습니다.따라서 우리는 후보군을 그 준비로 더욱 제한할 수 있다.

이 예에서 알 수 있듯이, 약간의 분석은 종종 후보 솔루션의 수를 극적으로 감소시키고 다루기 어려운 문제를 사소한 문제로 바꿀 수 있습니다.

경우에 따라서는 분석을 통해 후보가 모든 유효한 솔루션 세트로 축소될 수 있습니다.즉, 테스트나 무효 후보 생성에 시간을 낭비하지 않고 원하는 모든 솔루션을 직접 열거(또는 적절한 경우 하나의 솔루션을 찾는) 알고리즘을 생성할 수 있습니다.예를 들어 "417로 균등하게 나눌 수 있는1 ~ 1,000,000 사이의 모든 정수를 찾습니다"라는 문제의 경우, 순진한 브루트포스 솔루션은 범위 내의 모든 정수를 생성하고 각각의 정수를 나눗셈 여부를 테스트합니다.그러나 이 문제는 417부터 시작하여 1,000,000을 초과할 때까지 417을 반복하면 훨씬 더 효율적으로 해결할 수 있습니다. 이는 2398(= 1,000,000 17 417) 단계만 거치면 되며 테스트는 수행되지 않습니다.

서치 공간 순서 변경

모든 솔루션이 아닌 하나의 솔루션만을 필요로 하는 어플리케이션에서는 brute force 검색의 예상 실행 시간은 후보 테스트 순서에 따라 달라집니다.원칙적으로 가장 유망한 후보자를 먼저 테스트해야 한다.예를 들어, 난수 n의 적절한 제수를 검색할 때는 n이 c로 나누어질 확률은 1/c이므로 후보 제수를 2부터n - 1까지 오름차순으로 열거하는 것이 좋습니다.게다가 후보자가 유효할 확률은 종종 이전의 실패한 시행에 의해 영향을 받습니다.예를 들어 특정 1000비트 문자열 P에서1비트를 검출하는 문제에 대해 생각해 보겠습니다.이 경우 후보 해는 지수 1 ~ 1000이고 후보 c는 P[c] = 1이면 유효합니다. 이제 P의 첫 번째 비트가 0 또는 1일 가능성이 같으나 그 이후의 각 비트는 90% 확률로 이전 비트와 같다고 가정합니다.후보를 1에서 1000의 순서로 나열하면 성공하기 전에 검사한 후보 t의 수는 평균 6개 정도가 됩니다.한편, 후보가 1,11,21,31…991,2,12,22,32 등의 순서로 열거되어 있는 경우, t의 기대치는 2를 조금 웃돌 뿐입니다.보다 일반적으로 이전 시행이 유효하지 않았으므로 다음 후보가 유효할 가능성이 가장 높은 방식으로 검색 공간을 열거해야 합니다.따라서 유효한 솔루션이 어떤 의미에서 "클러스터화"될 가능성이 높은 경우, 각각의 새로운 후보는 같은 의미에서 이전 후보와 가능한 한 멀리 떨어져 있어야 합니다.물론 그 반대는 해답이 우연에 의해 예상보다 균일하게 펼쳐질 가능성이 높은 경우 유효하다.

무차별 검색 대체 수단

솔루션에 대한 다양한 부분적 지식을 활용할 수 있도록 설계된 다른 검색 방법 또는 메타 휴리스틱이 많이 있습니다.휴리스틱스를 사용하여 검색의 일부를 조기에 차단할 수도 있습니다.이것의 한 예는 게임 트리를 검색하기 위한 미니맥스 원리로, 검색 초기에 많은 하위 트리를 제거합니다.언어 구문 분석과 같은 특정 분야에서는 차트 구문 분석과 같은 기술이 문제의 제약을 이용하여 지수 복잡도 문제를 다항 복잡도 문제로 줄일 수 있습니다.제약 조건 만족 문제처럼 많은 경우 제약 조건 프로그래밍 언어로 효율적으로 구현되는 제약 조건 전파를 통해 검색 공간을 크게 줄일 수 있습니다.또한 전체 문제를 단순 버전으로 대체하여 문제 검색 공간을 줄일 수 있습니다.예를 들어 컴퓨터 체스에서 게임의 나머지 부분에 대해 가능한 모든 움직임의 완전한 미니맥스 트리를 계산하는 것이 아니라 미니맥스 가능성의 보다 제한된 트리를 계산하고 트리의 나머지 부분을 정적 평가 함수로 근사한다.

암호학에서

주요 기사: 무차별 공격

암호학에서 브루트 포스 공격은 올바른 키가 [5]발견될 때까지 가능한 모든 키를 체계적으로 검사합니다.이 전략은 이론적으로 암호화 시스템의 약점을 이용할 수 없는 공격자가 암호화된 데이터[6](일회성 패드 제외)에 대해 사용할 수 있으며, 그렇지 않으면 작업이 쉬워집니다.

암호화에 사용되는 키 길이에 따라 짧은 키보다 긴 키를 크래킹하기가 기하급수적으로 더 어려워지는 무차별 포스 공격의 실행 가능성이 결정됩니다.무차별 포스 공격은 부호화할 데이터를 난독화함으로써 효과를 떨어뜨릴 수 있습니다.이 때문에 공격자가 코드를 해독했을 때 이를 인식하기가 더욱 어려워집니다.암호화 시스템의 강도에 대한 척도 중 하나는 이론적으로 공격자가 암호화 시스템에 대해 무차별적인 공격을 성공시키는 데 걸리는 시간입니다.

레퍼런스

  1. ^ "Brute Force Algorithms Explained". freeCodeCamp.org. 2020-01-06. Retrieved 2021-04-11.
  2. ^ "Complexity of brute force search". coursera. Retrieved 14 June 2018.
  3. ^ "Is there a freely available online 7 piece Endgame tablebase?". Stack Exchange.
  4. ^ "Lomonosov Endgame Tablebases". ChessOK.
  5. ^ Mark Burnett, "Blocking Brute Force Attacks" Wayback Machine, UVA Computer Science, 2007년 12월 3일 아카이브 완료
  6. ^ Christof Paar; Jan Pelzl; Bart Preneel (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. p. 7. ISBN 3-642-04100-0.

「 」를 참조해 주세요.