webxoss/webxoss-core

check energe zone with mixed color

Closed this issue · 15 comments

Deardrops commented

中文描述：
能量区存在以下卡牌时，支付费用时判断能量是否 足够支付：

  • 万花色卡（支付费用时可以替代任何有色费用）
  • 混色卡 （支付两种颜色的其中一种）
  • 小剑 三日月 （可以支付自身的白色或者另外一种颜色）
  • 美巧 （可以作为替代支付白色）
  • 御仙狐（可以作为【绿2】或【绿3】使用）

费用需求 可能有：

  • 双色（可以用x颜色或者x颜色支付该卡需要的【无】）
Deardrops commented

解决方案：

建立 一个 0-1整数线性规划 模型，不需要寻找最优解，只需要判断是否有可行解。
首先把能量区每一张牌从1到n编号，用a,b,c,d,e 分别表示 红 白 蓝 绿 黑

决策变量

a1,a2...an,b1,b2...,e1,e2..en 要么取0，要么取1
比如，b2取1代表第二张牌作为白色被支付。取0则相反。
实际上并不会创建这么多变量，比如万花色卡会创建5个变量，
双色卡会创建2个变量，而普通的卡只会有一个变量。

约束条件：

  1. 同一张卡片只能取一种颜色，即a1+b1+c1+d1+e1<=1
  2. 每一种颜色必须满足对应费用的要求，即a1+a2+...+an>=A，其中A代表需要的红色费用

模型求解：

github上找了一个求解0-1整数线性规划问题的库 zero-one
输入上述决策变量和约束条件后，可以有效地判断是否有解，示例如下：

const ZeroOneProgram = require('./src/zero_one_program')
program = new ZeroOneProgram()
x1 = program.addVariable();
x2 = program.addVariable();
y1 = program.addVariable();
y2 = program.addVariable();
y3 = program.addVariable();
program.addConstraint({
  variables: { [x1.id]: 1, [y1.id]: 1 },
  type: "max",
  value: 1
})
program.addConstraint({
  variables: { [x1.id]: 1, [x2.id]: 1 },
  type: "min",
  value: 2
})
program.addConstraint({
  variables: { [y1.id]: 1, [y2.id]: 1, [y3.id]: 1 },
  type: "min",
  value: 2
})
console.log(program.solve())

运行结果：
image
结果表示存在以下的可行解：

a1 = 1 第1张牌作为红色费用支付
b1 = 0 
a2 = 1 第2张牌作为红色费用支付
b3 = 1 第3张牌作为白色费用支付
b4 = 1 第4张牌作为白色费用支付

最后判断能量区剩余的卡的数量是否大于所需要的无色费用。（这一步在求解模型后再做）

webxoss commented
  1. 复杂度呢?
  2. 美巧「可以代替白色费用」，这个应该也能用 0-1 规划
  3. 御先狐「可以代替【绿3】或【绿2】」呢?
  4. Demo 直接得到了一个解，会不会仅得到解的存在性会比较省时间？
Deardrops commented

@webxoss

  1. 时间复杂度为e^n
  2. 美巧可以看作一张白色和绿色的双色卡（如果场上存在SP07-011 不思议的童话 梅尔）
  3. 这个issue只讨论混色卡的处理，减少费用这类问题建议另外开issue讨论。
    这类问题包括但不限于：
  • 减少费用 比如，御仙狐在能量区时，可以替代支付【绿2】或者【绿3】

「使用这张技艺时，可以将你的任意只S横置，每横置1只，【无】减1」

  • 增加费用 比如，lock you，增加对手使用魔法或技艺的费用【无3】
  1. 不会。证明有解存在是通过尝试找出一个可行解来实现的。两者其实是一回事。
webxoss commented

<御仙狐> 不能当作 d1 (绿色的能量用第一张卡,御先狐) 的值为 2 或 3，用同一个模型吗？

（虽然这样就不是0-1规划了）

Deardrops commented

补充说明

用a,b,c,d,e 分别表示 红 白 蓝 绿 黑

决策变量

a1,a2...an,b1,b2...,e1,e2..en 分别代表决策变量，要么取0，要么取1

  • 普通的卡有1个变量，比如红色卡只有a1这一个变量。
  • 万花色卡有5个变量。
  • 双色卡有2个变量，比如红/白 双色卡，会有a1和b1两个变量。
  • 三月日和美巧会被当作双色卡。

约束条件：

  1. 同一张卡片只能取一种颜色，即a1+b1+c1+d1+e1<=1
  2. 每一种颜色必须满足对应费用的要求，即a1+a2+...+an>=A，其中A代表需要的红色费用
  3. 有 御仙狐 的情况，不失一般性，设d1代表能量区中一张<御仙狐>作为绿色费用被支付。
    条件2应该改写为3*d1+d2+...+dn>=D。
    具体到程序里，判断输入的第几张卡是御仙狐，再为它乘上系数3。
  4. 对于费用要求为 黑/白 的情况，要求能量区中黑和白色卡的数量大于费用需求中黑和白色卡的总数量。即 ∑b+∑e>=B+E+BE
    其中B为要求的白色费用数量，E为要求的黑色数量，BE代表费用需求为 黑/白 的数量。

求解出结果后，再判断能量区剩余的卡的数量是否大于所需要的无色费用。

时间复杂度

NP完全问题，无法求得时间复杂度。

算法剖析

zero-one 用到两种求解算法：

  • 回溯算法
  • 分支定界法 （改进的回溯算法）

由于我们没有约束条件，算法实际上是在一棵满二叉树上深度优先遍历出一个可行解来。
最坏的情况下，n个决策变量对应一个n+1层满二叉树，一共有2^(n+1)-1种情况。
举个栗子，能量区有5张万花色的卡，对应25个决策变量，即最坏需要运算10^8次
一个令人绝望的数字。

个人意见

  1. 对能量区的卡进行预处理，将决策变量的数量控制在15个以内。
    比如不将万花色放入决策变量中，而是在作为约束条件。
  2. 优化决策变量的顺序，优先处理能量区中单色卡。
  3. 按费用筛选出一定不符合要求的分支。剪去。
webxoss commented

有 御仙狐 的情况，不失一般性，设d1代表能量区中一张<御仙狐>作为绿色费用被支付。
条件2应该改写为 3*d1+d2+...+dn>=D 。

御先狐可当为 1~3 绿，而约束条件只需要考虑 3 ，因为 >= 已经包含了 1 和 2 的情况。
对吗？

Deardrops commented

是的，因为这里只是检查有没有足够的费用，取最好的情况（3张绿色费用）即可。

webxoss commented

那就搞起来吧。

封装一个类库：

  1. 给定能量池和费用需求，给出是否有解。
  2. 给定能量池、费用需求和解，给出解是否有效。
gugugupan commented

基于二分图网络流的模型

  • 2017/6/13：修改问题模型，使其能够兼容同一个能量支持“被当做不同颜色能量支付时，所能承受的数量不同”的条件。并且在这个问题下，网络流的模型才能更好地解决该问题。

问题再定义

针对能量区中存在的多种不同的能量，判断某一个费用是否可以使用能量区中的能量进行支付，返回True or False。

  • 支付费用的定义：
    • 需要支付的费用为复数以下属性的对象进行组成：
      • 单色费用（如红费用需要一个红色费用或者一个万花色费用进行支付）；
      • 多色费用（如黑或白费用需要一个黑色或者一个白色或者一个万花色费用进行支付）；
  • 能量区中能量定义：
    • 能量区中每一个能量将会包含多个费用条件，每一个费用条件说明了该能量可以作为某一种颜色付费，以及按该费用付费时可以付费的数量。单一费用条件对象应包含下列属性：
      • 能量的颜色（如单一颜色红或绿，或者特殊颜色万花色）；
      • 能量的数量（如常规能量被当做费用付费时，能量数量为1；御仙狐在被当做绿色付费时，能量数量为3）；
    • 能量区中将会拥有复数个能量。

构造模型

之前作为二分图设计的模型已经成为历史：

* 构建一个二分图的模型，二分图的一边（左边）由N个需要支付的费用抽象成的点构成，另外一边（右边）由M个能量区中的能量进行构成。
  * 如需要支付的费用为`2红2绿2无`，其中无色费用只能通过黑色或者白色进行支付，则在二分图的左边将抽象出6个离散点，分别代表了`红`，`红`，`绿`，`绿`，`黑或白`，`黑或白`6种不同的费用支付方法；
  * 如能量区中的卡片为`热情割裂`，`热情割裂`，`三剑`，`美巧`，`美巧`，`侍从O2`，则在二分图的右边抽象出6个离散点，分别代表了`红`，`红`，`绿`，`绿或白`，`绿或白`，`万花`6种不同的费用；
* 在二分图之间构建边集，如果两个点所表示颜色交集不为空，则在点与点之前构建一条边集；
  * 在上面的例子中，将所有的点按顺序用数字进行编号，抽象的到的边集为：`(0,0)`,`(0,1)`,`(0,5)`,`(1,0)`,`(1,1)`,`(1,5)`,`(2,2)`,`(2,3)`,`(2,4)`,`(2,5)`,`(3,2)`,`(3,3)`,`(3,4)`,`(3,5)`,`(4,3)`,`(4,4)`,`(4,5)`,`(5,3)`,`(5,4)`,`(5,5)`
* 在边集中如果可以选取出一个子集，它满足以下条件的话，则表示费用可以成功支付：
  * 二分图左边的每一个点都被至少一条边覆盖过（能量都要满足付出的条件）；
  * 二分图左边的每一个点都不能被两条（或以上）边覆盖（不需要重复付费）；
  * 对二分图右边的每一个点而言，覆盖它的边数不能超过定义在该点上的“能量的数量”参数（每一个能量使用的次数不能超过它的最大产能限度）；

求解方法

可以使用网络流算法对最终结果进行求解：

  • 构建二分图的结构（其中的边权容量均为正无穷），源点S以及汇点T；
  • 源点S到二分图左边的每一个点构建一条容量为1的边；
  • 二分图右边的每一个点到汇点T构建一条容量为该点能量的数量的边；
  • 对网络求其最大流的大小，若最大流的大小 == 需要支付费用个数则表示可以支付，否则表示无法支付。

时间复杂度

  • 构造模型：O(N * M)
  • 求解过程：O(N^2 * M^2) （最坏情况）
  • 👍1
Deardrops commented

@gugugupan 其实小雪的思路挺好的，从费用要求出发去找可行解，肯定比我从能量区出发去找可行解要快得多。（因为能量区的卡一般比费用要求要多）

提一下以下两个问题：

  1. 我觉得这不是一个最大流的问题。最大网络流的目标是 找出满足条件的唯一路径，对于这个问题，我们不需要找出唯一的最好的路径（做这一步工作可能花费很多时间），只需要判断网络中是否有满足条件（即左边的点有且仅有一条边连向右边，右边的点连入的边不超过数量限制）的路径存在即可。
    并且，最大流问题只定义了边上的容量作为约束条件，没有定义点上的容量。
    这个模型中添加了若干 非标准 的约束条件，可能无法使用常规的最大流算法求解。
  2. 对于费用费用中有一般的【无】的情况，模型会复杂很多（左边一个无色点将与右边所有点有可能建立边，最后得到的边集会非常大）。
gugugupan commented

手机打字可能会格式有点不好看，回复一下你的两个问题：

  1. 可能我讲的不是太清楚，网络流的模型建立出来后，从源点到汇点的每一条路径都表示了“一个费用使用一个能量进行支付”的可能性，所谓最大流就是让流量最大，找到最多的“可能支付的可能性”。所以这里如果最大流的大小与需要支付能量相同就找到了一个支付方案，应该是没有问题的。你可以把我上面的那个例子在纸上画一下看看🙈

  2. 对于全部都是无色的情况，能量区中最多可能存在的点数为40，需要支付的能量最多为10（现在还没有看过比这个更多的），在这个最坏的情况下边集的大小是400，一个O(NumOfEdge^2)的网络流算法完全可以承受。

webxoss commented

二分图左边的每一个点都不能被两条（或以上）边覆盖（不需要重复付费）

被两个边覆盖不也是能支付吗？

对二分图右边的每一个点而言，覆盖它的边数不能超过定义在该点上的“能量的数量”参数

对于<御先狐>，能量的数量是3？
假如某只<御先狐>获得了【万花色】，那它只能作为绿色的时候数量是3。
这样的话模型是不是就不对了？

webxoss commented

想了想，并没有那么复杂...

定义

  • 卡
    一张卡是一个颜色的集合 ( 即 {红, 蓝, 绿, 白, 黑} 的子集 ), 记为 红, 红蓝, 红蓝绿 等.
    万花色即为 红蓝绿白黑 .
    无色即为空集.

  • 能量区
    能量区为卡的集合.

  • 红卡集
    卡 C 属于红卡集，当 C 属于能量区且 红 属于 C.
    同理可定义蓝卡集, 绿卡集等.

  • 红蓝卡集
    红蓝卡集 = 红卡集 ∩ 蓝卡集

  • 红或蓝卡集
    红或蓝卡集 = 红卡集 ∪ 蓝卡集

  • 元(能量)需求
    元需求为有序对 [N, 卡集X], 其中 N 为正整数. 记为 NX .
    如: 1红, 2蓝, 3红蓝, 4红或蓝

  • 总(能量)需求
    总需求为元需求的集合, 其中元需求的卡集各不相同.
    记为卡集的多项式: N1X1 + N2X2 + N3X3 + ... . (注意 N? 为正整数, X? 为各不相同的卡集)
    如: 1红 + 2蓝 + 3红蓝 + 4红或蓝

  • 总需求的解

    定义在能量区 S 上的总需求 N1X1 + N2X2 + N3X3 + ... + NnXn 有解, 当:

    存在各不相同的卡 Cij 属于 S, 使

    • C11, C12, C13, ..., C1N1 属于 X1;
    • C21, C22, C23, ..., C2N2 属于 X2;
    • ...
    • Cn1, Cn2, Cn3, ..., CnNn 属于 Xn.

    ( 亦可表述为: 存在 Y1 ⊆ X1, Y2 ⊆ X2, ... Yn ⊆ Xn, 满足 n(Yi) = Ni 且对于任意 i,j, Yi ∩ Yj = Φ . )

    并称由上述 Cij 组成的集合为该总需求的一个解.

有解的等价条件

定义在能量区 S 上的总需求 N1X1 + N2X2 + N3X3 + ... + NnXn 有解, 当:

对于 { X1, X2, X3, ..., Xn } 的任意子集 { Xa, Xb, Xc, ... } , n(Xa ∪ Xb ∪ Xc ∪ ...) >= Na + Nb + Nc + ...

证明

必要性

记 Yk = { Ck1, Ck2, Ck3, ..., CkNk }. 显然 Yk ⊆ Xk.

因 Cij 各不相同, 对于任意{ Xa, Xb, Xc, ... }, 有

n(Xa ∪ Xb ∪ Xc ∪ ...) >= n(Ya ∪ Yb ∪ Yc ∪ ...) = Na + Nb + Nc + ...

充分性

TODO...

讨论

  • 上面对解的原始定义符合游戏逻辑吗？

  • 证明或伪证上述等价条件.

  • 上述等价条件的求解复杂度是多少？

webxoss commented

先证弱命题:

若

  • n(X1) >= N1
  • n(X2) >= N2
  • n(X1 ∪ X2) = n(X1) + n(X2) - n(X1 ∩ X2) >= N1 + N2

则存在 Y1 ⊆ X1, Y2 ⊆ X2, 满足 n(Y1) = N1, n(Y2) = N2, Y1 ∩ Y2 = Φ .

webxoss commented

设 n(X1) = N1 + Δ1, n(X2) = N1 + Δ2, 显然 Δ1 >= 0, Δ2 >= 0, Δ1 + Δ2 >= n(X1 ∩ X2) . 有

  • n(X1 - X2) = N1 + Δ1 - n(X1 ∩ X2) >= N1 - Δ2
  • n(X2 - X1) = N2 + Δ2 - n(X1 ∩ X2) >= N2 - Δ1

然后嘛，上面两就是 Y1, Y2, 但是还不够，不够的从交集里面补上，最后肯定是够的，我想想怎么写...