时间戳

首页 > 解决方案 > 用递归找到最便宜的路

c# - 用递归找到最便宜的路

问题描述

我需要使用递归找到最便宜的道路。
道路从点 1 开始，需要经过所有其他点（2、3、4、5）并返回到点 1。每个点之间的行程成本在一个二维数组（地图）中。

╔═══════════════════════╗
║    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)              ║
╚═══════════════════════╝

这意味着例如从第 1 点到第 5 点有 2 个“金钱”成本，从第 5 点到第 4 点的成本是 7。每次在地图中切换“方向”。我认为尝试应该等于 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);
}

预期的道路（点顺序）输出应该是 1、5(2)、3(1)、2(4)、4(2)、1(4) 并且成本 = 13
关于for循环的外观有什么建议吗？

标签： c#algorithmrecursion

解决方案

Traveling Saleman Problem是一个已知为NP-hard的优化问题，这意味着它不太可能承认有效的最优算法。话虽如此，可以使用动态编程在指数运行时范围内解决它。这种算法可以在这里找到，或者（在最近的出版物中）在这里。

推荐阅读