University of British Columbia
Ant colony optimization and rectilinear Steiner minimal trees
Abstract
dc:descriptionThis paper consists of two distinct parts. In the first part, we introduce the Rectilinear Steiner Minimal Tree (RSMT) problem and describe the Ant Colony algorithm which we use to construct the RSMT. The development of an Ant Colony algorithm called AntCol Steiner is described and we create a working program of the algorithm using the Sun Microsystems Java programming language (see appendix A to H for details). We investigate the effectiveness of our algorithm by using AntCol Steiner to construct; and draw RSMT a given a random set of terminals. In the second part, we look at an application of the Kirchoff's Matrix Tree theorem. We find the length of a Rectilinear Minimal Spanning Tree (RMST) spanning a set of random terminals. We verify the accuracy of our results from the Kirchoff's Matrix Tree algorithm using Prim's RMST Algorithm. Our original plan was to develop an algorithm based on this theorem to determine the length of a RSTM. However, we were unable to modify the algorithm we used to find the length of the RMST, for the case of a RSMT.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Mathematics
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2006
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Blackman, Anthony Curtis
Rights
dc:rights- Statement dc:rights
-
- For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/17733