[컴퓨터 알고리즘] 최소 비용 통신망 설계 및 구현
- 등록일 / 수정일
- 페이지 / 형식
- 자료평가
- 구매가격
- 2008.12.10 / 2019.12.24
- 30페이지 / hwp (아래아한글2002)
- 평가한 분이 없습니다. (구매금액의 3%지급)
- 2,000원
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
추천 연관자료
- 목차
-
※
설 계 과 제 요약서
제1장
서 론
제1절
설 계 과 제 목 표
제2절
설 계 과 제 필요성
제3절
설 계 과 제 내 용
제2장
시스템의 구조 및 구성
제1절
전 체 구 성 도
제2절
시스템 세 부 구 성
제3절
시스템 개 발 환 경
제3장.
결 론
제1절
창 의 성 측 면
제2절
기 술 적 측 면
제3절
협 동 성 측 면
제4절
경제- 산업적 측면
제5절
활 용 방 안
제4장.
참 고 문 헌
제5장.
부 록
< 그림 목차 >
표 1.
설계과제 요약서
표 2.
세부추진현황 및 진행률
표 3.
시스템구성도
- 본문내용
-
제 1 장 서론
제 1 절 설계과제 목적
최근 기술적 동향을 살펴보면, 정보통신기술의 발전에 있어서 통신망 시설의 확충을 요구하고 있다. 이에 따라 송수신자간 통신을 위해 각 지점을 연결하는 통신망의 구축이 필요한 시점이다. 그래서 우리의 설계과제 목적은 모든 지점 간에 통신이 가능하도록 각 지점을 최소의 비용으로 통신망을 구축하는 것이다. 이에 맞는 알고리즘을 설계하고 구현함으로써 실습 과제를 수행하는 것이다.
제 2 절 설계과제 필요성
▶ 최근 정보통신기술의 발달로 통신서비스에 대한 요구가 증가함에 따라 전국 곳곳에 통신망이 연결되어 있음
▶ 통신망의 설치도 고속도로와 같은 국가 기반시설로서 막대한 예산과 자원, 시간이 필요한 작업으로 최소경비로 구축가능한 통신망을 설계하는 것이 중요함
▶ 최소 비용으로 각 지점을 연결 할 수 있는 통신망을 설계 구현함으로서 제한된 자원을 가지고 효율적으로 원하는 기능을 수행하는 통신망을 경제적으로 구축 가능함
제 3 절 설계과제 내용
1) 최소비용 통신망 문제 인식
- 통신망을 가중 그래프를 이용하여 나타낼 수 있다.
- 가중 그래프 : 각 정점간의 연결과 그 노드에 가중치를 표현한 그래프
- 각 정점을 통신지점, 노드를 망의 연결, 가중치를 비용을 의미한다.
- 최소비용 통신망을 구하기 위해서 최소비용 신장트리를 이용한다.
- 최소비용 신장트리 : 어떤 그래프의 신장 나무들 중에서 간선들의 비용의 합이 최소가 되는 신장나무를 말한다.
- 따라서 주어진 통신망에 대해 최소비용 신장트리를 구현한다.
2) 입출력의 정의
- 입력 : 시뮬레이션을 위해 작성된 통신망
- 출력 : 최소의 비용으로 연결된 통신망
- 입력은 정점과 간선, 가중치 정보가 저장된 파일로 받는 방식과 사용자가 직접 정보를 입력하는 방식을 이용한다.
- 출력은 만들어진 최소비용 신장트리를 그래픽을 사용하여 직접 보여주고, 그때의 최소비용을 계산함으로서 성능분석 자료로 활용한다.
3) 최소비용을 구하는 알고리즘의 설계
- 최소비용 신장나무를 찾아내는 알고리즘을 개발함
- 기존에 나와있던 알고리즘과 새로 개발한 알고리즘의 성능분석을 실시
- 성능분석은 최소비용의 경로를 구하는 시간을 최우선 기준으로 삼음
4) 알고리즘의 구현
< 우선순위 탐색법 >
▶ 자료구조 : 우선순위 큐를 사용 (Heap)
※ 우선순위 큐 : 우선순위가 가장 높은 것을 가장 먼저 꺼냄
▶ 알고리즘
① 주변 정점 중의 한 정점 V를 나무 정점으로 만든다.
- 우선순위 큐에 들어있는 주변 정점 중에서 가장 우선 순위가 높은(가중치가 가장 적은) 정점 V를 꺼내서 나무 정점으로 만든다.
② 정점 V와 연결된 모든 보이지 않는 정점을 주변 정점으로 만든다.
- 나무 정점 V와 연결되어 있는 보이지 않는 정점들에 대해서 주변 정점으로 만든다
- 이 나무 정점과 연결되어 있는 주변 정점에 대해서 더 작은 가중치로 갱신 할 수가 있으면 더 작은 가중치로 갱신을 한다.
< Kruskal 알고리즘 >
▶ 자료구조 : 우선순위 큐를 사용 (Heap)
※ 우선순위 큐 : 우선순위가 가장 높은 것을 가장 먼저 꺼냄
▶ 알고리즘
① 남아 있는 간선 중 가장 가중치가 작은 간선을 찾아냄
- 우선순위 큐를 이용해서 해결 가능
② 선택된 간선이 회로를 이루는지를 확인
- 두 노드간 간선 AB가 연결되어 있는지 검색하는 함수를 구현함
- A와 B가 연결되어 있지 않으면 두 간선은 최소비용 신장트리의 간선으로 채택
③ 최소비용 신장나무인지를 판별
자료평가
-
아직 평가한 내용이 없습니다.