기록기록 우는 갈매기

backtracking은 깊이우선탐색(DFS) 방식으로 상태공간트리를 탐색하는 알고리즘으로, 최적화 문제를 해결하는데에 사용될 수 있다. backtracking의 진행절차는 다음과 같다. ① 상태공간트리의 깊이우선검색(DFS)을 실시 ② 각 노드가 유망(promising)한지 점검 ③ 유망하지 않은 노드들은 더 이상 검색하지 않고 그 노드의 부모노드로 돌아가서 검색을 계속(pruning), 유망한 노드들은 그 노드의 자식노드를 검색 여기서 promising, 즉 유망하다는 것은 더 내려다볼 가치가 있다는 것이고 반대로 유망하지 않다(non-promising)는 것은 전혀 해답이 나올 가능성이 없다는 것을 의미한다. 유망하지 않으면 그 자식노드에 대한 탐색을 중단하고 부모노드로 돌아가는데, 이를 '가지친다..

프림 알고리즘의 locally optimal의 기준은 이미 방문한 정점들의 집합 Y에서부터 방문한 적이 없는 한 정점까지의 거리이다. 즉, 방문한 적이 없는 정점들 중 출발점과의 거리가 가장 가까운 정점부터 선택한다는 것이다. 이 과정을 간단한 수도코드와 그림으로 나타내면 다음과 같다. 수도코드(high level) F := ∅; //edge의 집합 Y := {v1}; //vertex의 집합, 출발점을 포함한 상태로 시작 while(the instance is not solved) { select a vertes in V-Y that is nearest to Y; //selection procedure, feasibility check add the vertex to Y; add the edge to F..

greedy approach를 신장트리로 시각화할 수 있다. 신장트리는 정점이 서로 연결되어있고 방향이 없는 그래프에서 순환 경로가 없도록 엣지를 제거하되 모든 정점이 그래프에 포함되도록 연결한 부분 그래프이다. 여기서 비용이 최소가 되도록 연결한 그래프(신장트리)를 최소비용 신장트리라고 한다. 글로만 읽으면 무슨 말인지 이해가 잘 안될테니 그림으로 이해해보자. 아래 그림은 신장트리의 한 예를 보여준다. 위 그림의 신장트리가 과연 최소신장트리일까? 오른쪽의 신장트리가 왼쪽의 그래프에서 도출될 수 있는 그래프들 중 비용이 가장 적은 그래프일까? 그렇지 않다. 비용이 더 작은 엣지들을 사용해서도 충분히 모든 정점들을 이으면서 순환 경로가 없도록 그래프를 만들 수 있다는 것을 알 수 있다. 하지만 이는 위의 ..