Project
Algorithm Design and Analysis
[email protected]
Steiner Tree Problem
Given an undirected distance graph G = (V, E, d) and a set S, where V is the set of vertices in G. E is the set of edges in G. d is the distance function which maps E into the set of nonnegative numbers and SV is a subset of the vertices of V.
The Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges.
For example, V = {1, 2, 3, 4}, E = {(1, 2), (2, 3), (3, 4), (1, 4)}, S = {1, 2, 3} and the distance of each edge in E is 1. The solution is 2 (selecting edges (1, 2) and (2, 3)).
Algorithm design
May 15, 2019 2 /
Data Format
The first line is 33D32945 STP File, STP Format Version 1.0 which could be ignored
Section comment, section graph and section terminals are following.
Section comment could be ignored.
Section graph describe the undirected graph. The first two lines in this section show the number of nodes and number of edges. And then there are several lines. E a b c (a, b, c are integers) means that there is an edge between vertex a and vertex b with distance c
Section terminals describe the set S. The first line shows the number of vertices in S. T a (a is an integer) means that a is in set S.
Algorithm design
May 15, 2019 3 /
What to submit
A zip/rar package (Deadline: 2019/6/16) Your codes
project.xlsx
name |V| cc3-4p 64 cc3-4u 64 cc6-2p 64 cc6-2u 64
hc6p 64 hc6u 64
b01 50
b02 50
Result
Running Time
Your report should include: At least two algorithms
Comparison experiments Results and analysis
Algorithm design
May 15, 2019
4 /
Thank you!
Algorithm design
May 15, 2019
5 /
Reviews
There are no reviews yet.