| 1 |
1
그래프에서 에지를 구성하는 노드 인덱스 및 에지 비용에 기초하여 적어도 1 개 이상의 에지로 이루어진 세그먼트의 세그먼트 최단 경로를 생성하는 단계;상기 세그먼트 최단 경로에서 제약 세그먼트의 시작 노드로 종료하는 종료 세그먼트 최단 경로 및 상기 세그먼트 최단 경로에서 상기 제약 세그먼트의 종료 노드로부터 시작하는 시작 세그먼트 최단 경로를 검색하는 단계;상기 종료 세그먼트 최단 경로, 상기 시작 세그먼트 최단 경로 및 상기 제약 세그먼트로 이루어진 확대 제약 세그먼트 최단 경로를 생성하는 단계; 및상기 세그먼트 최단 경로에서 상기 확대 제약 세그먼트 최단 경로를 제외하여 최종 세그먼트 최단 경로를 생성하는 단계를 포함하는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 2 |
2
제 1 항에 있어서, 상기 최단 경로 탐색 방법은경로 요청 메시지가 입력되는 경우, 상기 최종 세그먼트 최단 경로에 기초하여 요청되는 경로를 구성하는 시작 에지와 종료 에지 사이의 최단 경로를 탐색하는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 3 |
3
제 2 항에 있어서, 상기 제약 세그먼트는1개의 에지 또는 다수의 에지로 이루어진 경로인 것을 특징으로 하는 최단 경로 탐색 방법
|
| 4 |
4
제 3 항에 있어서, 상기 최단 경로 탐색 방법은상기 세그먼트 최단 경로에서 상기 확대 제약 세그먼트 최단 경로의 비용을 무한대로 설정하여 상기 세그먼트 최단 경로에서 상기 확대 제약 세그먼트 최단 경로를 제외하는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 5 |
5
제 3 항에 있어서, 상기 세그먼트 최단 경로, 상기 시작 세그먼트 최단 경로, 상기 종료 세그먼트 최단 경로, 상기 확대 제약 세그먼트 최단 경로 및 상기 최종 세그먼트 최단 경로 중 어느 하나는세그먼트를 구성하는 시작 노드, 종료 노드, 종료 노드의 부모 노드 및 상기 노드 노드와 종료 노드 사이의 최단 경로의 비용을 포함하는 테이블로 구성되는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 6 |
6
제 5 항에 있어서, 상기 종료 세그먼트 최단 경로는 상기 세그먼트 최단 경로에서 제약 세그먼트의 시작 노드로 종료하는 후보 종료 세그먼트 최단 경로를 검색하는 단계;검색한 상기 후보 종료 세그먼트 최단 경로 중 상기 후보 종료 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 종료 세그먼트 최단 경로를 판단하는 단계; 및상기 후보 종료 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 종료 세그먼트 최단 경로를 상기 후보 종료 세그먼트 최단 경로에서 삭제하여 상기 종료 세그먼트 최단 경로를 생성하는 단계를 통해 생성되는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 7 |
7
제 5 항에 있어서, 상기 시작 세그먼트 최단 경로는 상기 세그먼트 최단 경로에서 제약 세그먼트의 시작 노드로 종료하는 후보 시작 세그먼트 최단 경로를 검색하는 단계;검색한 상기 후보 시작 세그먼트 최단 경로 중 상기 후보 시작 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 시작 세그먼트 최단 경로를 판단하는 단계; 및상기 후보 시작 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 시작 세그먼트 최단 경로를 상기 후보 시작 세그먼트 최단 경로에서 삭제하여 상기 시작 세그먼트 최단 경로를 생성하는 단계를 통해 생성되는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 8 |
8
제 5 항에 있어서, 상기 확대 제약 세그먼트 최단 경로는상기 종료 세그먼트 최단 경로, 상기 시작 세그먼트 최단 경로 및 상기 제약 세그먼트 중 적어도 2개의 조합으로 이루어진 후보 제약 세그먼트 최단 경로를 생성하는 단계;상기 후보 제약 세그먼트 최단 경로 중 상기 후보 제약 세그먼트 최단 경로의 비용이 비용 임계값보다 큰 삭제 세그먼트 최단 경로를 판단하는 단계; 및상기 삭제 세그먼트 최단 경로를 상기 후보 제약 세그먼트 최단 경로에서 제외하여 상기 확대 제약 세그먼트 최단 경로를 생성하는 단계를 통해 생성되는 것을 특징으로 하는 최단 경로 탐색 방법
|
| 9 |
9
그래프에서 에지를 구성하는 노드 인덱스 및 에지 비용에 기초하여 적어도 1 개 이상의 에지로 이루어진 세그먼트의 세그먼트 최단 경로를 생성 세그먼트 생성부;상기 세그먼트 최단 경로에서 제약 세그먼트의 시작 노드로 종료하는 종료 세그먼트 최단 경로를 검색하는 종료 세그먼트 생성부; 상기 세그먼트 최단 경로에서 상기 제약 세그먼트의 종료 노드로부터 시작하는 시작 세그먼트 최단 경로를 검색하는 시작 세그먼트 생성부;상기 종료 세그먼트 최단 경로, 상기 시작 세그먼트 최단 경로 및 상기 제약 세그먼트로 이루어진 확대 제약 세그먼트 최단 경로를 생성하는 확대 제약 세그먼트 생성부;상기 세그먼트 최단 경로에서 상기 확대 제약 세그먼트 최단 경로를 제외하여 최종 세그먼트 최단 경로를 생성하는 최종 세그먼트 생성부; 및경로 요청 메시지가 입력되는 경우, 상기 최종 세그먼트 최단 경로에서 요청되는 경로를 구성하는 시작 에지와 종료 에지 사이의 최단 경로를 탐색하는 최단 경로 탐색부를 포함하는 것을 특징으로 하는 최단 경로 탐색 장치
|
| 10 |
10
제 9 항에 있어서, 상기 종료 세그먼트 생성부는상기 세그먼트 최단 경로에서 제약 세그먼트의 시작 노드로 종료하는 후보 종료 세그먼트 최단 경로를 검색하는 후보 종료 세그먼트 검색부;검색한 상기 후보 종료 세그먼트 최단 경로 중 상기 후보 종료 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 종료 세그먼트 최단 경로를 판단하는 종료 비용 비교부;상기 후보 종료 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 종료 세그먼트 최단 경로를 상기 후보 종료 세그먼트 최단 경로에서 삭제하여 상기 종료 세그먼트 최단 경로를 생성하는 최종 종료 세그먼트 생성부를 포함하는 것을 특징으로 하는 최단 경로 탐색 장치
|
| 11 |
11
제 9 항에 있어서, 상기 시작 세그먼트 생성부는상기 세그먼트 최단 경로에서 제약 세그먼트의 시작 노드로 종료하는 후보 시작 세그먼트 최단 경로를 검색하는 후보 시작 세그먼트 검색부;검색한 상기 후보 시작 세그먼트 최단 경로 중 상기 후보 시작 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 시작 세그먼트 최단 경로를 판단하는 시작 비용 비교부;상기 후보 시작 세그먼트 최단 경로의 비용이 비용 임계값과 상기 제약 세그먼트의 비용 사이의 차보다 큰 후보 시작 세그먼트 최단 경로를 상기 후보 시작 세그먼트 최단 경로에서 삭제하여 상기 시작 세그먼트 최단 경로를 생성하는 최종 시작 세그먼트 생성부를 포함하는 것을 특징으로 하는 최단 경로 탐색 장치
|
| 12 |
12
제 9 항에 있어서, 상기 확대 제약 세그먼트 생성부는상기 종료 세그먼트 최단 경로, 상기 시작 세그먼트 최단 경로 및 상기 제약 세그먼트 중 적어도 2개의 조합으로 이루어진 후보 제약 세그먼트 최단 경로를 생성하는 후보 제약 세그먼트 생성부;상기 후보 제약 세그먼트 최단 경로 중 상기 후보 제약 세그먼트 최단 경로의 비용이 비용 임계값보다 큰 삭제 세그먼트 최단 경로를 판단하는 제약 비용 비교부; 및상기 삭제 세그먼트 최단 경로를 상기 후보 제약 세그먼트 최단 경로에서 제외하여 상기 확대 제약 세그먼트 최단 경로를 생성하는 최종 제약 세그먼트 생성부를 포함하는 것을 특징으로 하는 최단 경로 탐색 장치
|
| 13 |
13
제 9 항에 있어서, 상기 최종 세그먼트 생성부는상기 세그먼트 최단 경로에서 상기 확대 제약 세그먼트 최단 경로의 비용을 무한대로 설정하여 상기 세그먼트 최단 경로에서 상기 확대 제약 세그먼트 최단 경로를 제외하는 것을 특징으로 하는 최단 경로 탐색 장치
|
