두 메트릭 (거리, 비용)을 기준으로 그래프의 최적 경로 (타협)

Question

원본으로 몇 년 동안 stackoverflow.com을 사용해 왔지만 내 통계에서 볼 수 있듯이이 포럼에서는 꽤 새로 왔습니다. 내 프로그래밍 질문에 대한 답변. 나는 당신이 저의 가벼운 사소한 일을 간과하고 아래의 작은 문제에 대한 생각을 나누기를기도합니다.

가능한 경로 및 시간에 따라 최적의 경로를 찾을 수있는 라우팅/경로 찾기 알고리즘이 있는지 궁금합니다. 이상적으로는 시간, 비용 또는 최적의 시간을 최상의 비용으로 환경 설정을 지정할 수 있습니다.

나는 Directed and Weighted 직사각형 네트워크에서 최단 경로를 라우팅하기 위해 Dijksta 알고리즘을 사용 해왔다. 모든 노드는 방향 엣지를 통해 왼쪽, 오른쪽, 위아래 및 45도 이웃에 연결됩니다. 즉, 모든 노드에 8 개의 가장자리가 있고 외부 경계에 존재하지 않는 가장자리가 없습니다. 모든 노드에 도달 할 수 있지만 더 높은 비용을 반영하기 위해 메트릭 (거리)을 늘릴 수 있습니다. 동일한 노드에서 다른 에지 목록을 사용하여 경로 찾기를 실행할 수 있습니다. 경로를 탐색 할 때 비용 (또는 거리) 측면을 나타내며 최저 비용 또는 단식 경로를 찾을 수 있습니다. 거리 측정법 (1 또는 코너 모서리의 경우 SQRT (2))과 함께 가장 짧은 경로를 제공했습니다.

이제는 거리와 비용 측면을 곱하여 간단히 곱하여 혼합 된 통계를 생성하는 방법에 대해 궁금해하고있었습니다. 이 접근법에 대해 어떻게 생각 하느냐, 또는 라우팅 알고리즘이 다른 "최적"이웃을 선택하여 시간, 비용 또는 절충안 중에서 가장 좋은 경로를 찾도록 만드는 방법입니다.

감사합니다.

Answer 1

새로운 대수학에 알려진 알고리즘 (Dijkstra, Floyd-Warshall)을 사용할 수 있습니다.
두 개의 필드와 구조체 같은 거리에 대한 생각 :

struct Distance { 
    int cost, distance; 
} 

는 이제 운영자 < 및 연산자 +를 정의해야합니다. 가장 비용으로 가장 좋은 시간을 원하는 경우에, 당신은 사용해야합니다

bool operator<(Distance d1, Distance d2) { 
    if (d1.cost == d2.cost) 
     return d1.time1 < d2.time 
    else 
     return d1.cost < d2.cost; 
} 

또는 일부 가중치 :

bool operator<(Distance d1, Distance d2) { 
    return wCost*d1.cost + wDistance*d1.distance < wCost*d2.cost + wDistance*d2.distance 
}