#dfs

Junjie

1 天以前 71d499e1ad7d4e2f2886627f7a57e0fadf0bc235

 src/main/java/com/zy/common/utils/NavigateSolution.java

@@ -23,6 +23,7 @@

    private static final long REDIS_MAP_CACHE_TTL_SECONDS = 60 * 60 * 24L;
    private static final long MAP_CACHE_TTL_MS = 5000L;
    private static final long SIMPLE_PATH_SEARCH_TIMEOUT_MS = 3000L;
    private static final Map<String, CachedNavigateMap> NAVIGATE_MAP_CACHE = new ConcurrentHashMap<>();
    private static final Map<String, CachedNavigateMapIndex> NAVIGATE_MAP_INDEX_CACHE = new ConcurrentHashMap<>();

@@ -459,6 +460,14 @@

        AtomicInteger pathCount = new AtomicInteger(0);
        Map<Integer, NavigateNode> guideNodeMap = buildGuideNodeMap(map, guideStationIds);
        SimplePathSearchContext searchContext = new SimplePathSearchContext(
                start,
                end,
                maxDepth,
                maxPaths,
                maxCost,
                System.currentTimeMillis() + SIMPLE_PATH_SEARCH_TIMEOUT_MS
        );

        dfsAllSimplePaths(map, start, end,
                visited, path, results,
@@ -467,7 +476,8 @@
                maxDepth, maxPaths, maxCost,
                pathCount,
                guideStationIds,
                guideNodeMap
                guideNodeMap,
                searchContext
        );

        return results;
@@ -490,8 +500,13 @@
            int maxCost,
            AtomicInteger pathCount,
            List<Integer> guideStationIds,
            Map<Integer, NavigateNode> guideNodeMap
            Map<Integer, NavigateNode> guideNodeMap,
            SimplePathSearchContext searchContext
    ) {
        if (isSimplePathSearchTimedOut(searchContext, results, pathCount, depth)) {
            return;
        }

        // 防爆：条数限制
        if (maxPaths > 0 && pathCount.get() >= maxPaths) return;

@@ -511,6 +526,10 @@
        neighbors = sortNeighborsByGuide(current, path, neighbors, guideStationIds, guideNodeMap);

        for (NavigateNode next : neighbors) {
            if (isSimplePathSearchTimedOut(searchContext, results, pathCount, depth)) {
                return;
            }

            // 防爆：条数限制
            if (maxPaths > 0 && pathCount.get() >= maxPaths) return;

@@ -540,13 +559,41 @@
                    maxDepth, maxPaths, maxCost,
                    pathCount,
                    guideStationIds,
                    guideNodeMap
                    guideNodeMap,
                    searchContext
            );

            // 回溯
            path.removeLast();
            visited.remove(nk);
        }
    }

    private boolean isSimplePathSearchTimedOut(SimplePathSearchContext searchContext,
                                               List<List<NavigateNode>> results,
                                               AtomicInteger pathCount,
                                               int depth) {
        if (searchContext == null || searchContext.timeoutLogged) {
            return searchContext != null && searchContext.timeoutLogged;
        }
        if (System.currentTimeMillis() < searchContext.deadlineMs) {
            return false;
        }

        searchContext.timeoutLogged = true;
        Integer startStationId = extractStationId(searchContext.startNode);
        Integer endStationId = extractStationId(searchContext.endNode);
        com.zy.core.News.warn("站点路径候选枚举超时返回，startStationId={}，endStationId={}，timeoutMs={}，foundPathCount={}，resultSize={}，depth={}，maxDepth={}，maxPaths={}，maxCost={}",
                startStationId,
                endStationId,
                SIMPLE_PATH_SEARCH_TIMEOUT_MS,
                pathCount == null ? 0 : pathCount.get(),
                results == null ? 0 : results.size(),
                depth,
                searchContext.maxDepth,
                searchContext.maxPaths,
                searchContext.maxCost);
        return true;
    }

    private String keyOf(NavigateNode n) {
@@ -1082,6 +1129,30 @@
        }
    }

    private static class SimplePathSearchContext {
        private final NavigateNode startNode;
        private final NavigateNode endNode;
        private final int maxDepth;
        private final int maxPaths;
        private final int maxCost;
        private final long deadlineMs;
        private boolean timeoutLogged;

        private SimplePathSearchContext(NavigateNode startNode,
                                        NavigateNode endNode,
                                        int maxDepth,
                                        int maxPaths,
                                        int maxCost,
                                        long deadlineMs) {
            this.startNode = startNode;
            this.endNode = endNode;
            this.maxDepth = maxDepth;
            this.maxPaths = maxPaths;
            this.maxCost = maxCost;
            this.deadlineMs = deadlineMs;
        }
    }

    private static class CachedNavigateMap {
        private final long cacheAtMs;
        private final List<List<NavigateNode>> navigateMap;