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

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

  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)$를 거리로 두면 최단 거리, 시간으로 두면 최소 시간의...