N-Queens 문제는 N x N 체스판에 서로 공격하지 않도록 N개의 퀸을 배치하는 제약 만족 문제이다. 기존의 백트래킹과 같은 완전 탐색 방법은 지수 시간 복잡도로 인해 대규모 인스턴스에 비효율적이다. 본 연구는 표준 Las Vegas 알고리즘을 기반으로 반복적인 가지치기를 통해 유효하지 않은 배치를 동적으로 제거하여 탐색 공간을 효과적으로 줄이는 하이브리드 알고리즘을 제안한다.
시사점, 한계점
•
제안된 알고리즘은 백트래킹보다 더 빠르게 유효한 해를 생성하여 단일 시점에 해를 얻는 경우에 적합하다.
•
알고리즘은 계산 비용과 해의 충실도 간에 효과적인 균형을 제공하여 자원 제약적인 환경에 적합하다.
