Перевести код алгоритма решения задачи коммивояжера методом ветвей и границ из 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
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д