题目重述
背景
考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。
游戏规则
- 以天为基本时间单位，游戏的开始时间为第 0 天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。
- 穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。
- 每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。
- 每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。
- 玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的 2 倍。
- 玩家第 0 天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。
- 玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的 3 倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
- 玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的 2 倍。
第一问
假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。
题目解析
决策变量
核心决策变量是玩家在第$i$天是否停留在第$j$号区域，类型为0-1变量。
这里的第$i$天停留区域是指玩家在这一天内的全部行动结束后，还未进入第二天前所停留的区域。
符号说明
| 符号名称 | 描述 | 备注 |
|---|---|---|
| $f_{i,j}$ | 玩家第i天是否停留在第j号区域 | 0-1变量,停留在j区域=1,停留在j以外=0 |
| $bw_i$ | 第i天的水基础消耗量 | 整数变量，单位:箱 |
| $bf_i$ | 第i天的食物基础消耗量 | 整数变量，单位:箱 |
| $t_i$ | 第i天的天气 | 整数变是，晴朗=1，高温=2，沙暴=3 |
| $water_i$ | 玩家第i天行动完后剩余水量 | 整数变量，单位:箱 |
| $food_i$ | 玩家第i天行动完后剩余食物量 | 整数变量，单位:箱 |
| $money_i$ | 玩家第i天行动完后剩余资金 | 整数变量，单位:元 |
| $mine_i$ | 玩家第i天是否挖矿 | 0-1 变量，挖矿=1，不挖=0 |
| $walk_i$ | 玩家第i天是否行走 | 0-1 变星，行走=1，不走=0 |
| $wcost_i$ | 玩家第i天需要消耗的水量 | 整数变量，单位:箱 |
| $fcost_i$ | 玩家第i天需要消耗的食物量 | 整数变量，单位:箱 |
| $D_{i,j}$ | 表示区域i与区域j是否相邻 | 0-1变量，相邻=1，不相邻=0 |
| $wbuy_i$ | 玩家第i天行动结束后购买的水量 | 整数变量，单位:箱 |
| $fbuy_i$ | 玩家第i天行动结束后购买的食物量 | 整数变量，单位:箱 |
| $m_i$ | 地图上第i个村庄的地区编号 | 整数变是，由每关地图决定 |
| $n_i$ | 地图上第i个矿山的地区编号 | 整数变是，由每关地图决定 |
| $a$ | 地图上矿山的数量 | 整数变是，由每关地图决定 |
| $mw$ | 每箱水的质量 | 整数常量，单位:千克 |
| $mf$ | 每箱食物的质量 | 整数常量，单位:千克 |
| $M$ | 初始资金数 | 整数常量，单位:元 |
| $cw$ | 每箱水的基准价格 | 整数常量，单位:元/箱 |
| $cf$ | 每箱食物的基准价格 | 整数常量，单位:元/箱 |
| $dl$ | 游戏截止日期 | 整数常量，单位:天 |
| $lm$ | 玩家负重上限 | 整数常量，单位:千克 |
| $ea$ | 挖矿一次基础收益 | 整数常量，单位:元 |
编程求解
动态规划求解
- 用(天数,区域,剩余水量,剩余食物)来表示一个解的状态
- 题目包含多种状态,某一天的最优解状态由前面已求得的状态转换而来
- 有大量的重叠状态,比如(15,15,133,145)这种随机赵太太,可能前一天的相邻区域最优解+今天行走,或者前一天当前区域最优解+今天停留得到,适合用动态规划记录大量重复状态
- 大的分支有
停留和行走,停留情况下可能有挖矿和购买,行走下只可能有购买
缩小时间复杂度
- 剪枝
- 设定村庄逗留时间最短值
- 设置购买水和食物的上限
第二问
思路是使用启发式搜索（A*）。启发式搜索决策是根据一个评估函数h(x)=f(x)+g(x)，其中f(x)表示已经有的收入，g(x)表示未来期望的收入。
评估函数选择的核心在于g(x)的选择，g(x)的预测越接近实际值，选择出最有路径的概率就越高。
