• LF몰 이벤트
  • 파일시티 이벤트
  • 서울좀비 이벤트
  • 탑툰 이벤트
  • 닥터피엘 이벤트
  • 아이템베이 이벤트
  • 아이템매니아 이벤트

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

*태*
최초 등록일
2010.05.20
최종 저작일
2009.04
9페이지/파일확장자 압축파일
가격 1,500원 할인쿠폰받기
다운로드
장바구니

소개글

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 방식을 사용하여 큰 문제를 작은 문제로 쪼개어 각각의 문제를 해결하였습니다. 최단 경로의 계산을 위해 벨만 포드 알고리즘을 프로그램에 맞게 수정하여 함수로 구현하였습니다. 최단 경로의 출력을 위해 간선 행렬을 인자로 갖는 재귀함수를 정의하였습니다. 최단 경로의 전체거리를 출력하기 위해 시작정점과 도착정점을 거리행렬의 인덱스로 받아 계산하였습니다. 선택한 자료구조의 이점 덕분에 그 외의 함수들은 쉽게 구현할 수 있었습니다.

참고 자료

없음

압축파일 내 파일목록

hw6.hwp
Topology.txt
hw6.cpp
*태*
판매자 유형Bronze개인

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

이런 노하우도 있어요!더보기

최근 본 자료더보기
탑툰 이벤트
graph를 이용한 adhoc 네트워크 구현
  • 레이어 팝업
AI 챗봇
2024년 05월 27일 월요일
AI 챗봇
안녕하세요. 해피캠퍼스 AI 챗봇입니다. 무엇이 궁금하신가요?
6:40 오후
New

24시간 응대가능한
AI 챗봇이 런칭되었습니다. 닫기