中央大学 理工学研究科 情報工学専攻 2024年8月実施 問題II

标签：

• 中央大学
• 关键路径法
• 拓扑排序

Author

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

Description

問題 I は必答。問題 II～V のうち，2 問を選んで解答すること。

複数の作業からなるプロジェクトを考える。作業間に順序関係が与えられることがあり，作業 A が作業 B の先行作業の場合，作業 A が終わってから作業 B を開始できる。4 つの作業 A，B，C，D からなるプロジェクトをグラフで表現した例を図 1 に示す。各辺には作業名と所要日数が付与される。図 1 において作業 C を始めるには作業 B が終わる必要があり，作業 D を始めるには作業 A と作業 C が終わる必要がある（このとき作業 B も必ず終わっている）。また，図 1 のプロジェクトの最短所要日数は 8 日である。以下の問に答えよ。

1. 図 2 のグラフで表されるプロジェクトにおいて，(1) から (6) を求めよ。解答は答えのみを記すこと。

   (1) 作業 K を始める前に必ず終わっている作業（複数ある場合はすべて答えよ。以下の設問も同様。）

   (2) 作業 F が終わってからしか始められない作業

   (3) プロジェクトの最短所要日数

   (4) その作業の所要日数が 1 日増えた場合にプロジェクトの最短所要日数が増加する作業

   (5) その作業の所要日数が 2 日増えてもプロジェクトの最短所要日数が変化しない作業

   (6) その作業の所要日数が 2 日減った場合にプロジェクトの最短所要日数が減少する作業

2. 図 1 と図 2 のグラフでは，すべての辺は作業に対応していた。しかし，作業間に与えられる順序関係によっては，作業に対応しない辺（ダミー辺とよび，破線で記す）を用いてグラフを書く必要がある。表 1 に示す 4 つの作業と順序関係をもつプロジェクトに対するグラフの一例を図 3 に示す。次の点に注意をして，表 2 に示すプロジェクトに対応するグラフを記せ。

   • 入ってくる辺のない頂点と，出ていく辺のない頂点がどちらもちょうど 1 つ存在するグラフを記すこと。
   • 作業に対応する辺には作業名のラベルをつけること（本設問では各作業の作業日数は省略し，記載の必要はない）。
   • 必要があれば順序関係のみを表すダミー辺を用いても良い。用いる場合は破線で記すこと。
   • 2 つの頂点の間に複数の辺（並行辺）は存在してはいけない。
   • 頂点の数ができるだけ少ないグラフを記すこと。

   表 1

   作業名	先行作業
   A	なし
   B	なし
   C	A，B
   D	B

   

   表 2

   作業名	先行作業	作業名	先行作業
   A	なし	G	B
   B	A	H	E
   C	B	I	C，F
   D	なし	J	G，H
   E	A，D	K	I，J
   F	B	L	J

3. プロジェクトを表す（図 2 のような）グラフが与えられたとき，(1) と (2) を求める効率的なアルゴリズムをそれぞれ記せ。アルゴリズムは，自然言語，プログラム（疑似コード），数式などのうち必要なものを（組み合わせて）用いて詳しく記述すること。(1) と (2) を求めるアルゴリズムにおいて重複する部分は繰り返して書く必要はない。

   (1) プロジェクトの最短所要日数

   (2) その作業の所要日数が $p$ 日増えてもプロジェクトの最短所要日数が変化しない作業

   ただし，$p$ はあらかじめ与えられる定数ではなく，様々な値を考えられるように工夫すること。

题目描述

问题 I 必答；问题 II～V 中选答 2 题。

考虑由多项工作组成的项目。工作之间可能存在先后关系；若工作 A 是工作 B 的前置工作，则只有 A 完成之后才能开始 B。图 1 给出了由 A、B、C、D 四项工作组成的项目的图表示，每条边标有工作名称及所需天数。在图 1 中，开始 C 之前必须完成 B；开始 D 之前必须完成 A 和 C（此时 B 也必然已经完成）。图 1 中项目的最短工期为 8 天。回答下列问题，所用图 1～图 3 如上。

1. 对图 2 所示项目，求以下 (1)～(6)。只需写出答案。

   (1) 在开始 K 之前必然已经完成的工作（若有多项，须全部列出；以下各问同样如此）。

   (2) 只有在 F 完成之后才能开始的工作。

   (3) 项目的最短工期。

   (4) 当该工作的工期增加 1 天时，会导致项目最短工期增加的工作。

   (5) 即使该工作的工期增加 2 天，项目最短工期仍不变的工作。

   (6) 当该工作的工期减少 2 天时，会导致项目最短工期减少的工作。

2. 图 1 和图 2 中的所有边均对应实际工作。但某些工作先后关系需要引入不对应实际工作的边，这种边称为虚边，并以虚线表示。表 1 给出了 4 项工作及其先后关系，图 3 是其图表示的一例。请按下列要求画出表 2 项目的对应图。

   • 恰好有一个没有入边的顶点，以及一个没有出边的顶点。
   • 对应实际工作的边须标注工作名称，本问省略工作天数，不必标注。
   • 可以按需使用仅表示先后关系的虚边；使用时须画成虚线。
   • 两个顶点之间不得存在多条边，即不得有平行边。
   • 顶点数量须尽可能少。

   表 1

   工作名	前置工作
   A	无
   B	无
   C	A、B
   D	B

   表 2

   工作名	前置工作	工作名	前置工作
   A	无	G	B
   B	A	H	E
   C	B	I	C、F
   D	无	J	G、H
   E	A、D	K	I、J
   F	B	L	J

3. 给定一个表示项目的图（如图 2），分别详细说明求以下两项的高效算法。可以结合自然语言、程序（伪代码）、公式等进行说明。两个算法中共同的部分不必重复写出。

   (1) 项目的最短工期。

   (2) 即使该工作的工期增加 $p$ 天，项目最短工期仍不变的工作。

   其中，$p$ 不是事先给定的常数，须设计成能够考虑多种不同的 $p$ 值。

Kai

1.

設問	答え
(1)	A，B，C，E，F，I
(2)	I，J，K，L，M，N
(3)	24 日
(4)	A，B，C，E，G，H，K，L，N
(5)	D，J，M
(6)	A，N

2. 頂点数を最小にしたグラフ

次のグラフは 11 頂点からなり，破線の $2\to3$，$5\to6$，$9\to10$ がダミー辺である。

図：祭音Myyura。

各辺を列挙すると次の通りである。

作業	辺	作業	辺
A	$1\to2$	G	$4\to8$
B	$2\to4$	H	$7\to8$
C	$4\to6$	I	$6\to10$
D	$1\to3$	J	$8\to9$
E	$3\to7$	K	$10\to11$
F	$4\to5$	L	$9\to11$

$2\to3$ により E は A，D の両方を待ち，$5\to6$ により I は C，F の両方を待つ。K は I，J の両方を待つが，L は J の完了だけで開始できるため，J の終点 9 と I，J の合流点 10 を分けて $9\to10$ を置く。始点は 1，終点は 11 のみであり，並行辺もない。

最小性。 各作業の開始に必要な全先行作業を，間接的なものも含めて列挙すると，次の 9 種類になる。

始まる作業	完了が必要な作業全体
A，D	$\varnothing$
B	A
C，F，G	A，B
E	A，D
H	A，D，E
I	A，B，C，F
J	A，B，D，E，G，H
L	A，B，D，E，G，H，J
K	A，B，C，D，E，F，G，H，I，J

同一頂点から始まる作業は同じ先行条件をもつので，これらには少なくとも 9 個の異なる開始頂点が必要である。さらに作業が始まらない終点が必要なので，少なくとも 10 頂点を要する。

もし 10 頂点だけなら，その頂点はこの 9 種類の開始頂点と終点で尽くされる。C と F はともに I の先行作業であるため，それぞれの終点から I の始点へ到達できなければならない。この 10 頂点の候補中で，C または F の完了後にあって I の開始以前に置けるのは，I の始点だけである。他の開始頂点を終点とすると，別の作業に C または F という不要な先行条件を課すか，I より後の頂点になってしまう。従って C，F は始点も終点も同じ並行辺となり，条件に反する。よって少なくとも 11 頂点が必要であり，上図が最小である。

3. (1) 最短所要日数

グラフを $G=(V,E)$，始点を $s$，終点を $t$，辺 $e=(u,v)$ の作業日数を $d_e\ge0$ とする。作業順序を表すのでグラフは有向非巡回グラフである。まずトポロジカル順序を求める。

始点から頂点 $v$ までの最長経路長を $E(v)$ とし，$E(s)=0$ とする。各頂点をトポロジカル順序で処理し，

$$E(v)=\max_{(u,v)\in E}\{E(u)+d_{uv}\}$$

を計算する。これは，$v$ に入るすべての作業が終了する最も早い時刻である。従って求める日数は

$$\boxed{T=E(t)}.$$

どの実行計画でも各経路上の作業を順番に行う必要があるので，$T$ 未満では完了できない。一方，各作業を始点の時刻 $E(u)$ に開始すればすべての順序条件を満たし，時刻 $T$ に完了する。よってこの下界は達成できる。トポロジカルソートと計算を合わせた時間計算量は $O(|V|+|E|)$ である。

3. (2) 各作業が許容できる増加日数

頂点 $v$ から終点までの最長経路長を $R(v)$ とする。$R(t)=0$ から，逆トポロジカル順序で

$$R(u)=\max_{(u,v)\in E}\{d_{uv}+R(v)\}$$

を計算する。辺 $e=(u,v)$ を通る最長経路の長さは $E(u)+d_e+R(v)$ である。そこで，その作業の余裕日数を

$$\sigma_e=T-E(u)-d_e-R(v)\ge0$$

と定義する。

この作業だけを $p\ge0$ 日延ばすと，その辺を通る経路はすべて $p$ 日長くなり，通らない経路は変わらない。ゆえに変更後の日数は

$$T_e(p)=\max\{T,\ E(u)+d_e+R(v)+p\}.$$

従って答えとなる作業の条件は

$$\boxed{\sigma_e\ge p}.$$

様々な $p$ に対応するため，まず全辺の $\sigma_e$ を一度だけ求め，余裕日数の昇順に作業を並べて保存する。各問い合わせでは二分探索で $\sigma_e\ge p$ を初めて満たす位置を求め，そこから末尾までの作業を出力する。前処理は $O(|V|+|E|\log|E|)$，1 回の問い合わせは，出力する作業数を $k$ として $O(\log|E|+k)$ であり，$p$ を変えるたびに最長経路を計算し直す必要はない。ダミー辺がある場合は日数 0 として計算に含め，作業一覧からは除く。

Reference

• 中央大学 2025年度 夏季一般入学試験・情報工学 公式問題（冊内 p.75／PDF 第76頁）