PRO_4_2.pas 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
  1. Program Pro_4_2; {例4的搜索算法}
  2. Const
  3. Map:Array['A'..'G','A'..'G'] Of Byte= {每两个农场之间的距离}
  4. ((0,56,43,71,35,41,36),
  5. (56,0,54,58,36,79,31),
  6. (43,54,0,30,20,31,58),
  7. (71,58,30,0,38,59,75),
  8. (35,36,20,38,0,44,67),
  9. (41,79,31,59,44,0,72),
  10. (36,31,58,75,67,72,0));
  11. Inputfile ='Input.Txt'; {输入文件名}
  12. Outputfile ='Output.Txt'; {输出文件名}
  13. Var
  14. F :Text; {文件变量}
  15. N :Integer; {任务的数目}
  16. Min :Word; {最短距离}
  17. Wu :Array[0..12,1..2] Of Char; {记录任务的数组}
  18. Dis :Array[0..12,0..12] Of Integer; {记录每两个任务的连接权值}
  19. Qiu,Pr :Array[0..14] Of Byte; {搜索中的记录数组}
  20. Se :Set Of Byte; {未完成的任务的集合}
  21. Procedure Init; {初始化过程}
  22. Var
  23. I :Integer;
  24. Ch :Char;
  25. Begin
  26. Assign(F,Inputfile);
  27. Reset(F);
  28. Readln(F,N); {读入数据}
  29. For I:=1 To N Do
  30. Readln(F,Wu[I,1],Ch,Wu[I,2]);
  31. Close(F);
  32. End;
  33. Procedure Prepare; {准备过程}
  34. Var
  35. I,J :Integer;
  36. Begin
  37. Wu[0,1]:='A';Wu[0,2]:='A'; {求出每两个任务的连接权值}
  38. For I:=0 To N Do
  39. For J:=0 To N Do
  40. Dis[I,J]:=Map[Wu[I,2],Wu[J,1]];
  41. End;
  42. Procedure Search(Dep:Byte;Al:Word); {搜索最优得路径}
  43. Var
  44. I :Byte;
  45. Begin
  46. If Al>=Min Then Exit;
  47. If Dep=N+1 Then
  48. Begin
  49. If Dis[Qiu[N],0]+Al<Min Then
  50. Begin
  51. Min:=Dis[Qiu[N],0]+Al; {如果更优,记录之}
  52. Pr:=Qiu;
  53. End;
  54. End
  55. Else
  56. For I:=1 To N Do {访问每个未访问的农场}
  57. If I In Se Then
  58. Begin
  59. Qiu[Dep]:=I;
  60. Exclude(Se,I);
  61. Search(Dep+1,Al+Dis[Qiu[Dep-1],I]);
  62. Include(Se,I);
  63. End;
  64. End;
  65. Procedure Print; {输出结果}
  66. Var
  67. I :Byte;
  68. Begin
  69. For I:=1 To N Do
  70. Inc(Min,Map[Wu[I,1],Wu[I,2]]);
  71. Assign(F,Outputfile);
  72. Rewrite(F);
  73. Writeln(F,Min);
  74. Write(F,'A ');
  75. For I:=1 To N Do
  76. Begin
  77. If Wu[Pr[I-1],2]<>Wu[Pr[I],1] Then Write(F,Wu[Pr[I],1],' ');
  78. Write(F,Wu[Pr[I],2],' ');
  79. End;
  80. If 'A'<>Wu[Pr[N],2] Then Write(F,'A');
  81. Close(F);
  82. End;
  83. Begin
  84. Init; {初始化}
  85. Prepare; {准备}
  86. Se:=[1..12]; {初始化各项搜索应用值}
  87. Qiu[0]:=0;
  88. Min:=60000;
  89. Search(1,0); {搜索}
  90. Print; {输出}
  91. End.