数学建模社区-数学中国

标题: 公交路线最小换乘次数的路径选择算法（C代码）（请求高手指教） [打印本页]
作者: 舞情＿Dong    时间: 2012-8-19 18:02
标题: 公交路线最小换乘次数的路径选择算法（C代码）（请求高手指教）
第三天了，关于交通路线的选择，用C语言写成了个样子，下面代码可以正常运行，就是路线选择的结果不是很好，结果有好多重复的，有些站点似乎选不出来，这和存放交通路线的数组a有关，我们是把公交路线的上行和下行放在二维数组的同一行的，肯定有重复，但对程序算法也有质疑，实在是惭愧，自己不才，对其它语法实在是不太了解，用的都是for，if循环嵌套，还请仁兄指教。这是2007年的全国竞赛题，网上也有各种算法（基于不同语言），我们建模培训做真题，按自己想法用C编写了下面的程序，但结果不是很好，自己对其它的语句又不是很了解，实在没辙了，真心请教各位大侠，现在在改数组，打算将同一条交通路线的上行和下行放入数组的不同行里，真心寻求帮助，请求仁兄指导，谢谢！# Q% ]  ~# g# @; x9 E

! i) |% z* a4 U) Z8 f+ s+ M& T
0 j) U! t: M- f. I) ]- g编写的C代码如下，由于数组a的数据带大，粘贴不过来（520条数据）( M# K" h1 Z+ d9 Y( g
本人实在是很惭愧，对C其他语法语句不是很熟悉，用的全是for，if循环嵌套，还请仁兄耐心查看
" @& r4 v/ J% H. z6 o8 g% N. k4 F8 j& H# U/ e

, l( p  U) L8 x' H5 s- {1 [3 p/ o         uint value1,value2;6 \+ L: Q; b$ H! I# x3 B$ n+ u  A8 m
        uint a[200],a1[200];//定义一个数组0 y- B' w" j3 p( z+ L; z
        uint b[200],b1[200];
. k7 R- I: p- O; G6 X    uint c[200];
% w6 F9 G2 @/ C0 Z' `! P1 n; ^: B8 k3 v1 R) j" X
. s$ a! ^1 T# M( m7 j; |

  ~, S1 q1 z% P4 F9 Nvoid routes()
& y9 P* X9 u' `! M{. O* X0 X! s0 r) E8 p" a
       
" o* b! V* w1 n' ~        uint i,j,j1,j2,j3,j4,c1,c2,k=0,k1=0,k2=0;
: R% h! R; m4 Y( e        uint linshi1,linshi2,e=0,f=0;2 o7 Y5 r  f' S* k! x
        uint q1,q2,q3,t;
: \; _* _' c6 a! \: Z# H8 O: O        uint luxian1=0;
6 Z; P1 b- t0 x8 t        uint m=0;  v% c* o0 r0 s% v' F% S
        uint n=0;
. X- V/ p) o( U4 T, j        for(i=0;i<520;i++)
4 Z, o. ]* y5 E% Z        {
% J, G$ X$ H1 Q) N2 q                for(j=0;j<200;j++)
  j. s- k4 y, H: [5 E; L$ Y+ X                {
1 w: r4 `* N" I" C: ^4 T7 ]2 [) d                        if(y[i][j]==value1)//寻找包含起点的所有路线,将路线值放入数组a% Q' o3 K- j0 j
                        {
' y7 W4 I1 |! e- K& C                                a[m]=i;7 f) l6 u) v: A' V! T  U0 i
                                //a1[m]=j;
! K! Q3 E6 w" A. Z6 _+ V" p2 d                                m++;
$ N3 C3 H; H2 O# `' x! O                        }" }6 [$ `& J: p) [8 |* O- Y
                        if(y[i][j]==value2)//寻找包含终点的所有路线，将其放入数组b7 a' C0 c; [. m) {( S: ], \
                        {7 h' ~! F# C1 M+ s) E) p
                                b[n]=i;5 s) @+ N2 e$ P8 [- A  [
                                //b1[n]=j;
/ ~/ N7 C1 E9 f1 T) C                                n++;
, X3 B6 \9 Z# V& f4 E                        }
+ z+ Y5 Z3 A" ^2 Y& H                }               
9 J" i- z, i% K' [& W6 B1 g        }
7 e' F2 a, L: c$ M- }0 t        printf("所有经过起点的路线a为：");
2 _0 K, |8 ~, U; _; m1 `/ V        for(i=0;i<m;i++). W3 a2 H5 R9 u- z1 d7 Y
        {
) u& U$ p9 \& M% q% o                printf("%d  ",a[i]);                2 F6 Z) @  h. ]$ @' z1 ]/ Z2 F
        }8 H; W- x7 l4 L9 i4 n+ U8 j
        printf("\n");
3 ~$ G: j2 A! S" w& G6 g        printf("所有经过终点的路线b为：");8 S8 J4 w/ g9 e1 U* V
        for(i=0;i<n;i++)* f7 J' `; H, A5 ^
        {
& F. z* Y4 {, Q, y7 H( O7 v9 I4 G                printf("%d  ",b[i]);               
( k8 R! G  @, h1 t) H- q1 h        }
* h, a6 i: |9 H        printf("\n");1 g" u0 E8 A! L1 I+ M7 Q4 T: A" `

" c9 I, K' A( R2 F$ U" {( [3 k, C0 |( c9 F9 T

0 F) Z% }( A# g% E: X) L7 y# `        for(i=0;i<m;i++)//直达路线的寻找
4 L5 ^6 P+ h' ]+ q/ [! f/ i        {. E, E" l5 f, O0 t8 ^+ ?
                for(j=0;j<n;j++)
& M% W; v  v" c, h                {
5 m! s, \0 \9 E' C1 r                        if(a[i]==b[j])
# l% n4 s8 I! ~$ R3 _+ ^* L                        {
4 _1 H" k; i$ {: S                                c[k]=a[i];, d1 i! P; g- i0 r% P! g2 C
                                k++;                                        % o& \/ u2 }) u6 V( c, C" I
                        }& z# k0 f5 U) d. n) d
                }8 u9 Y9 m$ u, ^, N: G8 h
        }+ r: ^: z# E2 k, c
        printf("您查询的站点的直达路线有：");
$ K" \1 Z4 ]: T3 z. O        for(i=0;i<k;i++)7 t$ C: [/ ]6 x& [; \3 e& t
        {; O8 [& _' r/ W; ^5 {+ z$ G
                if(c[i]!=0)" L1 u$ |8 Z/ P/ h/ s* R
                printf("%d  ",c[i]);2 C( A2 Q0 T. t. k- n
        }
* }, E2 Z6 @- D/ K+ ?6 [        printf("\n");//若没有直达路线这数组c为零，接着下面转乘一次路线的寻找
+ b" b( b& z3 m9 M  J  p3 f* n2 K7 J; u6 r! P, W! B
+ S  y0 ]2 T9 x3 V% E$ K
        if(k==0)
% Y# G( W. _7 D- J, b7 C/ C7 C/ h        {7 z& a" E7 c3 [1 b1 b+ y& j* x. x
                for(c1=0;c1<m;c1++)//转乘一次路线的寻找9 J7 o+ c! W7 x! ?
                {' z$ `  ~; m8 X
                        for(j=0;j<200;j++)
2 Z9 R3 z( P8 p8 h7 O                        {
6 A* N! V% j) X6 A2 M                                linshi1=a[c1];
* T; @/ b6 E! q! y0 r) C                                k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。( @+ f. y9 l4 _/ U# `+ k
                                for(c2=0;c2<n;c2++)! D) |- ~; G* t5 p" H. h
                                {' c; i$ e) W- g+ |" [6 U
                                        for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。4 i/ O! s5 z4 ~1 ?# f1 F: ~; F; l
                                        {# j. d- u7 o! |+ m$ J3 K
                                                linshi2=b[c2];9 ?) x. m: S1 _: J
                                                k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
( y8 \1 u9 f- u1 E( q" Y                                                if(k1==k2/*||k1==k2+1||k1==k2-1*/&&(k1!=0)&&(linshi1!=0)&&(linshi2!=0))//寻找数组a,b中的站点，有相同的及为转乘一次的转乘点，并输出。8 g: q: K" s, Y; s- u* H7 ?* |5 W1 r
                                                {% G% d- u1 w% ^6 K8 G# n
                                                        printf("您可以转乘一次，起始路线为:%d ，中间转站点为：%d ,%d终点路线为：%d\n",linshi1,k1,k2,linshi2);
& T4 I4 a2 ^# m! i2 w+ z                                                        luxian1++;
, C/ Y' g% `- m" j                                                }
; _( D- k) x% {6 u& h                                        }                                5 f+ O, H( G" t4 F) j9 |! r  i/ s
                                 }       
/ S( c7 Q% H" V                        }        
9 a5 ?0 c  k. |8 y8 J+ N3 z                }
8 o8 ?* x: D" p6 F- D        }2 w0 @  E/ d8 l3 Z" y1 I

4 Q4 n1 \& I( u8 L$ l0 D& {3 h/ r- l5 v8 v
        if(luxian1==0&&k==0)/ s; u" K* ^# o
        {
/ O( @4 v0 p5 \  P& k  c                for(c1=0;c1<m;c1++)//转乘两次路线的寻找
5 l1 x" {, K! W) g9 E! x( |) R                {; Q) I- ]5 x. @$ [9 A3 ~' U
                        for(j=0;j<200;j++)
9 L& |: x8 t9 b. V- B                        {
0 p/ l3 A% K6 e( O/ D) P                                linshi1=a[c1];2 X6 g* S, g) F' W5 @: Y# @
                                k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。0 ?9 G9 l6 a) w* P% I
                                for(c2=0;c2<n;c2++)' ]0 |2 y" i# |6 O' R3 H
                                {
2 _1 O, W6 N5 `4 \' D5 }9 m                                        for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。
' M- [- i$ P1 j0 D( {                                        {
8 k& A# k7 y$ ]  ?& H; Z" r' a" D8 j                                                linshi2=b[c2];! x" w; K5 W3 h: r
                                                k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。! M( N! p1 h/ W
                                                for(i=0;i<520;i++)
3 v9 T4 R2 T, F* V9 g! U2 B4 v                                                        {
. O; [: v$ e: F% q, R                                                                for(j=0;j<200;j++): b/ s( w5 a6 h- ~
                                                                {+ G; t/ b: V: N! s2 q0 y" c
                                                                if(k1==y[i][j]&&k1!=0)
9 y% g. _9 ^+ u. p! ]% O" Z3 Y+ }                                                                {
7 S; [" m7 s) V4 Q; y- \                                                                        f=i;
* |! p4 M- Y# X/ ]7 `0 e' V                                                                        e=j;                                                               
; ~" p! d3 s) C; w2 @                                                                        for(j=0;j<200;j++)
; V5 g4 v3 F& f' [3 L                                                                        {+ U" E  z1 I# N- v8 F( _
                                                                                if(k2==y[i][j]&&k2!=0&&(e<j)&&(linshi1!=0)&&(linshi2!=0))4 W% ?$ a8 e8 N/ K6 L, D. ]
                                                                                {
5 I8 y. @' a! G1 y$ @                                                                                        printf("您需转乘两次，起始路线为：%d ,第一个转车站点为：%d,中间路线为：%d,第二个转车站点为：%d,终点路线为：%d\n",linshi1,y[i][e],f,y[i][j],linshi2);" J* a5 [9 P( Y& C- S: d
                                                                                        //q1=abs(e-a1[c1]);//计算每条路线上经过的站点数( j4 D% P: B( b5 x! Q) g' ^
                                                                                        //q2=abs(j-e);& h% y( _. _& E$ ?- C, P5 @1 A
                                                                                        //q3=abs(b1[c2]-j);8 P, Y( X( r# H! e  ?+ e9 W
                                                                                        //t=3*(q1+q2+q3)+10;2 l; c) p+ N: ~5 G
                                                                                        //printf("该路线总共计时为：%d 分钟\n",t);& D' e7 n/ q. R1 k" z* Q) i, G
                                                                                }
& V  R( a# g5 u3 {+ m' h                                                                        }
- H8 |2 _8 s9 p- j, ^( l                                                                }0 D9 s! B& m3 ?2 h! F# X
                                                                }2 Y, i  P/ a  J
                                                        }    ( Y/ b; y+ j; R
                                        }        : P0 Z8 B4 s1 J1 n. L8 m$ q
                                }) [% t( W" [( u+ H
                        }
: z$ i% m: E; B( d! P" C9 o
5 `  y0 @! }* v$ n                }' ^2 v7 X1 G) W. J2 m
        }. v7 {6 S9 |$ ?8 @6 J; X+ w; G* |) l

  k) r5 O; {1 ~3 g5 V0 ~. W, {9 w) S5 V! S3 ]* u

& @2 L- h* `9 W" t& T
; a* b. A5 T- r5 k; K
- `& q# X: N, G4 Q, v
2 l& Y' S, |" z$ }
3 c( K' e% O6 b0 _( h* L+ K* }' r
  b% Z9 h1 ^+ R2 z, b9 |
8 B/ o$ @1 K4 M

0 n& g/ s- ~, i3 g
" G$ b' y  v- ~3 k3 {}
& ~/ Z9 }# h- h: g+ p$ L6 q# j
        void main()) n% P- T4 I* z0 R4 `- T  P+ _8 Z
        {
. o6 T/ y+ g4 R* v1 ^- S                printf("请输入起始站点和终止站点（中间空格间开）: \n");  n: c& }  h; e7 T9 |  a
                scanf("%d %d",&value1,&value2);               
0 r, i: T# G3 a2 z6 [                routes();$ H7 O. t% E" w" ~" c+ A1 v
$ R% q8 C+ z$ Y2 |4 \6 C
        }6 _. k/ \0 y0 k' W
       
作者: huakaibubai    时间: 2012-8-20 09:01
顶！！！！！！！！！
作者: huakaibubai    时间: 2012-8-20 09:01
好好！！！
作者: 倦了流年    时间: 2014-7-14 00:29
顶一个先！！！！！！！



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5