#dfs

Junjie

1 天以前 71d499e1ad7d4e2f2886627f7a57e0fadf0bc235

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

@@ -23,13 +23,14 @@

    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<>();

    // Open表用优先队列
    public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
    //Close表用普通的数组
    public ArrayList<NavigateNode> Close = new ArrayList<NavigateNode>();
    //Close表用坐标key集合，O(1)查找
    public Set<String> Close = new HashSet<>();
    //用来存放已经出现过的结点。
    Map<String, Integer> bestGMap = new HashMap<>();

@@ -392,13 +393,13 @@
            }

            //将这个结点加入到Close表中
            Close.add(current_node);
            Close.add(keyOf(current_node));
            //对当前结点进行扩展，得到一个四周结点的数组
            ArrayList<NavigateNode> neighbour_node = extend_current_node(map, current_node);
            //对这个结点遍历，看是否有目标结点出现
            for (NavigateNode node : neighbour_node) {
                // 已在关闭列表中的节点不再处理，避免父链反复改写形成环
                if (Close.contains(node)) {
                if (Close.contains(keyOf(node))) {
                    continue;
                }
                // G + H + E (对启发函数增加去拐点方案calcNodeExtraCost)
@@ -410,7 +411,7 @@
                node.setH(calcNodeCost(node, end));
                node.setF(node.getG() + node.getH());

                String key = node.getX() + "_" + node.getY();
                String key = keyOf(node);
                Integer recordedG = bestGMap.get(key);
                // 仅当找到更小的代价时才更新与入Open，避免等价代价反复入队导致父链抖动
                if (recordedG == null || node.getG() < recordedG) {
@@ -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;