dongtaiguihua.rar_公交优化_公交运营_路线规划

//--------------------动态规划解最优路径问题------------------ #include<iostream.h> #include<math.h> //全局变量 int N=0;//节点状态段数 int M[10];//记录每段的状态个数 int C[10][10];//记录从状态转移的费用 int S[10][10];//记录每段中的状态 //输入接口函数 void input() { //定义变量 int temp[10]; for( int i=0;i<10;i++) for(int j=0;j<10;j++) { M[i]=0; temp[i]=0; C[i][j]=0; S[i][j]=0; } //读入所求问题的基本条件 cout<<"--------------------------参数输入-------------------"<<endl; cout<<"请按提示输入下列参数："<<endl<<endl; cout<<" 路线的状态段数N： "<<" N= "; cin>>N; cout<<endl<<" 输入每段中所含有的城市数及城市名： "<<endl; for( i=1;i<=N;i++) { cout<<" 第"<<i<<"段: "<<endl<<" 城市数:"; cin>>M[i]; cout<<" 城市名："; for(int j=1;j<=M[i];j++) { cin>>S[i][j]; } } //读入状态转移的费用 cout<<endl<<endl<<"-----输入出发城市到到达城市所得利润------"<<endl; for(i=1;i<N;i++) { cout<<endl<<"第"<<i<<"段到第"<<i+1<<"段: "<<endl; for(int j=1;j<=M[i];j++) { cout<<endl<<"出发城市:"<<S[i][j]<<" "; temp[i]=S[i][j]; for(int k=1;k<=M[i+1];k++) { cout<<"到达城市:"<<S[i+1][k]<<" 利润："; temp[i+1]=S[i+1][k]; cin>>C[temp[i]][temp[i+1]]; cout<<" "; } } } } void comput() { //运用动态规划法求最优解 //定义变量 int y[10][10]; int temp=0,temp1,t=1; for(int i=0;i<10;i++) for(int j=0;j<10;j++) y[i][j]=0; for( i=N-1;i>=1;i--) { for(int j=1;j<=M[i];j++) { for(int k=1;k<=M[i+1];k++) { if(i==N-1) y[i][j]=C[S[i][j]][S[i+1][k]]; else { temp=C[S[i][j]][S[i+1][k]]+y[i+1][k]; if (temp>y[i][j]) { y[i][j]=temp; } } } } } cout<<"-------------------输出最优结果-------------------"<<endl<<endl; cout<<"最大利润为： "<<y[1][1]<<endl; //----------计算输出线路------------------ cout<<"最优路线为: "<<S[1][1]; for(i=1;i<N;i++) { for(int j=1;j<=M[i];j++) { if(j!=t) continue; else { for(int k=1;k<=M[i+1];k++) { temp1=y[i][j]-C[S[i][j]][S[i+1][k]]; if(y[i+1][k]==temp1) { cout<<"---"<<S[i+1][k]; t=k; break; } } break; } } } cout<<endl; return; } void main() { cout<<"------------------------109230 艾伟清-----------------"<<endl; cout<<"-----------------------动态规划法求解最优路线问题----------------"<<endl; input(); comput(); }