1/0 백분위 가중치가 적용된 배낭 변형

Question

현재 라우팅 문제를 조사 중입니다. 최대 여행 시간을 초과하지 않고 방문하고 싶은 장소의 하위 집합을 찾은 다음 변형을 제안했습니다. 원래의 문제를 해결하는 것 같아 보이는 1/0 배낭 문제.

은 위키에 1/0 배낭 같이 설명있어서

가

항목 세트가 지정하는 질량 값 각각이되도록 컬렉션에 포함시키고 각 항목의 수를 결정 총 가중치가 주어진 제한값보다 작거나 같고 총 값이 가능한 한 커야합니다.

따라서 각 항목에 대해 동적 프로그래밍을 사용하여 문제를 해결할 때 쉽게 사용할 수있는 고정 무게 (질량)가 있습니다.

그러나 특정 항목 의 무게는 가방의 이전 내용에 의존하는 경우? 즉 (그리고 더 일반적인 방법으로) :

각 노드

을 (를 A, B, C, D, E)이 내가 투입 할 수 있습니다 항목을 나타냅니다의 다음과 같은 전체 그래프를 살펴 보자 내 배낭. 각 노드에 특정 값이 할당되어 있다고 가정 해 봅니다 (그래프에 표시되지 않음). 나는 여전히 최적의 배낭을 가지기를 원한다. 따라서 최대 점수를 가진 노드의 부분 집합이지만, 이번에는 현재의 배낭에 특정 노드를 추가하는 비용이 노드 자체에 할당되지 않고 가장자리에 할당된다. 그것으로 이어진다.

노드를 추가하는 비용은 배낭의 이전 내용에 따라 달라집니다 (예 : 이미 포함 된 노드 중 가장 적은 비용으로 가장자리를 사용). 예를 들어, 현재 배낭이 {A, C}로 구성된 경우 B 추가 비용은 2 (A-> B 또는 C-> B 중 하나를 취함)입니다. 현재 배낭이 {D, E}로 구성된 경우 B를 추가하는 데 드는 비용은 대신 3입니다.

불행히도이 문제를 해결하기위한 좋은 알고리즘을 찾을 수 없습니다. 고전적인 배낭 DP 접근 방식은 최적의 솔루션을 반환하지 않는 경우를 쉽게 만들 수 있기 때문에 실제로 여기서 작동하지 않습니다. 예를 들어 "잘못된"노드가있는 배낭 만들기를 시작하면 매우 좋은 노드를 추가하는 데 드는 비용 (최적의 솔루션에 포함해야하지만 늦게 시도해야 함)이 용량을 초과 할 수 있습니다.

문제에 완전히 접근하지 못하고 있습니까? 이 문제를 해결할 수있는 더 나은 알고리즘이 있다고 생각합니까?

Answer 1

우선이 문제는 NP 하드입니다. 다음은 가중치가 적용된 전체 그래프에서 가장 짧은 해밀턴 경로에서이 그래프로의 감소입니다. 그래프가 주어지면 모든 노드의 값을 1로 지정한 다음 해답을 통해 이진 탐색을 실행할 수 있습니다. 이 문제에 대한 다항식 솔루션이 있다면 모든 정점을 포함하고 주어진 값보다 길지 않은 경로가 있는지 확인할 수 있습니다. 따라서 우리는 다항식 시간에서 가장 짧은 해밀턴 경로 문제를 풀 수있을 것이다. 실제로 그것은 아무도 문제에 대한 효율적인 올바른 다항식 해결책을 모른다는 것을 의미합니다. 정점의 수 (20의 주위에) 오히려 작은 경우 정확한 솔루션을 얻기 위해 동적 프로그래밍을 사용할 수

1. :

   지금이 개 갈 수있는 방법이 있습니다. 상태는 (mask, last_vertex)입니다.값은 mask의 모든 꼭지점을 방문하고 last_vertex에 멈추는 데 필요한 최단 시간입니다. 이 솔루션의 시간 복잡도는 O(2^n * n^2)입니다.

2. 정점의 수가 훨씬 큰 경우 대략적인 해결책을 찾을 수 있습니다. 휴리스틱 (heuristics), 다양한 욕심 많은 알고리즘, 지역 최적화를 통한 무작위 샘플링 등 여러 가지 방법이 있습니다.