引言
宝可梦系列游戏中，18种属性之间存在着复杂而精妙的克制关系。火克草、水克火、草克水——这些基础规则构成了一个庞大的有向图。对于竞技玩家和算法爱好者而言，一个核心问题是：给定一组宝可梦的属性组合，如何最大化覆盖对手可能的弱点？ 本文将用Java构建属性克制图，并实现Floyd-Warshall算法来计算任意两属性间的克制链最短路径，最终解决类型覆盖优化问题。
属性克制图建模
宝可梦的属性克制关系可以用带权有向图表示。每个节点代表一种属性，边的权重表示克制倍率（如2.0表示效果拔群，0.5表示效果不佳，0.0表示无效）。
核心数据结构
import java.util.*;
/**
* 宝可梦属性克制图
* 18种属性：普通、火、水、草、电、冰、格斗、毒、地面、飞行、超能力、虫、岩石、幽灵、龙、恶、钢、妖精
*/
public class PokemonTypeGraph {
// 18种属性的名称
public static final String[] TYPES = {
"普通", "火", "水", "草", "电", "冰",
"格斗", "毒", "地面", "飞行", "超能力", "虫",
"岩石", "幽灵", "龙", "恶", "钢", "妖精"
};
// 克制矩阵：effectiveness[攻击方][防御方] = 伤害倍率
// 2.0=效果拔群, 1.0=一般, 0.5=效果不好, 0.0=无效
private final double[][] effectiveness;
// Floyd-Warshall计算后的最短克制链距离
private double[][] shortestChain;
// 路径记录，用于重构克制链
private int[][] nextNode;
public PokemonTypeGraph() {
this.effectiveness = new double[18][18];
this.shortestChain = new double[18][18];
this.nextNode = new int[18][18];
initializeEffectiveness();
}
/**
* 初始化官方属性克制表（核心数据）
* 数据来源：宝可梦官方属性克制规则
*/
private void initializeEffectiveness() {
// 默认所有属性对普通属性都是1.0倍
for (int i = 0; i < 18; i++) {
Arrays.fill(effectiveness[i], 1.0);
}
// 火属性：克草、冰、虫、钢；被水、地面、岩石克
effectiveness[1][2] = 0.5; // 火打水
effectiveness[1][3] = 2.0; // 火打草
effectiveness[1][5] = 2.0; // 火打冰
effectiveness[1][11] = 2.0; // 火打虫
effectiveness[1][16] = 2.0; // 火打钢
// 水属性：克火、地面、岩石；被草、电克
effectiveness[2][1] = 2.0; // 水打火
effectiveness[2][3] = 0.5; // 水打草
effectiveness[2][8] = 2.0; // 水打地面
effectiveness[2][12] = 2.0; // 水打岩石
// 草属性：克水、地面、岩石；被火、冰、毒、虫、飞行克
effectiveness[3][1] = 0.5; // 草打火
effectiveness[3][2] = 2.0; // 草打水
effectiveness[3][7] = 0.5; // 草打毒
effectiveness[3][8] = 2.0; // 草打地面
effectiveness[3][9] = 0.5; // 草打飞行
effectiveness[3][11] = 0.5; // 草打虫
effectiveness[3][12] = 2.0; // 草打岩石
effectiveness[3][5] = 0.5; // 草打冰
// 电属性：克水、飞行；被地面克（无效）
effectiveness[4][2] = 2.0; // 电打水
effectiveness[4][8] = 0.0; // 电打地面（无效！）
effectiveness[4][9] = 2.0; // 电打飞行
// 冰属性：克草、地面、飞行、龙；被火、格斗、岩石、钢克
effectiveness[5][1] = 0.5; // 冰打火
effectiveness[5][3] = 2.0; // 冰打草
effectiveness[5][8] = 2.0; // 冰打地面
effectiveness[5][9] = 2.0; // 冰打飞行
effectiveness[5][14] = 2.0; // 冰打龙
effectiveness[5][6] = 0.5; // 冰打格斗
effectiveness[5][12] = 0.5; // 冰打岩石
effectiveness[5][16] = 0.5; // 冰打钢
// 格斗属性：克一般、冰、岩石、恶、钢；被超能力、飞行、妖精克；对幽灵无效
effectiveness[6][0] = 2.0; // 格斗打普通
effectiveness[6][5] = 2.0; // 格斗打冰
effectiveness[6][12] = 2.0; // 格斗打岩石
effectiveness[6][15] = 2.0; // 格斗打恶
effectiveness[6][16] = 2.0; // 格斗打钢
effectiveness[6][10] = 0.5; // 格斗打超能力
effectiveness[6][9] = 0.5; // 格斗打飞行
effectiveness[6][17] = 0.5; // 格斗打妖精
effectiveness[6][13] = 0.0; // 格斗打幽灵（无效）
// 毒属性：克草、妖精；被地面、超能力克；对钢无效
effectiveness[7][3] = 2.0; // 毒打草
effectiveness[7][17] = 2.0; // 毒打妖精
effectiveness[7][8] = 0.5; // 毒打地面
effectiveness[7][10] = 0.5; // 毒打超能力
effectiveness[7][16] = 0.0; // 毒打钢（无效）
// 地面属性：克火、电、毒、岩石、钢；被草、冰、水克；对飞行无效
effectiveness[8][1] = 2.0; // 地面打火
effectiveness[8][4] = 2.0; // 地面打电
effectiveness[8][7] = 2.0; // 地面打毒
effectiveness[8][12] = 2.0; // 地面打岩石
effectiveness[8][16] = 2.0; // 地面打钢
effectiveness[8][3] = 0.5; // 地面打草
effectiveness[8][5] = 0.5; // 地面打冰
effectiveness[8][2] = 0.5; // 地面打水
effectiveness[8][9] = 0.0; // 地面打飞行（无效）
// 飞行属性：克草、格斗、虫；被电、冰、岩石克
effectiveness[9][3] = 2.0; // 飞行打草
effectiveness[9][6] = 2.0; // 飞行打格斗
effectiveness[9][11] = 2.0; // 飞行打虫
effectiveness[9][4] = 0.5; // 飞行打电
effectiveness[9][5] = 0.5; // 飞行打冰
effectiveness[9][12] = 0.5; // 飞行打岩石
// 超能力属性：克格斗、毒；被虫、恶、幽灵克；对恶无效
effectiveness[10][6] = 2.0; // 超能力打格斗
effectiveness[10][7] = 2.0; // 超能力打毒
effectiveness[10][11] = 0.5;// 超能力打虫
effectiveness[10][15] = 0.0;// 超能力打恶（无效）
effectiveness[10][13] = 0.5;// 超能力打幽灵
// 虫属性：克草、超能力、恶；被火、格斗、飞行、毒、幽灵、钢、妖精克
effectiveness[11][3] = 2.0; // 虫打草
effectiveness[11][10] = 2.0;// 虫打超能力
effectiveness[11][15] = 2.0;// 虫打恶
effectiveness[11][1] = 0.5; // 虫打火
effectiveness[11][6] = 0.5; // 虫打格斗
effectiveness[11][9] = 0.5; // 虫打飞行
effectiveness[11][7] = 0.5; // 虫打毒
effectiveness[11][13] = 0.5;// 虫打幽灵
effectiveness[11][16] = 0.5;// 虫打钢
effectiveness[11][17] = 0.5;// 虫打妖精
// 岩石属性：克火、冰、飞行、虫；被格斗、地面、钢、水、草克
effectiveness[12][1] = 2.0; // 岩石打火
effectiveness[12][5] = 2.0; // 岩石打冰
effectiveness[12][9] = 2.0; // 岩石打飞行
effectiveness[12][11] = 2.0;// 岩石打虫
effectiveness[12][6] = 0.5; // 岩石打格斗
effectiveness[12][8] = 0.5; // 岩石打地面
effectiveness[12][16] = 0.5;// 岩石打钢
effectiveness[12][2] = 0.5; // 岩石打水
effectiveness[12][3] = 0.5; // 岩石打草
// 幽灵属性：克超能力、幽灵；被恶、幽灵克；对普通无效
effectiveness[13][10] = 2.0;// 幽灵打超能力
effectiveness[13][13] = 2.0;// 幽灵打幽灵
effectiveness[13][15] = 0.5;// 幽灵打恶
effectiveness[13][0] = 0.0; // 幽灵打普通（无效）
// 龙属性：克龙；被冰、龙、妖精克；对妖精无效
effectiveness[14][14] = 2.0;// 龙打龙
effectiveness[14][5] = 0.5; // 龙打冰
effectiveness[14][17] = 0.0;// 龙打妖精（无效）
// 恶属性：克超能力、幽灵；被格斗、虫、妖精克
effectiveness[15][10] = 2.0;// 恶打超能力
effectiveness[15][13] = 2.0;// 恶打幽灵
effectiveness[15][6] = 0.5; // 恶打格斗
effectiveness[15][11] = 0.5;// 恶打虫
effectiveness[15][17] = 0.5;// 恶打妖精
// 钢属性：克冰、岩石、妖精；被火、格斗、地面克
effectiveness[16][5] = 2.0; // 钢打冰
effectiveness[16][12] = 2.0;// 钢打岩石
effectiveness[16][17] = 2.0;// 钢打妖精
effectiveness[16][1] = 0.5; // 钢打火
effectiveness[16][6] = 0.5; // 钢打格斗
effectiveness[16][8] = 0.5; // 钢打地面
// 妖精属性：克格斗、龙、恶；被毒、钢克
effectiveness[17][6] = 2.0; // 妖精打格斗
effectiveness[17][14] = 2.0;// 妖精打龙
effectiveness[17][15] = 2.0;// 妖精打恶
effectiveness[17][7] = 0.5; // 妖精打毒
effectiveness[17][16] = 0.5;// 妖精打钢
}
Floyd-Warshall算法实现
Floyd-Warshall算法用于计算图中所有节点对之间的最短路径。在属性克制图中，我们可以用它来寻找”最优克制链”——即通过属性转换，找到从任意属性A到属性B的最有效克制路径。
/**
* Floyd-Warshall算法：计算所有属性对之间的最短克制链
* 将克制倍率取负对数作为边权，使"效果越好"的路径长度越短
*/
public void computeShortestChains() {
int n = 18;
// 初始化距离矩阵和路径矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
shortestChain[i][j] = 0;
nextNode[i][j] = -1;
} else if (effectiveness[i][j] > 0) {
// 使用-log(倍率)作为边权：2.0->-0.693, 1.0->0, 0.5->0.693
// 这样效果拔群的路径权重更小（更"短"）
shortestChain[i][j] = -Math.log(effectiveness[i][j]);
nextNode[i][j] = j;
} else {
// 无效关系（倍率为0），设为无穷大
shortestChain[i][j] = Double.POSITIVE_INFINITY;
nextNode[i][j] = -1;
}
}
}
// 核心三重循环：Floyd-Warshall
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (shortestChain[i][k] + shortestChain[k][j] < shortestChain[i][j]) {
shortestChain[i][j] = shortestChain[i][k] + shortestChain[k][j];
nextNode[i][j] = nextNode[i][k];
}
}
}
}
}
/**
* 重构从start到end的最短克制链
*/
public List<String> getChain(int start, int end) {
List<String> chain = new ArrayList<>();
if (shortestChain[start][end] == Double.POSITIVE_INFINITY) {
return chain; // 不存在路径
}
int current = start;
chain.add(TYPES[current]);
while (current != end) {
current = nextNode[current][end];
chain.add(TYPES[current]);
}
return chain;
}
类型覆盖优化问题
在实际对战中，玩家需要组建一支队伍（每只宝可梦有1-2种属性），使得队伍能覆盖尽可能多的对手弱点。这是一个组合优化问题。
/**
* 类型覆盖优化：给定k只宝可梦（每只最多2种属性），计算能覆盖多少种防御属性的弱点
* 使用贪心策略：每次选择能覆盖最多未覆盖弱点的属性组合
* @param teamSize 队伍大小（宝可梦数量）
* @return 最优属性组合及其覆盖范围
*/
public TeamResult optimizeTypeCoverage(int teamSize) {
// 预计算每种单一属性对所有防御属性的克制情况
// coverage[i][j] = true 表示属性i能效果拔群地攻击属性j
boolean[][] coverage = new boolean[18][18];
for (int i = 0; i < 18; i++) {
for (int j = 0; j < 18; j++) {
coverage[i][j] = effectiveness[i][j] >= 2.0;
}
}
// 枚举所有可能的单属性/双属性组合（共18 + C(18,2) = 171种）
List<int[]> allCombos = new ArrayList<>();
for (int i = 0; i < 18; i++) {
allCombos.add(new int[]{i}); // 单属性
for (int j = i + 1; j < 18; j++) {
allCombos.add(new int[]{i, j}); // 双属性
}
}
// 贪心选择：每次选覆盖最多未覆盖弱点的组合
Set<Integer> covered = new HashSet<>();
List<int[]> selectedTeam = new ArrayList<>();
Set<String> selectedNames = new LinkedHashSet<>();
for (int t = 0; t < teamSize && covered.size() < 18; t++) {
int[] bestCombo = null;
int bestNewCoverage = -1;
for (int[] combo : allCombos) {
int newCoverage = 0;
for (int def = 0; def < 18; def++) {
if (covered.contains(def)) continue;
for (int atk : combo) {
if (coverage[atk][def]) {
newCoverage++;
break; // 该防御属性已被此宝可梦覆盖
}
}
}
if (newCoverage > bestNewCoverage) {
bestNewCoverage = newCoverage;
bestCombo = combo;
}
}
if (bestCombo == null || bestNewCoverage == 0) break;
selectedTeam.add(bestCombo);
StringBuilder name = new StringBuilder();
for (int type : bestCombo) {
name.append(TYPES[type]);
}
selectedNames.add(name.toString());
// 更新已覆盖的防御属性
for (int def = 0; def < 18; def++) {
for (int atk : bestCombo) {
if (coverage[atk][def]) {
covered.add(def);
break;
}
}
}
}
return new TeamResult(selectedNames, covered.size());
}
public static class TeamResult {
public final Set<String> teamMembers;
public final int coverageCount;
public TeamResult(Set<String> teamMembers, int coverageCount) {
this.teamMembers = teamMembers;
this.coverageCount = coverageCount;
}
}
完整运行示例
public static void main(String[] args) {
PokemonTypeGraph graph = new PokemonTypeGraph();
// 1. 计算最短克制链
graph.computeShortestChains();
// 2. 查询示例：从"火"到"钢"的最短克制链
System.out.println("=== 最短克制链查询 ===");
List<String> chain = graph.getChain(1, 16); // 火 -> 钢
System.out.println("火 -> 钢的最短克制链: " + String.join(" -> ", chain));
chain = graph.getChain(4, 8); // 电 -> 地面
System.out.println("电 -> 地面的最短克制链: " + String.join(" -> ", chain));
// 3. 类型覆盖优化
System.out.println("\n=== 类型覆盖优化 ===");
TeamResult result = graph.optimizeTypeCoverage(6);
System.out.println("推荐6只宝可梦的属性组合：" + result.teamMembers);
System.out.println("可覆盖的弱点属性数：" + result.coverageCount + "/18");
// 4. 打印完整克制矩阵（部分）
System.out.println("\n=== 属性克制矩阵（效果拔群标记为*）==="");
System.out.print(" ");
for (String type : TYPES) {
System.out.printf("%3s ", type.substring(0, Math.min(2, type.length())));
}
System.out.println();
for (int i = 0; i < 18; i++) {
System.out.printf("%3s: ", TYPES[i].substring(0, Math.min(2, TYPES[i].length())));
for (int j = 0; j < 18; j++) {
String mark = graph.effectiveness[i][j] >= 2.0 ? " * " :
graph.effectiveness[i][j] <= 0.0 ? " X " : " ";
System.out.print(mark);
}
System.out.println();
}
}
算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| Floyd-Warshall | O(V³) = O(5832) | O(V²) = O(324) | V=18种属性，实际运行极快 |
| 类型覆盖贪心 | O(K × C × V) | O(V²) | K=队伍大小, C=171种组合 |
| 路径重构 | O(V) | O(V) | 线性时间 |
由于属性种类固定为18种，所有算法的实际运行时间都在毫秒级别。Floyd-Warshall的O(18³)仅约6000次运算，在现代CPU上几乎瞬时完成。
扩展思考
-
双属性宝可梦的防御计算：当宝可梦拥有两种防御属性时，伤害倍率为两种属性各自倍率的乘积。例如，草+毒被火攻击时：2.0 × 1.0 = 2.0倍伤害。
-
队伍构建的完整优化：本文使用贪心策略，但全局最优解需要枚举所有组合（NP-hard问题）。对于6只宝可梦、171种可选组合，精确解需要O(171⁶)的暴力搜索，不可行。贪心策略在实践中能获得接近最优的解。
-
动态对局适配：在真实对战中，可以根据对手的已亮出宝可梦，动态调整剩余宝可梦的出场顺序，这可以建模为在线学习或博弈论问题。
总结
本文用Java完整实现了宝可梦属性克制图的构建、Floyd-Warshall最短克制链计算，以及贪心策略的类型覆盖优化。通过将有向图算法应用于游戏策略分析，我们不仅理解了经典图算法的实际应用，也揭示了宝可梦对战背后的数学之美。读者可以在此基础上扩展更多功能，如双打对战的多属性协同分析、特性与技能的算法建模等。
