名古屋大学 情報科学研究科 計算機数理科学専攻 2015年8月実施 問題8（アルゴリズム設計法）

标签：

• 名古屋大学
• 动态规划原理
• 算法复杂度

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

英文の文章の左右の端をそろえて見栄えよく印刷するための改行 (line break) 位置を決めたい。ここで、改行は単語 (word) と単語の間のみで行うものとし、最終行の右端はそろえなくてよいものとする。$k$ 番目と $k+1$ 番目の単語の間を改行位置 $k$ とよび、実際に改行を行う改行位置の系列 $k_1,k_2,\ldots,k_l$ で配置を定める。たとえば図 1 と図 2 は同じ文章の異なるレイアウトであり、図 1 の改行位置系列は $5,7,11$、図 2 の系列は $6,9,13$ である。

文章は $n$ 個の単語からなり、$i$ 番目の単語の幅 $w_i$ $(i=1,2,\ldots,n)$ と行の幅 $L$ が与えられる。ただし $L$ は十分大きく、1 行に 2 単語以上入る幅である。

$i$ 番目から $j$ 番目まで $(i<j)$ の単語を 1 行に配置したとき、次の図のように単語間に均等にスペースを配置するときのスペース幅を $\tilde{s}(i,j)$ とする。

また、$j=i$ のときは便宜上 $\tilde{s}(i,i)=+\infty$ とし、

$$\begin{gathered} \tilde{s}(i,j)=\\ \begin{cases} \displaystyle\frac{L-(w_i+w_{i+1}+\cdots+w_j)}{j-i}, & \text{if }i<j,\\[6pt] +\infty, & \text{if }i=j \end{cases} \end{gathered}$$

と定義する。$j=n$（最終行）において $\tilde{s}(i,n)$ が $1$ を超える場合には次の図のように単語間のスペースとして $1$ を用いる。

以上のことを考慮して、$s(i,j)$ $(i\le j)$ を

$$s(i,j)= \begin{cases} \tilde{s}(i,j), & \text{if }j<n,\\ \min\{\tilde{s}(i,j),1\}, & \text{if }j=n \end{cases}$$

と定義し、これを単語間のスペースに用いて配置する。

このとき、$i$ 番目から $j$ 番目まで $(i\le j)$ の単語を 1 行に配置したときのコスト $c(i,j)$ を

$$c(i,j)= \begin{cases} +\infty, & \text{if }s(i,j)\le0,\\ |s(i,j)-1|, & \text{otherwise} \end{cases}$$

と定める。さらに、改行位置系列 $k_1,k_2,\ldots,k_l$ で配置を定めるときのレイアウトのコスト $z$ を

$$\begin{aligned} z={}&c(1,k_1)+c(k_1+1,k_2)\\ &+\cdots+c(k_l+1,n) \end{aligned}$$

と定め、その最小化を図る。

以下の各問に答えよ。

(1) 図 1 のレイアウトを考える。この図に現れる単語の幅を文字数で定義すると、以下の表が得られる。

$i$	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$w_i$	2	2	4	9	2	6	13	10	4	3	11	3	5	9

ここで、ピリオド “.” を無視することで、14 個めの単語 instances の幅を $w_{14}=9$ としている。行幅を $L=30$ とするとき、各行のコスト、および文章全体のコスト $z$ を求めよ。

(2) すべての $i,j$ の組 $(1\le i\le j\le n)$ に対して $c(i,j)$ の値を計算する効率の良い方法を述べ、その計算量を評価せよ。

(3) 改行位置系列を全列挙することで $z$ 最小のレイアウトを求める方法の計算量を述べよ。

(4) $i$ 番目から $n$ 番目までの $n-i+1$ 個の単語からなる文章をレイアウトするときの最小コストを $g(i)$ とする。$g(i)$ を計算する動的計画法 (dynamic programming) の漸化式 (recurrence formula) を書け。（必要であれば $g(n+1)=0$ としてよい。）

(5) $g(1),\ldots,g(n)$ を具体的に計算する方法を説明し、その計算量を評価せよ。

(6) $n$ 個の単語からなる文章をレイアウトする際のコスト $z$ の最小値、ならびに、それを実現する改行位置系列の求め方を説明せよ。

题目描述

希望通过选择英文文章的换行位置，使左右两端对齐、排版美观。只能在单词之间换行，最后一行的右端可以不对齐。将第 $k$ 个单词与第 $k+1$ 个单词之间称为换行位置 $k$，以实际采用的换行位置序列 $k_1,k_2,\ldots,k_l$ 确定排版。例如，上面的图 1 与图 2 是同一篇文章的两种排版：图 1 的换行位置序列为 $5,7,11$，图 2 为 $6,9,13$。

文章包含 $n$ 个单词，已知第 $i$ 个单词的宽度 $w_i$ $(i=1,2,\ldots,n)$ 以及行宽 $L$。假设 $L$ 足够大，一行能够容纳至少两个单词。

将第 $i$ 至第 $j$ 个单词 $(i<j)$ 放在同一行，按照上面的等间距示意图，在单词之间均匀分配空白，记空白宽度为 $\tilde{s}(i,j)$。为方便起见，在 $i=j$ 时规定 $\tilde{s}(i,i)=+\infty$，即

$$\begin{gathered} \tilde{s}(i,j)=\\ \begin{cases} \displaystyle\frac{L-(w_i+w_{i+1}+\cdots+w_j)}{j-i}, & i<j,\\[6pt] +\infty, & i=j. \end{cases} \end{gathered}$$

当 $j=n$，即该行是最后一行时，若 $\tilde{s}(i,n)>1$，则按照上面的末行示意图，将单词之间的空白宽度取为 $1$。因此定义

$$s(i,j)= \begin{cases} \tilde{s}(i,j), & j<n,\\ \min\{\tilde{s}(i,j),1\}, & j=n, \end{cases} \qquad i\le j,$$

并用该值作为单词间距。

将第 $i$ 至第 $j$ 个单词 $(i\le j)$ 排在同一行的成本定义为

$$c(i,j)= \begin{cases} +\infty, & s(i,j)\le0,\\ |s(i,j)-1|, & \text{其他情况}. \end{cases}$$

采用换行位置序列 $k_1,k_2,\ldots,k_l$ 时，整篇文章的排版成本为

$$\begin{aligned} z={}&c(1,k_1)+c(k_1+1,k_2)\\ &+\cdots+c(k_l+1,n). \end{aligned}$$

目标是使 $z$ 最小。回答下列问题。

(1) 考虑图 1 的排版。以字符数作为单词宽度，得到以下数据。

$i$	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$w_i$	2	2	4	9	2	6	13	10	4	3	11	3	5	9

这里忽略了句点 “.”，因此第 14 个单词 instances 的宽度为 $w_{14}=9$。当行宽 $L=30$ 时，求每一行的成本与整篇文章的总成本 $z$。

(2) 说明一种高效计算所有 $(i,j)$（$1\le i\le j\le n$）所对应的 $c(i,j)$ 的方法，并分析其计算复杂度。

(3) 说明通过枚举全部换行位置序列，寻找总成本 $z$ 最小的排版的方法的计算复杂度。

(4) 令 $g(i)$ 表示将第 $i$ 至第 $n$ 个、共 $n-i+1$ 个单词组成的文章排版时的最小成本。写出计算 $g(i)$ 的动态规划递推式。必要时可以设 $g(n+1)=0$。

(5) 说明如何具体计算 $g(1),\ldots,g(n)$，并分析计算复杂度。

(6) 说明如何求出整篇 $n$ 个单词的文章的最小排版成本 $z$，以及实现这一最小值的换行位置序列。

Kai

(1)

図 1 の改行位置は $5,7,11$ なので、各行の単語区間は $[1,5]$、$[6,7]$、$[8,11]$、$[12,14]$ である。

単語区間	単語幅の和	$s(i,j)$	$c(i,j)$
$[1,5]$	$19$	$11/4$	$7/4$
$[6,7]$	$19$	$11$	$10$
$[8,11]$	$28$	$2/3$	$1/3$
$[12,14]$	$17$	$1$	$0$

最終行では $\tilde{s}(12,14)=(30-17)/2=13/2>1$ なので、実際のスペース幅は $1$ となる。したがって、

$$\boxed{z=\frac74+10+\frac13+0=\frac{145}{12}}.$$

(2)

累積和

$$P_0=0,\qquad P_t=\sum_{r=1}^{t}w_r\quad(1\le t\le n)$$

を $\Theta(n)$ 時間で計算する。これにより、各区間の単語幅の和は

$$\sum_{r=i}^{j}w_r=P_j-P_{i-1}$$

と $O(1)$ 時間で得られる。$i<j$ なら、この値から $\tilde{s}(i,j)$、$s(i,j)$、$c(i,j)$ を定義どおり順に計算する。$i=j$ は別に扱い、

$$c(i,i)= \begin{cases} +\infty, & i<n,\\ 0, & i=n \end{cases}$$

とする。最終行以外の 1 単語だけの行は無限大コストであり、最後の 1 単語だけの行は $s(n,n)=\min\{+\infty,1\}=1$ なのでコスト $0$ である。

組の総数は $n(n+1)/2$ だから、全 $c(i,j)$ の計算時間は $\Theta(n^2)$、表として保存する領域も $\Theta(n^2)$ である。以下の計算量は、数値の四則演算・比較を定数時間とする。

(3)

改行可能な位置は $n-1$ 箇所あり、それぞれについて改行するか否かを選ぶので、改行位置系列は

$$2^{n-1}$$

通りある。各候補について先頭から行区間を走査し、前問で計算した $c(i,j)$ を加算する素朴な全列挙法では、1 候補の評価に $O(n)$ 時間を要し、全体は $O(n2^n)$ 時間となる。

なお、共通する先頭部分のコストを保持しながら深さ優先で全候補を生成すれば、全列挙自体は $O(2^n)$ 時間にもできる。いずれも候補数は指数的であり、以下の動的計画法より大きい。

(4)

最初の行に第 $i$ 単語から第 $j$ 単語までを置くと、その行のコストは $c(i,j)$ であり、残りの文章の最小コストは $g(j+1)$ である。よって、

$$\boxed{ \begin{aligned} g(n+1)&=0,\\ g(i)&=\min_{i\le j\le n}\{c(i,j)+g(j+1)\}. \end{aligned} }$$

となる。最初の行の末尾 $j$ を固定したとき、残りが最適でなければ、残りだけを最適な配置に置き換えて全体のコストを減らせるため、この漸化式が成り立つ。

(5)

$g(n+1)=0$ を初期値とし、$i=n,n-1,\ldots,1$ の順に計算する。この順序なら、$g(i)$ の計算に必要な $g(j+1)$ はすべて計算済みである。

g[n + 1] = 0
for i = n, n - 1, ..., 1:
    g[i] = +infinity
    for j = i, i + 1, ..., n:
        value = c(i, j) + g[j + 1]
        if value < g[i]:
            g[i] = value
            next[i] = j

比較する候補数の合計は

$$\sum_{i=1}^{n}(n-i+1)=\frac{n(n+1)}2$$

であるから、動的計画法の時間計算量は $\Theta(n^2)$ である。(2) の前計算を含めても $\Theta(n^2)$ であり、$g$ と next に必要な追加領域は $O(n)$ である。累積和から $c(i,j)$ をその都度計算すれば、コスト表を保存せず、全体の補助領域を $O(n)$ にできる。

(6)

文章全体の最小コストは $g(1)$ である。(5) では、最小値を与える行末 $j$ を next[i] に保存している。同じ最小値を与える候補が複数ある場合は、そのうちの 1 つを保存すればよい。

$i=1$ から始め、$j=\mathrm{next}[i]$ を取り出す。$j<n$ なら $j$ を改行位置として出力し、$i=j+1$ に更新する。$j=n$ なら最終行なので終了する。各更新で $i$ が増加するため、この復元は $O(n)$ 時間で終わる。

$g(1)=+\infty$ の場合は有限コストのレイアウトが存在しないと判定し、改行位置の復元は行わない。

例えば (1) の単語幅と $L=30$ に対しては、最小コストは $g(1)=13/6$、最適な改行位置系列は $6,9,13$（図 2）となる。その各行のコストは順に $0,1/2,5/3,0$ であり、合計は $13/6$ である。

Reference

• 名古屋大学公式入試問題（2016 年度・2015 年 8 月 6 日実施、PDF 9–10 ページ、公式サイトのアーカイブ）