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())
- 今回は、深さ優先探索をした。
- 深さ優先探索の仲間で、深さ制限探索というものがあった。
- 調べる範囲を制限することで、無限ループや、無限に長い経路を調べずに済む
- その代わり、最適性はない。
- これは深さ優先探索にも当てはまる。
- コードを書いてみた。
def Depth_Limited_Search(graph, start, limit):
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本の辺全てが橋である、ことも同値
- 橋というのは、取り除いたらグラフが非連結になる辺。
- 木であることと、N個の頂点とN-1個の辺を持ち連結である、は同値。
木はデータ構造としても面白いし、木(植物)はそれはそれで興味の範疇なので、近いうちに調べたい。
IDA*も気になるが今は触れないでおく。
バイバイ!