Перевести код алгоритма решения задачи коммивояжера методом ветвей и границ из Java в C#

Узнай цену своей работы

Формулировка задачи:

Здравствуйте. Нашел код на JAVA алгоритма решения задачи коммивояжера методом ветвей и границ.Вот он http://elitecoder.wdfiles.com/local-.../bbstatic.java Хотел переписать его под c# для матрицы 5 на 5. Вот что получилось
Листинг программы
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. using System.IO;
  7. namespace branch_tsp
  8. {
  9. public class lobject
  10. {
  11. public int city;
  12. public int cost;
  13. public int[,] matrix;
  14. public int[] remainingcity;
  15. public int city_left_to_expand;
  16. public Stack<int> st;
  17. public lobject(int number)
  18. {
  19. matrix = new int[number, number];
  20. st = new Stack<int>();
  21. }
  22. }
  23. class Program
  24. {
  25. public static int[] min(int[] array, int min)
  26. {
  27. // Recurse through array and reduce with the passed "min" value
  28. for (int j = 0; j < array.Length; j++)
  29. {
  30. array[j] = array[j] - min;
  31. }
  32. // Return reduced array
  33. return array;
  34. }
  35. /*
  36. Minimum Function - Calculates the minimum value with which a matrix can be reduced
  37. Input - Array for which minimum value is to be calculated
  38. Return - Minimum value
  39. */
  40. public static int minimum(int[] array)
  41. {
  42. // Declaring default as something lesser than infinity but higher than valid values
  43. int min = 9000;
  44. // Recursing through array to find minimum value
  45. for (int i = 0; i < array.Length; i++)
  46. {
  47. // If value is valid i.e. less than infinity, reset min with that value
  48. if (array[i] < min)
  49. {
  50. min = array[i];
  51. }
  52. }
  53. // Check if min value is unchanged i.e. we met an infinity array
  54. if (min == 9000)
  55. {
  56. // Return 0 as nothing to reduce
  57. return 0;
  58. }
  59. // Else return the min value
  60. else
  61. {
  62. return min;
  63. }
  64. }
  65. public static void output(lobject l1)
  66. {
  67. Console.WriteLine("============================================");
  68. Console.WriteLine("============================================");
  69. Console.WriteLine("This city is :" + l1.city);
  70. Console.WriteLine("The node cost function:" + l1.cost);
  71. // Printing remaining cities
  72. Console.WriteLine("The remaining cities to be expanded from this node");
  73. for (int h = 0; h < l1.remainingcity.Length; h++)
  74. {
  75. Console.Write(l1.remainingcity[h]);
  76. Console.Write(" ");
  77. }
  78. Console.WriteLine();
  79. Console.WriteLine("The number of possible remaining expansions from this node are" + l1.city_left_to_expand);
  80. Console.WriteLine();
  81. Console.WriteLine("============================================");
  82. Console.WriteLine("============================================");
  83. }
  84. public static void expand(List<lobject> l,lobject o)
  85. {
  86. // Number of cities to be traversed
  87. int length = o.remainingcity.Length;
  88. for(int i = 0 ;i < length;i++)
  89. {
  90. // Variable Initialization
  91. if(o.remainingcity[i] ==0) continue;
  92. int cost = 0;
  93. cost = o.cost;
  94. int city = o.city;
  95. Stack<int> st = new Stack<int>();
  96. for(int st_i=0;st_i<o.st.Count;st_i++)
  97. {
  98. int k = o.st.ElementAt(st_i);
  99. Console.WriteLine(k);
  100. st.Push(k);
  101. }
  102. st.Push(o.remainingcity[i]);
  103. // Fetching matrix contents into a temporary matrix for reduction
  104. int[,] temparray = new int[5,5];
  105. for(int i_1 =0;i_1 < 5;i_1++ )
  106. {
  107. for(int i_2=0;i_2 <5;i_2++)
  108. {
  109. temparray[i_1,i_2] = o.matrix[i_1,i_2];
  110. }
  111. }
  112. //Adding the value of edge (i,j) to the cost
  113. cost = cost + temparray[city,o.remainingcity[i]];
  114. //Making the ith row and jth column to be infinity
  115. for(int j=0;j<5;j++)
  116. {
  117. temparray[city,j] = 9999;
  118. temparray[j,o.remainingcity[i]] = 9999;
  119. }
  120. //Making (j,0) to be infinity
  121. temparray[o.remainingcity[i],0] = 9999;
  122. //Reducing this matrix according to the rules specified
  123. int cost1 = reduce(temparray,cost,city,o.remainingcity[i]);
  124. // Updating object contents corresponding to current city tour
  125. lobject finall = new lobject(5);
  126. finall.city = o.remainingcity[i];
  127. finall.cost = cost1;
  128. finall.matrix = temparray;
  129. int[] temp_array = new int[o.remainingcity.Length];
  130. // Limiting the expansion in case of backtracking
  131. for(int i_3 = 0;i_3<temp_array.Length;i_3++)
  132. {
  133. temp_array[i_3] = o.remainingcity[i_3];
  134. }
  135. temp_array[i]=0;
  136. finall.remainingcity = temp_array;
  137. finall.city_left_to_expand = o.city_left_to_expand -1;
  138. finall.st = st;
  139. l.Add(finall);
  140. }
  141. }
  142. /*
  143. Reduce - Reduces the passed Matrix with minimum value possible
  144. Input - 2D Array to be reduced, Previous Step's Cost, Row to be processed, Column to be processed
  145. Return - Cost of Reduction
  146. */
  147. public static int reduce(int[,] array, int cost, int row, int column)
  148. {
  149. // Variables
  150. // Arrays to store rows and columns to be reduced
  151. int[] array_to_reduce = new int[5];
  152. int[] reduced_array = new int[5];
  153. // Variable to store updated cost
  154. int new_cost = cost;
  155. // Loop for reducing rows
  156. for (int i = 0; i < 5; i++)
  157. {
  158. // If the row matches current city, do not reduce
  159. if (i == row) continue;
  160. // If the row is not corresponding current city, try to reduce
  161. for (int j = 0; j < 5; j++)
  162. {
  163. // Fetch the row to be reduced
  164. array_to_reduce[j] = array[i,j];
  165. }
  166. // Check if current row can be reduced
  167. if (minimum(array_to_reduce) != 0)
  168. {
  169. // Updating new cost
  170. new_cost = minimum(array_to_reduce) + new_cost;
  171. // Reducing the row
  172. reduced_array = min(array_to_reduce, minimum(array_to_reduce));
  173. // Pushing the reduced row back into original array
  174. for (int k = 0; k < 5; k++)
  175. {
  176. array[i,k] = reduced_array[k];
  177. }
  178. }
  179. }
  180. // Loop for reducing columns
  181. for (int i = 0; i < 5; i++)
  182. {
  183. // If column matches current city, do not reduce
  184. if (i == column) continue;
  185. // If column does not match current city, try to reduce
  186. for (int j = 0; j <5; j++)
  187. {
  188. // Fetching column to be reduced
  189. array_to_reduce[j] = array[j,i];
  190. }
  191. // Check if current column can be reduced
  192. if (minimum(array_to_reduce) != 0)
  193. {
  194. // Updating current cost
  195. new_cost = minimum(array_to_reduce) + new_cost;
  196. // Reducing the column
  197. reduced_array = min(array_to_reduce, minimum(array_to_reduce));
  198. // Pushing the reduced column back into original array
  199. for (int k = 0; k < 5; k++)
  200. {
  201. array[k,i] = reduced_array[k];
  202. }
  203. }
  204. }
  205. // Reduction done, return the new cost
  206. return new_cost;
  207. }
  208. public static int[] decreasing_sort(int[] temp)
  209. {
  210. int[] y = new int[temp.Length];
  211. // Retreiving Array contents
  212. for (int j = 0; j < temp.Length; j++)
  213. {
  214. y[j] = temp[j];
  215. }
  216. int x = 0;
  217. // Sorting
  218. for (int i = 0; i < temp.Length - 1; i++)
  219. {
  220. if (temp[i] < temp[i + 1])
  221. {
  222. x = temp[i];
  223. temp[i] = temp[i + 1];
  224. temp[i + 1] = x;
  225. }
  226. }
  227. int[] to_be_returned = new int[temp.Length];
  228. int f = 0;
  229. // Putting sorted contents into array to be returned
  230. for (int j = 0; j < temp.Length; j++)
  231. {
  232. for (int j1 = 0; j1 < temp.Length; j1++)
  233. {
  234. if (temp[j] == y[j1])
  235. {
  236. to_be_returned[j] = j1;
  237. }
  238. }
  239. }
  240. return to_be_returned;
  241. }
  242. }
  243. }
Стоимость пути выводит корректно, но сам путь почему то перепутывается. Мне кажется что ошибка в методе expand но никак не могу понять в чем она. Помогите пожалуйста.

Решение задачи: «Перевести код алгоритма решения задачи коммивояжера методом ветвей и границ из Java в C#»

textual
Листинг программы
  1.   static void Main(string[] args)
  2.         {
  3.             // Starting the count for Run Time
  4.             var start_time = DateTime.Now;
  5.             // Opening Data File and Finding the Number of Cities
  6.  
  7.  
  8.          
  9.         int NUMBER_CITIES =5;
  10.        
  11.  
  12.  
  13.         String input = File.ReadAllText("text.txt");
  14.  
  15.         int i = 0, j = 0;
  16.         int[,] array = new int[5, 5];
  17.         foreach (var row in input.Split('\n'))
  18.         {
  19.             j = 0;
  20.             foreach (var col in row.Trim().Split(' '))
  21.             {
  22.                 array[i, j] = int.Parse(col.Trim());
  23.                 j++;
  24.             }
  25.             i++;
  26.         }
  27.  
  28.  
  29.             // Performing First Reduction of the Cost Matrix
  30.             int[,] maintemp = new int[NUMBER_CITIES, NUMBER_CITIES];
  31.             int x = 0;
  32.             x = reduce(array, x, 9999, 9999);
  33.             lobject l1 = new lobject(NUMBER_CITIES);
  34.  
  35.             //The root of the tree starting at city 0.
  36.             l1.city = 0;
  37.             l1.cost = x;
  38.             l1.matrix = array;
  39.             l1.st.Push(0);
  40.             l1.remainingcity = new int[NUMBER_CITIES - 1];
  41.             l1.city_left_to_expand = NUMBER_CITIES - 1;
  42.  
  43.             for (int o = 0; o < 4; o++)
  44.             {
  45.                 l1.remainingcity[o] = o + 1;
  46.             }
  47.             //variable for keeping track of the number of expanded nodes
  48.             int count = 0;
  49.             //Stack DS for maintaining the nodes in the tree
  50.             Stack<lobject> s = new Stack<lobject>();
  51.             //Pushing the root onto the stack
  52.             s.Push(l1);
  53.  
  54.             //Temporary variable for storing the best solution found so far
  55.             lobject temp_best_solution = new lobject(NUMBER_CITIES);
  56.             int current_best_cost = 100000;
  57.             //Stack iterations including backtracking
  58.             // Starting the Tree Traversal - Traverses until stack gets empty i.e, all nodes have been expanded
  59.             while (s.Count != 0)
  60.             {
  61.                 // Variable Initialization
  62.                 List<lobject> main = new List<lobject>();
  63.  
  64.                 lobject hell = new lobject(NUMBER_CITIES);
  65.                 hell = s.Pop();
  66.                 //Expand Stack only if the node is not a leaf node and if its cost is better than the best so far
  67.                 if (hell.city_left_to_expand == 0)
  68.                 {
  69.                     //Comparing the cost of this node to the best and updating if necessary
  70.                     if (hell.cost <= current_best_cost)
  71.                     {
  72.                         temp_best_solution = hell;
  73.                         current_best_cost = temp_best_solution.cost;
  74.                     }
  75.                 }
  76.                 else if (hell.city_left_to_expand != 0)
  77.                 {
  78.                     if (hell.cost <= current_best_cost)
  79.                     {
  80.                         count++;
  81.                         // Expanding the latest node popped from stack
  82.                         expand(main, hell);
  83.  
  84.                         //Determing the order in which the expanded nodes should be pushed onto the stack
  85.                         int[] arrow = new int[main.Count()];
  86.                         for (int pi = 0; pi < main.Count(); pi++)
  87.                         {
  88.                             lobject help = (lobject)main.ElementAt(pi);
  89.                             arrow[pi] = help.cost;
  90.                         }
  91.                         // Sorting nodes in decreasing order based on their costs
  92.                         int[] tempppp = decreasing_sort(arrow);
  93.                         for (int pi = 0; pi < tempppp.Length; pi++)
  94.                         {
  95.                             // Pushing the node objects into stack in decreasing order
  96.                             s.Push((lobject)main.ElementAt(tempppp[pi]));
  97.                            
  98.                         }
  99.                     }
  100.                 }
  101.             }
  102.             // Calculating Stop time for Run Time
  103.             var stop_time = DateTime.Now;
  104.             var run_time = stop_time - start_time;
  105.  
  106.             // Checking if a solution is found
  107.             if (temp_best_solution.st.Count() == 5 & temp_best_solution.cost < 9000)
  108.             {
  109.                 // Printing Tour Cost
  110.                 Console.WriteLine();
  111.                 Console.WriteLine(current_best_cost);
  112.                 Console.WriteLine();
  113.                 // Printing Optimal Tour
  114.                 Console.Write("[ ");
  115.                 for (int st_i = 0; st_i < 5; st_i++)
  116.                 {
  117.                     Console.Write(temp_best_solution.st.ElementAt(st_i));
  118.                    
  119.                     Console.Write(", ");
  120.                 }
  121.                 Console.Write("0 ");
  122.                 Console.Write("]");
  123.                 Console.WriteLine();
  124.                 Console.WriteLine();
  125.                 // Printing Running Time
  126.                 Console.WriteLine(run_time);
  127.                 Console.WriteLine();
  128.                 //The number of nodes expanded in the algorithm
  129.                 Console.WriteLine(count);
  130.                 Console.WriteLine();
  131.             }
  132.             else
  133.             {
  134.                 Console.WriteLine("\nNo Solution.\n");
  135.                 // Printing Running Time
  136.                 Console.WriteLine(run_time);
  137.                 Console.WriteLine();
  138.             }
  139.         }//1

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.889 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы