各位编程专家、算法工程师们，大家好！
今天，我们聚焦一个既基础又深邃的话题：非确定性图（Non-deterministic Graphs）。在传统的图论中，我们习惯于处理确定性的问题：从A到B的最短路径是固定的，网络流量的路由是可预测的。然而，真实世界，尤其是涉及人类决策的过程，充满了不确定性。人类的选择并非总是理性、最优或可预测的。它们受到情绪、信息不完整、个人偏好、外部环境等多种因素的影响。
那么，我们如何在严谨的图论框架中，引入这种“受控的随机性”，以更准确地模拟和理解人类的决策过程呢？这正是非确定性图的魅力所在。它允许我们构建更具鲁棒性、更贴近现实的模型，从而在人工智能、推荐系统、游戏AI、风险评估等领域展现出巨大的潜力。
确定性图与非确定性图：核心差异
在我们深入探讨非确定性图之前，让我们快速回顾一下确定性图的基本概念，并明确它们与非确定性图的关键区别。
确定性图（Deterministic Graphs）
在确定性图中，图的结构（节点和边）以及边的属性（如权重）是固定的、已知的。从一个节点到另一个节点的路径和成本通常是唯一确定的。
- 节点（Nodes/Vertices）：代表状态、位置或实体。
- 边（Edges）：代表连接、转换或关系。
- 权重（Weights）：通常代表成本、时间、距离或容量，是固定的数值。
经典的算法，如Dijkstra、A*、Floyd-Warshall，都致力于在这样的确定性环境中找到最优解，例如最短路径。
import networkx as nx
# 示例：一个简单的确定性图
deterministic_graph = nx.Graph()
deterministic_graph.add_edge('A', 'B', weight=10)
deterministic_graph.add_edge('A', 'C', weight=3)
deterministic_graph.add_edge('B', 'D', weight=5)
deterministic_graph.add_edge('C', 'D', weight=12)
# 寻找最短路径
try:
path = nx.shortest_path(deterministic_graph, 'A', 'D', weight='weight')
length = nx.shortest_path_length(deterministic_graph, 'A', 'D', weight='weight')
print(f"确定性图中的最短路径从 A 到 D: {path}, 长度: {length}")
except nx.NetworkXNoPath:
print("没有找到路径。")非确定性图（Non-deterministic Graphs）
非确定性图则在图的结构或属性中引入了随机性或概率。这意味着从一个节点到另一个节点的转换，或者转换的成本，不再是单一确定的。可能有多种可能的后续状态，每种状态都有其发生的概率；或者，转换的成本本身就是一个随机变量。
核心差异可以总结如下：
| 特性 | 确定性图 | 非确定性图 |
|---|---|---|
| 边的属性 | 固定数值（如成本、时间） | 概率分布、期望值、或基于事件的概率 |
| 状态转换 | 从一个节点到下一个节点是唯一确定的 | 从一个节点出发，可能有多个后续节点，每个都有发生概率 |
| 决策过程 | 寻找单一最优解 | 寻找期望最优解、风险规避策略，或模拟多种可能的结果 |
| 适用场景 | 物理路径、静态网络路由 | 人类决策、游戏AI、金融市场、不确定环境下的机器人规划 |
非确定性图的目标不再是找到一个“最短”或“最优”的固定路径，而是找到一个“期望最优”的策略，或者评估在不同决策下可能遇到的各种结果的分布。
模拟人类决策中的随机性来源
人类决策之所以难以预测，是因为其背后存在多种随机性来源。在构建非确定性图时，我们需要理解这些来源，并将其映射到图的元素中。
-
主观偏好与情绪（Subjective Preferences & Emotions）
- 人类的偏好并非总是理性且一致的。例如，在选择餐厅时，一个人可能今天想吃中餐，明天想吃西餐，即使两者的客观评价相似。情绪（如饥饿、疲劳）也会影响决策，导致非最优选择。
- 图的映射：可以将边的权重建模为与情绪或偏好相关的随机变量，或者在决策节点引入概率分支，代表不同偏好下的选择倾向。
-
信息不对称与不确定性（Information Asymmetry & Uncertainty）
- 我们很少拥有做出完美决策所需的所有信息。例如，投资决策时，未来的市场走势是不确定的；选择一条路线时，实时的交通状况是未知的。
- 图的映射：通过概率边（例如，某条路畅通的概率为P，拥堵的概率为1-P），或在节点处引入“机会节点”（Chance Nodes），表示外部事件的发生。
-
认知偏差与启发式（Cognitive Biases & Heuristics）
- 人类大脑为了简化复杂问题，常常依赖启发式规则，这可能导致系统性的偏差，而非完全理性的决策。例如，锚定效应、可得性偏误等。
- 图的映射：这可能更复杂，可能需要修改决策节点的选择逻辑，使其倾向于某种“次优”但符合人类行为模式的选项，或者调整相关边的概率分布。
-
外部环境的不可预测性（Unpredictable External Factors）
- 天气变化、突发事件、他人行为等都可能影响决策的后果。这些因素超出了决策者的控制范围。
- 图的映射：通常通过概率边或机会节点来表示这些外部随机事件。例如，成功执行某项任务的概率会受到天气影响。
在图中引入受控的随机性：建模方法
既然我们理解了随机性的来源，接下来就是如何在图结构中具体实现这些非确定性。
1. 概率边（Probabilistic Edges）
最直接的方式是给图的边赋予概率。这意味着从节点A到节点B不再是必然的，而是以一定的概率发生。如果转换失败，可能会停留在原地，或者进入一个“失败”状态，或者尝试另一条边。
场景示例：一个玩家尝试通过一个危险区域。有70%的概率成功通过并到达下一个安全区域，但有30%的概率触发陷阱并回到起点。
class ProbabilisticGraph:
def __init__(self):
self.graph = {} # {node: {neighbor: {'probability': p, 'cost': c}}}
def add_edge(self, u, v, probability, cost):
if u not in self.graph:
self.graph[u] = {}
if v not in self.graph:
self.graph[v] = {} # 确保所有节点都存在
self.graph[u][v] = {'probability': probability, 'cost': cost}
def get_neighbors_with_probabilities(self, u):
return self.graph.get(u, {})
def __str__(self):
s = "Probabilistic Graph:n"
for u in self.graph:
for v, data in self.graph[u].items():
s += f" {u} --({data['probability']:.2f}, cost={data['cost']})--> {v}n"
return s
# 示例构建
pg = ProbabilisticGraph()
pg.add_edge('Start', 'A', 0.8, 5) # 80%概率到A，花费5
pg.add_edge('Start', 'B', 0.2, 10) # 20%概率到B，花费10
pg.add_edge('A', 'End', 0.9, 3) # 从A到End有90%概率成功，花费3
pg.add_edge('A', 'Fail', 0.1, 1) # 从A到End有10%概率失败，花费1，进入Fail状态
pg.add_edge('B', 'End', 0.7, 2)
pg.add_edge('B', 'Fail', 0.3, 1)
print(pg)在这个模型中，我们可以进一步扩展，如果失败，不一定是进入一个固定的’Fail’节点，而是可以指定一个“失败后”的节点，或者尝试另一条路径。
2. 概率节点结果（Probabilistic Node Outcomes / Chance Nodes）
这种方法不是在边上设置概率，而是在节点上设置。当到达某个“决策点”或“事件点”节点时，根据预设的概率分布，系统会自动跳转到多个可能的后续节点之一。这更像是外部事件或随机选择的结果。
场景示例：一个人决定去一家新开的餐厅（节点’NewRestaurant’）。有60%的概率食物很好（节点’GoodMeal’），20%的概率食物一般（节点’OkayMeal’），20%的概率食物很差（节点’BadMeal’）。
class ProbabilisticNodeOutcomeGraph:
def __init__(self):
self.graph = {} # {node: [{outcome_node: 'N1', probability: p1, cost: c1}, ...]}
def add_outcome(self, source_node, outcome_node, probability, cost):
if source_node not in self.graph:
self.graph[source_node] = []
self.graph[source_node].append({'outcome_node': outcome_node, 'probability': probability, 'cost': cost})
# 确保所有涉及的节点都存在，即使它们没有出边
if outcome_node not in self.graph:
self.graph[outcome_node] = []
def get_outcomes(self, node):
return self.graph.get(node, [])
def __str__(self):
s = "Probabilistic Node Outcome Graph:n"
for u in self.graph:
if self.graph[u]: # Only show nodes with outcomes
s += f" From node '{u}':n"
for outcome in self.graph[u]:
s += f" -> {outcome['outcome_node']} (prob={outcome['probability']:.2f}, cost={outcome['cost']})n"
return s
# 示例构建
png = ProbabilisticNodeOutcomeGraph()
png.add_outcome('StartDecision', 'OptionA_Success', 0.6, 5)
png.add_outcome('StartDecision', 'OptionA_Failure', 0.4, 10)
png.add_outcome('OptionA_Success', 'EndState1', 1.0, 2) # 从成功状态到终点1
png.add_outcome('OptionA_Failure', 'EndState2', 1.0, 7) # 从失败状态到终点2
print(png)3. 随机边权重（Stochastic Edge Weights）
在这种模型中，边本身是确定存在的，但其权重（如旅行时间、成本）不再是固定值，而是遵循某种概率分布（如正态分布、均匀分布）。这更真实地反映了许多实际情况，例如通勤时间会因交通状况而波动。
场景示例：从家到公司的通勤，通过高速公路可能平均需要30分钟，但实际时间可能在25到40分钟之间波动，遵循一个正态分布。
import numpy as np
import random
class StochasticWeightGraph:
def __init__(self):
self.graph = {} # {node: {neighbor: {'type': 'normal', 'mean': mu, 'std_dev': sigma}}}
def add_edge(self, u, v, distribution_type, **params):
if u not in self.graph:
self.graph[u] = {}
if v not in self.graph:
self.graph[v] = {}
self.graph[u][v] = {'type': distribution_type, **params}
def sample_weight(self, u, v):
edge_data = self.graph[u][v]
dist_type = edge_data['type']
if dist_type == 'normal':
return np.random.normal(edge_data['mean'], edge_data['std_dev'])
elif dist_type == 'uniform':
return np.random.uniform(edge_data['low'], edge_data['high'])
elif dist_type == 'fixed': # For comparison, a fixed weight
return edge_data['value']
else:
raise ValueError("Unsupported distribution type")
def __str__(self):
s = "Stochastic Weight Graph:n"
for u in self.graph:
for v, data in self.graph[u].items():
s += f" {u} --({data['type']} dist)--> {v} with params {data}n"
return s
# 示例构建
swg = StochasticWeightGraph()
swg.add_edge('Home', 'Highway', 'normal', mean=30, std_dev=5) # 平均30分钟，标准差5分钟
swg.add_edge('Highway', 'Office', 'uniform', low=10, high=20) # 10到20分钟之间均匀分布
swg.add_edge('Home', 'LocalRoad', 'fixed', value=45) # 固定45分钟
print(swg)
# 模拟几次通勤时间
print("n模拟从 Home 经 Highway 到 Office 的通勤时间:")
for _ in range(5):
time_highway = swg.sample_weight('Home', 'Highway')
time_office = swg.sample_weight('Highway', 'Office')
total_time = max(0, time_highway) + max(0, time_office) # 时间不能为负
print(f" 一次模拟总时间: {total_time:.2f} 分钟")4. 概率状态转换（Probabilistic State Transitions）
这是一个更广义的概念，涵盖了前两种情况，并与马尔可夫决策过程（Markov Decision Processes, MDPs）紧密相关。在这种模型中，代理（Agent）在一个状态下执行一个动作（Action），然后根据该动作和环境的随机性，以一定的概率转换到下一个状态。
图的映射：节点代表状态，边代表动作，边的属性除了成本，还包含一个概率分布，描述执行该动作后可能达到的下一个状态及其概率。
适用于非确定性图的图结构
为了更好地组织和分析非确定性图，我们可以借用一些特定的图结构。
-
概率图（Probabilistic Graphs, PGs）：
- 这是最基础的形式，如我们上面讨论的概率边模型。边的存在或属性是概率性的。
- 主要关注边的存在概率或条件概率。
-
决策图（Decision Graphs / Influence Diagrams）：
- 这类图专门用于决策分析。它区分三种类型的节点：
- 决策节点（Decision Nodes）：由决策者控制，表示需要做出的选择。
- 机会节点（Chance Nodes）：表示随机事件的结果，由概率决定。
- 效用节点（Utility Nodes）：表示决策和事件结果带来的最终价值或收益。
- 边表示信息流或因果关系。决策图的目标是找到最大化期望效用的决策序列。
- 这类图专门用于决策分析。它区分三种类型的节点：
-
马尔可夫决策过程（Markov Decision Processes, MDPs）：
- MDPs 提供了一个强大的数学框架来建模序列决策问题，其中结果是部分随机的，并受决策者控制。
- 一个MDP由以下元素组成：
- 状态集（S）：所有可能的环境状态。
- 动作集（A）：在每个状态下可以采取的动作。
- 转移概率函数（P）：
P(s' | s, a)，表示在状态s采取动作a后，转移到状态s'的概率。 - 奖励函数（R）：
R(s, a, s')，表示从状态s采取动作a并转移到状态s'获得的即时奖励。 - 折扣因子（γ）：衡量未来奖励相对于当前奖励的重要性。
- MDPs 的目标是找到一个“策略”（Policy），即一个从状态到动作的映射，使得长期期望奖励最大化。虽然MDP不是传统意义上的“图”，但其状态和动作可以自然地映射为图的节点和边，形成一个状态-动作图。
# 伪代码：MDP的结构表示 class MDP: def __init__(self, states, actions, transition_probs, rewards, discount_factor): self.states = states self.actions = actions self.transition_probs = transition_probs # P[s][a][s_prime] = probability self.rewards = rewards # R[s][a][s_prime] = reward self.discount_factor = discount_factor def get_transition_probability(self, state, action, next_state): return self.transition_probs.get(state, {}).get(action, {}).get(next_state, 0.0) def get_reward(self, state, action, next_state): return self.rewards.get(state, {}).get(action, {}).get(next_state, 0.0) # 简单示例MDP (格子世界) # 状态: (row, col) # 动作: 'up', 'down', 'left', 'right' # 假设有墙壁和目标 states = [(r, c) for r in range(3) for c in range(3)] actions = ['up', 'down', 'left', 'right'] # 转移概率: 假设80%概率成功移动，20%概率随机转向左右各10% # 奖励: 目标格子+10，其他-1 # ... (实际实现会非常复杂，这里只示意结构) -
部分可观察马尔可夫决策过程（Partially Observable Markov Decision Processes, POMDPs）：
- MDP的扩展，适用于代理无法完全知道当前状态的情况。代理只能通过观察（Observation）来推断当前所处的状态。
- 比MDP更复杂，但更贴近人类在信息不完整环境下的决策。
| 图结构 | 随机性来源 | 主要关注点 | 典型应用 |
|---|---|---|---|
| 概率图 (PG) | 边的存在或属性概率 | 连通性、可靠性 | 网络可靠性分析、生物网络 |
| 决策图 | 机会节点、决策节点 | 期望效用最大化 | 商业决策、医疗诊断、风险评估 |
| 马尔可夫决策过程 (MDP) | 状态转换概率 | 长期期望奖励最大化、最优策略 | 机器人路径规划、游戏AI、强化学习 |
| 部分可观察MDP (POMDP) | 状态转换概率、观察模型 | 不确定状态下的最优策略 | 无人驾驶、人机交互、复杂环境下的规划 |
非确定性图的算法：超越最短路径
传统的图算法在非确定性图中不再适用，我们需要新的方法来处理概率和不确定性。
1. 期望值路径（Expected Value Pathfinding）
目标是找到一条路径，使得沿途的“期望成本”最小，或“期望收益”最大。这里的关键是计算每个决策点或状态的期望值。
算法思想：可以类比Dijkstra或Bellman-Ford算法，但边的权重不再是固定值，而是由其后续状态的概率和成本的加权平均值构成。对于一个节点u，其期望成本E(u)是所有可能的后续节点v的期望成本E(v)与到达v的概率P(u,v)及边u->v的即时成本C(u,v)的加权和。
E(u) = min_action( C(u, action) + SUM_{v in outcomes(u,action)} [ P(v | u, action) * E(v) ] )
这实质上是MDP中的值迭代（Value Iteration）思想，尤其是在有向无环图（DAG）或有限步骤问题中。对于一般图，可能需要迭代收敛。
import math
class ExpectedValueGraph:
def __init__(self):
self.graph = {} # {u: {v: {'probability': p, 'cost': c}}}
def add_edge(self, u, v, probability, cost):
if u not in self.graph:
self.graph[u] = {}
if v not in self.graph:
self.graph[v] = {}
self.graph[u][v] = {'probability': probability, 'cost': cost}
def find_expected_min_cost(self, start_node, end_node, max_iterations=100, tolerance=1e-6):
# 初始化所有节点的期望成本为无穷大，终点为0
expected_costs = {node: float('inf') for node in self.graph}
expected_costs[end_node] = 0.0
for iteration in range(max_iterations):
delta = 0
new_expected_costs = expected_costs.copy()
for u in sorted(self.graph.keys(), reverse=True): # 逆拓扑排序有助于收敛，如果图是DAG
if u == end_node:
continue
min_expected_cost_from_u = float('inf')
# 在此处，我们假设从u到v是一个确定性的动作，但v的后果是概率性的
# 对于每个可能的动作/边 u -> v
for v, edge_data in self.graph.get(u, {}).items():
prob = edge_data['probability']
cost = edge_data['cost']
# 假设如果从u到v的转移成功，则产生cost，并进入v状态
# 如果失败（1-prob），则停留在u状态（或者进入一个失败状态，这里简化为停留在u）
# 这是一个简化的MDP模型，其中动作是选择一条边。
# 更复杂的模型会考虑所有可能的后续状态及概率。
# 这里我们计算采取特定动作 (u->v) 的期望成本
# 期望成本 = 当前动作成本 + 成功转移到v的概率 * v的期望成本 + 失败转移的概率 * 失败状态的期望成本
# 简化：假设失败则无法继续，或进入高成本状态。
# 更合理的处理：
# 对于概率边，通常会有一个成功转移的成本和失败转移的成本及目标。
# 这里的prob是转移到v的概率，1-prob可能是停留在u或者转移到另一个失败节点。
# 为了简化，我们假设这条边只有两个结果：成功到v（prob），或者“失败”后成本很高（即不选择这条边）。
# 更符合MDP值迭代的思路：
# 对于节点u，我们考虑所有可能的“动作”
# 假设每个出边就是一个动作，执行这个动作后，有prob的概率到达v，并付出cost
# 如果没有到达v，则可能停留在u，或者有其他后果。
# 这里采取最直接的期望计算：
# E[u] = min_{v} (cost(u,v) + E[v]) -- 这是确定性图
# E[u] = min_{action} (SUM_{s'} P(s'|u, action) * (R(u, action, s') + E[s'])) -- 这是MDP
# 假设这里的edge_data['probability']是到达v的概率，并且1-prob的概率无法到达v，则该路径不可选
# 这需要更复杂的MDP框架，此处我们用一个简化的模型：
# 每个节点u的期望成本是所有出边中，其“期望未来成本”最低的那个。
# 期望未来成本 = 当前边成本 + (成功概率 * 目标节点的期望成本)
# 这种简化仅适用于特定问题，例如，成功率低的边会被惩罚。
# 让我们修正为更标准的Bellman方程形式：
# 对于每个可能的动作（即选择一个出边 u -> v）
action_expected_cost = cost + prob * expected_costs[v] + (1 - prob) * expected_costs[u] # 失败则停留在u
min_expected_cost_from_u = min(min_expected_cost_from_u, action_expected_cost)
if min_expected_cost_from_u != float('inf'):
new_expected_costs[u] = min_expected_cost_from_u
# 检查收敛
for node in self.graph:
delta = max(delta, abs(new_expected_costs[node] - expected_costs[node]))
expected_costs = new_expected_costs
if delta < tolerance:
print(f"收敛于迭代 {iteration+1} 次。")
break
return expected_costs[start_node]
# 示例：
evg = ExpectedValueGraph()
evg.add_edge('A', 'B', 0.9, 1) # 90%到B，成本1
evg.add_edge('A', 'C', 0.8, 2) # 80%到C，成本2
evg.add_edge('B', 'D', 1.0, 3) # 100%到D，成本3
evg.add_edge('C', 'D', 0.7, 1) # 70%到D，成本1
evg.add_edge('C', 'E', 0.3, 5) # 30%到E，成本5
evg.add_edge('D', 'End', 1.0, 0) # 终点成本为0
evg.add_edge('E', 'End', 1.0, 0) # 终点成本为0
# 在这个简化的模型中，如果概率边失败，我们假设它停留在当前节点。
# 实际MDP中，转移函数 P(s'|s,a) 会覆盖所有可能的 s'。
# 这里的实现更像是在寻找一个期望成本最低的路径，其中失败的代价是停留在当前节点。
# 这是一个简化的值迭代，更准确的MDP值迭代会考虑所有动作和其导致的所有可能状态。
# 为了使得这个例子有意义，我们假设如果概率边失败，成本会大幅增加或无法到达目标。
# 我们可以重新定义期望成本的计算：
# E[u] = min_{v} ( cost(u,v) + P(u->v_success) * E[v] + P(u->v_fail) * E[fail_state] )
# 假设fail_state为无穷大，则 P(u->v_fail) * E[fail_state] 这一项会使得期望成本大幅增加。
# 或者，对于一个动作，如果它有多个结果，例如：
# 动作a从u出发: 0.7概率到v1(cost1), 0.3概率到v2(cost2)
# E[u] = min_{action_a} (0.7 * (cost1 + E[v1]) + 0.3 * (cost2 + E[v2]))
# 让我们使用一个更标准的MDP值迭代函数：
def value_iteration_mdp(graph_data, start_node, end_node, gamma=0.9, max_iterations=100, tolerance=1e-6):
# graph_data: {u: {action_label: [{target_node: v, probability: p, reward: r}, ...]}}
# 这里我们把cost视为负的reward，所以目标是最大化期望值。
# 转换为最小化期望成本，则reward取负。
# 初始化所有状态的值函数 V(s) = 0
V = {node: 0.0 for node in graph_data}
V[end_node] = 0.0 # 终点状态的价值为0
for i in range(max_iterations):
delta = 0
V_prime = V.copy()
for s in graph_data:
if s == end_node:
continue
max_q_value = -float('inf') # 寻找最佳动作的Q值
if s not in graph_data: # 如果节点没有出边，则其价值为0
V_prime[s] = 0.0
continue
for action_label, outcomes in graph_data[s].items():
q_value_for_action = 0.0
for outcome in outcomes:
v_prime = outcome['target_node']
prob = outcome['probability']
reward = outcome['reward'] # 即时奖励
q_value_for_action += prob * (reward + gamma * V[v_prime])
max_q_value = max(max_q_value, q_value_for_action)
# 更新状态s的价值
if max_q_value != -float('inf'):
V_prime[s] = max_q_value
else: # 如果没有有效动作，价值保持不变或设为0
V_prime[s] = V[s] # Or 0.0 if it's a terminal state without explicit reward
delta = max(delta, abs(V_prime[s] - V[s]))
V = V_prime
if delta < tolerance:
print(f"值迭代收敛于 {i+1} 步。")
break
return V[start_node]
# 定义一个MDP风格的图数据
mdp_graph_data = {
'A': {
'Action1_to_B': [{'target_node': 'B', 'probability': 0.9, 'reward': -1}, # 成功到B，成本1
{'target_node': 'A', 'probability': 0.1, 'reward': -5}], # 失败停留在A，成本5
'Action2_to_C': [{'target_node': 'C', 'probability': 0.8, 'reward': -2}, # 成功到C，成本2
{'target_node': 'A', 'probability': 0.2, 'reward': -6}] # 失败停留在A，成本6
},
'B': {
'Action3_to_D': [{'target_node': 'D', 'probability': 1.0, 'reward': -3}]
},
'C': {
'Action4_to_D': [{'target_node': 'D', 'probability': 0.7, 'reward': -1},
{'target_node': 'E', 'probability': 0.3, 'reward': -5}]
},
'D': {
'Action5_to_End': [{'target_node': 'End', 'probability': 1.0, 'reward': 0}]
},
'E': {
'Action6_to_End': [{'target_node': 'End', 'probability': 1.0, 'reward': 0}]
},
'End': {} # 终点没有出边
}
expected_value_A = value_iteration_mdp(mdp_graph_data, 'A', 'End', gamma=0.95)
print(f"n从A到End的期望最大奖励 (最小化成本): {expected_value_A:.2f}")
# 注意：gamma折扣因子在这里很重要。如果gamma=1，且存在环，则可能不收敛或得到无穷大/小。
# 成本是负奖励，所以我们找的是最大奖励。
2. 蒙特卡洛模拟（Monte Carlo Simulation）
当图的结构非常复杂，或者需要考虑长期、多步骤的随机性时，解析解可能难以获得。蒙特卡洛模拟提供了一种通过大量随机抽样来估计期望值或结果分布的通用方法。
算法思想：
- 从起点开始。
- 在每个节点，根据边的概率分布或节点结果的概率分布，随机选择一个后续节点。
- 重复步骤2，直到到达目标节点或达到最大路径长度。
- 记录当前模拟路径的成本/收益。
- 重复以上过程数千到数百万次。
- 对所有模拟路径的结果进行统计分析（如计算平均值、标准差、分布）。
import random
class MonteCarloGraph:
def __init__(self):
self.graph = {} # {u: {v: {'probability': p, 'cost': c}}}
def add_edge(self, u, v, probability, cost):
if u not in self.graph:
self.graph[u] = {}
if v not in self.graph:
self.graph[v] = {}
self.graph[u][v] = {'probability': probability, 'cost': cost}
def simulate_path(self, start_node, end_node, max_steps=100):
current_node = start_node
total_cost = 0
path = [start_node]
for _ in range(max_steps):
if current_node == end_node:
break
possible_transitions = self.graph.get(current_node, {})
if not possible_transitions: # 死胡同
# print(f"Warning: Node {current_node} is a dead end before reaching {end_node}.")
return float('inf'), path # 返回无穷大成本
# 构建概率分布用于随机选择
outcomes = []
probabilities = []
for neighbor, data in possible_transitions.items():
outcomes.append((neighbor, data['cost']))
probabilities.append(data['probability'])
# 确保概率和为1，如果不是，需要归一化或者处理失败情况
if abs(sum(probabilities) - 1.0) > 1e-6:
# print(f"Warning: Probabilities from {current_node} do not sum to 1.0. Normalizing.")
total_prob = sum(probabilities)
probabilities = [p / total_prob for p in probabilities]
if not outcomes: # 没有有效的出边
return float('inf'), path
# 随机选择下一个节点
chosen_idx = random.choices(range(len(outcomes)), weights=probabilities, k=1)[0]
next_node, edge_cost = outcomes[chosen_idx]
total_cost += edge_cost
path.append(next_node)
current_node = next_node
else:
if current_node != end_node: # 达到最大步数仍未到达终点
# print(f"Warning: Max steps reached. Path did not reach {end_node}.")
return float('inf'), path
return total_cost, path
def run_monte_carlo_simulations(self, start_node, end_node, num_simulations=1000, max_steps_per_sim=100):
costs = []
for _ in range(num_simulations):
cost, _ = self.simulate_path(start_node, end_node, max_steps_per_sim)
if cost != float('inf'):
costs.append(cost)
if not costs:
return {"mean_cost": float('inf'), "std_dev_cost": float('nan'), "min_cost": float('inf'), "max_cost": float('inf'), "num_successful_sims": 0}
mean_cost = np.mean(costs)
std_dev_cost = np.std(costs)
min_cost = np.min(costs)
max_cost = np.max(costs)
return {
"mean_cost": mean_cost,
"std_dev_cost": std_dev_cost,
"min_cost": min_cost,
"max_cost": max_cost,
"num_successful_sims": len(costs)
}
# 示例：
mcg = MonteCarloGraph()
mcg.add_edge('Start', 'A', 0.8, 5)
mcg.add_edge('Start', 'B', 0.2, 10)
mcg.add_edge('A', 'C', 0.7, 3)
mcg.add_edge('A', 'D', 0.3, 8)
mcg.add_edge('B', 'C', 0.6, 2)
mcg.add_edge('B', 'D', 0.4, 7)
mcg.add_edge('C', 'End', 1.0, 1)
mcg.add_edge('D', 'End', 1.0, 4)
sim_results = mcg.run_monte_carlo_simulations('Start', 'End', num_simulations=10000)
print("n蒙特卡洛模拟结果:")
print(f" 成功模拟路径数: {sim_results['num_successful_sims']}")
print(f" 平均成本: {sim_results['mean_cost']:.2f}")
print(f" 成本标准差: {sim_results['std_dev_cost']:.2f}")
print(f" 最小成本: {sim_results['min_cost']:.2f}")
print(f" 最大成本: {sim_results['max_cost']:.2f}")蒙特卡洛模拟的优点是直观且易于实现，适用于各种复杂的概率分布。缺点是计算成本高，需要大量的模拟才能获得准确的估计，并且无法直接给出“最优策略”。
3. 风险规避/风险偏好路径寻找（Risk-Averse/Risk-Seeking Pathfinding）
在人类决策中，期望值并非唯一考量。有些人偏好风险规避，即使期望收益略低，也倾向于选择结果更稳定的选项；而有些人则偏好风险，愿意为了小概率的高回报而承担更大的不确定性。
算法思想：
- 风险规避：除了期望成本/收益，还考虑结果的方差或标准差。目标可能是最小化期望成本的同时，最小化成本的方差。或者，寻找一个在某个置信水平下，成本不超过某个阈值的路径。例如，使用条件风险值（CVaR）或在最坏情况下的表现（Minimax）。
- 风险偏好：可能通过最大化高回报事件的概率，即使其期望值不高。
这通常需要结合蒙特卡洛模拟（来生成结果分布）和优化技术（来选择满足风险偏好的路径）。
# 概念性代码：如何将风险纳入考量
def find_risk_averse_path(mc_results, risk_tolerance_threshold=0.95):
"""
假设mc_results包含多条路径的成本分布。
这里简化为从蒙特卡洛模拟得到的成本列表。
目标是找到一个路径，使得其成本的某个百分位数（如95%）低于某个阈值，
或者选择平均成本较低且标准差较小的路径。
"""
costs = mc_results['costs'] # 假设这里是一个成本列表
if not costs:
return None
# 计算成本的某个百分位数，例如95%置信区间的上限
# 越低表示风险越小 (在95%的情况下，成本不会超过这个值)
percentile_cost = np.percentile(costs, risk_tolerance_threshold * 100)
print(f"n风险规避分析 (基于 {risk_tolerance_threshold*100}% 置信度):")
print(f" 在 {risk_tolerance_threshold*100}% 的情况下，成本不会超过: {percentile_cost:.2f}")
# 实际应用中，你需要比较不同“策略”（即不同的决策序列）的这些统计量
# 进而选择一个最符合风险偏好的策略。
# 这里的MC模拟只模拟了一条单一的“路径”的随机性，
# 而不是多个“策略”的对比。
# 对于多个策略的对比，需要为每个策略运行MC模拟，然后比较它们的统计特性。
# 假设mcg对象和之前的模拟结果
# path_costs_for_strategy_1 = mcg.run_monte_carlo_simulations('Start', 'End', num_simulations=10000)['costs']
# path_costs_for_strategy_2 = # ... 假设有另一个策略的成本
# find_risk_averse_path({"costs": path_costs_for_strategy_1})实际应用与挑战
非确定性图在多个领域都有着广泛的应用：
- 游戏AI：NPC（非玩家角色）的行为决策，使其更具“人性化”和不可预测性。例如，一个敌人AI在攻击时，有一定概率会选择更冒险但可能更高收益的策略。
- 推荐系统：模拟用户在多种推荐下的选择倾向，考虑用户情绪、上下文和偏好的不确定性，提供更个性化和动态的推荐。
- 金融建模：股票市场波动、投资组合风险评估。通过随机边权重（股价波动）和概率节点（经济事件发生），评估不同投资策略的期望收益和风险。
- 自动驾驶与机器人导航：在复杂、不确定环境下（如交通、天气、行人行为）进行路径规划和决策。例如，一个车道变更有90%的成功概率，10%的概率会遇到障碍物。
- 医疗决策：疾病诊断和治疗方案选择。不同的治疗方法有不同的成功率和副作用概率，需要评估期望的健康结果。
实现细节与挑战：
- 数据结构：需要扩展传统的邻接列表或邻接矩阵，以存储概率、分布参数或多个可能的后续状态。
- 计算复杂度：
- 期望值路径算法（值迭代）在状态空间大时可能计算量巨大。
- 蒙特卡洛模拟需要大量的重复，尤其是在需要高精度时。
- 处理随机边权重需要反复采样，增加了每次边遍历的开销。
- 参数估计：如何准确地获取概率值和分布参数是一个核心挑战。这通常需要：
- 历史数据分析：从过去的行为或事件中学习概率。
- 专家知识：领域专家根据经验提供概率估计。
- 机器学习/强化学习：通过与环境互动，自动学习最优策略和环境动态。
- 可伸缩性：对于大规模图，如何高效地存储、遍历和计算非确定性属性是一个难题。
- 可解释性：当算法推荐一个非直观的“期望最优”策略时，如何向人类解释其背后的随机性考量，以建立信任。
展望未来
非确定性图是连接理论图论与现实世界复杂性的桥梁。随着人工智能和机器学习技术的发展，尤其是强化学习（Reinforcement Learning），我们有能力在高度不确定的环境中学习和优化决策策略。强化学习本质上就是在解决MDP或POMDP问题，通过试错来发现最优的行为策略。结合贝叶斯网络等概率图模型，我们还可以更精细地建模随机变量之间的依赖关系。
未来的研究将继续致力于开发更高效、更鲁棒的算法，以应对更大规模、更复杂的非确定性图，并更好地融合人类的认知偏好和风险态度，使我们的AI系统能够做出更“像人”的决策。
非确定性图为我们提供了一个强大的工具集，用以模拟和理解那些充满随机性、高度动态的真实世界决策过程。通过引入受控的随机性，我们不仅能更准确地预测系统行为，更能设计出更智能、更适应不确定性的AI系统。这对于构建真正能够与人类世界互动、理解人类意图的智能体至关重要。