나는이 문제를 가지고 있으며 효율적인 솔루션을 보지는 못하고 있지만 무차별 접근 방식을 취하고 있습니다. 누가 내게 돈을 빌려 줄까?그래프와 제약 조건 일치
이 문제는 그래프 G = (V, E)로 지정되고 가중치 및 비순환 식으로 구성됩니다. 엣지에는 가중치 w (u, v)가 있습니다. (u, x)와 (u, y)가 존재하면 w (u, v)의 값은 원점 (w (u, x) = w (u, y)에만 의존합니다. 원래, 각 버텍스는 들어 오거나 나가는 가장자리가 여러 개있을 수 있습니다. 목표는 총 잔량이 최대 인 방식으로 최대 하나의 정점 당 하나의 나가는 가장자리를 유지하는 것입니다. 나가는 모서리가있는 정점 에는 들어오는 자릿수가있는을 포함 할 수 없습니다. 예를 들어, 그림 1을 고려하십시오. 왼쪽 그래프는 원래 그래프입니다. 많아야 하나의 나가는 가장자리를 유지하면서 오른쪽 그래프는 최대 총 무게를위한 솔루션을 나타냅니다. 17
그러나이 문제에 또 다른 제약이 있습니다. 각 정점에는 2 개의 값, 용량 및로드가 지정됩니다. 용량은 얼마나 많은 부하가 걸릴 수 있는지 말합니다. 최대 총 중량 구성을 찾는 동안 용량도 고려해야합니다. 그림 2는 그림 1과 같은 그래프이지만 용량 제한이 결정적인 역할을합니다. 이 상황에서 최대 총 무게 구성이 다른 것을 확인하십시오 (오른쪽 그래프, 그림 2). 요약
최대 총 중량을 얻기 위하여 제한이 3 :
- 복종 용량 제한;
- 나가는 가장자리가있는 꼭지점에는 들어오는 가장자리가 없습니다.
- 정점에는 최대 하나의 나가는 가장자리가 있습니다.
내가 알아 낸 유일한 해결책은 가능한 모든 구성을 테스트하고 유효한지 추적하여 최대한 추적하는 것입니다. 누구든지이 문제를 해결할 더 나은 접근법을 가지고 있습니까?
[cstheory.se]로 확인하십시오. –