← 返回题目列表

AtCoder · hokudai_hitachi2018_a

A. 问题设置A

中文机器翻译题面 查看原题

通知

如果方程显示不正确,我们建议查看 新AtCoder系统.

问题设置

创建一种算法,为高阶伪布尔函数提供二次化。

定义:高阶二次伪布尔函数

让 f(X) 是 伪布尔函数 of N 二进制变量 X = \left[ x_1, \ldots, x_{N} \right] (x_i \in \left\{ 0, 1 \right\}) 和 g(Y) 是一个伪布尔函数 S 二进制变量 Y = \left[ y_1, \ldots, y_{S} \right] (y_i \in \left\{ 0, 1 \right\})。对于本次竞赛的范围,让 f(X) 和 g(Y) 是多项式

  • f(X) = f(x_1, \ldots, x_{N}) = H + \sum_{i=1}^{N} p_i x_i + \sum_{1 \leq i < j \leq N} q_{ij} x_i x_j + \sum_{1 \leq i < j < k \leq N} r_{ijk} x_i x_j x_k + \cdots,
  • g(Y) = g(y_1, \ldots, y_{S}) = H' + \sum_{i=1}^{S} p_i' y_i + \sum_{1 \leq i < j \leq N+M} q_{ij}' y_i y_j,
具有整数系数 H, p_i, q_{ij}, r_{ijk}, \cdots\inℤ 和 H', p_i', q_{ij}'\inℤ。此外,让 f 是一个具有次数的高阶伪布尔函数 d 较大的两个 (d>2),同时 g 应表示最多二次的二次伪布尔多项式。

示例: 高阶二次伪布尔函数 f(x_1, x_2, x_3)= - x_1 x_2 x_3 是一个 3 阶高阶伪布尔函数,共有 1 项和 3 个二元变量。另一方面, g(y_1, y_2, y_3, y_4) = y_4 \times (2-y_1-y_2-y_3) 是一个 2 次二次伪布尔函数,共有 4 项和 4 个二元变量。

任务:高阶布尔函数二次化算法

给定一个高阶伪布尔函数 f(X) 作为输入,创建一个提供二次伪布尔函数的算法 g(Y)=g(X,W) 度数最多为 2,这样:

f(X) = \min_{W \in \left\{0, 1\right\}^M} g(X, W) 对于所有人 X \in \left\{0, 1\right\}^N.

一个函数 满足上述条件的 g(Y)=g(X,W) 被称为 f(X)。二次化 g(Y)=g(X,W) 共享一组通用变量 \left[ y_1, \ldots, y_{N} \right]=\left[ x_1, \ldots, x_{N} \right]=X \in \left\{0, 1\right\}^N 与 f(X),同时维护一组附加辅助变量 \left[ y_{N+1}, \ldots, y_{N+M} \right]=\left[ w_1, \ldots, w_{M} \right]=W \in \left\{0, 1\right\}^M.

示例: 正交化 功能 g(x_1, x_2, x_3, w) = w (2-x_1-x_2-x_3) 是二次化 f(x_1, x_2, x_3)= -x_1 x_2 x_3。为了看到这一点,我们考虑两种情况:
  • 情况1:所有变量 x_1=x_2=x_3=1: 在这种情况下 f(x_1, x_2, x_3)=-1。另一方面, g(x_1, x_2, x_3, w)=-w 及其最小值 w 给出 min_w g(x_1, x_2, x_3, w) = -1.
  • 情况 2:至少有一个变量 x_1, x_2, x_3 is 0
    如果至少有一个变量 x_1, x_2, x_3 is 0, f(x_1,x_2,x_3)=0。另一方面,考虑到功能 g 我们有 (2-x_1-x_2-x_3)≥0。因此,最小化 g 关于 w\in[0,1] 我们发现 min_w{ g(x_1,x_2,x_3,w)}=0.

旁注:

在给定的计算时间限制内不可能根据上述定义检查提交的算法是否提供适当的二次化。因此,我们接受提供二次伪布尔函数的算法,该函数根据以下公式提供真实二次化的上限:

f(X) \le \min_{W \in \left\{0, 1\right\}^M} g(X, W) 对于所有人 X \in \left\{0, 1\right\}^N.

话虽如此,值得记住的是,成功提交将提供一个二次伪布尔函数来保持间隙

e(X):= \min_{W \in \left\{0, 1\right\}^M} g(X, W)-f(X)\ge 0

尽可能小 X \in \left\{0, 1\right\}^N.

评分:

获奖算法将提供二次化 g(X,W) 伪布尔函数 f(X) 这样

  • g(X,W) 具有尽可能少的辅助变量 W=[w_1, \ldots, w_M] 尽可能,
  • g(X,W) 的术语尽可能少,
  • 的系数 g(X,W) 尽可能小。
  • 如果算法提供二次化,则会获得额外分数 g(X,W),可以轻松地根据辅助变量最小化 W 通过模拟退火。
有关更多详细信息,请参阅下面的评分部分。

示例: 得分 功能 g(x_1, x_2, x_3, w) = (2w - x_1 w - x_2 w - x_3 w) 是二次化 f(x_1, x_2, x_3)= -x_1 x_2 x_3。它包含一个辅助变量 w,共四项,其最大系数为2。


关于问题设置A、B、C的差异

请注意,问题陈述 A、B 和 C 中算法之后的思想基本相同。特别是,可以对所有三个问题提交相同的算法并获得分数。另一方面,问题设置 A、B 和 C 之间的主要区别在于高阶伪布尔值的结构 f(X) 将作为输入提供给您的算法。

所有输入问题都将采用高阶伪布尔多项式的结构 f(X) 由上面的等式指定。对于所有输入情况,我们将选择随机系数 H, p_i, q_{ij}, r_{ijk}, \cdots \in \mathbb{Z} 在下面指定的范围内均匀采样。输入样本将根据非零系数的结构而变化。

  • 问题A:在问题 A 中,我们考虑具有大次数的高阶伪布尔输入函数 d,即度数达到可用变量的完整大小 d\le N。然而,具有非零系数的项的数量将非常低,使得输入变得“稀疏”。
  • 问题B:在问题 B 中,我们考虑低阶的高阶伪布尔输入函数。特别是,没有输入函数的次数大于 6 (d\le 6)。此外,只有一些潜在的多项式项将具有非零系数,从而导致另一个稀疏输入。
  • 问题C:在问题 C 中,我们将提供 6 阶输入问题,其中所有可用项的系数被选为随机输入,从而导致“密集”输入问题。

提供三类不同类型的输入问题的目的在于让算法有机会针对不同的输入目标采用不同的调整策略。下表给出了问题陈述 A、B 和 C 中输入问题的全面总结。

密集(所有术语) 稀疏(很少的术语)
高度 问题A
低度 问题C 问题B

输入格式

高阶伪布尔函数 f(X) 将通过以下输入格式提供

N K
d_1 c_1 v_{1, 1} ... v_{1, d_1}
d_2 c_2 v_{2, 1} ... v_{2, d_2}
:
d_K c_K v_{K, 1} ... v_{K, d_K}
  • 所有输入值均为整数类型。
  • N 表示二进制变量的数量 X = \left[ x_1, \ldots, x_{N} \right].
  • K 表示高阶伪布尔多项式的项数 f(X).
  • 每行 2, \ldots, K+1 对其中之一的信息进行编码 K 条款 f(X).
    特别是, i第一项解码如下: d_i 表示程度 i第学期, c_i 表示系数 i第一项,以及 号码 v_{i, 1} \ldots v_{i, d_i} 表示二进制变量的索引 x_{v_{i, 1}} \ldots x_{v_{i, d_i}} 组成 i第一项(单项式)。
  • 在特殊情况下 d_i = 0 我们只提供常量偏移量 c_i 并且没有其他变量 v_{i, 1} \ldots v_{i, d_i}.

输入示例

高阶布尔单项式 f(x_1, x_2, x_3, x_4, x_5) = - x_{1}x_{2}x_{3} + 4 x_{4}x_{5} 编码如下。

5 2
3 -1 1 2 3
2 4 4 5

第一行:f(X) 包含 5 个二元变量和两项。
第二行:第一项的次数为 3,即它是三个变量的乘积。它的前因子/系数是 -1。该术语包含变量 x_{1}, x_{2}, x_{3}.
第三行:第二项的次数为 2,即它是两个变量的乘积。它的前因子/系数是 4。该术语包含变量 x_{4}, x_{5}.

对输入问题应提出以下附加要求。

  • 3 \leq N \leq 50
  • 1 \leq K \leq 50
  • 0 \leq d_i \leq N
  • 1 \leq \left|c_i \right| \leq 100
  • 1 \leq v_{i, j} \leq N
  • 对于所有人 j (1 \leq j \lt d_i) 我们要求 v_{i, j} < v_{i, j+1}
  • 对于两条线 i,j 与 i \neq j 我们要求 \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right],即两个单独的行不应编码相同类型的单项式。
  • 该行 d_i = 0 不应超过该系数。
  • 所有变量 k (1 \leq k \leq N) 应该出现在至少一个术语中,即存在至少一个 v_{i,j} 这样 k = v_{i, j}.

输出格式

提交的算法应提供获得的二次化 g(Y)=g(X,W) 使用以下输出格式。

S L
d_1' c_1' v_{1, 1}' ... v_{1, d_1'}'
d_2' c_2' v_{2, 1}' ... v_{2, d_2'}'
:
d_L' c_L' v_{L, 1}' ... v_{L, d_L'}'
  • 输出文件中的所有值应为整数类型
  • S 表示二次化所使用的二进制变量的数量 g(X,W),其中 S 应是“旧”和“新”变量的总和 S=N+M.
  • L 表示项(单项式)的数量 g(X,W).
  • 每行 2, \ldots, L+1 对其中之一的信息进行编码 L 条款 g(Y)=g(X,W).
    特别是, d_i' 表示程度 i第学期, c_i' 表示系数 i第一项,以及 变量 v_{i, 1}' \ldots v_{i, d_i}' 表示二进制变量的索引 y_{v_{i, 1}'} \ldots y_{v_{i, d_i}'} 形成 i第一项(单项式)。
  • 指数 必须选择 v_{i,l}' ,以便二进制变量 y_{r} 与 r=1,...,N of g(Y) 可以安全地用二进制变量识别 x_{r} 与 r=1,...,N of f(X) as y_{r}=x_{r} 对于所有人 r=1,...,N.
  • 在特殊情况下 d_i' = 0 仅恒定偏移量 出现 c_i' 并且没有更多变量 应提供 v_{i, 1}' \ldots v_{i, d_i}' 。

对输出格式应施加以下附加要求。

  • N \leq S \leq 3 \times10^3
  • 1 \leq L
  • 0 \leq d_i' \leq 2
  • 1 \leq \left|c_i'\right| \leq 2^{31}-1
  • 1 \leq v_{i, j}' \leq S
  • 对于所有人 j (1 \leq j \lt d_i') 我们要求 v_{i, j}' < v_{i, j+1}'.
  • 对于两条线 i, j 与 i \neq j 我们要求 \left[ v_{i, 1}', \dots , v_{i, d_i'}' \right] \neq \left[ v_{j, 1}', \dots, v_{j, d_j'}' \right],即两个单独的行不应包含相同单项式的信息。
  • 该行 d_i' = 0 不得超过该系数。

评分

您的算法将通过在几个输入问题上运行来评分 f(X)。对于每个输入问题,产生的二次化 g(X,W) 将按如下所述进行评分。您的总分将是每个输入问题获得的分数的总和。

比赛期间和比赛结束后输入问题的数量:

在比赛期间,我们将通过对每个子问题 A、B 和 C 的 15 个输入问题初步运行您的算法来估计您的分数。这将允许估计您的排名。比赛结束后,我们将通过对每个子问题 A、B 和 C 的 100 个先前未公开的输入问题(使用完全相同的统计属性创建)运行您的算法来评估您的最终分数。采取此措施是为了避免将算法调整为针对该组输入问题的特定统计波动。

输入问题的评分:

对于每个输入问题,您的算法将获得以下分数:

A \times PX \times PY \times PZ,

其中 A=10000 是一个常数,因子定义如下

  • PX = E \left(1 - \frac{\min(e_{SA}, T)}{T} \right),
  • PY = \frac{1000}{BM + L + 1000},
  • PZ = \frac{1000}{\max_i |c_i'| + 1000},
带有常量 E=10000, B=5, T=100 和 e_{SA}=e_{SA}(X) 是衡量原始输入之间差距的数量 f(X) 及其近似值,最小化时获得 g(X,W) 关于辅助变量 W 配置 X,基于 模拟退火(SA) 如下文进一步更详细地描述。

评分基于以下逻辑:

  • PX 衡量算法提供二次化的能力,从中得出原始函数的真实值 f(X) 可以根据模拟退火大致恢复。特别是,如果您的算法提供了二次化 e_{SA} 为零,第一个因素将取其最大值 E。此外,如果 e_{SA} < T=100,即,如果您的算法至少允许近似原始值 f(X) 有一定的准确性。最后,应该 e_{SA} < 0 您的算法提供了错误的提交,您的总分为零。欲了解更多详情 e_{SA},请参阅下面的部分。
  • PY 对使用过多辅助变量的二次化进行了罚款 M 否则产生具有许多项的二次化 L。它将鼓励使用尽可能少的辅助变量和项来创建二次化的算法。
  • PY 引入了对产生大模数系数的算法的罚款 \max_{i}|c_i'|。这将鼓励所需系数的位宽不会增长得太严重的算法。
最后,对于每个输入案例,我们将使用上述规则对您的算法进行两次评分。在一种情况下,我们将评估差距 e_{SA}(X) 完全随机配置 X \in \left\{ 0, 1 \right\}^N。这将给出分数 PA。在第二种情况下,我们将评估差距 e_{SA}(X) 用于所有位都处于向上位置的配置,即 [x_1, x_2, ..., x_N]=[1, 1, ..., 1]。这将给出分数 PB。每个输入问题的总分将是平均值,定义为

SCORE = \lfloor \frac{PA + PB}{2} \rfloor.

测定 e_{SA}

为了确定 e_{SA} 我们继续执行以下步骤:

  • 我们修复输入变量集 x_1, \dots ,x_N 随机配置 X \in \left\{ 0, 1 \right\}^N 或在选择所有位的配置中,即 [x_1, x_2, ..., x_N]=[1, 1, ..., 1] .
  • 对于这组变量 X 我们最小化 g(X,W) 关于剩余的新变量 W \in \left\{ 0, 1 \right\}^M 通过运行以下版本 模拟退火(SA) 重复五次。 [参见提供的 软件工具包 了解详细信息。] SA 的五次重复将导致变量的配置 w_{1,SA}, \dots ,w_{M,SA} 我们获得最小间隙 如果模拟退火找到相对于的真实最小值,

e_{SA} :=g(x_1, \dots ,x_N, w_{1,SA}, \dots ,w_{M,SA})-f(x_1, \dots ,x_N).

  • e_{SA} 将为零 W。如果模拟退火找到近似局部最小值, e_{SA} 将大于零。如果 e_{SA} 小于零,提交的算法有错误,总分将被设置为零。

请注意,选择随机配置的种子 x_1, \dots ,x_N 以及模拟退火过程的随机元素无法公开。 与比赛排名相比,其中 x_1, \dots ,x_N 15 个案例中的每一个都是相同的,最终测试将使用不同的配置 x_1, \dots ,x_N 适用于所有 100 个案例。

无效提交

请注意,提交的算法可能因多种原因而无效,例如,如果真实函数值与相对于真实最小值的二次化最小值之间的差距变得小于零。如果输出违反上述输出格式,则会出现给定提交获得零分的另一种情况。在所有这些情况下,给定的提交将标有信号 AtCoder 排名部分中的 WA 。


输入格式示例 1

3 1
3 1 1 2 3

该输入文件代表函数 f(x_1, x_2, x_3) = x_{1}x_{2}x_{3}.

输出格式示例 1

4 5
2 1 1 2
1 1 4
2 -1 1 4
2 -1 2 4
2 1 3 4

该输出示例提供了输入示例的平方化,总共 S=4 二进制变量和 L=5 项,即二次化使用单个辅助变量 W = \left[ w_1 \right] 和 M=1。总而言之,输出格式示例解码了以下成本函数 g(x_1, x_2, x_3, w_1) = x_{1}x_{2} +w_1 -x_{1}w_1 -x_{2}w_1 +x_{3}w_1 = x_{1}x_{2} +w_1(1 -x_1 -x_2 +x_3).

输出提供了输入问题的有效二次化,因为对于任何组合 x_1, x_2, x_3 可以证明 f(x_1, x_2, x_3) = \min_{W} g(x_1, x_2, x_3, W)。二次化的最大系数为 \max|c_i'|=1.

最后,假设 对于随机配置, e_{SA} = 0 都变为零 [x_1, x_2, x_3] 以及配置 [x_1, x_2, x_3]=[1,1,1] 上面的输出有

  • M=1 辅助变量,
  • L=5 条款,
  • 最大系数 \max_i |c_i'|=1,
导致

PA = PB = A\times E(1-0)\times\frac{1000}{B\times1 +5 + 1000} \times \frac{1000}{1+1000}=98910990.00009891.

和总分

SCORE = \lfloor \frac{2\times 98910990.00009891}{2}\rfloor =98910990.


输入格式示例 2

6 7
3 69 3 5 6
3 -93 2 3 4
3 -63 2 5 6
4 -95 1 2 5 6
3 24 1 4 5
2 75 1 6
2 49 3 6

输出格式示例 2

11 28
2 24 1 4
2 24 1 5
2 75 1 6
2 -95 1 7
2 -24 1 8
2 -95 2 7
2 -93 2 9
2 -63 2 10
2 69 3 5
2 118 3 6
2 -93 3 9
2 -69 3 11
2 24 4 5
2 -24 4 8
2 -93 4 9
2 69 5 6
2 -95 5 7
2 -24 5 8
2 -63 5 10
2 -69 5 11
2 -95 6 7
2 -63 6 10
2 -69 6 11
1 285 7
1 24 8
1 186 9
1 126 10
1 69 11

示例代码和文献提示

  • 生成输入格式和分数评估的示例代码可以从以下位置下载 这里.
  • 为了开始二次化,我们鼓励使用下面列出的文献和开源软件。
评论

简要回顾一下将高阶布尔多项式化简为二次伪布尔多项式的主要思想。

  • [评论] Endre Boros 和 Aritanan Gruber,“关于伪布尔函数的二次化” [arxiv]

修复、格鲁伯、波罗斯、扎比

有关高阶伪布尔成本函数平方的最先进算法和开源软件实现的两篇论文可从以下链接获取。

  • [论文] Alexander Fix 等人,“高阶马尔可夫随机场的图割算法” [IEEE] [pdf]
  • [论文] Alexander Fix 等人,“高阶二元马尔可夫随机场的基于超图的约简” [IEEE]
  • [代码] 亚历山大修复

石川
另外两篇关于对高阶伪布尔成本函数进行平方化的最先进算法的论文。