3
가정하자 내가 스패닝 트리 계산에 제한 3 종류가 있습니다제약도 + 경계 직경 최소 스패닝 트리에 대한 알고리즘?
- 제약 정도를 (예 : 스패닝 트리 만 다른 3 개의 노드를 연결 수 있습니다 의 노드)
- 경계 직경 (예 : 모든 가장자리의 가중치는 합산 된 후 100을 초과 할 수 없습니다.
2.1. 가능하면이 기준을 충족하는 모든 하위 트리를 표시하십시오. - 두
거야되지 않은이 문제를 해결 미친 저를 모는 좋은 알고리즘이 있습니까? 다소 큰 inpputs (1000 개 이상의 노드)를 사용하여이 작업을 수행해야하므로 복잡성이 너무 높아질 수 없습니다.
나는 그것을 이해하지만, 나는 최적의 해결책을 찾고 있지 않다. 그러나 그렇다고해서 내가 직접 뭔가 해킹 할 수있는 것은 아닙니다. – iceburn
그가 지적한 참고 자료는 근사 알고리즘에 대한 논문과 연결되어 있습니다. – kunigami