dynamic-programming
동적 프로그래밍을 사용하여 그래프 문제 해결
수색…
Floyd-Warshall 알고리즘
Floyd-Warshall 의 알고리즘은 양 또는 음의 에지 가중치가있는 가중 그래프에서 최단 경로를 찾는 알고리즘입니다. 알고리즘을 한 번 실행하면 모든 꼭지점 쌍 사이의 최단 경로 길이 (합계 가중치)를 찾을 수 있습니다. 약간의 변형으로 최단 경로를 인쇄하고 그래프에서 음수 사이클을 감지 할 수 있습니다. Floyd-Warshall은 동적 프로그래밍 알고리즘입니다.
예를 살펴 보겠습니다. 이 그래프에서 Floyd-Warshall의 알고리즘을 적용 할 것입니다. 
우선 우리는 두 개의 2D 행렬을 취합니다. 이것들은 인접 행렬 입니다. 행렬의 크기는 정점의 총 수입니다. 우리의 그래프에서 우리는 4 * 4 행렬을 취할 것입니다. Distance Matrix 는 두 정점 사이에서 지금까지 발견 된 최소 거리를 저장합니다. 처음에는 가장자리에 대해 uv 와 거리 / 무게 사이의 가장자리가 있으면 w 를 저장합니다. distance[u][v] = w . 존재하지 않는 모든 가장자리에 대해 우리는 무한을 넣을 것입니다. 경로 매트릭스 는 두 정점 사이의 최소 거리 경로를 재생성하기위한 것입니다. 그래서 처음에는 u 와 v 사이에 경로가 있다면 path[u][v] = u 를 넣을 것입니다. 즉, vertex-u 에서 vertex- v 로 오는 가장 좋은 방법은 v 와 u 를 연결하는 가장자리를 사용하는 것입니다. 두 꼭지점 사이에 경로가 없으면 N 을 입력하여 현재 사용할 수있는 경로가 없음을 나타냅니다. 그래프의 두 테이블은 다음과 같습니다.
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 6 | 15 | | 1 | N | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | inf | 0 | -2 | inf | | 2 | N | N | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | inf | inf | 0 | 2 | | 3 | N | N | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | inf | inf | 0 | | 4 | 4 | N | N | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
루프가 없으므로 대각선은 N 으로 설정됩니다. 그리고 정점 자체와의 거리는 0 입니다.
Floyd-Warshall 알고리즘을 적용하기 위해 중간 정점 k 를 선택합니다. 그런 다음 각 꼭지점 i 에 대해 i 에서 k까지 , 그리고 k 에서 j 로 갈 수 있는지 확인합니다. 여기서 j 는 다른 꼭지점이며 i 에서 j 로가는 비용을 최소화합니다. 현재 거리 [i] [j] 가 distance [i] [k] + distance [k] [j] 보다 큰 경우 distance [i] [j]를 이 두 거리의 합계와 같게 지정합니다 . 그리고 경로 [i] [j] 는 경로 [k] [j] 로 설정 될 것입니다. i 에서 k 로 이동 한 다음 k 에서 j 로 이동하는 것이 좋습니다. 모든 정점이 k 로 선택됩니다. 우리는 3 개 중첩 루프를해야합니다 : 1에서 4로가는 k에 대한, 내가 1 일부터 4 일에서 우리는 수표를 겁니다 4. 갈 J으로 이동 :
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
그래서 우리가 기본적으로 검사하는 것은 모든 꼭지점 쌍에 대해 다른 꼭지점을 통과함으로써 더 짧은 거리를 얻는 것입니까? 그래프의 총 작업 수는 4 * 4 * 4 = 64 입니다. 즉, 우리는이 수표를 64 번 할 것입니다. 그 중 몇 가지를 살펴 보겠습니다.
때 K = 1, i가 = 2, J = 3, 거리가 [I] [J] 거리보다 크지 이는 -2 [I] [K] +의 거리 [K] [J] = -2 + 0 = -2 . 그래서 그것은 변하지 않을 것입니다. 또, K = 1, 난 = 4, J = 2, 거리 [I] [J]를 거리보다 큰 무한대 = 때 [I] [K] +의 거리 [K] [J] = 1 + 3 = 4 . 그래서 우리는 distance [i] [j] = 4 를 놓고 path [i] [j] = path [k] [j] = 1을 넣습니다. 이 말은 꼭지점 4 에서 꼭짓점 2 로 가려면 4-> 1-> 2 경로가 기존 경로보다 짧아야한다는 것입니다. 이것이 우리가 두 행렬을 채우는 방법입니다. 각 단계에 대한 계산이 여기 에 표시 됩니다 . 필요한 변경을 한 후에, 우리의 행렬은 다음과 같이 보입니다.
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| | 1 | 2 | 3 | 4 | | | 1 | 2 | 3 | 4 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 1 | 0 | 3 | 1 | 3 | | 1 | N | 1 | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 2 | 1 | 0 | -2 | 0 | | 2 | 4 | N | 2 | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 3 | 3 | 6 | 0 | 2 | | 3 | 4 | 1 | N | 3 |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
| 4 | 1 | 4 | 2 | 0 | | 4 | 4 | 1 | 2 | N |
+-----+-----+-----+-----+-----+ +-----+-----+-----+-----+-----+
distance path
이것은 우리의 최단 거리 매트릭스입니다. 예를 들어, 1 에서 4 까지의 최단 거리는 3 이고 4 와 3 사이의 최단 거리는 2 입니다. 우리의 의사 코드는 다음과 같습니다.
Procedure Floyd-Warshall(Graph):
for k from 1 to V // V denotes the number of vertex
for i from 1 to V
for j from 1 to V
if distance[i][j] > distance[i][k] + distance[k][j]
distance[i][j] := distance[i][k] + distance[k][j]
path[i][j] := path[k][j]
end if
end for
end for
end for
경로 인쇄 :
경로를 인쇄하려면 경로 행렬을 확인합니다. u 에서 v 까지 경로를 인쇄하려면 경로 [u] [v] 부터 시작합니다. 우리는 변화하는 V = 경로를 계속 설정합니다 [유] [V] 우리가 찾을 때까지 경로 [U] [V] = U를하고 [U] [V] 스택에 경로의 모든 값을 누릅니다. U를 발견하고 난 후에, 우리는 U를 인쇄하고이를 스택에서 항목을 보여주고 시작하고 인쇄 할 수 있습니다. 이것은 경로 행렬이 다른 노드의 v에 대한 최단 경로를 공유하는 정점의 값을 저장하기 때문에 작동합니다. 의사 코드는 다음과 같습니다.
Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
S.push(Path[source][destination])
destination := Path[source][destination]
end while
print -> source
while S is not empty
print -> S.pop
end while
네거티브 에지 사이클 찾기 :
네거티브 에지 사이클이 있는지 알아 보려면 거리 매트릭스의 주 대각선을 확인해야합니다. 대각선의 값이 음수이면 그래프에 음수 사이클이 있음을 의미합니다.
복잡성:
Floyd-Warshall 알고리즘의 복잡성은 O (V³) 이고 공간 복잡도는 O (V²) 입니다.
최소 정점 커버
최소 정점 커버 는 고전적인 그래프 문제입니다. 예를 들어, 한 도시에서 약간의 지점을 연결하는 길은 몇 개 있습니다. 노드를 사용하여 가장자리와 점을 사용하여 도로를 표현합시다. 두 가지 예제 그래프를 보겠습니다.
우리는 파수꾼을 몇 가지 점에서 설정하려고합니다. 파수꾼은 그 지점에 연결된 모든 도로를 감시 할 수 있습니다. 문제는 모든 도로를 감당할 수있는 파수꾼의 최소 수는 얼마인가? 우리가 노드 A , B , H , I 및 J 에서 파수꾼을 설정하면 모든 도로를 커버 할 수 있습니다.
이것이 우리의 최적의 솔루션입니다. 우리는 도시 전체를 지키기 위해 최소한 5 명의 경비원이 필요합니다. 이것을 결정하는 방법?
처음에는 이것이 NP 어려운 문제, 즉 문제에 다항식 시간 솔루션이 없음을 이해해야합니다. 그러나 그래프가 트리 라면, 즉 n-1 개의 노드가 있고 n 은 에지의 수이고 그래프에는 사이클이 없으면 동적 프로그래밍을 사용하여 해결할 수 있습니다.
DP 솔루션을 구축하려면 두 가지 전략을 따라야합니다.
- 노드에 파수꾼이 없으면 노드에 연결된 모든 노드에 파수꾼이 있어야합니다. 그렇지 않으면 모든 도로가 덮히 지 않습니다. u 와 v 가 연결되어 있고 u 가 파수꾼이 없다면 v 에는 파수꾼이 있어야합니다.
- 한 노드에 파수꾼이있는 경우, 파수꾼과 연결된 다른 노드에 파수꾼이있을 수도 있고 없을 수도 있습니다. 그것은 파수꾼이 필요하지는 않지만 유용 할 수 있음을 의미합니다. U와 V가 연결되어 있고 u는 경비원이있는 경우, 우리는 확인에 의해 우리에게 도움이되는 찾을 수 있습니다 :
- 파수꾼을 v .에 세우다.
- v .에서 경비원을 지정하지 않음.
상태가 현재 노드이고 파수꾼이 있는지 여부와 함께 재귀 함수를 정의합시다. 이리:
F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.
이 함수는 나머지 노드에있는 파수꾼의 수를 반환합니다.
예제 트리를 보겠습니다.
우리가 node- A 에 파수꾼을 배치하지 않으면 노드 B , C 및 D 에 파수꾼을 배치해야한다고 쉽게 말할 수 있습니다. 우리는 추론 할 수 있습니다 :
F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0
우리가 노드 A 에 파수꾼을 배치하지 않으면 필요한 파수꾼의 수를 반환합니다. 우리는 현재 노드에서 파수꾼을 설정하지 않았으므로 끝에 0 을 추가했습니다.
이제 F(A,1) 는 node- A 에서 파수꾼을 설정한다는 것을 의미합니다. 이를 위해 연결된 모든 노드에서 파수꾼을 설정할 수도 있고 그렇게하지 않을 수도 있습니다. 최소한의 파수꾼을 우리에게 제공 할 것입니다.
F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1
우리는 각 노드에서 파수꾼을 설정하고 최적 값을 취하는 것으로 설정하여 점검합니다.
한 가지주의해야 할 것은, 일단 우리가 자식 노드에 가면 우리는 결코 부모 노드를 되돌아 보지 않을 것입니다. 위의 예에서 우리는 A 에서 B 로갔습니다. 따라서 parent [B] = A 입니다. 그래서 우리는 B 에서 A 로 돌아 가지 않을 것입니다.
기본 사건을 결정하기 위해 노드에서 다른 노드로 갈 수 없다면 현재 노드에 파수꾼이 있다면 1을 , 현재 노드에는 파수꾼이 없다면 0을 반환합니다. 마디.
우리 나무에 대한 인접 목록을 갖는 것이 좋습니다. 목록을 가장자리 로 표시하십시오. 우리는 배열 dp [n] [2]를 가질 것입니다. 여기서 n 은 계산 된 값을 저장하고 -1로 초기화 할 노드의 수를 나타냅니다. 노드 사이의 부모 및 자식 관계를 나타 내기위한 부모 [n] 배열도 있습니다. 우리의 의사 코드는 다음과 같습니다.
Procedure f(u, isGuarded):
if edge[u].size is equal to 0 //node doesn't have any new edge
Return isGuarded
else if dp[u][isGuarded] is not equal to -1 //already calculated
Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
v := edge[u][i]
if v is not equal to parent[u] //not a parent
parent[v] := u
if isGuarded equals to 0 //not guarded, must set a watchman
sum := sum + f(v,1)
else //guarded, check both
sum := sum + min(f(v,1), f(v,0)
end if
end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]
노드 A 를 루트로 나타내면 min(f(A,1), f(A,0)) 함수를 호출합니다. 즉 루트 노드에서 파수꾼을 설정하는 것이 가장 적합한 지 여부도 확인합니다. 이것이 당사의 DP 솔루션입니다. 이 문제는 최대 매칭 알고리즘 또는 최대 흐름을 사용하여 해결할 수도 있습니다.