design schedule
1. Analyze the data attributes of the optical fiber network in residential areas, and determine the algorithm design scheme according to the functional requirements of optical fiber laying;
2. Complete the data structure design of network optical fiber laying, including the structure and storage structure of graph files, the storage structure of minimum spanning tree, the display structure of graphs, etc.;
3. Complete functional design work, including randomly generating cost files, reading graph files, calculating minimum spanning tree, displaying minimum spanning tree, etc.;
4. Use C or C++ programming language to write and implement algorithm programs;
5. Complete the major work report.
design content
Carefully refer to the relevant reference materials and data of the course, understand the principle and requirements of laying network optical fibers, and design an algorithm to realize the optimal selection of network optical fiber laying between residential areas. The specific contents are as follows:
It is necessary to lay network optical fibers between n residential areas in a city. Assuming that optical fibers need to be laid between any two residential areas, only n-1 optical fibers need to be laid between these n residential areas to form a network. , but due to different geographical environments, the required costs are not the same. The design of this course requires random generation of the cost of laying network optical fibers between any residential area in advance, and the cost is stored in a file, and then an optimal solution is designed for optical fiber laying, so that the network between all the areas can be connected, and the network can be The cost of fiber laying is the smallest, and the optimal solution designed is finally output in the form of graphics.
demand analysis
1. Optical fiber network design
Lay network optical fibers between n residential areas in a city, and design an optimal solution for optical fiber laying, which can not only connect the networks between all the residential areas, but also minimize the cost of network optical fiber laying.
2. Functional requirements
Enter the number of residential areas, the number of optical fibers, the unit price of optical fibers, and the distance between each residential area, and use the Kruskal algorithm to output the optimal laying plan of the system.
code specific
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
cout<<"Optimum Design of Optical Fiber Route Laying in Residential Areas "<<endl;
int neighborhoodNum, opticalNum; // Number of residential areas, number of optical fiber lines
int neighborhood1, neighborhood2; //two residential areas
double price; //Price per unit length of fiber optic line
double distance, shortest_distance=0; //Shortest total route length
int neighborhoodArrary[100][100]; //adjacency matrix
int i, j;
cout<<"Please enter the number of residential areas: ";
cin>>neighborhoodNum;
cout<<"Please enter the number of fiber optic lines: ";
cin>>opticalNum;
cout<<"Please enter the price per unit length of the fiber optic line : ";
cin>>price;
cout<<endl;
for(i=0; i<neighborhoodNum; i++)
for(j=0; j<neighborhoodNum; j++)
{
neighborhoodArrary[i][j]=9999;
}
cout<<"Please enter the two residential areas and distances for each fiber optic line:"<<endl;
j=1; //j represents the nth line
for(i=0; i<opticalNum; i++)
{
cout<<"Please enter the "<<j<<" Two residential areas and distances of a fiber optic line: "; //Store two neighborhoods and distances
cin>>neighborhood1>>neighborhood2>>distance;
neighborhoodArrary[neighborhood1][neighborhood2]=distance;
neighborhoodArrary[neighborhood2][neighborhood1]=distance;
j++;
}
int short_way[100];
int near_neighborhood[100];
int min_way;
int temp_neighborhood;
for(i=1; i<neighborhoodNum; i++)
{
short_way[i]=neighborhoodArrary[0][i];
near_neighborhood[i]=0;
}
short_way[i]=0;
near_neighborhood[i]=0;
cout<<"The optimal plan for laying optical fiber routes in residential areas is designed as follows: \n";
for(i=1; i<neighborhoodNum; i++)
{
min_way=9999; j=1; temp_neighborhood=1;
while(j<neighborhoodNum)
{
if(short_way[j]!=0 && short_way[j]<min_way)
{
min_way=short_way[j];
temp_neighborhood=j;
}
j++;
}
cout<<" residential area "<<near_neighborhood[temp_neighborhood]<<"----("<<min_way<<"Meter) ----residential area"<<temp_neighborhood<<endl;
short_way[temp_neighborhood]=0;
shortest_distance+=min_way;
for(j=0; j<neighborhoodNum; j++)
if(neighborhoodArrary[temp_neighborhood][j]<short_way[j])
{
short_way[j]=neighborhoodArrary[temp_neighborhood][j];
near_neighborhood[j]=temp_neighborhood;
}
}
cout<<"The shortest total length is: "<<shortest_distance<<"Meter"<<endl;
cout<<"The minimum total cost is: "<<shortest_distance*price<<"Yuan"<<endl<<endl;
char choice;
cout<<"clear data, re-enter? T or F : "; cin>>choice;
if(choice=='T' )
{
system("cls") ; //clear screen, start over
}
if(choice=='F' )
{
cout<<"exit successfully!";
exit(0) ; //exit the program }
}
}
The result of running the code:
Summarize:
Using the minimum spanning tree, the point represents the residential area, the path represents the optical fiber line, and the Kruskal algorithm is used to connect the network between all the residential areas, and to minimize the cost of network optical fiber laying. Considering the convenience of input and output streams of the iostream library, C++ code is used. In the process of thinking about the design process, the difficulty of algorithm selection is encountered, and finally Kruskal's algorithm is selected considering the time complexity and space complexity.