Перевести код алгоритма решения задачи коммивояжера методом ветвей и границ из 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