<file_sep>﻿
namespace TSP
{
    interface Solver
    {
        Problem solve(Problem cityData);
    }
}
<file_sep>using System;
using System.Collections.Generic;

namespace TSP
{
    class Problem
    {
        // Default values
        public const int DEFAULT_SEED = 1;
        public const int DEFAULT_PROBLEM_SIZE = 20;
        public const int DEFAULT_TIME_LIMIT = 60;        // in seconds
        private const double FRACTION_OF_PATHS_TO_REMOVE = 0.20;

        // Class members
        public int seed;
        public int size;
        public int timeLimit;
        public HardMode.Modes mode;
        private Random rnd;

        public City[] cities;
        public TSPSolution bssf;
        public TimeSpan timeElasped;
        public int solutions;

        // Constructors
        public Problem()
        {
            initialize(DEFAULT_SEED, DEFAULT_PROBLEM_SIZE, DEFAULT_TIME_LIMIT, HardMode.Modes.Hard);
        }

        public Problem(int seed, int size, int timeInSeconds, HardMode.Modes mode)
        {
            initialize(seed, size, timeInSeconds, mode);
        }

        private void initialize(int seed, int problemSize, int timeInSeconds, HardMode.Modes mode)
        {
            this.seed = seed;
            this.rnd = new Random(seed);

            // CRITICAL - TO MAKE THE POINTS LOOK LIKE THE
            // POINTS IN THE OLD VERSION FOR THE SAME SEEDS
            // DO NOT REMOVE THIS FOR LOOP
            for (int i = 0; i < 50; i++)
                rnd.NextDouble();

            this.size = problemSize;
            this.mode = mode;
            this.timeLimit = timeInSeconds * 1000;                        // timer wants timeLimit in milliseconds
            this.resetData();
        }

        // Reset the problem instance
        private void resetData()
        {
            cities = new City[size];
            bssf = null;

            if (mode == HardMode.Modes.Easy)
            {
                for (int i = 0; i < size; i++)
                    cities[i] = new City(rnd.NextDouble(), rnd.NextDouble());
            }
            else // Medium and hard
            {
                for (int i = 0; i < size; i++)
                    cities[i] = new City(rnd.NextDouble(), rnd.NextDouble(), rnd.NextDouble() * City.MAX_ELEVATION);
            }

            HardMode mm = new HardMode(this.mode, this.rnd, cities);
            if (mode == HardMode.Modes.Hard)
            {
                int edgesToRemove = (int)(size * FRACTION_OF_PATHS_TO_REMOVE);
                mm.removePaths(edgesToRemove);
            }
            City.setModeManager(mm);
        }

        //  Return the cost of the best solution so far. 
        public double costOfBssf()
        {
            if (bssf != null)
            {
                // go through each edge in the route and add up the cost. 
                int x;
                List<City> route = bssf.route;
                City here;
                double cost = 0D;

                for (x = 0; x < route.Count - 1; x++)
                {
                    here = route[x];
                    cost += here.costToGetTo(route[x + 1]);
                }

                // go from the last city to the first. 
                here = route[route.Count - 1];
                cost += here.costToGetTo(route[0]);
                return cost;
            }
            else
                return -1D; 
        }
    }
}
<file_sep>﻿using System;

namespace TSP
{
    class Test
    {
        public static void run()
        {
            bBHardLastCityBlocked();
            greedyHard();
            bbHardBetterThanGreedy();
        }

        public static void greedyEasy()
        {
            Problem cityData = new Problem(1, 5, 60, HardMode.Modes.Easy);
            cityData = GreedySolver.solve(cityData);
            if (cityData.bssf.costOfRoute != 2060)
                throw new SystemException("Incorrect cost");
        }

        public static void greedyEasy2()
        {
            Problem cityData = new Problem(1, 20, 60, HardMode.Modes.Hard);
            cityData = GreedySolver.solve(cityData);
            if (cityData.bssf.costOfRoute != 4484)
                throw new SystemException("Incorrect cost");
        }

         //This case should return the greedy value bc that is best
        public static void bBEasy()
        {
            Problem cityData = new Problem(1, 5, 60, HardMode.Modes.Easy);
            BranchAndBoundSolver solver = new BranchAndBoundSolver(cityData);
            cityData = solver.solve();
            if (cityData.bssf.costOfRoute != 2060)
                throw new SystemException("Incorrect cost");
        }

        // There exists a better path than the greedy one
        public static void bBNormal()
        {
            Problem cityData = new Problem(268, 16, 60, HardMode.Modes.Normal);
            BranchAndBoundSolver solver = new BranchAndBoundSolver(cityData);
            cityData = solver.solve();
            if (cityData.bssf.costOfRoute != 4069)
                throw new SystemException("Incorrect cost");
        }

        // The last city is blocked
        // Ends up using the greedy value
        public static void bBHardLastCityBlocked()
        {
            Problem cityData = new Problem(1, 5, 60, HardMode.Modes.Hard);
            BranchAndBoundSolver solver = new BranchAndBoundSolver(cityData);
            cityData = solver.solve();
            if (cityData.bssf.costOfRoute != 2123)
                throw new SystemException("Incorrect cost");
        }

        public static void greedyHard()
        {
            Problem cityData = new Problem(1, 20, 60, HardMode.Modes.Hard);
            cityData = GreedySolver.solve(cityData);
            if (cityData.bssf.costOfRoute != 4928)
                throw new SystemException("Incorrect cost");
        }

        public static void bbHardBetterThanGreedy()
        {
            Problem cityData = new Problem(1, 8, 60, HardMode.Modes.Hard);
            BranchAndBoundSolver solver = new BranchAndBoundSolver(cityData);
            cityData = solver.solve();
            if (cityData.bssf.costOfRoute != 3015)
                throw new SystemException("Incorrect cost");
        }
    }
}
<file_sep>﻿using System.Diagnostics;

namespace TSP
{
    /////////////////////////////////////////////////////////////////////////////////////////////
    // Project 6
    ////////////////////////////////////////////////////////////////////////////////////////////

    /*
     * Implement the greedy solver in the solve() method of this class.
     */
    static class GreedySolver
    {
        // finds the greedy tour starting from each city and keeps the best (valid) one
        // For an example of what to return, see DefaultSolver.solve() method.
        public static Problem solve(Problem cityData)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();

            State state = new State(cityData.size);
            SolverHelper.initializeState(state, cityData);
            state.currCityIndex = 0;
            recur(state);

            timer.Stop();

            // Since cityData is static, it is pointing to the cityData object
            // that was passed in. Setting it's BSSF here will set the BSSF 
            // of the cityData object in the Form1 class.
            cityData.bssf = new TSPSolution(cityData.cities, state.cityOrder, state.lowerBound);
            cityData.timeElasped = timer.Elapsed;
            cityData.solutions = 1;

            return cityData;
        }

        // Returns the index of the last city to be visited in the cycle
        private static void recur(State state)
        {
            //state.printState();
            int currCityIndex = state.currCityIndex;
            // All cities have been visited; finish and return
            if(state.getCitiesVisited() == state.size - 1)
            {
                // The current path cannot be completed bc there is no path from the last city to the first
                if (state.matrix[currCityIndex, state.cityOfOriginIndex] == double.PositiveInfinity)
                {
                    state.lowerBound = double.PositiveInfinity;   
                }
                else
                {
                    state.addCity(currCityIndex);
                    state.lowerBound += state.matrix[currCityIndex, state.cityOfOriginIndex];
                    return;
                }
            }

            state.addCity(currCityIndex);
            
            // find the smallest distance to any other city
            double closestCityDistance = double.PositiveInfinity;
            int closestCityIndex = -1;
            for (int j = 1; j < state.matrix.GetLength(1); j++)
                // For a different starting city, the following code
                // would have to be added:
                //for (int j = 0; j < state.matrix.GetLength(1); j++)
                //if (j == state.startCityIndex)
                //    continue;
                if (state.matrix[currCityIndex, j] < closestCityDistance)
                {
                    closestCityIndex = j;
                    closestCityDistance = state.matrix[currCityIndex, j];
                }

            // add [i,j]
            state.lowerBound += closestCityDistance;

            // Blank out appropriate spaces
            SolverHelper.blankOut(state, closestCityIndex);

            // reduce
            SolverHelper.reduce(state);

            state.currCityIndex = closestCityIndex;
            recur(state);
        }
    }
}
<file_sep>﻿using System;
using Newtonsoft.Json;

namespace TSP
{
    static class SolverHelper
    {
        public const double SPACE_PLACEHOLDER = double.PositiveInfinity;

        // Example: https://gist.github.com/TangChr/4711193c87f40c9fb18d
        public static T clone<T>(T source)
        {
            var json = JsonConvert.SerializeObject(source);
            return JsonConvert.DeserializeObject<T>(json);
        }

        // Populate the state matrix with distances between cities
        public static void initializeState(State state, Problem cityData)
        {
            for (int i = 0; i < cityData.size; i++)
            {
                City city = cityData.cities[i];
                for (int j = 0; j < cityData.size; j++)
                {
                    if (i == j)
                        state.matrix[i, j] = SPACE_PLACEHOLDER;
                    else
                        state.matrix[i, j] = city.costToGetTo(cityData.cities[j]);
                }
            }

            reduce(state);
        }

        // Blank out row and column
        public static void blankOut(State state, int otherCityIndex)
        {
            // row i
            for (int j = 0; j < state.matrix.GetLength(1); j++)
                state.matrix[state.currCityIndex, j] = SolverHelper.SPACE_PLACEHOLDER;

            // column j
            for (int i = 0; i < state.matrix.GetLength(0); i++)
                state.matrix[i, otherCityIndex] = SolverHelper.SPACE_PLACEHOLDER;

            // [j,i]
            state.matrix[otherCityIndex, state.currCityIndex] = SolverHelper.SPACE_PLACEHOLDER;
        }
        
        // Makes sure that there is a 0 in every row and column
        public static void reduce(State state)
        {
            // Reduce the rows
            for (int i = 0; i < state.matrix.GetLength(0); i++)
            {
                // Find the smallest value in the row
                double minInRow = double.PositiveInfinity;
                for (int j = 0; j < state.matrix.GetLength(1); j++)
                    minInRow = Math.Min(minInRow, state.matrix[i, j]);

                // If the smallest value in the row is 0,
                // then there already is a 0 in the row
                // We don't need to add a 0 into the row
                //
                // If the smallest value in the row is infinity,
                // then we have a row of infinities
                // Nothing happens
                if (minInRow != 0 && minInRow != SPACE_PLACEHOLDER)
                {
                    // Add the smallest value in the row to the lower bound
                    state.lowerBound += minInRow;

                    // Subtract that value from all the values in the row
                    // The [i,j] that contained the smallest value will be
                    // set to 0, bc minInRow - minInRow = 0;
                    // If the value at [i,j] is the placeholder, nothing happens
                    for (int j = 0; j < state.matrix.GetLength(1); j++)
                        if (state.matrix[i, j] != SPACE_PLACEHOLDER)
                            state.matrix[i, j] -= minInRow;
                }

            }

            // Reduce the columns
            for (int j = 0; j < state.matrix.GetLength(1); j++)
            {
                // Find the smallest value in the column
                double minInColumn = double.PositiveInfinity;
                for (int i = 0; i < state.matrix.GetLength(0); i++)
                    minInColumn = Math.Min(minInColumn, state.matrix[i, j]);

                // Same as above, except switching rows for columns
                if (minInColumn != 0 && minInColumn != SPACE_PLACEHOLDER)
                {
                    // Add the smallest value in the column to the lower bound
                    state.lowerBound += minInColumn;

                    // Subtract that value from all the values in the column
                    for (int i = 0; i < state.matrix.GetLength(0); i++)
                        if (state.matrix[i, j] != SPACE_PLACEHOLDER)
                            state.matrix[i, j] -= minInColumn;
                }
            }
        }
    }
}
<file_sep>﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace TSP
{
    class DefaultSolver : Solver
    {
        // This is the entry point for the default solver
        // which just finds a valid random tour 
        // <returns>The random valid tour</returns>
        public Problem solve(Problem cityData)
        {
            int i, swap, temp = 0;
            City[] cities = cityData.cities;
            string[] results = new string[3];
            int[] perm = new int[cities.Length];
            List<City> route = new List<City>();
            Random rnd = new Random();
            Stopwatch timer = new Stopwatch();

            timer.Start();
            do
            {
                for (i = 0; i < perm.Length; i++)                                 // create a random permutation template
                    perm[i] = i;
                for (i = 0; i < perm.Length; i++)
                {
                    swap = i;
                    while (swap == i)
                        swap = rnd.Next(0, cities.Length);
                    temp = perm[i];
                    perm[i] = perm[swap];
                    perm[swap] = temp;
                }
                route.Clear();
                for (i = 0; i < cities.Length; i++)                            // Now build the route using the random permutation 
                {
                    route.Add(cities[perm[i]]);
                }
                cityData.bssf = new TSPSolution(route);
            } while (cityData.costOfBssf() == double.PositiveInfinity);                // until a valid route is found
            timer.Stop();

            cityData.bssf.costOfRoute = cityData.costOfBssf();
            cityData.timeElasped = timer.Elapsed;
            cityData.solutions = 1;

            return cityData;
        }
    }
}
<file_sep>﻿using System;
using System.Collections.Generic;

namespace TSP
{
    class State
    {
        public int size;
        public int cityOfOriginIndex;
        public int currCityIndex;
        public double[,] matrix;
        public double lowerBound;
        public List<int> cityOrder;


        public State(int size)
        {
            this.size = size;
            this.cityOfOriginIndex = 0;
            this.currCityIndex = 0;
            this.matrix = new double[size, size];
            this.lowerBound = 0;
            this.cityOrder = new List<int>(size+1);
        }

        public void addCity(int cityIndex)
        {
            this.cityOrder.Add(cityIndex);
        }

        public int getCitiesVisited()
        {
            return this.cityOrder.Count;
        }

        public void printState()
        {
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    if (matrix[i, j] == 0)
                        Console.Write("00000");
                    else if (matrix[i, j] == double.PositiveInfinity)
                        Console.Write("infin");
                    else if (matrix[i, j] < 10)
                    {
                        Console.Write("0000");
                        Console.Write(matrix[i, j]);
                    }
                    else if (matrix[i, j] < 100)
                    {
                        Console.Write("000");
                        Console.Write(matrix[i, j]);
                    }
                    else if (matrix[i, j] < 1000)
                    {
                        Console.Write("00");
                        Console.Write(matrix[i, j]);
                    }
                    else if (matrix[i, j] < 10000)
                    {
                        Console.Write("0");
                        Console.Write(matrix[i, j]);
                    }
                    else
                        Console.Write(matrix[i, j]);

                    Console.Write(',');
                }
                Console.Write("\n");
            }
            Console.Write("\n\n");
        }
    }
}
<file_sep>﻿using System;
using System.Collections.Generic;

namespace TSP
{
    class TSPSolution
    {
        // we use the representation [cityB,cityA,cityC] 
        // to mean that cityB is the first city in the solution, cityA is the second, cityC is the third 
        // and the edge from cityC to cityB is the final edge in the path.  
        // You are, of course, free to use a different representation if it would be more convenient or efficient 
        // for your data structure(s) and search algorithm. 
        public List<City> route;
        public double costOfRoute;

        public TSPSolution(City[] cities, List<int> cityOrder, double costOfRoute)
        {
            // From the list of city indexes, create the list of cities
            route = new List<City>(cityOrder.Count);
            foreach (int i in cityOrder)
            {
                City temp = SolverHelper.clone(cities[i]);
                route.Add(temp);
            }
            this.costOfRoute = costOfRoute;
        }
        
        // <param name="iroute">a (hopefully) valid tour</param>
        public TSPSolution(List<City> iroute)
        {
            route = new List<City>(iroute);
        }
    }
}
<file_sep>﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace TSP
{
    /////////////////////////////////////////////////////////////////////////////////////////////
    // Project 5
    ////////////////////////////////////////////////////////////////////////////////////////////

    /*
     * Implement your branch and bound solver in the solve() method of this class.
     */
    class BranchAndBoundSolver
    {
        Problem cityData;
        Queue<State> q;

        public BranchAndBoundSolver(Problem cityData)
        {
            this.cityData = cityData;
            q = new Queue<State>();
        }
        
        // finds the best tour possible using the branch and bound method of attack
        // For an example of what to return, see DefaultSolver.solve() method.
        public Problem solve()
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();

            State beginningState = new State(cityData.size);
            SolverHelper.initializeState(beginningState, cityData);
            this.q.Enqueue(beginningState);
            Problem determineBSSFProblem = SolverHelper.clone(cityData);
            this.cityData.bssf = GreedySolver.solve(determineBSSFProblem).bssf;

            while (q.Count > 0)
            {
                recur(q.Dequeue());
                //Clear out any states that have a BSSF less than 
                //that of the current
            }

            timer.Stop();
            cityData.timeElasped = timer.Elapsed;

            return cityData;
        }

        private void recur(State state)
        {
            // This is a leaf
            // All cities have been visited; finish and return
            if (state.getCitiesVisited() == cityData.size - 1)
            {
                // The path to the last city is blocked
                if (state.matrix[state.currCityIndex, state.cityOfOriginIndex]
                    == SolverHelper.SPACE_PLACEHOLDER)
                    return;

                state.addCity(state.currCityIndex);

                // Since we've hit a leaf node, we've found another possible solution
                cityData.solutions++;

                // Add the last hop to the lower bound to get the cost of the complete cycle
                state.lowerBound += state.matrix[state.currCityIndex, state.cityOfOriginIndex];

                // Check to see if this route is smaller than the current BSSF
                // If so, replace the current BSSF
                if (state.lowerBound < cityData.bssf.costOfRoute)
                    cityData.bssf = new TSPSolution(cityData.cities, state.cityOrder, state.lowerBound);

                return;
            }

            state.addCity(state.currCityIndex);

            for (int j = 1; j < state.matrix.GetLength(1); j++)
            {
                //Console.WriteLine(state.currCityIndex + " " + j);
                //state.printState();

                double currDistVal = state.matrix[state.currCityIndex, j];
                if (currDistVal != SolverHelper.SPACE_PLACEHOLDER &&
                    state.lowerBound + currDistVal < cityData.bssf.costOfRoute)
                {
                    State childState = SolverHelper.clone(state);

                    // add [i,j]
                    childState.lowerBound += currDistVal;

                    // Blank out the appropriate values with the placeholder
                    SolverHelper.blankOut(childState, j);
                    //childState.printState();

                    // reduce
                    SolverHelper.reduce(childState);

                    childState.currCityIndex = j;

                    if(childState.lowerBound < cityData.bssf.costOfRoute)
                        q.Enqueue(childState);
                }
            }
        }
    }
}
