그래서 여행자가 그래프에서 특정 거리를 여행 할 수 있고 모든 양방향 가장자리가 길이 (거리)가있는 문제를 발견했습니다. 특정 가장자리 (어느 방향)를 여행 할 때 여행 할 수있는 주어진 거리에 대해 수집 할 수있는 최대 금액을 찾아야하므로 돈/선물 (모든 가장자리에 문제가 있음)이 표시된다고 가정하십시오. 기본적인 문제는 주어진 거리 (그래프에 루프가있을 수 있음)로 가능한 모든 경로를 찾는 방법이며 가능한 모든 경로를 찾은 후 수집 된 최대 금액의 경로가 단순히 답이 될 것입니다. 참고 : 가능한 모든 경로는 반복문 (직선 경로)이 있어서는 안됩니다.그래프 이론, 주어진 거리를 가진 모든 경로
가장자리 (거리 및 보상)에 이중 가중치가있는 연결되지 않은 연결된 그래프가 표시됩니다. 가능한 거리에 해당하는 고정 숫자 d가 부여됩니다. 각 노드 쌍 (유, v)를, u는 당신이 누구의 총 거리를 d없이 반복 노드와 u와 V를 연결
처음에는 플로이드 - 와샬 알고리즘의 수정 된 버전을 사용하려고합니다. 여기서 가장 짧지 만 경로는 찾지 않습니다. Floyd-Warshall은 u와 v 사이의 "중간 노드"w를 고려한 전략을 사용하고 u와 v 사이의 거리를 최소화하는 경로를 재귀 적으로 찾습니다.
모든 경로를 제외하는 대신 동일한 작업을 수행 할 수 있습니다 최소값은 inf에 이미 거리 매트릭스에서 방문한 노드를 처리하고 거리가 d보다 길거나 끝까지 도달하는 재귀의 부분 경로를 런타임에서 제외합니다 (이들은 u와 v를 연결 함) 거리가 d보다 짧다.
이 두 번째 경우와 같이 항상 공백 집합을 얻는 것처럼 단일 값 d 대신 거리 [d, D]의 간격이 주어지면 일반화 할 수 있습니다.
두 번째 단계에서는 첫 번째 단계를 해결할 때 발견 된 각 경로의 보상을 비교하면됩니다.
완전한 대답보다는 제안 된 방향이 더 길지만 도움이되기를 바랍니다!
시작 및 종료 노드가 지정되었거나 최적화되어야합니까? – SeF
이 지정되지 않았습니다. 경로 길이에 문제가있는 모든 소스 및 대상에 대해 최적화하십시오. –