[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 119 (1002ﾚｽ)
上
下
前
次
1-
新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
899
: 2023/03/29(水)22:23
AA×
[240|
320
|
480
|
600
|
100%
|
JPG
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
899: [sage] 2023/03/29(水) 22:23:07.57 1/3重心分解 (one-third centroid decomposition) は、木のアルゴリズムの一種です。木を根付き木として表現したとき、1/3重心分解は、木を3つの部分木に分割することによって木を効率的に処理することができる手法です。 具体的には、まず木の重心を計算し、重心を根とする部分木を1つ、残りの部分木を2つに分割します。このとき、分割された2つの部分木のうち、少なくとも1つの部分木のサイズは元の木のサイズの1/3以下であることが保証されます。 そして、再帰的に各部分木に対して同じ手法を適用することで、木全体を処理します。このとき、各部分木のサイズが1以下になるまで再帰を行います。 1/3重心分解は、木の直径や最大独立集合、最小頂点被覆などの問題を効率的に解くことができることが知られています。また、このアルゴリズムは、計算時間が O(n log n) であり、木のサイズに対して非常に効率的であることが特徴です。 http://medaka.5ch.net/test/read.cgi/prog/1678852419/899
重心分解 は木のアルゴリズムの一種です木を根付き木として表現したとき重心分解は木をつの部分木に分割することによって木を効率的に処理することができる手法です 具体的にはまず木の重心を計算し重心を根とする部分木をつ残りの部分木をつに分割しますこのとき分割されたつの部分木のうち少なくともつの部分木のサイズは元の木のサイズの以下であることが保証されます そして再帰的に各部分木に対して同じ手法を適用することで木全体を処理しますこのとき各部分木のサイズが以下になるまで再帰を行います 重心分解は木の直径や最大独立集合最小頂点被覆などの問題を効率的に解くことができることが知られていますまたこのアルゴリズムは計算時間が であり木のサイズに対して非常に効率的であることが特徴です
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 103 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
ぬこの手
ぬこTOP
0.028s