C#中深度优先搜索(DFS)求解最优路径无预期结果问题排查

核心问题导致无结果返回 #

1. 最优值初始值设置不合理：原代码将optimalGoodness初始化为0，若所有可能的闭环路线总goodness均≤0，即使存在合法路线，也不会触发结果更新，最终返回空路线。
2. DFS遍历效率极低：2000个城市规模下，每次DFS循环都遍历全部travelData，时间复杂度爆炸，DFS可能因超时或资源占用过大无法完成遍历，自然找不到结果。
3. 无结果兜底缺失：若不存在从起点出发再返回的闭环路线，代码不会返回任何有效路线（甚至连仅包含起点的默认路线都没有）。

修复步骤与代码优化 #

1. 构建邻接表优化遍历效率 #

将travelData转换为按出发城市分组的邻接表，避免每次遍历全量数据，大幅降低时间开销。

2. 调整最优值初始值 #

将optimalGoodness初始化为double.NegativeInfinity，确保任何合法闭环路线的总goodness都能触发结果更新。

3. 补充无结果兜底逻辑 #

若最终未找到任何闭环路线，返回仅包含起点的默认路线（可根据需求调整）。

修改后的完整代码 #

static RouteResult FindOptimalRoute(string startCity, Dictionary<string, double> goodnessRatings, List<TravelData> travelData)
{
    var optimalRoute = new List<string>();
    double optimalGoodness = double.NegativeInfinity;

    // 构建邻接表，按出发城市分组
    var adjacencyList = travelData.GroupBy(t => t.FromCity)
                                  .ToDictionary(g => g.Key, g => g.ToList());

    void DFS(string currentCity, HashSet<string> visited, List<string> route, double currentGoodness)
    {
        // 找到闭环路线时更新最优结果
        if (route.Count > 1 && currentCity == startCity)
        {
            if (currentGoodness > optimalGoodness)
            {
                optimalGoodness = currentGoodness;
                optimalRoute = new List<string>(route);
            }
            return;
        }

        // 仅遍历当前城市的出边
        if (adjacencyList.TryGetValue(currentCity, out var outgoingRoutes))
        {
            foreach (var travel in outgoingRoutes)
            {
                if (!visited.Contains(travel.ToCity))
                {
                    visited.Add(travel.ToCity);
                    route.Add(travel.ToCity);

                    double cityGoodness = goodnessRatings.TryGetValue(travel.ToCity, out double value) ? value : 0;
                    DFS(travel.ToCity, visited, route, currentGoodness + cityGoodness);

                    // 回溯
                    visited.Remove(travel.ToCity);
                    route.RemoveAt(route.Count - 1);
                }
            }
        }
    }

    var initialVisited = new HashSet<string> { startCity };
    var initialRoute = new List<string> { startCity };

    double startCityGoodness = goodnessRatings.TryGetValue(startCity, out double startValue) ? startValue : 0;
    DFS(startCity, initialVisited, initialRoute, startCityGoodness);

    // 兜底：未找到闭环路线时返回仅含起点的路线
    if (optimalRoute.Count == 0)
    {
        return new RouteResult(new List<string> { startCity }, startCityGoodness);
    }

    return new RouteResult(optimalRoute, optimalGoodness);
}

internal class RouteResult
{
    public List<string> Route { get; }
    public double TotalGoodness { get; }

    public RouteResult(List<string> route, double totalGoodness)
    {
        Route = route;
        TotalGoodness = totalGoodness;
    }
}

internal class TravelData
{
    public string FromCity { get; }
    public string ToCity { get; }
    public int Time { get; }

    public TravelData(string fromCity, string toCity, int time)
    {
        FromCity = fromCity;
        ToCity = toCity;
        Time = time;
    }
}

额外建议 #

• 2000个城市规模下，DFS暴力遍历的时间复杂度为O(N!)，完全不可行，建议改用**动态规划（TSP问题解法）**或启发式算法（如遗传算法、模拟退火）处理大规模数据。
• 先使用3-5个城市的小规模数据验证算法逻辑，确认能正确返回闭环路线后再扩展到大规模数据。

内容的提问来源于stack exchange，提问作者NoOne