초록 ▼

키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법은, 노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 단계; 상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 단계; 상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 추정하는 단계; 상기 2차

키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법은, 노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 단계; 상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 단계; 상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 추정하는 단계; 상기 2차원 그래프의 각 에지 비용을 대응하는 저항으로, 상기 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 설정하여, 상기 2차원 그래프의 각 에지에 흐르는 부 전류를 설정하는 단계; 및 각 에지의 부 전류를 추정하는 상기 KCL 및 KVL의 선형 연립 방정식을 이용하여 일부 에지를 제거하는 단계;를 포함한다. 이에 따라, 네트워크 분야의 검색 문제 혹은 경로 탐색 문제에서 그래프를 최적화할 수 있다.

대표청구항 ▼

그래프 단순화 장치에서의 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법에 있어서,그래프 변환부에서 노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 단계;그래프 분석부에서 상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 단계;전압 추정부에서 상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대

그래프 단순화 장치에서의 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법에 있어서,그래프 변환부에서 노드와 에지로 구성된 2차원 그래프를 전기 회로적으로 해석하여 노드의 각 레벨을 나타내는 원형궤도 상에 각 노드의 전위를 노드 열(column)로 나타내는 3차원 전위 그래프로 생성하는 단계;그래프 분석부에서 상기 3차원 전위 그래프에서 원점(O), 시작 노드(S) 및 터미널 노드(T)를 연결하여 직각 삼각형을 구성하는 단계;전압 추정부에서 상기 직각 삼각형의 빗변(ST)의 길이보다 작은 양의 실수 중에서 선택된 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 추정하는 단계;전류 추정부에서 상기 2차원 그래프의 각 에지 비용을 대응하는 저항으로, 상기 최대전압(Vmax)을 상기 2차원 그래프의 전체 전압으로 설정하여, 상기 2차원 그래프의 각 에지에 흐르는 부 전류를 설정하는 단계; 및에지 제거부에서 각 에지의 부 전류를 추정하는 KCL(Kirchhoff's Current Law) 및 KVL(Kirchhoff's Voltage Law)의 선형 연립 방정식을 이용하여 일부 에지를 제거하는 단계;를 포함하는, 키르히호프의 회로 법칙을 이용한 탐색 문제의 그래프 단순화 방법.