跳到主要内容

名古屋工業大学 工学研究科 工学専攻 情報工学系 2020年8月実施 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

I　頂点集合 VV を持つ有向グラフが与えられているものとする。図1のアルゴリズムは開始頂点 s∈Vs\in V から任意の v∈Vv\in V までの経路を探し，経路上の辺のコストの和を配列 DD の各要素 D[v]D[v] に保存するものである。このとき，次の (1)〜(5) の問いについて答えよ。ただし，cost⁡(u,v)\operatorname{cost}(u,v) は u∈Vu\in V から v∈Vv\in V への有向辺 (u,v)(u,v) のコスト（正の実数値）を表す関数，∅\varnothing は空集合，X∪YX\cup Y は X,YX,Y の和集合とする。アルゴリズムの4行目において最小の頂点が複数存在する場合は，頂点のアルファベット順で選ぶものとする。また，(4) と (5) において，2つの経路上のすべての頂点が同一の順序で現れる場合にのみ，それらを同じ経路とみなす。

1  for (v ∈ V) { D[v] ← ∞ }
2  X ← ∅; D[s] ← 0
3  while (X ≠ V) {
4      u を D[v] (v ∉ X) が最小となる頂点とする
5      X ← X ∪ {u}
6      for (v ∈ ‘u から v への有向辺が存在する頂点 v の集合’) {
7          D[v] ← min(D[v], D[u] + cost(u,v))
8      }
9  }

図1：アルゴリズム

(1) 図1のアルゴリズムを図2と図3のグラフに適用する。whileループ中の4〜8行目が一回終了した時点と，アルゴリズムが終了した時点での D[v] (v∈V)D[v]\ (v\in V) をまとめた表1と表2の空欄 (A)〜(K) に入る値をそれぞれ答えよ。ただし，図中，各有向辺付近の数値が辺のコストである。

図2：グラフ1　図3：グラフ2

表1：グラフ1での配列 DD の値

D[s]D[s]D[a]D[a]D[b]D[b]
1回目(A)33(B)
終了時(C)(D)11

表2：グラフ2での配列 DD の値

D[s]D[s]D[a]D[a]D[b]D[b]D[c]D[c]
1回目(E)(F)(G)∞\infty
終了時(H)(I)(J)(K)

(2) 図1のアルゴリズムに関する以下の (ア)〜(エ) の記述の，それぞれ正誤を答えよ。

(ア) このアルゴリズムは，クラスカル法と呼ばれる。

(イ) グラフが閉路を持つ場合，アルゴリズムが終了しない可能性がある。

(ウ) アルゴリズムが終了した時点での D[v] (v∈V)D[v]\ (v\in V) の値が，ss から任意の v∈Vv\in V へ至る経路の最小コストとなっている。

(エ) アルゴリズムが実行される過程において，D[v] (v∈V)D[v]\ (v\in V) の値が増加することはない。

(3) 頂点集合 VV のサイズを nn，有向辺の総数を mm としたとき，図1のアルゴリズムの計算コストとして以下の (a)〜(d) から最もタイトなものを選び，(a)〜(d) の記号で答えよ。ただし，配列 DD の各要素やコスト cost⁡(u,v)\operatorname{cost}(u,v) へのアクセスと X≠VX\ne V の判定は O(1)O(1)，4〜5行目の操作は O(n)O(n) とし，6〜8行目のfor文は uu の出次数に比例する計算量で実行されるものとする。

(a) O(m+n2)(b) O(m2+n2)(c) O(mn+n2)(d) O(m2+n)\begin{array}{ll} \text{(a)}\ O(m+n^2)&\text{(b)}\ O(m^2+n^2)\\ \text{(c)}\ O(mn+n^2)&\text{(d)}\ O(m^2+n) \end{array}

(4) あるグラフに対して，図1のアルゴリズムが終了した時点で ss から各頂点 vv への最小コストが D[v]D[v] として得られたものとする。以下の問い (ア) と (イ) に答えよ。ただし，経路上の頂点 vv の直前の頂点とは，その経路上で vv の1つ前に通過する頂点である。例えば，頂点 s,a,b,cs,a,b,c の順に移動する経路があった場合，cc の直前の頂点は bb のことを指す。

(ア) 開始頂点 ss から各 vv（ただし，v≠sv\ne s）までコスト D[v]D[v] で至る各経路に対して，最後の頂点 vv の直前の頂点を配列 PP の各要素 P[v]P[v] に保存できたものとする。いま，P[a]=s,P[b]=s,P[c]=d,P[d]=bP[a]=s,P[b]=s,P[c]=d,P[d]=b であった場合，ss から dd へ至る最小コスト経路として PP が示している頂点の移動順を以下の (a)〜(d) から適切なものを選び，(a)〜(d) の記号で答えよ。

(a) s,a,b,d(b) s,b,c,d(c) s,b,d(d) s,c,d\begin{array}{ll} \text{(a)}\ s,a,b,d&\text{(b)}\ s,b,c,d\\ \text{(c)}\ s,b,d&\text{(d)}\ s,c,d \end{array}

(イ) 有向グラフ上に同じコストの異なる経路がいくつか存在する場合がある。ss から各 vv（ただし，v≠sv\ne s）までコスト D[v]D[v] で至るすべての経路に対して，最後の頂点 vv の直前の頂点を配列 PP の各要素 P[v]P[v] に集合として保存できたものとする。例えばもし，cc に至る最小コストの経路が s,a,b,cs,a,b,c と s,a,cs,a,c の2つであった場合，P[c]={a,b}P[c]=\{a,b\} となる。いま，P[a]={s},P[b]={s},P[c]={s,a,b},P[d]={b,c}P[a]=\{s\},P[b]=\{s\},P[c]=\{s,a,b\},P[d]=\{b,c\} であったとして，配列 PP が示す ss から dd への異なる最小コスト経路はいくつあるか答えよ。

(5) 図1のアルゴリズムを修正して，同じコストの異なる経路の数を保存することを考える。配列 NN の各要素 N[v]N[v] には頂点 vv に到達する同一コストの経路の数を保存する。v≠sv\ne s については N[v]=0N[v]=0，N[s]=1N[s]=1 として初期化されているものとする。図1のアルゴリズムの7行目を以下の図4に置き換えるとき，空欄 (A) と (B) に入る式をそれぞれ答えよ。ただし，N[v]N[v] と N[u]N[u] のいずれか，または両方を用いた式とすること。

if (D[v] > D[u] + cost(u,v)) {
    D[v] ← D[u] + cost(u,v)
    N[v] ← (A)
} else if (D[v] = D[u] + cost(u,v)) {
    N[v] ← (B)
}

図4：図1のアルゴリズムの7行目の変更後

题目描述​

I　给定顶点集合为 VV 的有向图。图1的算法查找从起点 s∈Vs\in V 到任意 v∈Vv\in V 的路径，并将路径上各边成本之和存入数组 DD 的元素 D[v]D[v]。请回答以下 (1) 至 (5) 问。函数 cost⁡(u,v)\operatorname{cost}(u,v) 表示从 u∈Vu\in V 指向 v∈Vv\in V 的有向边 (u,v)(u,v) 的成本（正实数）；∅\varnothing 表示空集，X∪YX\cup Y 表示 X,YX,Y 的并集。第4行如有多个最小值顶点，则按顶点的字母顺序选择。在第 (4)、(5) 问中，仅当两条路径的所有顶点以相同顺序出现时，才视为同一路径。

1  for (v ∈ V) { D[v] ← ∞ }
2  X ← ∅; D[s] ← 0
3  while (X ≠ V) {
4      令 u 为使 D[v] (v ∉ X) 最小的顶点
5      X ← X ∪ {u}
6      for (v ∈ {存在从 u 到 v 的有向边的顶点 v}) {
7          D[v] ← min(D[v], D[u] + cost(u,v))
8      }
9  }

图1：算法

(1) 将图1算法分别用于图2和图3。表1、表2汇总 while 循环中第4至8行完成一次时与算法结束时的 D[v] (v∈V)D[v]\ (v\in V)。请分别填入 (A) 至 (K)。图中各有向边附近的数值表示该边的成本。

图2：图1　图3：图2

表1：第一个图中数组 DD 的值

D[s]D[s]D[a]D[a]D[b]D[b]
第1次(A)33(B)
结束时(C)(D)11

表2：第二个图中数组 DD 的值

D[s]D[s]D[a]D[a]D[b]D[b]D[c]D[c]
第1次(E)(F)(G)∞\infty
结束时(H)(I)(J)(K)

(2) 分别判断关于图1算法的下列 (ア) 至 (エ) 陈述是否正确。

(ア) 该算法称为 Kruskal 算法。

(イ) 若图中含环，算法可能无法结束。

(ウ) 算法结束时，D[v] (v∈V)D[v]\ (v\in V) 的值为从 ss 到任意 v∈Vv\in V 的路径的最小成本。

(エ) 在算法执行过程中，D[v] (v∈V)D[v]\ (v\in V) 不会增大。

(3) 设顶点集合 VV 的大小为 nn，有向边总数为 mm。从 (a) 至 (d) 中选择图1算法计算成本最紧的界，以相应字母作答。假设访问 DD 的各元素、访问成本 cost⁡(u,v)\operatorname{cost}(u,v) 及判断 X≠VX\ne V 均需 O(1)O(1)；第4至5行操作需 O(n)O(n)；第6至8行 for 循环的计算量与 uu 的出度成正比。

(a) O(m+n2)(b) O(m2+n2)(c) O(mn+n2)(d) O(m2+n)\begin{array}{ll} \text{(a)}\ O(m+n^2)&\text{(b)}\ O(m^2+n^2)\\ \text{(c)}\ O(mn+n^2)&\text{(d)}\ O(m^2+n) \end{array}

(4) 对某个图，图1算法结束后得到的 D[v]D[v] 为从 ss 到各顶点 vv 的最小成本。回答 (ア)、(イ)。路径上顶点 vv 的前驱，是在该路径中通过 vv 之前经过的那个顶点。例如按 s,a,b,cs,a,b,c 顺序移动时，cc 的前驱为 bb。

(ア) 对从起点 ss 到各 v≠sv\ne s、成本为 D[v]D[v] 的路径，设末顶点 vv 的前驱已存入数组 PP 的元素 P[v]P[v]。若 P[a]=s,P[b]=s,P[c]=d,P[d]=bP[a]=s,P[b]=s,P[c]=d,P[d]=b，请选择 PP 所表示的从 ss 到 dd 的最小成本路径的顶点顺序，以 (a) 至 (d) 作答。

(a) s,a,b,d(b) s,b,c,d(c) s,b,d(d) s,c,d\begin{array}{ll} \text{(a)}\ s,a,b,d&\text{(b)}\ s,b,c,d\\ \text{(c)}\ s,b,d&\text{(d)}\ s,c,d \end{array}

(イ) 有向图中可能存在多条成本相同的不同路径。对从 ss 到各 v≠sv\ne s、成本为 D[v]D[v] 的所有路径，设其末顶点 vv 的前驱作为集合存入 P[v]P[v]。例如，到 cc 的最小成本路径只有 s,a,b,cs,a,b,c 与 s,a,cs,a,c 两条时，P[c]={a,b}P[c]=\{a,b\}。若 P[a]={s},P[b]={s},P[c]={s,a,b},P[d]={b,c}P[a]=\{s\},P[b]=\{s\},P[c]=\{s,a,b\},P[d]=\{b,c\}，求数组 PP 所表示的从 ss 到 dd 的不同最小成本路径数。

(5) 修改图1算法，以保存成本相同的不同路径数。数组元素 N[v]N[v] 保存到达顶点 vv 的同成本路径数；初始时，对 v≠sv\ne s 有 N[v]=0N[v]=0，并有 N[s]=1N[s]=1。将图1算法第7行替换为图4时，分别填入 (A)、(B) 中的表达式。表达式须使用 N[v]N[v] 与 N[u]N[u] 中的一个或两个。

if (D[v] > D[u] + cost(u,v)) {
    D[v] ← D[u] + cost(u,v)
    N[v] ← (A)
} else if (D[v] = D[u] + cost(u,v)) {
    N[v] ← (B)
}

图4：图1算法第7行的替换代码

Kai​

(1)​

グラフ 1 では最初に ss を選び、

D[a]=3,D[b]=1D[a]=3,\qquad D[b]=1

となる。次に bb を選ぶと

D[a]=min⁡(3,1+1)=2D[a]=\min(3,1+1)=2

である。したがって、

(A)=0, (B)=1, (C)=0, (D)=2\boxed{(A)=0,\ (B)=1,\ (C)=0,\ (D)=2}

となる。

グラフ 2 では最初に ss を選び、

(D[s],D[a],D[b],D[c])=(0,1,3,∞)(D[s],D[a],D[b],D[c])=(0,1,3,\infty)

となる。その後 a,b,ca,b,c の順に選ばれ、

D[b]=min⁡(3,1+1)=2,D[c]=min⁡(1+4,2+2)=4.D[b]=\min(3,1+1)=2,\qquad D[c]=\min(1+4,2+2)=4.

よって、

(E)=0,(F)=1,(G)=3,(H)=0,(I)=1,(J)=2,(K)=4.\boxed{\begin{aligned} (E)&=0,&(F)&=1,&(G)&=3,&(H)&=0,\\ (I)&=1,&(J)&=2,&(K)&=4. \end{aligned}}

である。

(2)​

  1. 誤\boxed{\text{誤}}。これはクラスカル法ではなくダイクストラ法である。
  2. 誤\boxed{\text{誤}}。各反復で新しい頂点が XX に加わるため、高々 ∣V∣|V| 回で終了する。
  3. 正\boxed{\text{正}}。すべての辺のコストが正なので、確定した距離は最短距離である。
  4. 正\boxed{\text{正}}。更新は最小値との置換だけなので、D[v]D[v] は増加しない。

(3)​

4--5 行目は nn 回反復され、合計 O(n2)O(n^2) である。6--8 行目の総計は出次数の総和より O(m)O(m) である。したがって、

O(n2)+O(m)=O(m+n2)O(n^2)+O(m)=O(m+n^2)

であり、答えは (a)\boxed{\text{(a)}} である。

(4)​

(ア)​

P[d]=bP[d]=b、P[b]=sP[b]=s を逆向きにたどると d←b←sd\leftarrow b\leftarrow s である。よって、

s→b→d(c)\boxed{s\to b\to d}\qquad\boxed{\text{(c)}}

となる。

(イ)​

各頂点までの経路数を C(v)C(v) とすると、

C(s)=1,C(a)=C(b)=1,C(s)=1,\qquad C(a)=C(b)=1,
C(c)=C(s)+C(a)+C(b)=3,C(d)=C(b)+C(c)=4.C(c)=C(s)+C(a)+C(b)=3,\qquad C(d)=C(b)+C(c)=4.

したがって、答えは 4\boxed{4} 本である。

(5)​

より短い経路が得られた場合は従来の経路数を捨て、uu までの経路数で置き換える。同じ距離の経路が得られた場合は、その経路数を加える。よって、

(A)=N[u],(B)=N[v]+N[u]\boxed{(A)=N[u]},\qquad \boxed{(B)=N[v]+N[u]}

である。

Reference​

本页目录