最短路径算法
搜索求解
以搜索最短路径为例
map.png
辅助信息:
图中给出了任意城市与目的城市(Bucharest)之间的直线距离
info.png
启发式求解
-
贪婪最优先算法
在知道两点之间的距离的情况下 每次都选择直线距离最近的两点; 如：第一个位置Arad 他的周围有3个点
Zerind，Sibiu，Timisoara，同时我们可以在下图中看出两个城市之间距离 分别时 253，329，374;进过比较当然选择Sibiu。
Greedy best-first search.png
优点简单易懂，而且可以快速得到答案
不足之处:
- 贪婪最佳优先搜索不是最优的。经过Sibiu到Fagaras到Bucharest的路径比经过Rimnicu Vilcea到Pitesti到Bucharest的路径要长32公里。
- 启发函数代价最小化这一目标会对错误的起点比较敏感。考虑从Iasi到Fagaras的问题，由启发式建议须先扩展Neamt，因为其离Fagaras最近，但是这是一条存在死循环路径。
- 贪婪最佳优先搜索也是不完备的。所谓不完备即它可能沿着一条无限的路径走下去而不回来做其他的选择尝试，因此无法找到最佳路径这一答案。
- 在最坏的情况下，贪婪最佳优先搜索的时间复杂度和空间复杂度都是O(𝑏𝑚)，其中𝑏是节点的分支因子数目、𝑚是搜索空间的最大深度。
-
A*搜索
定义评价函数：
g(n) 表示从起始节点到节点𝑛的开销代价值
ℎ(𝑛)表示从节点𝑛到目标节点路径中所估算的最小开销代价值。
f(𝑛)可视为经过节点𝑛 、具有最小开销代价值的路径。
A1.png
对抗搜索
主要内容:
- 最小最大搜索
最小最大搜索(Minimax Search): 最小最大搜索是在对抗搜索中最为基本的一种让玩家来计算最优策略的方法.
- Alpha-Beta剪枝搜索
Alpha-Beta剪枝搜索(Pruning Search): 一种对最小最大搜索进行改进的算法，即在搜索过程中可剪除无需搜索的分支节点，且不影响搜索结果
- 蒙特卡洛树搜索
-
最大最小搜索(MAX and MIN)
目前主要讨论在确定的、全局可观察的、竞争对手轮流行动、零和游戏（zero-sum）下的对抗搜索
两人对决游戏 (MAX and MIN, MAX先走) 可如下形式化描述，从而将其转换为对抗搜索问题
| 初始状态𝑆0 | 游戏所处于的初始状态 |
|---|---|
| 玩家𝑃𝐿𝐴𝑌𝐸𝑅(𝑠) | 在当前状态𝑠下，该由哪个玩家采取行动 |
| 行动𝐴𝐶𝑇𝐼𝑂𝑁𝑆 (𝑠) | 在当前状态𝑠下所采取的可能移动 |
| 状态转移模型𝑅𝐸𝑆𝑈𝐿𝑇 (𝑠,𝑎) | 在当前状态𝑠下采取行动𝑎后得到的结果 |
| 终局状态检测𝑇𝐸𝑅𝑀𝐼𝑁𝐴𝐿−𝑇𝐸𝑆𝑇 (𝑠) | 检测游戏在状态𝑠是否结束 |
| 终局得分𝑈𝑇𝐼𝐿𝐼𝑇𝑌 (𝑠,𝑝) | 在终局状态𝑠时，玩家𝑝的得分。 |
MAX先行，可在初始状态的9个空格中任意放一个X
MAX希望游戏终局得分高、MIX希望游戏终局得分低
所形成游戏树的叶子结点有9!=362,880,国际象棋的叶子节点数为
-
Alpha-Beta剪枝搜索
在MaxMin中如果 搜索数极大,就会导致计算成本加大，短时间内没有办法完成。因此在这个基础上我们提出了Alpha-Beta剪枝搜索，在剪去了不影响最终结果的前提下忽略不必要的搜索加快计算效率。
算法描述:
Alpha-Beta.png
-
蒙特卡洛规划 (Monte-Carlo Planning)
单一状态蒙特卡洛规划： 多臂赌博机 (multi-armed bandits)
上限置信区间策略 (Upper Confidence Bound Strategies, UCB)
蒙特卡洛树搜索 (Monte-Carlo Tree Search)
Restemplate 的3种用法
应用间通信 客户端负载均衡器 Ribbon
RestTemplate Feign Zuul 都用到了 Ribbon
Ribbon 实习负载均衡的方法 有3点 服务发现 服务选择规则 服务监听
Fiegn 也可以实现服务间应用的通信
