많은 미로 해결 알고리즘이 있습니다. 그러나 지금 나는개념 : 멀티 스레딩으로 미로 해결
는 양자 컴퓨터가 한 시간에 진 미로의 모든 경로를 시도 할 수 있습니다 상태 양자 컴퓨터에 대한 설명을 가로 질러 와서 극적으로 같은 유치 문제를 해결하는 데 필요한 시간을 줄일 수 미로
그러나 우리는 지금 그 일을 할 수 없었습니다. 나는 병렬 컴퓨팅에 익숙하지 않지만 (원하는만큼 많은 스레드를 만들 수 있다고 가정 할 때) 우리 프로그램이 미로에서 분기 된 경로를 볼 때마다 새로운 스레드를 생성 할 수는 없습니다. 이것은 동시에 두 경로를 시도 할 것입니다 (맞습니까?).
우리는 (거의) 같은 시간에 모든 솔루션을 시도하는 것을 제외하면 시행 착오와 비슷할 것입니다.
전제 조건 : 폐기시 매우 많은 코어가 필요합니다.
새로운 스레드가 모두 실제로 병렬로 실행되지 않습니다 - 당신이 을 코어를 가지고있는 경우에만 병렬로 많은 스레드를 실행할 수 (그래서 4 코어 컴퓨터에서, 단지 4 개의 코어는 한 번에 코드를 실행 할 수 있습니다) . OS 스레드 스케줄러는 어떤 스레드가 어떤 코어에서 몇 초마다 실행되는지를 전환하므로, 은 동시에 실행되는 것처럼처럼 보이지만 실제로는 그렇지 않습니다.
가능한 모든 경로에 하나의 코어를 할당하기에 충분한 코어가 있다면 그렇습니다. 그러면 아이디어가 효과적입니다. GPU의 작은 미로에서는 실제로 5k + 코어 이상을 차지할 수 있습니다.
각 스레드가 실제로 동기화 (각 스레드는 동일한 명령을 동시에 처리 함)하고 분기 분기 패널티가 커지므로 GPU가 이러한 유형의 문제에 대해 작동하지 않는다고 생각합니다. – SirGuy
@GuyGreer : SM 당 사실입니다. IIRC의 경우, 현재의 Nvidia 카드에는 SM 당 32 개의 스레드가 있으며, 절반 정도만 잠금 단계 *로 실행됩니다 ("반 휨"과 같은 재미있는 이름이 붙습니다). 그래서, 우리가 half-warps가 대부분 sync (* 할 수 있어야합니다) *가되도록 그것을 쓸 수 없다고 가정하더라도, thread-divergence의 최대 penalty는 16x입니다. 극단적 인 경우에도 여전히 새로운 Nvidia Tesla 카드에서 5k + 코어가 주어지면 속도가 빨라집니다. –
GPU는 가지를 다룰 수없는 데서 먼 길을왔다. :). – SirGuy
** 무한 ** 코어 수를 사용하면 정확하지만 강력한 필수 조건입니다. ;) – Pragmateek