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