비용이 이동 이력에 따라 달라지는 그래프의 최단 경로

Question

목표는 도로 (가장자리)와 연결된 주어진 도시 (꼭짓점) 사이의 최단 경로 (최저 비용)를 찾는 것입니다. 각 도로 및 각 도시에는 수수료 (비용)이 해당 도로/도시에 입점하기 전에 지급되어야합니다.

만약 이것이 전체 작업이라면, Dijkstra 알고리즘을 사용하여 최단 경로를 찾고 (그 직전에 연결된 도로 비용에 도시 비용을 추가하십시오).

하지만이 :

도시는 협력 협정 같은 것을 가지고 - 당신이 방문하고 그 중 하나에 요금을 지불 할 때,이 particural 협력 도시의 나머지 부분을 입력 무료입니다.

따라서 꼭지점 (이전에 연결된 가장자리)의 비용은 이미 통과 한 꼭지점에 따라 달라집니다.

그런 종류의 문제에 대한 알고리즘이 있습니까?

감사합니다.

Answer 1

여기서 원하는 것은 클러스터링입니다.

Dijkstra 또는 다른 알고리즘을 실행하기 전에 그래프에서 몇 가지 변경 사항을 실행하여 서로 일치하는 모든 도시가 하나의 새 노드로 변환됩니다.
이 노드에서 도시 중 하나에서 도달 한 모든 도시 (가장 저렴한 코스 선택)에 도달 할 수 있습니다.

이것은 합의한 두 ​​도시 사이의 가장자리의 경우 해당 도로 요금을 0으로 변경하는 것과 매우 비슷합니다.

Answer 2

당신은 세트 커버 문제를 줄일 수 있습니다. 즉, 문제는 NP가 어렵다는 것을 의미하며 일반적으로 효율적인 솔루션을 찾으려고해서는 안됩니다.

즉, 파트너십의 수가 적기를 희망하고, 아마도 비 단통 도로/도시 파트너십의 모든 가능한 하위 집합을 고려하고 각 경로에 대한 최단 경로를 찾는 것으로 벗어날 수 있습니다 (경로 고려중인 특정 하위 집합의 도로/도시 만 통과하게됩니다.) 그런 다음 알고리즘은 2^P * (N + M) 시간에 실행됩니다. 여기서 P는 파트너쉽의 수이고 N과 M은 각각 도시와 도로의 수입니다.

세트 커버 문제는 당신이 n은 유한 집합 S = {S [1], ...,들 [부여하고 있다는 것입니다 : 완성도를 들어

, 여기 그래프 문제에 세트 덮개에서 감소의 ]} 및 S : S [1], S [1], S [2], ..., S [N]의 서브 세트로 구성된다.

최소한의 커버를 찾기 위해 도시 문제를 사용하려면 다음과 같은 그래프를 작성하십시오. 그래프의 꼭짓점을 START, END 및 쌍 (S [i], t)으로하고 t는 S [i]에 놓습니다. 간의 그래프에서 에지를 추가

• START과 (S [I], S [1])은 각각 초 동안 [I]과 S [1]과 S [I]
• (S [I] , s [n]) 및 S [i]의 s [n]을 가진 각 S [i]에 대한 END. 1 ... n-1의 각 k 및 각각의 S [i] 및 S [k]에 대한 (S [i], s [k]) 및 (S [i], s [k] i ']가 포함되어 있습니다.

에지 가중치를 모두 1로하고 입력 비용 (S [i], s)도 1로합시다. 모든 도시/정점 (S [i], s) , t)는 동일한 비용을 공유한다. 두 개의 도로/가장자리가 비용을 공유하지 않습니다.

이제 START에서 END까지의 최저 비용 경로는 S를 포함하는 S [i]의 최소 집합을 찾는 것과 같습니다. 경로의 비용은 1 + n + p가됩니다. 여기서 p는 최소 덮개.

Answer 3

Dijkstra는 올바르게 모델링하면이 문제를 완벽하게 해결할 수 있습니다.

적절하게 말하자면 트럭 상태가 현재 위치뿐 아니라 그 역사라는 것을 인식해야합니다.

class TruckState { 
    City current; 
    List<City> visited; 
} 

참고 : 입장료가 보수적 인 경우 순서는 중요하지 않을 수는 (합의 절 내의 모든 도시에 관계없이 순서, 같은 비용 혜택을 제공?). 그래서 경우 Set 역사를 대표하는, 당신은 작은 검색 공간을 얻을 것이다 :이

class TruckState { 
    City current; 
    Set<City> visited; 
} 

---

이 모든 검색 공간이 아니라 LAGE 있습니다. 만약 당신의 모형이 그것을 허락한다면 다시 더 유 입할 수 있습니다. 예를 들어, 트럭의 유용한 상태가 위치 일 수 있으며 Agreements 인 Set입니다. 이러한 잠금 해제가 가능한 합의가 도시보다 적 으면 상태를 최소한으로 압축합니다.

---

class TruckState { City current; Set<Agreement> unlocked; } 

는 [편집] : 순서의 문제를 보인다는 합의 풀의 첫 번째 도시로 입장료를 지불해야합니다. 계약서의 어느 도시를 먼저 방문했는지 추적해야합니다. 그럼 다음과 같은 상태를 제안한다

class TruckState { 
    City current; 
    Map<Agreement, City> visited; 
} 

참고 : 그것은 매우 어려운 사소한 미만 것이다 허용 휴리스틱을 찾는대로 A-별을 사용하는 것입니다. 귀하의 비용이 어떤 종류의 거리 기능을 포함하는지 모르겠으므로 조언 할 수 없습니다. 상태에 따라 비용이 0이 될 수 있기 때문에, 유일한 허용 가능한 Heurisitic은 상수 값 0입니다. 유용하지 않음 ...