C++에서 Greedy Best-First 검색 알고리즘 구현

컴퓨터 과학에서 좋은 문제 해결은 GBFS(Greedy Best First Search)와 같은 효율적인 알고리즘에 크게 의존합니다. GBFS는 경로 찾기 또는 최적화 문제에 대한 최상의 솔루션으로 신뢰성을 확립했습니다. 따라서 이 기사에서는 C++를 사용하여 GBFS 구현을 탐색하면서 GBFS에 대해 심층적으로 논의합니다.

문법

으아아아

알고리즘

그리디 베스트 우선 검색 알고리즘은 그래프에서 주어진 시작 노드에서 대상 노드까지의 경로를 찾는 것을 목표로 합니다. 알고리즘의 일반적인 단계는 다음과 같습니다 -

• 빈 우선순위 대기열을 초기화합니다.

• 시작 노드를 우선순위 큐에 넣습니다.

• 방문한 노드를 추적하기 위해 빈 세트를 만듭니다.

• 우선순위 큐가 비어있지 않은 경우 -

• 대기열에서 우선순위가 가장 높은 노드를 대기열에서 제거합니다.

• 큐에서 제거된 노드가 대상 노드인 경우 알고리즘이 종료되고 경로를 찾습니다.

• 그렇지 않으면 대기열 제거 노드를 방문한 것으로 표시하세요.

• 큐에서 제외된 노드의 방문하지 않은 모든 이웃 노드를 우선순위 큐에 넣습니다.

• 대상 노드에 도달하기 전에 우선순위 큐가 비어 있으면 경로가 존재하지 않는 것입니다.

방법 1: 유클리드 거리 기반 휴리스틱 함수

예

으아아아

출력

으아아아

지침

이 코드에는 두 가지 핵심 요소가 포함되어 있습니다. 첫째, 인접 목록을 사용하여 그래프 구조를 나타내는 Graph 클래스의 정의가 포함되어 있습니다.

두 번째로, 유클리드 거리 공식을 사용하여 대상 노드로부터의 거리를 추정하여 노드를 평가하기 위한 사용자 정의 비교기인 CompareEuclideanDistance를 소개합니다.

greedyBestFirstSearch 기능은 탐욕스러운 최고의 우선 검색 알고리즘을 구현합니다. 우선순위 대기열을 사용하여 휴리스틱 값을 기반으로 노드를 저장합니다.

알고리즘은 먼저 시작 노드를 우선순위 대기열에 넣습니다.

각 반복에서 우선순위가 가장 높은 노드를 대기열에서 제거하고 대상 노드인지 확인합니다.

대상 노드를 찾으면 "Path Found!"라는 메시지가 인쇄됩니다. 그렇지 않으면 알고리즘은 대기열에서 제거된 노드를 방문한 것으로 표시하고 방문하지 않은 인접 노드를 대기열에 추가합니다.

우선순위 큐가 비어 있고 대상 노드를 찾을 수 없으면 "경로가 존재하지 않습니다!"라는 메시지가 인쇄됩니다.

주 함수는 그래프를 생성하고, 시작 노드와 대상 노드를 정의하고,greedyBestFirstSearch 함수를 호출하여 알고리즘의 사용법을 보여줍니다.

방법 2: 맨해튼 거리에 따른 휴리스틱 함수

이 문제를 해결하기 위한 우리의 전략에는 맨해튼 거리 개념에 의존하는 휴리스틱 기능의 사용이 필요합니다. 유도 거리라고도 하는 이 거리 측정에는 노드 사이의 수평 및 수직 거리를 추가하는 작업이 포함됩니다.

예

으아아아

출력

으아아아

지침

이 코드는 방법 1과 유사한 구조를 따르지만 맨해튼 거리 공식을 사용하여 대상 노드까지의 예상 거리를 기준으로 노드를 비교하는 사용자 지정 비교기 CompareManhattanDistance를 사용합니다.

greedyBestFirstSearch 기능은 맨해튼 거리 휴리스틱을 사용하여 그리디 베스트 우선 검색 알고리즘을 구현합니다.

메인 함수는 알고리즘의 사용법을 보여주고, 그래프를 생성하고, 시작 노드와 대상 노드를 정의하고,greedyBestFirstSearch 함수를 호출합니다.

결론

이 기사에서는 탐욕스러운 최고 우선 검색 알고리즘과 C++에서의 구현을 살펴봅니다. 이러한 방법을 사용함으로써 프로그래머는 그래프에서 경로를 효율적으로 찾고 최적화 문제를 해결할 수 있습니다. 유클리드 거리 또는 맨해튼 거리와 같은 경험적 기능의 선택은 다양한 시나리오에서 알고리즘 성능에 큰 영향을 미칠 수 있습니다.

위 내용은 C++에서 Greedy Best-First 검색 알고리즘 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!