[SOLVED] 代写 algorithm graph Project

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 S∈V 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 /