비결정론적 알고리즘

컴퓨터 프로그래밍에서, 비결정론적 알고리즘은 결정론적 알고리즘과는 대조적으로, 같은 입력에도 불구하고, 다른 실행에서 다른 동작을 나타낼 수 있는 알고리즘이다.알고리즘이 실행마다 다르게 동작하는 방법은 여러 가지가 있습니다.동시 알고리즘은 레이스 조건으로 인해 주행마다 다르게 수행될 수 있습니다.확률론적 알고리즘의 동작은 난수 발생기에 따라 달라집니다.비결정적 다항식 시간에 문제를 해결하는 알고리즘은 실행 중 선택에 따라 다항식 시간 또는 지수 시간에 실행될 수 있습니다.비결정론적 알고리즘은 정확한 해법이 결정론적 해법을 사용하기에는 비용이 너무 많이 들 때 해법에 대한 근사치를 찾는 데 종종 사용된다.

그 개념은 로버트 W에 의해 도입되었다. 1967년 ^[1]플로이드.

사용하다

종종 계산 이론에서 "알고리즘"이라는 용어는 결정론적 알고리즘을 가리킵니다.비결정론적 알고리즘은 다양한 경로를 사용하여 결과에 도달할 수 있다는 점에서 보다 친숙한 결정론적 알고리즘과는 다릅니다.결정론적 알고리즘이 입력에서 결과에 이르는 단일 경로를 나타내는 경우, 비결정론적 알고리즘은 다수의 경로에 이르는 단일 경로를 나타내며, 일부는 동일한 출력에 도달하고 일부는 고유한 출력에 도달합니다.이 속성은 비결정론적 유한 오토마톤과 같은 "비결정론적" 계산 모델에서 수학적으로 포착됩니다.시나리오에 따라 가능한 모든 경로를 동시에 실행할 수 있습니다.

알고리즘 설계에서 비결정론적 알고리즘은 알고리즘에 의해 해결된 문제가 본질적으로 여러 결과를 허용하는 경우(또는 결과가 발견될 수 있는 여러 경로를 가진 단일 결과가 있는 경우, 각각 동일하게 선호되는 경우) 종종 사용됩니다.결정적으로 비결정론적 알고리즘이 생성하는 모든 결과는 알고리즘이 실행 중에 어떤 선택을 하든 유효합니다.

계산 복잡도 이론에서, 비결정론적 알고리즘은 가능한 모든 단계에서 다중 연속성을 허용할 수 있는 알고리즘입니다(숲의 길을 걸어가는 사람을 상상하고, 한 걸음 더 나아갈 때마다, 그들이 가고자 하는 갈림길을 선택해야 합니다).이러한 알고리즘은 가능한 모든 계산 경로에 대한 솔루션에 도달하는 것은 아닙니다. 그러나 일부 경로에 대한 올바른 솔루션에 도달하는 것이 보증됩니다(즉, 숲을 통과하는 사람은 "올바른" 경로의 조합을 선택할 경우에만 오두막을 찾을 수 있습니다).이러한 선택사항은 검색 과정에서 추측으로 해석될 수 있습니다.

컴퓨팅 이론에서 가장 유명한 미해결 질문인 P 대 NP를 포함한 많은 문제들이 비결정론적 알고리즘을 통해 개념화될 수 있다.