复杂的C# Linq算法

Question

我有一个需要解决的C#问题。我正在创建一个应用程序，可以确定最短路线。有一个港口网络，方法需要计算出最快的路线。

我已经在我的方法中做到了这一点，但似乎我在重复编写代码，可能的路线可能永无止境。是否有人有更好的想法来测试所有可能的旅程，以便我能够计算出最短的路线？

 public int ShortestJourneyTime(string startPort, string endPort)
    {
        int shortJourneyTime = 0;
        var possStartRoutes = RouteData.Where(p => p.Key[0] == startPort);

        if (possStartRoutes.Count() <= 0)
            throw new InvalidOperationException(string.Format("{0} : Start port is invalid", startPort));

        foreach (var p in possStartRoutes)
        {
            int currentJourneyTime = p.Value;

            var possRoutes2 = RouteData.Where(p2 => p2.Key[0] == p.Key[1]);

            foreach (var p2 in possRoutes2)
            {
                if (p2.Key[1] == endPort)
                {
                    currentJourneyTime += p2.Value;
                    if (shortJourneyTime > currentJourneyTime || shortJourneyTime == 0)
                        shortJourneyTime = currentJourneyTime;
                }
                else
                {
                    var possRoutes3 = RouteData.Where(p3 => p3.Key[0] == p2.Key[1]);
                }
            }
        }

        return shortJourneyTime;
    }

端口数据存储如下：

  Dictionary<List<string>, int>  testData = new Dictionary<List<string>, int>();

        List<string> routeOne = new List<string>() { "Buenos Aires", "New York" };
        testData.Add(routeOne, 6);

- user1826413

---

你的问题描述是：“我需要尝试重构它。”你的确切问题是什么？ - CodeCaster

@Scott 这不是“危险边缘”，而是：什么是递归？ - CodeCaster

@CodeCaster 我故意含糊其辞，希望不在评论中回答问题。但是，我认为 OP 想知道如何重写他的代码以实现递归。 - Scott Chamberlain

@user，你正在犯与你问题中相同的错误。"Does not really work"并不真正鼓励他人来帮助你。请解释一下你期望它做什么，它实际上做了什么以及你已经尝试过哪些方法来解决这些差异。请参考[ask]。 - CodeCaster

@user1826413 去读一下重复的问题，并看一下 Dijkstra 算法的例子。 - Paul Zahra

Answer 1

有人建议使用Dijkstra算法。以下是您需要的算法。我保留了您的数据结构Dictionary<List<string>, int>，因此您仍然可以使用它。但是我更改了算法内部的数据结构，并选择了更合适的数据结构，使算法更容易。

思路是获取从起点到终点的所有可能路径。然后将最短路径作为结果。请注意，传递的路径不应重复，这意味着如果我们通过New York，我们不应再次经过它，否则我们会陷入无限循环。

此方法的返回类型为Tuple<List<string>, int>。其中List<string>是按顺序保存港口的最短路径，int是该路径的长度。您可以使用属性Item1和Item2访问它们。

例如，从Buenos Aires到Liverpool的最短路径是这个字符串列表"Buenos Aires"，"Casablanca"，"Liverpool"，长度为8天。

请注意，如果未找到任何内容，则此方法将返回null。如果您想要，可以抛出异常。只需取消注释我注释的throw expetion即可。

此方法中的路径类型为Tuple<string，string，int>。 Item1是起始港口，Item2是终止港口，Item3是这两个港口之间的长度。

public Tuple<List<string>, int> TakeShortestJourney(string startPort, string endPort)
{
    if (startPort == endPort) // just for special case when user puts same start and end port.
    {
        return new Tuple<List<string>, int>(new List<string>(){startPort}, 0);
    }

    // convert from Dictionary<List<string>, int> into List<Tuple<string, string, int>>
    var t = RouteData.Select(x => new Tuple<string, string, int>(x.Key[0], x.Key[1], x.Value));
    var allPaths = new List<Tuple<string, string, int>>(t);

    // This will hold all possible short paths.
    var passedPaths = new List<Tuple<List<string>, int>>();

    // create a recursion method to do the search and fill the passedPaths.
    Action<List<string>, string, int> getPath = null;
    getPath = (list, start, length) =>
    {
        list.Add(start);

        foreach (
            var currentRoad in
                allPaths.Where(x => !list.Contains(x.Item2) && x.Item1 == start).OrderBy(x => x.Item3))
        {
            int newLength = length + currentRoad.Item3; // calculate new length.

            if (currentRoad.Item2 == endPort)
            {
                list.Add(currentRoad.Item2);
                passedPaths.Add(new Tuple<List<string>, int>(list, newLength));
                break;
            }

            if (passedPaths.Any(x => x.Item2 < newLength)) break;

            getPath(new List<string>(list), currentRoad.Item2, newLength);
        }
    };

    // start search with initial empty list and 0 length. start from startPort
    getPath(new List<string>(), startPort, 0);

    // Take the shortest path from passed paths.
    var shortestPath = passedPaths.OrderBy(x=> x.Item2).FirstOrDefault();

    if (shortestPath == null) {
    //    throw new ApplicationException("nothing was found");
    }

    return shortestPath;
}

这是如何使用该方法的示例。

var shortestPath = TakeShortestJourney("Buenos Aires", "Liverpool");

foreach (var p in shortestPath.Item1) // Item1 holds path
{
    Console.WriteLine(p);
}

Console.WriteLine(shortestPath.Item2); // Item2 holds length

关于递归操作：

list.Add(start);

我们为每个调用做这件事，所以我们按顺序构建我们的路径。

allPaths.Where(x => !list.Contains(x.Item2) && x.Item1 == start).OrderBy(x => x.Item3)

这个查询将获取以 start 开头的路径，该路径是前一个路径的结尾 (x.Item1 == start)，但它不会获取已经存在于我们列表中的路径以防止重复 (!list.Contains(x.Item2))。最后，它将按照 Item3 (长度) 进行排序，以便我们首先获取最短的路径 (OrderBy(x => x.Item3))。

if (currentRoad.Item2 == endPort)
{
    list.Add(currentRoad.Item2);
    passedPaths.Add(new Tuple<List<string>, int>(list, newLength));
    break;
}

此操作将检查我们路径的结尾。当Item2（当前路径的结束）等于结束口时，它会发生。最后，我们将最后一个项（Item2）添加到列表中，将列表和最终长度一起保存在passedPaths中。我们打破循环，因为我们知道此路径之后的长度将更长，因为我们已经到达了终点，所以继续其他路径是不必要的。（请记住，我们按Item3对其进行了排序）

if (passedPaths.Any(x => x.Item2 < newLength)) break;

这个部分只是为了进一步优化。意思是，如果存在任何完整路径，并且当前路径的长度大于该路径，则停止构建此路径，因为存在更短的路径。而且由于查询已经排序，下一个项目的长度甚至更长，因此我们只需从此路径返回即可。根据RouteData，这可能会增加或降低性能。您可以安全地删除此部分，而不会影响结果。

getPath(new List<string>(list), currentRoad.Item2, newLength);

这里是这个算法的核心！递归调用。第一个参数是我们正在构建的list，但每次我们都会创建一个新的引用，因此列表在递归时保持不变，我们可以继续在foreach循环中进行。第二个参数currentRoad.Item2是当前路径的结束点，也是下一条路径的起点。最后一个参数newLength，当我们将最终路径保存在Tuple<List<string>, int>中时，我们需要它。

- M.kazem Akhgary

---

谢谢您的解释，非常有帮助！@M.kazemAkhgary - user1826413

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - user1826413

不行。因为这种方法可以防止重复。所以当你经过第一个端口时，它将永远无法再次经过它以完成路径。但是你可以通过删除起始端口来解决这个问题。这样终止端口就不会成为重复项了。@user1826413 - M.kazem Akhgary

请注意，此方法将几乎完成路径，例如“布宜诺斯艾利斯=>卡萨布兰卡=>开普敦”，但不会再次回到“布宜诺斯艾利斯”，因为第一个“布宜诺斯艾利斯”是重复的。 您可以通过将!list.Contains(x.Item2)更改为!list.Skip(1).Contains(x.Item2)来解决这个问题。还要记得删除第一个if (startPort == endPort)...语句，以处理这种特殊情况。 - M.kazem Akhgary

@SOreadytohelp 非常感谢！非常感激。 - user1826413

很高兴能帮到你！ :) @user1826413 - M.kazem Akhgary