최단경로문제

소개글

최단경로문제에 대한 보고서 자료입니다.

본문내용

1.문제 개요
이번 프로젝트에서 다룰 문제로 1학기 때 배운 최단 경로 문제의 장비 교체 문제를 선정했다. 그 이유는 우리가 많이 사용하는 자료처리 분석실의 최적의 컴퓨터 교체 시기를 파악하여 최소의 비용으로 최적의 교체를 할 수 있도록 하는 것을 목적으로 삼았기 때문이다. 그러나 이번 프로젝트에서는 문제의 풀이 방법에 대한 이해도를 높여서 완벽하게 이해한 뒤 프리젠테이션을 하는 것이 목적이므로 비용은 임의대로 정하였다. 2년 이상 사용할 때 마다 비용이 늘어나도록 정하였다.
최단 경로 문제 [ shortest path problem, 最短經路問題 ]
유향(有向) 또는 무향(無向) 그래프에서 어떤 두 점 사이를 맺는 유향 또는 무향 경로 중 가장 짧은 것, 즉 가지의 길이 합을 최소로 하는 것을 구하는 문제. 그래프가 평면 접속인 경우에는 쌍대(雙對) 그래프의 최대 흐름을 구하는 문제와 등가이다.
2. 문제에 대한 정의 및 입력자료 설명
- 문제에 대한 설명
최단 경로 문제에서 인천대학교 산업경영공학과 자료 처리 분석실의 컴퓨터를 최소 2년에서 최대 5년 사이에서 사용한다. 교체 계획 기간은 06학번의 입학년도인 2006년부터 졸업년도인 2010년 까지 이고 비용표는 아래와 같이 주어진다.
3. 모형 개발 및 해에 대한 설명
1. 각각의 2006년에서 2010년에 대한 모형을 그린 후 1년에 대한 교체비용은 M값으로 지정한다.
(교체주기가 최소 2년~ 5년이므로)

키워드

최단경로문제,   사례,   풀이