加法的tree metric復元
概要
全点対距離行列の加法性から葉の接続先とedge長を決め、候補木の全距離を再計算して存在を完全検証する。
考え方
まず、距離が与えられたN頂点が木の全頂点であり、追加頂点を許さず、各辺の重みが正であるモデルを固定する。D[i,j]を入力距離とし、D[i,i]=0、D[i,j]=D[j,i]>0(i≠j)を確認する。距離表から候補を作る段階と、候補が全条件を満たすかを検証する段階を分ける。
根からの距離で親を決める
根rを一つ固定する。真の木が存在するなら、jがrからiへのpath上にある条件はD[r,j]+D[j,i]=D[r,i]である。path外のjへ寄り道すると、分岐点からjまでの正の距離が二重に加わるので等号は成立しない。
i≠rについて、この等式を満たすj≠iのうちD[j,i]が最小の頂点をp[i]とする。全頂点が表に含まれるため、path上でiの直前にある親も候補に含まれる。正の辺長により、それより上の祖先はすべて遠い。したがって親は一意に決まり、辺(p[i],i)の重みはD[p[i],i]となる。各iについて全jを走査すれば、候補をO(N²)で構築できる。候補がない、または最小値が同点なら、このモデルでは存在しない。
構成した各辺ではD[r,p[i]]=D[r,i]−D[p[i],i]<D[r,i]である。親をたどると根距離が厳密に減るためcycleはなく、親を持たないrに到達する。N−1辺で全頂点が連結となり、候補は木になる。ただし、この時点では他の頂点対の距離まで一致するとは限らない。
全距離を検証する
候補木の各頂点を始点にDFSし、辺長の和で求めた全距離をDと比較する。一つでも違えば棄却し、すべて一致すれば候補そのものが存在の証明になる。存在する木の親は上の規則で必ず選ばれるので、構成に失敗した入力を誤って棄却することもない。N回のDFSもO(N²)である。
追加分岐点を許す復元との違い
三点x,y,zのpathの交点mについては、D[x,m]=(D[x,y]+D[x,z]−D[y,z])/2と書ける。しかし、mが入力の頂点にあることはこの式からは分からない。三頂点間の距離がすべて2なら、追加した中心へ長さ1の辺を三本張れば実現できる一方、元の三頂点だけの正重み木では実現できない。上の親規則では二頂点がともに根へ重み2でつながり、その間の距離4が再検証で拒否される。
入力が葉や観測点だけの場合は、未観測の分岐頂点を追加する加法的距離復元が別途必要になる。四点条件はそのモデルの判定に使えるが、入力頂点だけでの実現を保証しない。
成立条件と計算量
全頂点・正重み・追加頂点なしのモデルではO(N²)時間、距離表を含めO(N²)空間。N=1は辺なしで成立する。長さ0の辺を許すと祖先の距離が同点になり、一意性と厳密減少の証明が崩れるため別のモデルとして扱う。辺重みが整数である制約も候補辺で確認する。距離の加算は入力上限の二倍と候補pathの総長まで収まる型で行う。
問題一覧
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 橙色(2400–2799)。距離行列から接続先と辺長を復元し、加法性と全距離の整合を検証する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 木構造。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-additive-tree-metric-reconstruction
加法的tree metric復元
習得する技能
- 加法的距離行列から正重み木の候補を復元し、全点対距離の再計算で存在を完全検証できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 基準点からの木距離・剰余類・直径・中心。
このUnitを直接前提とする単元: なし。
木距離・直径・中心・最遠点で得た考え方と実装を再利用し、加法的tree metric復元の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- 加法的tree metric復元の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。