c# - C＃既知のポイントの適切なリストチェーンを見つける

Question

   var route1 = new List<int> { 1, 2, 3 };
   var route2 = new List<int> { 6, 7, 8 };
   var route3 = new List<int> { 3, 7, 13 };
   var route4 = new List<int> { 8, 9, 10 };

質問はそれです。出発点は 2 で、目標点は 9 です。私の目的は、適切なルート チェーンを見つけることです。この状況では、ルートは [ルート 1 - ルート 3 - ルート 2 - ルート 4] になります。しかし、この問題を解決する方法がわかりません。アルゴリズムが見つかりません。答えは疑似コードまたは C# の実装です。

私のやり方はそれです。ルート 1 の出発点 (2)、ルート 4 の目的地 (9) です。次に、ルート 1 とルート 4 を接続する中間ルートを見つける必要があります。アルゴリズムかテクニックが必要です。

Answer 1

このコードは、任意の 2 点間のルートを見つけます (存在する場合)。ルートは常に最短であるとは限りません (たとえば、3 から 13 まではルート 1 からルート 3 になります)。また、再帰を使用します-これは、(タグに基づいて) 必要なもののようです。vistedRoutes通過したルートが含まれています。

   static void Main(string[] args)
    {
        var route1 = new List<int> { 1, 2, 3 };
        var route2 = new List<int> { 6, 7, 8 };
        var route3 = new List<int> { 3, 7, 13 };
        var route4 = new List<int> { 8, 9, 10 };

        List<List<int>> routeList = new List<List<int>>();
        routeList.Add(route1);
        routeList.Add(route2);
        routeList.Add(route3);
        routeList.Add(route4);

        int start = 3;
        int end = 9;

        var vistedRoutes = new List<List<int>>();

        foreach(var route in routeList.FindAll(r => r.Contains(start)))
        {
            vistedRoutes.Add(route);
            routeList.Remove(route);
            FindPath(vistedRoutes, routeList, start, end);

            if (vistedRoutes.Last().Contains(end))
            {
                break;
            }
        }

        Console.WriteLine("done");
    }

    static void FindPath(List<List<int>> visitedRoutes, List<List<int>> remainingRoutes, int start, int end)
    {
        if (visitedRoutes.Last().Contains(end))
        {
            return;
        }
        for (int i = 0; i < remainingRoutes.Count; i++ )
        {
            var route = remainingRoutes[i];

            foreach (var point in route)
            {
                if (visitedRoutes.Last().Contains(point))
                {
                    visitedRoutes.Add(route);
                    var newRemainingRoutes = new List<List<int>>(remainingRoutes);
                    newRemainingRoutes.Remove(route);
                    FindPath(visitedRoutes, newRemainingRoutes, start, end);
                    if (visitedRoutes.Last().Contains(end))
                    {
                        return;
                    }
                    else
                    {
                        visitedRoutes.Remove(route);
                    }
                }
            }
        }
    }

Answer 2

どうぞ：

        var route1 = new List<int> { 1, 2, 3 };
        var route2 = new List<int> { 6, 7, 8 };
        var route3 = new List<int> { 3, 7, 13 };
        var route4 = new List<int> { 8, 9, 10 };

        List<List<int>> routeList = new List<List<int>>();
        routeList.Add(route1);
        routeList.Add(route2);
        routeList.Add(route3);
        routeList.Add(route4);

        int startPoint = 2;
        int endPoint = 9;


        List<List<int>> finalRouteOrder = new List<List<int>>();

        //  Find starting route.
        List<int> currentRoute = routeList.Find(a => a.Contains(startPoint));

        //  Don't need that route in the list anymore.
        routeList.Remove(currentRoute);

        //  Add it to our final list of routes.
        finalRouteOrder.Add(currentRoute);

        bool done = false;
        while (!done)
        {
            foreach (int x in currentRoute)
            {
                currentRoute = routeList.Find(a => a.Contains(x));
                if (currentRoute != null)
                {
                    finalRouteOrder.Add(currentRoute);  // add this route toi our final list of routes
                    routeList.Remove(currentRoute);  // remove that list since we are done with it.

                    if (currentRoute.Contains(endPoint))
                    {
                        done = true;
                    }
                    break;
                }
                if (done)
                    break;

            }
            if (done)
                break;
        }

        //  finalRouteOrder contains the routes in order.

        MessageBox.Show("Done.");