0
해결하려는 시나리오는 연결된 유향 그래프의 각 정점이 값이 인 최대화 문제입니다. 그러나 각 모서리와 정점도 입니다. 시작 정점과 비용 예산을 감안할 때주어진 서브 그래프 "값"최대화
, 정점 값 (시작 정점 포함) 을 극대화 연결된 서브 그래프를 찾을 수있는 추천 알고리즘 또는 방법이있다?
A
답변
0
이것은 각 터미널의 값을 1로 설정하고 각 꼭지점의 비용을 0으로 설정하고 각 가장자리의 비용을 1로 설정하여 Steiner tree problem in graphs을 해결하기위한 알고리즘을 사용할 수 있으므로 NP 하드입니다. k의 비용 예산을 가진 알고리즘이 모든 터미널에서 값을 캡처 할 수있는 경우에만 k가있는 Steiner 트리가 있습니다.
Steiner 나무에 대한 문헌을 조사하여 근사해에 대한 아이디어를 얻을 수 있습니다.
감사합니다. 매우 도움이되었습니다. 슈타이너 트리 (Steiner Trees)에 대한 배경 지식과 특히 슈타이너 트리 (Steiner Tree) 문제 및 그 변형을 수여하는 상을 받았습니다. 관심있는 두 가지는 노드 가중 및 에지 가중치입니다. –