서지주요정보
Solving the minimum dissemination time problem in broadcasting by meta-heuristics = 최소전파 시간문제의 메타 휴리스틱 해법
서명 / 저자 Solving the minimum dissemination time problem in broadcasting by meta-heuristics = 최소전파 시간문제의 메타 휴리스틱 해법 / Se-Hyun Jun.
저자명 Jun, Se-Hyun ; 전세현
발행사항 [대전 : 한국과학기술원, 1999].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8009670

소장위치/청구기호

학술문화관(문화관) 보존서고

MIE 99020

SMS전송

도서상태

이용가능

대출가능

반납예정일

등록번호

9005855

소장위치/청구기호

서울 학위논문 서가

MIE 99020 c. 2

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This thesis considers the minimum dissemination time problem in broadcasting. Given an undirected network, we want to find the initial broadcasting node and the sequence of broadcasting which gives the smallest broadcasting time to transmit the information to the rest of nodes in the network. We give an integer programming formulation and propose tabu search and genetic algorithms to solve the problem. We test the algorithms on randomly generated data sets. Computational results show that the tabu search algorithm can find good solutions consistently.

본 논문은 임의의 네트워크에서, 하나의 정보를 전파할 때 최초 전달자의 위치 선정과 전파의 최적경로를 구하는 문제를 다루고 있다 정보의 전파에는 다음과 같은 제약하에서 전달하게 된다. 첫째, 정보를 아는 곳은 이웃한 곳에 한번에 한번만 전달하게 되어있다. 이러한 조건하에서 본 논문은 최단 시간안에 네트워크에 있는 모든 지점에 정보를 전달하는 방법과, 최초의 전달위치를 발견하는 문제이다. 본 논문에서는 이 문제에 대해 두가지의 메타 휴리스틱 기법을 이용하여 해법을 제시하였다. 기본적 알고리즘은 다음과 같이 구성된다. 전파의 방법은 네트워크에서 트리를 만들기에, 트리를 만든 후에 메타 휴리스틱인 타부 탐색, 유전자 알고리즘의 기법을 이용하여 보다나은 트리를 만들도록 하였다. 최적의 트리가 생성되면, 트리에서의 전파 알고리즘을 이용하여 전파순서를 파악하였다. 여러 실험 데이터에 대해서 실험을 해본 결과, 타부 탐색을 이용한 알고리즘이 일관성있게 좋은 결과를 나타냄을 알 수 있었다.

서지기타정보

서지기타정보
청구기호 {MIE 99020
형태사항 40 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 전세현
지도교수의 영문표기 : Sung-Soo Park
지도교수의 한글표기 : 박성수
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 Reference : p. 39-40
주제 Broadcasting
Meta-heuristic
전파
휴리스틱
QR CODE qr code