Перевести код алгоритма решения задачи коммивояжера методом ветвей и границ из Java в C#
Формулировка задачи:
Здравствуйте. Нашел код на JAVA алгоритма решения задачи коммивояжера методом ветвей и границ.Вот он
http://elitecoder.wdfiles.com/local-.../bbstatic.java
Хотел переписать его под c# для матрицы 5 на 5.
Вот что получилось
Стоимость пути выводит корректно, но сам путь почему то перепутывается. Мне кажется что ошибка в методе expand но никак не могу понять в чем она. Помогите пожалуйста.
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.IO; namespace branch_tsp { public class lobject { public int city; public int cost; public int[,] matrix; public int[] remainingcity; public int city_left_to_expand; public Stack<int> st; public lobject(int number) { matrix = new int[number, number]; st = new Stack<int>(); } } class Program { public static int[] min(int[] array, int min) { // Recurse through array and reduce with the passed "min" value for (int j = 0; j < array.Length; j++) { array[j] = array[j] - min; } // Return reduced array return array; } /* Minimum Function - Calculates the minimum value with which a matrix can be reduced Input - Array for which minimum value is to be calculated Return - Minimum value */ public static int minimum(int[] array) { // Declaring default as something lesser than infinity but higher than valid values int min = 9000; // Recursing through array to find minimum value for (int i = 0; i < array.Length; i++) { // If value is valid i.e. less than infinity, reset min with that value if (array[i] < min) { min = array[i]; } } // Check if min value is unchanged i.e. we met an infinity array if (min == 9000) { // Return 0 as nothing to reduce return 0; } // Else return the min value else { return min; } } public static void output(lobject l1) { Console.WriteLine("============================================"); Console.WriteLine("============================================"); Console.WriteLine("This city is :" + l1.city); Console.WriteLine("The node cost function:" + l1.cost); // Printing remaining cities Console.WriteLine("The remaining cities to be expanded from this node"); for (int h = 0; h < l1.remainingcity.Length; h++) { Console.Write(l1.remainingcity[h]); Console.Write(" "); } Console.WriteLine(); Console.WriteLine("The number of possible remaining expansions from this node are" + l1.city_left_to_expand); Console.WriteLine(); Console.WriteLine("============================================"); Console.WriteLine("============================================"); } public static void expand(List<lobject> l,lobject o) { // Number of cities to be traversed int length = o.remainingcity.Length; for(int i = 0 ;i < length;i++) { // Variable Initialization if(o.remainingcity[i] ==0) continue; int cost = 0; cost = o.cost; int city = o.city; Stack<int> st = new Stack<int>(); for(int st_i=0;st_i<o.st.Count;st_i++) { int k = o.st.ElementAt(st_i); Console.WriteLine(k); st.Push(k); } st.Push(o.remainingcity[i]); // Fetching matrix contents into a temporary matrix for reduction int[,] temparray = new int[5,5]; for(int i_1 =0;i_1 < 5;i_1++ ) { for(int i_2=0;i_2 <5;i_2++) { temparray[i_1,i_2] = o.matrix[i_1,i_2]; } } //Adding the value of edge (i,j) to the cost cost = cost + temparray[city,o.remainingcity[i]]; //Making the ith row and jth column to be infinity for(int j=0;j<5;j++) { temparray[city,j] = 9999; temparray[j,o.remainingcity[i]] = 9999; } //Making (j,0) to be infinity temparray[o.remainingcity[i],0] = 9999; //Reducing this matrix according to the rules specified int cost1 = reduce(temparray,cost,city,o.remainingcity[i]); // Updating object contents corresponding to current city tour lobject finall = new lobject(5); finall.city = o.remainingcity[i]; finall.cost = cost1; finall.matrix = temparray; int[] temp_array = new int[o.remainingcity.Length]; // Limiting the expansion in case of backtracking for(int i_3 = 0;i_3<temp_array.Length;i_3++) { temp_array[i_3] = o.remainingcity[i_3]; } temp_array[i]=0; finall.remainingcity = temp_array; finall.city_left_to_expand = o.city_left_to_expand -1; finall.st = st; l.Add(finall); } } /* Reduce - Reduces the passed Matrix with minimum value possible Input - 2D Array to be reduced, Previous Step's Cost, Row to be processed, Column to be processed Return - Cost of Reduction */ public static int reduce(int[,] array, int cost, int row, int column) { // Variables // Arrays to store rows and columns to be reduced int[] array_to_reduce = new int[5]; int[] reduced_array = new int[5]; // Variable to store updated cost int new_cost = cost; // Loop for reducing rows for (int i = 0; i < 5; i++) { // If the row matches current city, do not reduce if (i == row) continue; // If the row is not corresponding current city, try to reduce for (int j = 0; j < 5; j++) { // Fetch the row to be reduced array_to_reduce[j] = array[i,j]; } // Check if current row can be reduced if (minimum(array_to_reduce) != 0) { // Updating new cost new_cost = minimum(array_to_reduce) + new_cost; // Reducing the row reduced_array = min(array_to_reduce, minimum(array_to_reduce)); // Pushing the reduced row back into original array for (int k = 0; k < 5; k++) { array[i,k] = reduced_array[k]; } } } // Loop for reducing columns for (int i = 0; i < 5; i++) { // If column matches current city, do not reduce if (i == column) continue; // If column does not match current city, try to reduce for (int j = 0; j <5; j++) { // Fetching column to be reduced array_to_reduce[j] = array[j,i]; } // Check if current column can be reduced if (minimum(array_to_reduce) != 0) { // Updating current cost new_cost = minimum(array_to_reduce) + new_cost; // Reducing the column reduced_array = min(array_to_reduce, minimum(array_to_reduce)); // Pushing the reduced column back into original array for (int k = 0; k < 5; k++) { array[k,i] = reduced_array[k]; } } } // Reduction done, return the new cost return new_cost; } public static int[] decreasing_sort(int[] temp) { int[] y = new int[temp.Length]; // Retreiving Array contents for (int j = 0; j < temp.Length; j++) { y[j] = temp[j]; } int x = 0; // Sorting for (int i = 0; i < temp.Length - 1; i++) { if (temp[i] < temp[i + 1]) { x = temp[i]; temp[i] = temp[i + 1]; temp[i + 1] = x; } } int[] to_be_returned = new int[temp.Length]; int f = 0; // Putting sorted contents into array to be returned for (int j = 0; j < temp.Length; j++) { for (int j1 = 0; j1 < temp.Length; j1++) { if (temp[j] == y[j1]) { to_be_returned[j] = j1; } } } return to_be_returned; } } }
Решение задачи: «Перевести код алгоритма решения задачи коммивояжера методом ветвей и границ из Java в C#»
textual
Листинг программы
static void Main(string[] args) { // Starting the count for Run Time var start_time = DateTime.Now; // Opening Data File and Finding the Number of Cities int NUMBER_CITIES =5; String input = File.ReadAllText("text.txt"); int i = 0, j = 0; int[,] array = new int[5, 5]; foreach (var row in input.Split('\n')) { j = 0; foreach (var col in row.Trim().Split(' ')) { array[i, j] = int.Parse(col.Trim()); j++; } i++; } // Performing First Reduction of the Cost Matrix int[,] maintemp = new int[NUMBER_CITIES, NUMBER_CITIES]; int x = 0; x = reduce(array, x, 9999, 9999); lobject l1 = new lobject(NUMBER_CITIES); //The root of the tree starting at city 0. l1.city = 0; l1.cost = x; l1.matrix = array; l1.st.Push(0); l1.remainingcity = new int[NUMBER_CITIES - 1]; l1.city_left_to_expand = NUMBER_CITIES - 1; for (int o = 0; o < 4; o++) { l1.remainingcity[o] = o + 1; } //variable for keeping track of the number of expanded nodes int count = 0; //Stack DS for maintaining the nodes in the tree Stack<lobject> s = new Stack<lobject>(); //Pushing the root onto the stack s.Push(l1); //Temporary variable for storing the best solution found so far lobject temp_best_solution = new lobject(NUMBER_CITIES); int current_best_cost = 100000; //Stack iterations including backtracking // Starting the Tree Traversal - Traverses until stack gets empty i.e, all nodes have been expanded while (s.Count != 0) { // Variable Initialization List<lobject> main = new List<lobject>(); lobject hell = new lobject(NUMBER_CITIES); hell = s.Pop(); //Expand Stack only if the node is not a leaf node and if its cost is better than the best so far if (hell.city_left_to_expand == 0) { //Comparing the cost of this node to the best and updating if necessary if (hell.cost <= current_best_cost) { temp_best_solution = hell; current_best_cost = temp_best_solution.cost; } } else if (hell.city_left_to_expand != 0) { if (hell.cost <= current_best_cost) { count++; // Expanding the latest node popped from stack expand(main, hell); //Determing the order in which the expanded nodes should be pushed onto the stack int[] arrow = new int[main.Count()]; for (int pi = 0; pi < main.Count(); pi++) { lobject help = (lobject)main.ElementAt(pi); arrow[pi] = help.cost; } // Sorting nodes in decreasing order based on their costs int[] tempppp = decreasing_sort(arrow); for (int pi = 0; pi < tempppp.Length; pi++) { // Pushing the node objects into stack in decreasing order s.Push((lobject)main.ElementAt(tempppp[pi])); } } } } // Calculating Stop time for Run Time var stop_time = DateTime.Now; var run_time = stop_time - start_time; // Checking if a solution is found if (temp_best_solution.st.Count() == 5 & temp_best_solution.cost < 9000) { // Printing Tour Cost Console.WriteLine(); Console.WriteLine(current_best_cost); Console.WriteLine(); // Printing Optimal Tour Console.Write("[ "); for (int st_i = 0; st_i < 5; st_i++) { Console.Write(temp_best_solution.st.ElementAt(st_i)); Console.Write(", "); } Console.Write("0 "); Console.Write("]"); Console.WriteLine(); Console.WriteLine(); // Printing Running Time Console.WriteLine(run_time); Console.WriteLine(); //The number of nodes expanded in the algorithm Console.WriteLine(count); Console.WriteLine(); } else { Console.WriteLine("\nNo Solution.\n"); // Printing Running Time Console.WriteLine(run_time); Console.WriteLine(); } }//1
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д