프로그래밍을 일상 생활속으로

  이전 글 참조 Dijkstra 알고리즘을 이용하여 출발점에서 종료점까지 가는 최소 비용의 경로를 찾을 수 있습니다. 하지만 시간 복잡도는 $$O(n^2)$$로 좋지 않습니다. Dijkstra 알고리즘은 종료점까지 도착한 경로들을 구한 뒤 가장 적은 비용의 경로를 선택합니다. 만일 각 노드마다 비용을 확인하여 도중에 탐색을 멈추게할 수 있다면 알고리즘을 개선할 수 있습니다.

 발등에 불이 떨어졌습니다. 현재 진행 중인 2월 중간 보고에 고객사 부사장님이 참석한다고 합니다. 이미 2개의 프로젝트가 절뚝거리며 진행하고 있기 때문에 지금 프로젝트는 제대로 해야합니다. 네트워크 망 구성과 최단 거리 찾기(Dijkstra 기반) 알고리즘에 대한 코드를 정리한 후에 김** 차장과 결과를 확인하기로 했습니다. 이렇게 From, To Cable Way를 선택한 후에 버튼을 눌러 결과가 나오기를 기다렸습니다. 1분가량의 시간이 흘렀습니다. 드디어 프로그램에서 From에서 To로 가는 4,128개의 경로를 찾았습니다. 우리가 생각하지도 못한 길을 찾다니 하고 감탄하고 있을때가 아닙니다. 무려 4,128개의 경로라니요, 눈으로 보기에는 고작 대여섯개의 경로만 보이는데 말입니다. 우리의 예측과 실제 결과가 다를때에는 그 원인을 찾아야 합니다. 고단하고 손가락 아프고 눈이 시린 디버깅의 시작입니다. 반드시 4,128개 경로들의 차이점을 찾아야 합니다. 어... Cable Way를 구성하는 Feature의 RangeBox가 실제 형상보다 크게 잡히는 것을 확인했습니다. 실제 형상과 동일한 RangeBox를 예상하고 있었는데 우리의 예상이 빗나갔습니다. RangeBox 우리의 잘못이 아닙니다. 지랄맞은 S3D입니다. Insulation, Maintenance, Operation Aspect 때문일까봐 켜보고 다시 확인해봤지만 결과는 변함이 없습니다. 밤은 늦었지만 어쩔수 없이 김** 차장에게 전화해 물어봤지만 뾰족한 방안은 없습니다. 모든 주어진 데이타와 대학교 1학년때까지 쌓은 수학적 지식을 총동원하여(사실 중학교때까지의 지식만으로도 충분했습니다.) 형상에 딱 맞는 RangeBox(실제는 OrientedRangeBox)를 구했습니다. Cable Way Feature 형상에 딱 맞는 OrientedRangeBox 구하는 방법은 다음 글에서 이야기하도록 하겠습니다. 밤 9시가 넘어가고 있습니다. 집중력이 떨어지고 있습니다. 나이들어 야근은 무리라는 걸...

  Networkx 라는 그래프에 관련된 훌륭한 라이브러리가 있습니다. 이 라이브러리에 관련된 여러 글들을 인터넷에서 찾아보고 지금 진행하고 있는 Cable Auto Routing에 적용할 수 있다는 것을 알게되었습니다. Cable Auto Routing은 두 장치를 연결하는 Cable의 최단 경로를 자동으로 찾는 것입니다. Networkx 의 shortest_path라는 함수를 이용하여 출발 노드에서 종료 노드에 도달하는 최단 경로를 구할 수 있습니다. $$path = \text{nx.dijkstra_path}(G, \text{start_node}, \text{end_node}, weight)$$ 아마 shortest_path 함수도 내부적으로 dijkstra 알고리즘을 사용할 것 같습니다. Cable Auto Routing 프로젝트에서 dijkstra 알고리즘을 직접 구현하여 문제를 해결할 수도 있겠지만 이미 검증된 라이브러리를 사용하는 편이 훨씬 효율적이고(알고리즘 구현에 시간을 낭비할 필요가 없습니다.) 안전할것 입니다. 이 라이브러리를 Cable Auto Routing에 적용하기 전에 기능 테스트를 위한 데모 프로그램을 작성하기로 하였습니다.  데모 프로그램은 아래와 같은 기능을 가집니다. 최단 거리 검색 노드 생성 에지 생성 노드, 에지 정보를 파일로 저장 및 저장된 파일 읽어오기 Open 툴바를 눌러 노드와 에지 정보가 저장된 Json 파일을 읽습니다. Networkx 툴바를 누르면 Networkx 관련 다이얼로그가 나타납니다. Find 버튼을 눌러 사용자가 입력한 출발 노드에서 종료 노드까지의 최단 경로를 검색합니다. 결과 화면(노란색이 최단 경로) 노드를 생성할때 노드 이름과 3D 좌표를 입력합니다. 사실 Networkx에서는 3D 좌표는 필요없습니다. 데모 프로그램에서 3D로 노드를 표시해주기 위해 3D 좌표를 입력하도록 하였습니다. 에지는 에지를 구성하는 두 노드 이름과 에지의 길이를 입력하도록 하였습니다. 에지의 길이는 에...

 Dijkstra는 대표적인 길찾기 알고리즘입니다. Dijkstra 알고리즘을 이용하여 출발 노드에서 종말 노드로 가는 최단 거리(최소 비용)의 경로를 찾을 수 있습니다. 아래와 같은 그래프를 생각해봅시다. 그래프 B에서 출발해 E에 도착하는 경로는 여러개가 있습니다. 여러개의 경로 중에서 최소 비용을 가지는 경로가 우리가 원하는 경로가 될것입니다. 노드에서 노드 사이를 옮겨다닐때 비용이 발생한다고 하면 경로의 비용은 $Cost(path) = \sum\limits_{i=1}^n Cost(edge),\text{ }(edge_1,edge_2...edge_n은\text{ }path에\text{ }속함)$이 됩니다. $edge$가 노드와 노드를 연결하니 $edge$에 비용을 추가하면 아래와 같이 됩니다. cost 추가 그럼 이제 경로를 구성하는 $edge$를 구하면 됩니다. 방문한 노드들을 트리 형식으로 구축하여 경로를 구성하는 $edge$들을 구할 수 있습니다. B-E 경로들 B에서 출발해 E에 도달하는 총 6개의 경로를 구할 수 있습니다. (주의: 진행 중인 경로에 속한 노드를 재방문할 수 없습니다. 그렇지 않으면 무한루프에 빠지게 됩니다.) 경로들에 대한 비용을 계산해 보면, $\begin{eqnarray} B\to A\to D\to C\to E &= 9 \\ B\to A\to D\to E  &= 6 \\ B\to D\to C\to E &= 10 \\ B\to D\to E &= 7 \\ B\to C\to D\to E &= 5 \\ B\to C\to E &= 6 \end{eqnarray}$ $B\to C \to D \to E$가 최소 비용 거리임을 확인 할 수 있습니다. 최소 비용 거리 $Cost(edge)$를 거리로 두면 최단 거리, 시간으로 두면 최소 시간의...