WEKO3
アイテム
木の公平な重み付けの手法について
https://ipsj.ixsq.nii.ac.jp/records/32639
https://ipsj.ixsq.nii.ac.jp/records/3263954d7982e-07d0-441b-a119-19799d59eaa6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL90016008.pdf (1.1 MB)
|
Copyright (c) 1990 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1990-07-16 | |||||||
| タイトル | ||||||||
| タイトル | 木の公平な重み付けの手法について | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A METHOD OF ASSIGNING FAIR WEIGHTS TO NODES OF TREE | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering, Waseda University | ||||||||
| 著者名 |
栗野, 俊一
× 栗野, 俊一
|
|||||||
| 著者名(英) |
Shun-Ichi, Kurino
× Shun-Ichi, Kurino
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 木構造に対する重み付けの手法としてトップダウンアルゴリズムとボトムアップアルゴリズムの2つが知られており，これらは異なる結果を与える．我々はトップダウンやボトムアップの重み付けの際の重みの移動に着目し，これを一般化した比付きの重み付けを考案した．そして各々の静的な重み付けのアルゴリズムと動的な重み付けのアルゴリズムを定義し，これらの性質を比較した．比付きの重み付けアルゴリズムを用いて，n個の節点を持ち，兄弟の数の最大値がwである木に対して重み付けを行った際の計算量はO（+）で，トップダウンアルゴリズムやボトムアップアルゴリズムの場合と同程度の計算量で済むことが分かった． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We propose a new algorithm for assigning weights to nodes of tree. This algorithm includes top-down and bottom-up algorithms as its special cases. This algorithm is called a ratio-weighting algorithm. Our approach is based on transfers of weights from nodes of a given tree to anew node which is added. This algorithm is applied both statically and dynamically like other algorithms. the computational complexity of static ratio-weighting algorithm is O(n+w), where n is a number of nodes and w is a maximum number of brothers. This result is as same as that of static top-down and static bottom-up algorithms. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1990, 号 58(1990-AL-016), p. 53-60, 発行日 1990-07-16 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
