CS6.006 Problem Set 6を解く - hisyatokaku’s blog

問題はこちら意訳が間違っていたらご指摘ください。

6-1

Renbookという架空の(Facebookのパクリ)webサイトの友達ランク計算の話。

$ER(u, v)\in[0, 1$ ]はuがvに興味を持った度合いを表す。
ユーザ同士の関係は有向グラフによって表される。友達同士はエッジで結ばれている。
「自分( $u_0$ とする)」と、「自分の友達( $u_1$ )の友達( $u_2$ )の...友達( $u_k$ )」との関連度の強さ(教材中ではstrngthと呼ばれている)は、 $S(p)$ で表される。（計算式は教材参照）
上の例で、 $u_0$ と $u_k$ について、 $k$ はvaguenessと呼ばれる。(k-1回友達を挟むことで $u_k$ にたどり着けるというイメージ)

また、

V: ユーザ数
E: 友達ペアの数(エッジの数)

とする。

このような状況において、ユーザ $s$ について、vaguenessが $k$ 以下である全てのユーザの関連度(strength)の中で、最も高いものを $O(kE+V)$ で計算するプログラムを記述せよ、という問題。

幅優先探索をすればよいのでは？自分の考えたpseudo-codeを書く。

def find_highest_strength(user = s、k):
  queue = []
  answer = 0
  seen = set()
  queue.append((user, 1, 0))
  while queue: 
    cur_user, strength, vagueness = queue.pop(0) # (1)
    seen.add(cur_user)
    if vagueness > k:
      break
    friends = get_friends(cur_user)
    for friend in friends: # (2)
      if friend in seen:
        continue
      new_strength = strength * ER(cur_user, friend)
      new_vagueness = vagueness + 1
      answer = max(answer, new_vagueness)
      queue.append((friend, new_strength, new_vagueness))

一見してO(1)で終わらなそうな箇所は(1), (2)である。 (1)はpythonのdequeueを使えばO(1)でできるので、コードを改良することは簡単である。 (pythonのリストの先頭を削除すると、先頭より後ろの要素を全て一つ前にずらす処理が行われるため、O(N)かかる(N:リストの長さ)ので、それを回避するためのdequeueというライブラリがある。)

(2)は各友達に対してループを回すので、cur_userのもつ友達の数だけループが実行される。トータルでは全ての友達の数だけループが実行されるので、 $O(E+V)$ の実行時間がかかる。 $O(kE+V)$ としている理由がわからない。。。

解答

全然違った。解答pdfからのスクショ。以下のような場合で、BがAより先に探索された場合、Aの距離は(1ではなく)2としてカウントされてしまい、 $k=2$ としたときに、tが拾えなくなる可能性がある。 f:id:hisyatokaku:20191216122501p:plain

ポイントは、startからendまでのコストだけでなく、pathの長さ(何本の辺を渡ったか)もk以下であるという制約を気にする必要がある。

どうすれば良いかというと、 - ベルマンフォードのイテレーション(iterとする)を|V|-1回の代わりにk回まわす。 - ベルマンフォードの更新式(d[v] = d[u] + w(u, v)のところ)で、前回のiterの値のみを使う。

二点目について詳しく言うと、i番目のiterで、例えばe1, e2, ..., eMという順で更新するとする。e4を更新するときに、i番目のe1, e2, e3の更新の結果ではなく、i-1番目のe1, e2, e3の更新の結果を使う必要があるということ。こうしないと、長さがk以上の解が見つかってしまうらしい。(解答PDF参照)

6-2

(a)

ライブラリの依存性解決の問題。ライブラリの数が全部でVだけあり、それぞれがどれか別のライブラリに依存しており、そのような依存関係がEだけあるとする。 $O(V+E)$ でどのような順番でライブラリを入れていけば良いかを答える。

問題文が示す通り、循環依存はないので、DAGである。つまり閉路がない有向グラフ。これはトポロジカルソートできるので、トポロジカルソートすると、末尾のノードが最初に依存されているノードになるので、末尾からインストールしていけばよい。

(b)

上の問題において、V個あるライブラリのうち(V-P)個がすでにインストールされている場合、 $O(P+PD)$ でライブラリのインストール順を答えろという問題。ここで、一つのライブラリは最大でもD個のライブラリにのみ依存しているとする。トポロジカルソートは、あるノードについて子供がすべて探索済みになったらそのノードをソート済みリストに追加するという考えで行えるため、深さ優先探索を行う。 pythonコードは以下。

L = [] #ソート済みリスト
visited = set()
def topological_sort(lib):
  depends = get_dependency(lib)
  visited.add(lib)
  for dep in depends: # 高々D回のループ
    if dep in visited:
      continue
    topological_sort(dep)
  L = [lib] + L

for lib in libraries:
  if installed(lib):
    continue # V-P回実行される。
  topological_sort(lib) # この時点でlibの子供は再帰的に探索し終わっているはずなので、このタイミングでソート済みリストに加えれば良い。P回実行される。

時間計算量について。 - 全てのノードを見る必要があるので、topological_sortは最大でP回実行される。 - 全てのエッジを見る必要があるので、topological_sortの中にある高々D回のループはP回実行されうる。よって時間は $O(PD)$ かかる。

以上から $O(P + PD)$

補足：O(P+PD) = O(PD)じゃないか？と思ったが、例えば実はDがゼロだったときを考えるとよい。依存関係が全くない状況だが、全てのノードについて依存関係を調べなくてはいけないので、topological_sort()内のvisited.add()部分のみが実行される。このとき、O(PD)にD=0を代入するとO(0)になってしまうので間違い。

解答

自分の回答では、depにinstallされているものがあった場合も探索してしまうので間違いな気がする。解答例の計算量がP+PDとなる理由がよくわからない。。。

6-3

2×2のルービックキューブを深さ優先探索(BFS)で解く問題。 startの状態とendの状態を受け取り、startからendに到るまでの最短道筋を返す。

Speeding Up Dijkstraにも紹介されているように、startから素直に幅優先していくのではなく、startとendの両方から交互に幅優先探索していくという実装が必要。

理由：

ルービックキューブは一つの盤面に対し6通りの動かし方がある
→ $i$ 回動かしたあとの状態が[tex:6ⁱ]通りある。
→ 2×2のルービックキューブは最大で14回で揃えられる（らしい）ため、最大で[tex:6¹⁴=78,364,164,096]、つまりだいたい[tex:10⁹]通りの状態数がある。

これらを全部探索するのは時間がかかるが、終わりの状態に注目すると、終わりの状態の一個前の状態は $6$ 通り。i個前の状態は[tex:6ⁱ]通りである。

つまり、始まりと終わりそれぞれの方向から探索していくと、最悪でも、始まりから7回動かしたあたりで、終わりから7回動かした状態と合流する。合流した状態を介してstartからendまで一本のルートがつながるので、そのルートが答えである。このとき、[tex:6⁷ = 279,936]、だいたい[tex:10⁵]なので、探索する状態は10000分の1で済む。

これを実装すればよい。普通のBFSでは、

visited: 訪れた状態を覚えておく変数。
queue: まだ訪れてなくて、次に訪れるべき状態を入れるキュー。
state: queueにつっこむ中身。盤面はもちろん、１つ前の盤面からの動きを保持する必要がある。

が必要。最初の思考では、

forward_visited
backward_visited
forward_queue
backward_queue
state

が必要だと思ったが、queue = [(start_state), (end_state)]として前からの状態と後ろからの状態を交互に入れれば、queueは一つで済む。また、難しかったのは、前後それぞれ7回ずつ探索して答えがみつからなかったら、探索を打ち切るということ。解答の実装では、以下のように、Noneをappendして、i回動かした状態とi+1回動かした状態の間に区切りをいれている。

for i in range(7)
  queue = [(start_state), (end_state), None]
  while True:
    state = queue.popleft()
    if not state:
      queue.append(None)
      break
   else:
      ...探索部分...

また、余談だが、aがNoneかどうか調べる時は、a==Noneよりa is Noneを使う。'=='は__eq__メソッドにより書き換え可能なので、人が書いたコードにバグがあった場合、意図せぬ結果となる。isはオブジェクトが一致するかどうか比較しているので、唯一のオブジェクトであるNoneに対して比較することができる。

6-4

ダイクストラ法を実装する。ヘルパ関数が用意されているのでそれを活用すればいいのだが、うまくできなかった。結局解答を見た。

総じて、あまりできなかったので解き直す必要あり。