Q&A
Nがどの程度の値でエラーになるのかを記載ください。
また、提示コードのおおまかな動きについての説明、あるいはコード作成するために参考にしたサイトなどの情報も記載されると回答得られやすくなるかと思います。
Python3で木グラフの直径を求めるために以下のプログラムを書いたのですが、入力値Nが大きすぎるためにリスト作成に時間がかかり、メモリエラーとなってしまいます。
アドバイスを頂けないでしょうか。
頂点の数が(2**N)-1 の木グラフの直径を求めよという問題です。
よろしくお願いします。
from collections import deque N = int(input()) def bfs(X): distance = [-1]*(2**N) distance[0] = 0 distance[X] = 0 d=deque() d.append(X) while d: v = d.popleft() if 2**(N-1) -1<= v and v <= 2**N-1 and v!=1: g = [[v//2,v]] elif v == 1: g = [[2,2],[3,3]] else: g = [[v//2,v],[v*2,v*2],[v*2+1,v*2+1]] for x, y in g: if distance[x] is not -1: continue distance[x] = distance[v] + y d.append(x) max_d = max(distance) return distance.index(max_d), max_d end2, d_end1_end2 = bfs(2**N-1) print(d_end1_end2)
> メモリエラーとなってしまいます。
エラーメッセージとスペックの記載をしてください。
GoogleのColaboratory上では時間がかかるものの、Nが大きな値でも計算できたのですが、今回の課題では制限時間と使えるメモリが制限されている環境で実行しないといけないので、上のプログラムだとエラーが出る次第です。
時間とメモリについては正確に答えることはできませんが、根本的に解法を改めないと上のアルゴリズムでは上手くいかないと思います。
木の始点からの距離を保存しておくリストdistanceを何とかして小さくできればと考えているのですが。
> 今回の課題では制限時間と使えるメモリが制限されている環境で実行しないといけないので
制限があるのであれば質問に追記しましょう。また「N」の上限は何ですか？
2<=N<=60の整数です。
Nは不明だがエラーが出るという事でしょうか？もしそうであれば
その課題の内容、実行環境、エラー内容を具体的に提示ください（AtCoderの「～」問題など）。
そもそも「頂点の数が(2**N)-1 の～」とありますがそれは正しいですか？
「頂点の数がNの～」ではありませんか？
頂点数は2**N -1であっています。
つまり縦にN段ある２分木です。
2<=N<=60の整数があてはまるので、膨大な数になります。
「２分木」という制約があるのであれば明示すべきと思います。
さらに重ねていいますが、その課題の内容（出典）、実行環境、エラー内容を具体的に提示すると回答が得られやすくなるかもしれません。
そもそも「頂点の数が(2**N)-1 の木グラフ」の接続情報はどのように与えられるのでしょうか？
N=60の場合は相当な情報量になるかと思いますが。
説明不足で申し訳ないです。
始点を1として、２段目に2,3に分岐し、３段目で4,5,6,7に分岐、４段目で8,9,10,11,12,13,14,15に分岐といった感じで、N段目には2**(N-1)から2**N-1の頂点が並ぶ図になります。
1から2(重み=2),3(3)に分岐、2から4(4),5(5)、3から6(6),7(7)に分岐といった感じです。
[ 1 2] [ 1 3] [ 2 4] [ 2 5] [ 3 6] [ 3 7] [ 4 8] [ 4 9] [ 5 10] [ 5 11] [ 6 12] [ 6 13] [ 7 14]
[ 7 15] [ 8 16] [ 8 17] [ 9 18] [ 9 19]...
各辺の重みは1-2をつなぐ辺で2、4-8をつなぐ辺で8のように、子の頂点の番号が重みになります。
接続情報は単純なので、if文でwhile d: の中に表しています。
それらの、この課題のより正確な制約および、それにもとづいた提示コードの動作（接続情報は単純なので～といった部分など）についての説明を、質問本文に追記、反映させてください。
ちなみにN=3や4といった単純な場合の答えがいくらになるのかも記載ください。
回答1件
0
ベストアンサー
ノード数が2**N-1と非常に大きくなるので、全ノードのデータを用意して解くことはできません。
直感ですが、以下の作戦でいけるのではないかと思います。
- 右下のノード(番号が2**N - 1のもの)を出発点にする。
- 出発点からx段だけ親をたどり、そこから1回だけ左の子ノードを選択する。
- 以降、末端ノードに到達するまで右ノードを選択し続けて直径を計算する。
これを全てのxについて繰り返す。
たとえば、N=4の場合
出発点のノードは15
- 出発点から1つ上の親に上がって左と選択: 15-7-14という経路になり直径は => 29
- 出発点から2つ上の親に上がって左右と選択: 15-7-3-6-13 => 41
- 出発点から3つ上の親に上がって左右右と選択: 15-7-3-1-2-5-11 => 43
この中から最大の43が答え。
N=24までは質問者さんのコードと同じ答えになることを確認しました。
python
1def calc_diameter(n): 2 if n == 1: 3 return 0 4 res = [] 5 for u in range(n-1): 6 d = 2**n - 1 # 今回求めた木の直径 7 p = d # 現在注目しているノード番号 8 for _ in range(u): 9 p //= 2 # 必要な段数だけ親をたどる 10 d += p 11 p //= 2 12 p *= 2 # 最初の1回だけ左の子を選択 13 d += p 14 while True: 15 p = p * 2 + 1 # 以降は右の子を選択 16 if p >= 2**n - 1: 17 break 18 d += p 19 res.append(d) 20 # print(res) 21 return max(res) 22 23 24for N in range(1, 60): 25 print(calc_diameter(N))
投稿2022/06/19 15:24
退会済みユーザー
総合スコア0
回答ありがとうございます。
丁寧に解説していただきとても助かります。
僕が書いていたのと違って、このプログラムだとN=3桁でもすぐに計算できてしまいますね。
型をつかうばかりじゃなくて、もう少し自分で考えてみないと駄目ですね。
勉強になりました、ありがとうございます。
あなたの回答
tips
プレビュー
