최근 인터뷰에서 다음 질문을 받았습니다 : 사이클이없는 양방향 그래프 G가 있습니다. 각 모서리에는 약간의 무게가 있습니다. 또한 노드 K의 집합이 서로 분리되어야합니다 (일부 가장자리 제거). K 세트의 두 노드 사이에는 하나의 경로 만 있습니다. 목표는 제거 된 모서리의 전체 가중치를 최소화하고 집합 K에서 모든 노드를 서로 분리하는 것입니다.bidirected 그래프에서 가중치 끝을 제거하십시오.
내 접근 방식은 K 세트에서 각 노드에 대해 BFS를 실행하고 모든 노드 쌍 사이의 모든 경로를 K에서 결정하는 것이 었습니다. 그렇다면 경로 집합을 가질 것입니다 (각 경로는 모서리 집합입니다). 다음 단계는 동적 프로그래밍 방식을 적용하여 제거 된 가장자리의 최소 총 무게를 찾는 것입니다. 그리고 여기에서 나는 갇혔다. DP가 어떻게 수행되어야하는지에 대해 저에게 직접 도와주십시오.
감사합니다.
"양방향"그래프가 방향이없는 그림과 같다고 가정 할 때이 소리는 나무의 다 방향 컷 문제와 유사합니다. 직접적인 동적 프로그래밍을 통해 다항식 시간으로 풀 수 있습니다. Chopra와 Rao : "On the multiway cut polyhedron", Networks 21 (1) : 51-89, 1991을 참조하십시오. this question도 참조하십시오.
이 문제는 분리 세트를 사용하여 해결할 수 있습니다. 이 문제에서는 숲과 같은 각 정점 집합을 만들어야합니다. 그런 다음 그래프에있는 모서리를 통해 서로 다른 두 세트에 속한 꼭짓점을 결합하여 다음과 같이 합니다. -
1 세트 중 하나에 k 세트의 노드에 언급 된 노드가 포함되어 있으면 노드는 다음과 같이됩니다. 대표 요소.
2) 두 세트 모두 원하지 않는 노드 (k 노드 세트에있는 노드)가 포함 된 경우 두 세트에서 최소 가중치 에지를 찾아 비교 한 다음 최소 에지를 에지와 비교하십시오 합쳐져 최소한을 찾아야한다. 그런 다음 찾은 가장자리를 삭제하여 경로가 존재하지 않도록하십시오.
3) 세트 중 어느 것도 원하지 않는 노드를 포함하지 않으면, 한 세트를 다른 세트에 결합하십시오.
이렇게하면 O (nlogn)의 순서로 매우 복잡한 시간 내에 파괴 된 가장자리의 최소 총 무게를 찾을 수 있습니다. 당신의 접근 방식도 효과가 있지만 시간 복잡성면에서 비용이 많이 드는 것으로 판명 될 것입니다. 여기
는 전체 코드입니다 - (GameAlgorithm.cpp) https://github.com/KARTHEEKCIC/RoboAttack
두 노드 사이의 하나의 경로 만이 있다면 당신은 _all_을 제거 할 필요는 없습니다 당신은 다른 사람과 모든 노드를 분리해야 사이? – BlackBear
아니요, 각 경로에서 하나의 가장자리를 제거하면 연결이 끊어집니다. 문제는 제거 할 모서리를 선택하는 방법입니다. –
내가이 질문을 이해한다면, K의 노드는 서로 연결이 끊어 져야하지만, K에없는 G 노드가 반드시 연결되어야하는 것은 아닙니다. 맞습니까? –