초록 ▼

1. 청구범위에 기재된 발명이 속한 기술분야본 발명은 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘 또는 플로이드-워셜 알고리즘을 이용한 최단경로 산출방법.2. 발명이 해결하려고 하는 기술적 과제본 발명은, 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘 또는 플로이드-워셜 알고리즘을 이용하여 교통망에서 최단경로를 산출하기 위한 최단경로 산출방법과 상기 방법을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하고자 함.3. 발명의 해결방법의 요지본 발명은, 최단경로 산출 시스템에 적용되는

1. 청구범위에 기재된 발명이 속한 기술분야본 발명은 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘 또는 플로이드-워셜 알고리즘을 이용한 최단경로 산출방법.2. 발명이 해결하려고 하는 기술적 과제본 발명은, 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘 또는 플로이드-워셜 알고리즘을 이용하여 교통망에서 최단경로를 산출하기 위한 최단경로 산출방법과 상기 방법을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하고자 함.3. 발명의 해결방법의 요지본 발명은, 최단경로 산출 시스템에 적용되는 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘을 이용한 최단경로 산출 방법에 있어서, 출발지와 목적지를 선택한 후, 회전 금지, 유-턴이나 피-턴을 하는 경우에 대비하여 교통정보에 근거한 가상 호값을 할당하는 제 1 단계; 모든 출발노드에서 임의의 노드까지 임시 레이블된 노드의 총운행시간 중에서 최단 운행시간을 선택하여 영구 레이블을 부여하는 제 2 단계; 및 도착지 노드에서 시작하여 영구노드를 추적하여 최단경로를 결정하는 제 3 단계를 포함함.4. 발명의 중요한 용도본 발명은 최단경로 산출 서비스 등에 이용됨.

대표청구항 ▼

최단경로 산출 시스템에 적용되는 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘을 이용한 최단경로 산출 방법에 있어서,출발지와 목적지를 선택한 후, 회전 금지, 유-턴이나 피-턴을 하는 경우에 대비하여 교통정보에 근거한 가상 호값을 할당하는 제 1 단계;모든 출발노드에서 임의의 노드까지 임시 레이블된 노드의 총운행시간 중에서 최단 운행시간을 선택하여 영구 레이블을 부여하는 제 2 단계; 및도착지 노드에서 시작하여 영구노드를 추적하여 최단경로를 결정하는 제 3 단계를 포함하는 최단경로 산출 방법.제 1 항에 있어서,상기 제

최단경로 산출 시스템에 적용되는 회전 금지, 유-턴, 피-턴을 고려한 다익스트라 알고리즘을 이용한 최단경로 산출 방법에 있어서,출발지와 목적지를 선택한 후, 회전 금지, 유-턴이나 피-턴을 하는 경우에 대비하여 교통정보에 근거한 가상 호값을 할당하는 제 1 단계;모든 출발노드에서 임의의 노드까지 임시 레이블된 노드의 총운행시간 중에서 최단 운행시간을 선택하여 영구 레이블을 부여하는 제 2 단계; 및도착지 노드에서 시작하여 영구노드를 추적하여 최단경로를 결정하는 제 3 단계를 포함하는 최단경로 산출 방법.제 1 항에 있어서,상기 제 1 단계의 가상 호값 할당 과정은,교통망에 이미 해당 노드를 연결하는 호(arc)가 존재한다면, 가상 호값이 기존의 호값보다 작을때는 가상 호값을 최단경로를 구하는데 사용하고, 클때는 기존의 호값을 최단경로를 구하는데 사용하는 것을 특징으로 하는 최단경로 산출 방법.제 1 항 또는 제 2 항에 있어서,상기 제 2 단계는,모든 노드에 출발노드로부터 노드 j 까지의 운행시간인 를 노드 1인 출발노드에서 노드 j까지 임시 레이블된 노드의 총운행시간인 에 할당하는 제 4 단계;상기 임시 레이블된 노드 j의 이전 영구노드인 b에는 출발노드인 1 을 할당하고, 만약 출발노드와 노드 j사이에 호가 없다면 무한대( = ∞)를 할당하는 제 5 단계;상기 출발노드로부터 노드 1까지의 총운행시간인 에는 0을 할당하는 제 6 단계;상기 노드 1인 출발노드에서 노드 j까지 임시 레이블된 노드의 총운행시간인 중에서 최단 운행시간 한개를 선택하여 영구 레이블을 부여하고, 상기 영구 레이블된 노드의 최단 운행시간을 출발노드로부터 상기 영구 레이블된 노드까지의 총운행시간으로 할당한 후, 더 이상의 임시 레이블이 없는지 확인하는 제 7 단계;상기 제 7 단계의 확인 결과, 더 이상의 임시 레이블이 없으면 상기 제 3 단계로 진행하는 제 8 단계; 및상기 제 7 단계의 확인 결과, 더 이상의 임시 레이블이 있으면 영구노드 i의 인접한 모든 임시 노드들의 값을 수정하고, 연속된 3개의 노드(경로 b-i-j)에서 회전금지라면, 상기 경로는 최단운행시간 고려대상에서 제외하고, 아니면 출발노드로부터 노드 j까지의 임시 레이블된 노드의 총운행시간인 와 출발노드로부터 영구노드 i까지의 총운행시간 에 i에서 인접 임시노드 j까지 거리 를 합한 값 중에서 작은 값을 선택하여(min[, + ]) 출발노드로부터 노드 j까지의 임시 레이블된 노드의 총운행시간 값으로 새롭게 부여하고, 출발노드로부터 노드 j까지의 임시 레이블된 노드의 총운행시간 값이 영구노드 i까지의 총운행시간 와 영구노드 i에서 인접 임시노드 j까지 거리 의 합값( + ) 보다 큰지를 확인하는 제 9 단계를 포함하는 최단경로 산출 방법.제 1 항 내지 제 3 항 중 어느 한 항에 있어서,상기 제 9 단계는,상기 제 9 단계의 확인 결과, > + 면 의 b에 이전의 영구노드인 i를 할당하고, 제 7 단계로 진행하는 제 10 단계; 및상기 제 9 단계의 확인 결과, > + 이 아니면 제 3 단계로 진행하는 제 11 단계를 포함하는 최단경로 산출 방법.최단경로 산출 시스템에 적용되는 회전 금지, 유-턴, 피-턴을 고려한 플로이드-워셜 알고리즘을 이용한 최단경로 산출 방법에 있어서,출발지와 목적지를 선택하여 모든 노드쌍에서 두 노드사이의 운행시간을 구하는 제 1 단계;상기 노드에 좌회전 금지가 있으면 가상노드(L')를 추가하고, 상기 가상노드를 이용하여 상기 노드쌍의 행렬을 구하는 제 2 단계; 및상기 노드쌍의 행렬을 이용하여 최단 운행시간을 구하는 제 3 단계를 포함하는 최단경로 산출 방법.제 5 항에 있어서,상기 제 2 단계의 노드쌍의 행렬을 구하는 과정은,상기 가상노드 L'를 추가하여 , 로 하여 행렬(1)()을 구하고, , 로 하여 행렬(2) 를 구하는 것을 특징으로 하는 최단경로 산출 방법.제 5 항 또는 제 6 항에 있어서,상기 제 3 단계는,상기 각 행렬에서 행 m과 열 m을 표시하여, 상기 행렬(1)과 행렬(2)에 대해 삼각연산을 이용하여 행렬을 구하는 제 4 단계;상기 m이 N+1(기존 노드의 수 + 가상 노드의 수)과 같은지 확인하는 제 5 단계;상기 제 5 단계의 확인 결과, m이 N+1(기존 노드의 수 + 가상 노드의 수)과 같으면 행렬(1)과 행렬(2)에 대해 최단 운행시간 를 구하기 위해 각 을 비교하여(808), 출발노드 S와 도착 노드 T에서의 최단 운행시간 를 구하는 제 6 단계; 및상기 제 5 단계의 확인 결과, m이 N+1(기존 노드의 수 + 가상 노드의 수)과 같지 않으면 제 4 단계로 진행하는 제 7 단계를 포함하는 최단경로 산출방법.대용량 프로세서를 구비한 최단경로 산출 시스템에,출발지와 목적지를 선택한 후, 회전 금지, 유-턴이나 피-턴을 하는 경우에 대비하여 교통정보에 근거한 가상 호값을 할당하는 제 1 기능;모든 출발노드에서 임의의 노드까지 임시 레이블된 노드의 총운행시간 중에서 최단 운행시간을 선택하여 영구 레이블을 부여하는 제 2 기능; 및도착지 노드에서 시작하여 영구노드를 추적하여 최단경로를 결정하는 제 3 기능을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.대용량 프로세서를 구비한 최단경로 산출 시스템에,출발지와 목적지를 선택하여 모든 노드쌍에서 두 노드사이의 운행시간을 구하는 제 1 기능;상기 노드에 좌회전 금지가 있으면 가상노드(L')를 추가하고, 상기 가상노드를 이용하여 상기 노드쌍의 행렬을 구하는 제 2 기능; 및상기 노드쌍의 행렬을 이용하여 최단 운행시간을 구하는 제 3 기능을 실현시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.