Competitive Programing Typical 90 Problem day3

Day3. 

I want to go behind the outward form of inner meaning of each problem.

 

Code is below.

N = int(input())
graph = [[] for i in range(N)]
#グラフを格納するもとを作る
for i in range(N-1):
  a,b = map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  #数字が1大きいので、その分を削る


def Depth_First_Search(graph,start):
  distance = [-1] * N
  #スタート地点からの距離が気になる
  distance[start] = 0
  #スタート地点は距離0とする。(原点)
  candidate = [start]
  #既知の言ってない場所を入れる
  while candidate:
    #全部行くまで続ける
    position = candidate.pop()
    #まだ行っていない場所を最近見たものから行く
    for neighbor in graph[position]:
      #行った場所の近隣を見渡し
      if distance[neighbor] == -1:
        #未知の行ってない場所なら
        candidate.append(neighbor)
        #既知の行ってない場所リストに入れる
        distance[neighbor] = distance[position] + 1
        #距離を知ったので、追加
  return distance

def main():
  start = 0
  first_search = Depth_First_Search(graph, start)
  #0からの距離のリストが返ってくる
  restart = max(enumerate(first_search), key = lambda x : x[1])[0]
  #一番遠いところを調べる
  second_search = Depth_First_Search(graph, restart)
  #そこからの距離のリストが返ってくる
  answer = max(second_search) + 1
  #木の直径が出てくる
  return answer

print(main())

 

  • 今回は、深さ優先探索をした。
    • 深さ優先探索とは、木やグラフを探索するためのアルゴリズム
    • 根(という1点)から始まり、目的のノードに行くか、子が見つかるまで、深く探していく。
    • そこで、バックトラックして、最近の未探索のノードを探す。
      • バックトラックとは、変数の組み合わせを探すときに、部分的組み合わせを排除するときに使える。
      • 一種の深さ優先探索
      • つまり、深さ優先探索の肝は、部分的に何かを調べることで、そこを考えなくて良いようにする、ということ。
      • 別の角度から捉えると、「最近見たものから試しましょう」という気持ちではある。流されやすいタイプ。
      • さらに、早く解に行きつく可能性もある。逆も然り。
    • 再帰的に出来る。
    • 縦型探索と言われる。
  • 深さ優先探索の仲間で、深さ制限探索というものがあった。
    • 調べる範囲を制限することで、無限ループや、無限に長い経路を調べずに済む
    • その代わり、最適性はない。
    • コードを書いてみた。
def Depth_Limited_Search(graphstartlimit):
  distance = [-1] * N
  #スタート地点からの距離が気になる
  distance[start] = 0
  #スタート地点は距離0とする。(原点)
  candidate = [start]
  #既知の言ってない場所を入れる
  while candidate:
    #全部行くまで続ける
    position = candidate.pop()
    #まだ行っていない場所を最近見たものから行く
    for neighbor in graph[position]:
      #行った場所の近隣を見渡し
      if 0 <= distance[neighbor] < limit:
        #ここが、深さの制限を設けている
        candidate.append(neighbor)
        #既知の行ってない場所リストに入れる
        distance[neighbor] = distance[position] + 1
        #距離を知ったので、追加
  return distance
  • さらに、深さ制限探索の派生形として、反復深化深さ優先探索というものがある。
    • 深さ制限探索の制限を徐々に上げていくもの。
    • ノードを初めて調べる順番は、幅優先探索のそれと同じ。
      • どちらも、徐々に調べる深さを上げるから。
    • 根に近いところを頻繁に調べることになるが、それは、計算量が小さいのでそこまで問題ではない。
    • 広範囲で深さが未知のものを調べるには、これが好ましい方法らしい。
      • 深すぎて探索できませんでした、ということが制限によって防げる。
      • かつ、良いところ(何をもって?)まで調べられる。
  • どうやら、これを知識有り全探索にしたもので、IDA*というものがあるらしい。
    • ここは踏み込まないことにする。
  • せっかくなので、について考えてみる。
    • 木であることと、N個の頂点とN-1個の辺を持ち連結である、は同値。
      • 今回はそれを利用した問題だった。
    • また、N-1本の辺全てが橋である、ことも同値
      • 橋というのは、取り除いたらグラフが非連結になる辺。

木はデータ構造としても面白いし、木(植物)はそれはそれで興味の範疇なので、近いうちに調べたい。

IDA*も気になるが今は触れないでおく。

バイバイ!