최근 스패닝 트리의 총 비용이 다음과 같이 주어진 그래프의 최소 비용 스패닝 트리를 계산하는 알고리즘을 찾을 수 있는지 물어 보았습니다. 그들의 합계보다는 가장자리 비용의 산물.에지 가중치를 곱하여 비용을 계산할 때 최소 스패닝 트리를 찾는 알고리즘
정규 미니멈 스패닝 트리를 계산하는 데 몇 가지 알고리즘이 있지만 위의 경우에 맞게 조정하는 방법을 잘 모르겠습니다. 어떤 아이디어?
감사합니다.
로그 (에지 비용의 곱) = 합계 (로그 (에지 비용))이므로 에지 가중치를 로그 변환하고 이러한 가중치에 대한 최소 비용 스패닝 트리를 찾습니다.
내 생각 - 무차별로 모든 최소 (불필요한 가장자리를 의미) 스패닝 트리를 찾아 가장 작은 제품으로 선택하십시오.
대부분의 (또는 모든) 효율적인 솔루션은 더 이상 적용되지 않습니다. 주로 최적의 솔루션입니다. 더 이상 최적의 하위 문제가 더 이상 포함되지 않습니다. (제한은 무엇입니까? 매우 중요합니다 - 1보다 작은 비용의 가장자리는 실제로는 음의 비용입니다. 길이 1의 모서리는 자유 롭습니다.) 그들은 모두 긍정적 인 결과를 얻었습니다.
이 질문이 정말로 중요한 것인지 확실하지 않습니다. 우리는 제로 (zero)로 제품을 가져갈 수 없기 때문에 자체 루프 비용 (또는 1로 가정)을 지불해야합니다. 경로 분할은 다르게 작동합니다. 동일한 경로를 두 번 이동하는 것은 c^2 비용입니까? 또한, '비용'과 다른 이름의 경로 품질이 달라야한다고 생각합니다.
논의를 위해 모든 비용은 양수가 1보다 크거나 같음. 아이디어를 제공해 주셔서 감사합니다. – AlexTex
대수는 단조 변환이므로 모든 로그를 취하면 최소 스패닝 트리가 완전히 동일합니다 가중치와 모든 가중치를 그대로 두는 것입니다. 그래서 모든 무게의 합과 모든 무게의 곱에 따라 MST를 찾는 데 차이가 없습니다. 그래프 의 최소 스패닝 트리가 graoh의 무게의 모노톤 변환을 향한 불변 사실 의 증거의 기사에 대한
, 유형 구글에서 최소 스패닝 트리 의 사가. 첫 번째 링크가 필요한 링크입니다. 페이지 167, 모노톤 동형 이성.
좋은 답변입니다! 아프다면 제약 조건을 분명히 말하면됩니다. 비용은 모두 양수 여야하며, 모두 1보다 커야합니다. –
@jon_darkstar 맞습니다. 모두 긍정적이어야하지만 0-1 값은 괜찮습니다. 결과 트리는 최소 비용 부분 그래프가되지 않습니다 (여분의 가장자리를 추가하면 잠재적으로 비용이 감소 할 수 있기 때문에)하지만 최소 비용은 여전히 _tree_입니다. – Aniko
네가 맞아, '나무'구속은 이미 그런 어리 석음을 막는다. –