Finding cheapest road with recursion

Question

I need to find the cheapest road using recursion.
The road starts at point 1 and it needs to go through all the other points(2,3,4,5) and come back to point the 1. The trip cost between each point is in a double dimension array(map).

╔═══════════════════════╗
║    1|2|3|4|5|(points) ║
║ 1--0 1 3 4 2          ║
║ 2--1 0 4 2 6          ║
║ 3--3 4 0 7 1          ║
║ 4--4 2 7 0 7          ║
║ 5--2 6 1 7 0          ║
║ (points)              ║
╚═══════════════════════╝

This means that for example from point 1 to point 5 there is 2"money" cost, from point 5 to point 4 cost is 7. Every time you switch "direction" in the map. I think attempts should be equal to 25(4! + 1)

void FindingRoad(int[][] map, int[] pointsOrder, ref int tripCost, ref int attempts)
{

    if (attempts == 0)
    {
        return;
    }
    int tempCost = 0;
    int[] tempPointsOrder = new int[5];
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {

        }
    }
    if (tempCost<tripCost)
    {
        tripCost = tempCost;
        pointsOrder = tempPointsOrder;
    }
    attempts--;
    FindingRoad(map,pointsOrder,ref tripCost,attempts);
}

Expected road(points order) output should be 1, 5(2), 3(1), 2(4), 4(2), 1(4) and is cost = 13
Any suggestions on how for loop could look like?

Answer 1

The Travelling Saleman Problem is an optimization problem which is known to be NP-hard, which means that it is unlikely to admit an efficient optimal algorithm. That being said, it it possible to solve it within an exponential runtime bound using Dynamic Programming. Such an algorithm can be found here, or (in a more recent publication) here.