나는이 문제에 상당히 혼란스러워합니다. 글을 올리기에 새롭다. 어리석은 질문이라면 나를 용서해주십시오.대상 비용으로 스패닝 트리 찾기
가중치가있는 그래프 G = (V, E)가 주어집니다. 나는 스패닝 트리의 비용이 모든 에지 비용의 합으로 정의되는 c의 목표 비용으로 G의 스패닝 트리를 생성하려고합니다. 비용 c를 갖는 G의 스패닝 트리가 존재하는지 어떻게 결정할 수 있습니까?
여기에 찌르다. 동적 프로그래밍을 사용하여 부분 집합 합계 문제를 풀고 각 하위 집합에 대해 스패닝 트리를 형성하는지 확인하면됩니다. 일부 합의 일반적인 제형 간다 : C는 [내가 S]가 제가
하자 즉 임의의 에지가되도록 합산 S의 서브 세트가 문
의 부울 값이라하자 . 그 후 재발은 보통 간다 :
C [내가 S '[또는 C U E는]에만 true C I, S] ='[I - 중량 (E), S ']
(가장자리 e를 사용하거나 그렇지 않으면 가장자리 e를 사용하여주기가 형성되지 않도록하십시오).
목표 비용이 c이면 각 1 n 개의 스윕을 수행해야합니다. < = i < = c 여기서 n은 모서리 수입니다.
마지막으로 선택한 모서리 수가 정점 수보다 1 작고 모두 연결되어 있는지 확인합니다.
다른 방법은 역 추적 재귀를 사용하여 모든 스패닝 트리를 검색하는 것입니다. < = targetCost.