선생님은 그 문제에 대한 동적 프로그래밍 솔루션을 구현하도록 요청했지만 Google을 사용하여 찾을 수 없기 때문에 존재하지 않는다고 생각합니다.k 최소 스패닝 트리를 계산하는 동적 프로그래밍 방법이 있습니까?
어쨌든 그래프와 k, 예를 들어 3이 주어지면 3 개의 최상위 MST를 찾아야합니다. 그래프에 k 하위 트리가없는 경우 동일한 트리를 여러 번 또는 최적이 아닌 트리를 반환 할 수 있습니다.
나는 그것에 대한 해결책을 정말로 생각할 수 없다.
당신은 저에게 잠시 혼란을 겪었고 당신이 그 문제를 오해했을 수도 있다고 생각했습니다. "k-MST"문제는 모서리의 합이 k 모서리의 하위 트리에서 얻을 수있는 다른 모든 합계보다 작거나 같도록 하위 트리를 형성하는 k 모서리를 찾는 것으로 구성됩니다. 그런데 나는 복수형을 보았다.
그래, 문제가있어, 개인적으로 "다음"MST를 생성하는 방법과 결합 된 MST를 찾는 DP 알고리즘을 찾으려고합니다. 이것은 동적 프로그래밍이기 때문에 반복적으로 무언가를 최적화 (이 경우에는 각 단계마다 최적화되지 않음)하거나 가장자리를 MST 설정에서 의미가있는 부분 집합으로 분할하는 다양한 방법을 살펴볼 것입니다. 몇 가지 방법이있을 수 있습니다.
그러나, 파티션과 최소 스패닝 트리를 찾고 난 그냥 대답하려는 경우 도움이 더 될 수있는이 발견 : http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004
무엇? 욕심 많은 알고리즘은 DP 알고리즘이 아니며 사용자의 대답이 전혀 도움이되지 않습니다. 그는 ** 무엇을 찾을 지 ** 묻는 중입니다 ** 찾을 수있는 것이 ** 없습니다. -1. – IVlad
사과드립니다. 탐욕에 대한 언급을 삭제하겠습니다. 다른 오해였습니다. (아직도 k-MST에 대해 생각하고 있었는데, 대부분의 MST 세대와 마찬가지로 욕심 많은 방식으로 하위 검색을 선택했습니다). 그리고 예, 당신 말이 맞아요, 나는 명백한 대답을하지 못했습니다. 어떻게 생각하거나 접근 할 수 있을까요? (숙제 문제이므로) – integer
실제 솔루션에 대한 설명이 추가되었습니다. – integer
날 믿어을, 대답을 알고있는 재미가 없다. 답변을 통해 자신 만의 길을 찾는 것이 실제 ** 재미 ** –
@Gollum : 음, +1에 대한 귀하의 의견 :-) –
'Google을 사용하여 찾을 수 없기 때문에 사람이 존재하지 않는다고 생각합니다. ': 나는 인터넷 검색이 생각보다 빨리 얻은 이후로 슬픈 시간임을 비웃는 사람을 기억합니다. –