[컴퓨터 알고리즘] 최소 비용 통신망 설계 및 구현

※ 미리보기 이미지는 최대 20페이지까지만 지원합니다.

분야
등록일
페이지/형식
구매가격
적립금

레포트 > 공학계열
2008.12.10
30페이지 / hwp
2,000원
60원 (구매자료 3% 적립)

다운로드 네이버 로그인

추천자료

[컴퓨터공학 인공지능]신경망 알고리즘

최단경로 알고리즘(다익스트라, 플로이드)

계명대컴퓨터공학과기출입시문제유형분석

[정보통신공학] 졸업작품-벡터데이터 전자지도 압축 알고리즘

[컴공]C++강좌 총정리

알고리즘 C언어

[압력실험] Airfoil 에어포일 실험

[자료구조] [C++]배열을 이용한 다항식 계산기

[자료구조,컴퓨터,실습,충남대] [자료구조1] 실습1~14주

[산업정보프로젝트] ADHD 검출 솔루션 개발

소개글

[컴퓨터 알고리즘] 최소 비용 통신망 설계 및 구현에 대한 자료입니다.

※
설 계 과 제 요약서

제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가 연결되어 있지 않으면 두 간선은 최소비용 신장트리의 간선으로 채택
③ 최소비용 신장나무인지를 판별

#int #void #cout #endl #통신망 #최소비용 #알고리즘 #Kruskal #최소 #_