2020 B题国赛优秀论文附带支撑材料，代码由python编写

2744557306

B题 穿越沙漠
考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。
游戏的基本规则如下：
（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。
（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。
( Q3 a* ^2 e# o; f" u5 L6 s8 f（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。
" l$ I' ]1 E+ J% ~. \（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。
（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的 倍。
（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。
（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的 倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
) S) ]" \; R3 [（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。
( \* y( h1 D* a# ~/ T8 D请根据游戏的不同设定，建立数学模型，解决以下问题。
假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。求解附件中的“第一关”和“第二关”，并将相应结果分别填入Result.xlsx。
% b8 F3 P/ p) B) G. X假设只有一名玩家，玩家仅知道当天的天气状况，可据此决定当天的行动方案，试给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。
现有 名玩家，他们有相同的初始资金，且同时从起点出发。若某天其中的任意 名玩家均从区域A行走到区域B( )，则他们中的任一位消耗的资源数量均为基础消耗量的 倍；若某天其中的任意 名玩家在同一矿山挖矿，则他们中的任一位消耗的资源数量均为基础消耗量的 倍，且每名玩家一天可通过挖矿获得的资金是基础收益的 ；若某天其中的任意 名玩家在同一村庄购买资源，每箱价格均为基准价格的 倍。其他情况下消耗资源数量与资源价格与单人游戏相同。
9 c' x: ~: }: b4 l9 e% k（1）假设在整个游戏时段内每天天气状况事先全部已知，每名玩家的行动方案需在第 天确定且此后不能更改。试给出一般情况下玩家应采取的策略，并对附件中的“第五关”进行具体讨论。
' x9 S* s9 V# T（2）假设所有玩家仅知道当天的天气状况，从第 天起，每名玩家在当天行动结束后均知道其余玩家当天的行动方案和剩余的资源数量，随后确定各自第二天的行动方案。试给出一般情况下玩家应采取的策略，并对附件中的“第六关”进行具体讨论。
注1：附件所给地图中，有公共边界的两个区域称为相邻，仅有公共顶点而没有公共边界的两个区域不视作相邻。
注2：Result.xlsx中剩余资金数（剩余水量、剩余食物量）指当日所需资源全部消耗完毕后的资金数（水量、食物量）。若当日还有购买行为，则指完成购买后的资金数（水量、食物量）。

; j3 W, m6 o1 U, W- j9 z5 @

解题思路：

到使用 Q-learning 算法优化固定环境参数的连续动作模型，并将地图数据转换为代表自环的连通图矩阵。然后，要将问题的背包容量、天气因素和生存条件等信息转化为约束条件，并采用精确购买策略。最后，在连通图矩阵中添加时间维度，使用动态 ε-greedy 策略进行探索和更新 Q 矩阵，直到收敛。最后通过完全贪婪策略输出Q矩阵表示的最优动作组合

第一关的最优策略为: [1,25, 24, 23, 23, 22, 9, 9, 15, 15, 15, 15, 13, 12, 12, 12, 12, 12,12,12,12,12, 13, 15, 9, 9, 21, 27] ，并且获得的最大保留资金为 10590 元。第二关的最优策略为: [1,9, 10, 19, 19, 27, 36, 36, 44, 53, 54, 54, 62, 55, 55, 55, 55, 55, 55, 55, 55, 55, 62, 55, 55, 55, 55, 55, 55, 55,55,55, 64] ，并且获得的最大保留资金为 12460 元。
$ Y1 g  U7 K  ~0 i4 b第二题
* T9 ~; }- \, \- Y1 _) X+ @% o问题一的基础上引入了天气变量的随机化，并通过改进的 Q-learning 算法（加入期望学习策略）使其适应随机环境参数。在三维 Q 矩阵中添加了天气变量维度，并使用最优 Q 值的期望值来更新 Q 矩阵。

针对第三关，无论天气的变化，最优路径始终是 [1, 4, 6, 13] 和 [1,5, 6, 13]。

针对第四关，玩家通关的概率和平均收获将随着高温和沙暴概率的增加而呈下降趋势。这意味着在高温和沙暴概率较高的天气条件下，玩家通关的可能性较低，同时平均收获也会减少。

第三题

对于问题三的第五关，要求玩家之间形成完全竞争关系，建立完全信息变和博弈模型。在这个模型中，通过命题证明的基础上求解，玩家可采用的最优策略仅有 [1, 4, 6, 13] 和 [1，5, 6, 13]。当两个玩家选择相同的策略时，每个玩家的保留资金都是 7640 元；当两个玩家选择不同的最优路径时，每个玩家的保留资金都是 8840 元。

这意味着在完全竞争关系下，每个玩家都在追求最优策略，最终导致了博弈结果的稳定。当两个玩家选择相同策略时，他们会达到均衡状态并获得相同的保留资金。而当两个玩家选择不同的最优路径时，尽管保留资金有所不同，但博弈结果仍然是稳定的。

对于问题三的第六关，建立了一个三人合作模型，并基于 Q-learning 算法，并应用谦让策略来选择最优路径。通过仿真结果显示，即使在天气情况较差时，部分玩家也能保持较高的通关率。这表明通过合作和谦让策略，玩家可以更好地应对困难的情况，并实现更好的协同效果。
本文的优点：

1.基于期望学习策略的 Q-learning 算法：该算法适应带有随机变量的环境参数，并使用奖励期望值来更新 Q 矩阵。这意味着算法可以在不确定的环境下进行学习和决策，提高了模型的鲁棒性和适应性。

2.改进的 Q-learning 算法时间复杂度低：相对于一般的群集智能优化算法，改进的 Q-learning 算法具有较低的时间复杂度。这使得算法能够更快速地进行学习和求解，提高了效率。

4 g4 q# a2 v' s* Z$ n# _, h) U2 A

3. 每个 Agent 可自行探索动态学习：在改进的 Q-learning 算法中，每个 Agent 可以根据自身的策略进行探索和学习。这使得算法能够同时兼顾局部搜索和全局搜索的能力，从而更好地发现最优策略。

最后附上该片优秀论文，及支撑材料
2 T0 T. m) ~( `* x
5 ?" x6 h$ i1 ]3 h' A% l
. v8 a8 _7 S5 h( C2 \- w) c7 Q% h$ g
" u7 n# t9 n, b7 O2 b6 }$ l