graph를 이용한 adhoc 네트워크 구현

소개

2009년 홍대 컴공 자료구조(data structure) 마지막 과제로 나왔던
그래프 이론으로 애드혹 네트워크를 구현하는 프로그램입니다
압축 파일에 프로그램 소스와 입출력 텍스트파일, 보고서가 들어있습니다

목차

1) Program Idea Overview
2) Flow Chart
3) Result
4) Analysis
5) Program Complexity
6) Different Points from Blueprint
7) Satisfaction for requirement
8) Total Analysis for reslove the problem

본문내용

6) Different Points from Blueprint
설계보고서에서 기획한 두 가지의 자료구조 클래스 중, 정점의 집합 및 간선행렬과 노드 데이터를 분리시키는 방법을 사용했습니다. 각각을 두 클래스로 나누어 GraphNode의 정보들을 클래스 AD_HOC가 관리하게끔 구조화하여 프로그램을 구현했습니다. 설계 과정에서는 노드가 경로에 포함될 시 일괄적으로 에너지를 감소시키려 하였으나, 실제 코드에서는 최단 경로의 출력과 함께 에너지를 감소시킵니다. 에너지를 일괄적으로 감소시키기 위해 다시 루프에 접근하려면 최소한 O(n2)의 복잡도를 가지는 함수를 다시 정의해야 하기 때문입니다.
최단거리 연산을 위해 벨만 포드 알고리즘에 틀을 두고, 선택한 자료구조에 맞추기 위해 임의로 수정을 가해서 복잡도 O(n3)를 가지는 알고리즘이 되었습니다. 설계보고서에 자세하게 명시하지 않았던 예외처리 부분을 모두 구현했습니다. 복잡도로 상수 값을 갖는 함수들이 예외처리를 위해 선형 탐색 시간을 갖는 루프를 한 개 또는 그 이상 포함하므로 O(n) 또는 O(n2)의 복잡도를 갖게 되었습니다.

7) Satisfaction for requirement
여러 가지 Input을 넣어 본 결과 적합한 Output을 출력하며, 선택해본 임의의 모든 경우에서 정상동작 하였습니다. 최단 경로 검색, 일반 노드 상태보기, 일반 노드 에너지 회복, 일반 노드 삽입, 추가 메시지 출력 등의 요구사항을 모두 만족시키며, 잘못된 결과를 출력할 수 있는 몇몇의 잘못된 입력 값에 대해서는 예외처리 하였습니다. 비동작 부분은 없습니다.

8) Total Analysis for reslove the problem
문제에서 가장 큰 비중을 차지하는 것은 최단 경로의 검색과 해당 경로의 출력이었습니다. 문제 해결을 위해 Divide and conquer 방식을 사용하여 큰 문제를 작은 문제로 쪼개어 각각의 문제를 해결하였습니다. 최단 경로의 계산을 위해 벨만 포드 알고리즘을 프로그램에 맞게 수정하여 함수로 구현하였습니다. 최단 경로의 출력을 위해 간선 행렬을 인자로 갖는 재귀함수를 정의하였습니다. 최단 경로의 전체거리를 출력하기 위해 시작정점과 도착정점을 거리행렬의 인덱스로 받아 계산하였습니다. 선택한 자료구조의 이점 덕분에 그 외의 함수들은 쉽게 구현할 수 있었습니다.

참고자료

· 없음