제약 조건의 최대 용량 경로 문제

Question

제약 조건의 최대 용량 문제에 대한 알고리즘을 개발하려고했지만 올바른 출력에 필요한 변경 사항을 알아낼 수는 없습니다. 문제는 다음과 같습니다 :
두 개의 매개 변수 (무게, 비용)가있는 미리없는 그래프가 주어집니다. 최대 용량 경로 문제가 소스에서 목적지까지 (경로의 합계)가 사용자가 지정한 고정 값 내에있는 것과 같은 소스에서 대상까지입니다.즉, (경로를 따라 비용 매개 변수의 합)은 일정한 가치에 의해 상한이 묶여 있습니다.
나는 에지를 이완시키면서 기존의 알고리즘을 추가하고 추가 비용의 제약을 추가함으로써 모든 유형의 그래프에 대해 일할 수 없었습니다.이 문제가 NP 완료인지 궁금했습니다.

Answer 1

다항식 시간에 해결할 수 있습니다.예를 들어, 무게보다 바이너리 검색을 사용할 수 있습니다.후보 체중이 주어지면 무게가 낮은 모든 가장자리를 삭제 한 다음 가장 낮은 비용 경로를 찾아서 비용이 하한보다 낮은지 여부를 테스트하십시오.그것은 무게가 너무 높거나 너무 낮았 지 여부를 알려줍니다.바이너리 검색이 수렴 할 때까지 반복하십시오.