0
나는 profit (i, j)가 profit (j, i)와 같지 않을 수 있도록 각 꼭지점 쌍 사이에 정의 된 약간의 이윤을 가진 꼭지점 집합을 가지고 있습니다. 또한, 양의 가중치 사이클이 있고 이윤은 음수 일 수 있습니다.양수 가중치 사이클을 가진 그래프에서 최대 이익
최대 이익을 찾는 것이 NP 하드 문제이므로 문제는 최대 1 개 도시 (모든 도시를 방문 할 필요가 없음)를 방문하는 이익을 최대화하는 것입니다. 다음 알고리즘을 찾으려고 시도했습니다.
- 완전한 정점 집합에 대한 욕심쟁이 알고리즘입니다.
- 무차별 대입 욕심 : 먼저 탐욕스러운 일련의 정점을 찾으십시오. 이것은 거의 클러스터를 형성하는 정점의 근사 세트를 제공합니다. 이제 연속적으로 8 개 도시를 말하며 무작위로 최대 이익을 발견 할 수 있도록 재정렬하십시오.
하지만 100 개의 정점에서 시도해도 좋은 결과는 아닙니다.
비용을 최대화 할 수있는 다른 확률적인 방법이나 근사적인 방법이 있습니까?
나는 그것을 시도했다. 그것은 모든 도시를 방문 할 필요가있을 때 가장 잘 적용됩니다. –
가장자리 무게가 엄격하게 긍정적입니까? – smk
아니요, 수정했습니다. –