From 71d499e1ad7d4e2f2886627f7a57e0fadf0bc235 Mon Sep 17 00:00:00 2001
From: Junjie <fallin.jie@qq.com>
Date: 星期三, 06 五月 2026 16:48:11 +0800
Subject: [PATCH] #dfs
---
src/main/java/com/zy/common/utils/NavigateSolution.java | 87 +++++++++++++++++++++++++++++++++++++++----
1 files changed, 79 insertions(+), 8 deletions(-)
diff --git a/src/main/java/com/zy/common/utils/NavigateSolution.java b/src/main/java/com/zy/common/utils/NavigateSolution.java
index 8aaabe1..7845e9b 100644
--- a/src/main/java/com/zy/common/utils/NavigateSolution.java
+++ b/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闆嗗悎锛孫(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);
// 浠呭綋鎵惧埌鏇村皬鐨勪唬浠锋椂鎵嶆洿鏂颁笌鍏pen锛岄伩鍏嶇瓑浠蜂唬浠峰弽澶嶅叆闃熷鑷寸埗閾炬姈鍔�
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={}锛宔ndStationId={}锛宼imeoutMs={}锛宖oundPathCount={}锛宺esultSize={}锛宒epth={}锛宮axDepth={}锛宮axPaths={}锛宮axCost={}",
+ 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;
--
Gitblit v1.9.1