1. Read chapters 7.1 – 7.7.
2. Solve the exercise problem 14 of the chapter 7.
14. 합병정렬 알고리즘(알고리즘 2.2와 2.4)에서 레코드의 저장 횟수를 기준으로 할 때 시간복잡도는 대략 T(n) = 2n lg n이 됨을 증명하시오.
합병정렬을 하기 위해서는
1. 기존의 주어진 배열(S[])을 두개의 배열을 가운데 인덱스를 기준으로 나누는 과정이 필요하다.
2. 나누어진 배열을 각각 U[1...h]와 V[1...m]에 copy해 저장한다.
3. copy한 값을 각각 mergesort 한다.
4. mergesort한 배열들을 다시 S[]로 합친다.
레코드에 저장횟수를 기준으로 시간복잡도를 구한 것은 합병병렬의 평균의 시간 복잡도와 같다. 합병병렬은 기존의 배열을 두개의 배열로 나누었으므로 합병병렬의 평균의 시간 복잡도의 2배가 된다. 그러므로 합병병렬을 레코드에 저장회수를 기준으로 시간 복잡도를 구했을 때, T(n) = 2n lg n임을 알 수 있다.
3. Refer to graph examples 1 and 2 on pages 21-22 of the class material titled 'Class material 06.pdf'. Given the graph, perform a Bi-Directional Search. The source vertex is 's', and the target vertex is 'D'. Draw the graphs for each step of your procedure.
Bi-Directional Search(양방향탐색)
1. 출발 노드(S)와 도착 노드(D)를 설정한다.
2. 출발 노드와 도착 노드에서 동시에 너비우선탐색(BFS)를 실시한다.
3. 출발 노드와 도착 노드가 동시에 만나는 지점이 나타날 때까지 반복한다.
example 1과 example 2 를 비교하였을 때, example 1은 시작 노드에서 도착 노드로 가는 최단거리를 찾았지만, example 2는 최단거리를 찾지 못하였다.
4. Can you improve this Bi-Directional Search algorithm? Describe the procedure.
note. The third problem in the class material has been updated as described above.
1. 다익스트라 알고리즘을 양방향탐색 알고리즘에 추가하여 사용한다면, 양방향 탐색 알고리즘을 향상시킬 수 있을 것이다.
chap GPT 참고했습니다.....
chat GPT 답변:
다익스트라 알고리즘을 사용한 양방향 BFS: 일반 BFS를 사용하는 대신 Dijkstra의 알고리즘을 사용하여 시작 노드와 종료 노드 모두에서 동시에 최단 경로를 찾을 수 있습니다. 이를 통해 방문해야 하는 노드 수를 크게 줄여 검색 시간을 단축할 수 있습니다.
A* 검색: A* 검색은 휴리스틱을 사용하여 검색을 목표로 유도하는 정보 검색 알고리즘입니다. 우리는 양방향 검색 알고리즘을 개선하기 위해 좋은 휴리스틱 기능을 가진 A* 검색을 사용할 수 있습니다. 도메인별 지식을 통합하여 A* 검색은 BFS보다 더 효율적으로 최적의 경로를 찾을 수 있습니다.
양방향 DFS: 양방향 검색 알고리즘을 개선하는 또 다른 방법은 BFS 대신 양방향 DFS를 사용하는 것입니다. 양방향 DFS는 경우에 따라 BFS보다 메모리 효율적이고 빠를 수 있습니다. 그러나 최적 경로를 찾지 못할 수도 있습니다.
양방향 IDDFS: 양방향 반복 심화 깊이 우선 검색(Bidirectional IDDFS)은 양방향 검색과 반복 심화 깊이 우선 검색(IDDFS)의 조합입니다. 알고리즘의 메모리 사용량과 런타임을 줄이면서 최적의 경로를 찾는 데 사용할 수 있습니다.
양방향 검색 알고리즘을 개선하기 위한 일반적인 절차에는 적절한 검색 알고리즘을 선택하여 당면한 문제에 적용하는 것이 포함됩니다. 검색 알고리즘의 선택은 검색 공간의 크기, 분기 요인 및 사용 가능한 경험적 정보와 같은 문제의 특성에 따라 달라집니다. 올바른 알고리즘을 선택하고 매개 변수를 최적화함으로써 양방향 검색 알고리즘의 효율성과 효과를 향상시킬 수 있습니다.
