根付き部分木ネットワークの利益最大化

安部, 友輔; ABE, Yusuke

このアイテムのアクセス数:42件（2025-04-29 09:44 集計）

Permalink : https://hdl.handle.net/10114/8705

閲覧可能ファイル

ファイル	フォーマット	サイズ	閲覧回数	説明
安部　友輔	pdf	1.61 MB	56

論文情報

ファイル出力

アイテムタイプ	学位論文
タイトル	根付き部分木ネットワークの利益最大化
その他のタイトル	Maximizing the profit of a rooted subtree
著者	著者名安部, 友輔
著者	著者名 ABE, Yusuke
言語	jpn
発行年	2013-03-24
著者版フラグ	Not Applicable (or Unknown)
学位授与年月日	2013-03-24
学位名	修士(工学)
学位授与機関	機関名法政大学 (Hosei University)
キーワード	Maximizing the profit of a rooted subtree
内容記述	工学研究科システム工学専攻; 指導教授: 五島洋行
抄録	本研究では「最大利益根付き部分木問題(maximum-profit-rooted-subtree problem (MPRS))」の問題のクラスや，効率的な解法などについて検討する．具体的には，点の集合，枝の集合に加え，点に付された収入，枝に付されたコスト，根の指定が与えられる．それに対して，最大利益根付き部分木を求めるという問題である．ケーブルTV やガス，水道事業など様々な事業がこの問題として定式化できる．この重要な問題は「古林ら（2003）」によってはじめて提案された．本研究の主な貢献は，NP 困難性の証明，混合整数計画問題としての定式化，新たなアルゴリズムの提案を行ったことである．なお，「最大利益根付き部分木問題」は最適化問題の一つである．最適化問題とは，ある制約条件と目的関数が与えられる．そして，その制約条件の下で，目的関数を最大化，もしくは最小化する解を求める問題である．最適化問題の中でも組合せ最適化問題は，解が順列，組合せで表される問題であり，さらに組合せ最適化問題の中にはネットワークとして表現することができる問題がある．ネットワークとは，グラフ理論でいう“グラフ”に，重みを持たせたものである．「最大利益根付き部分木問題」はここに位置付けられる．第1章では，研究背景と論文構成を述べる．次に第2章で用語の定義を行う．なお，グラフ理論における用語の定義は，文献によって異なることが多い．本論文では第2章での定義を使用することとする．それを用いて第3章でMPRS を組合せ最適化問題として定式化する．さらに，応用と先行研究について述べる．第4章ではMPRS を混合整数計画問題として定式化する．第5章ではNP 困難性の証明をする．なお，NP 困難である問題は，多項式時間で最適解を求めることが難しい問題である．次の第6章では近似解を求めるための提案手法を三つ紹介する．一つは我々の提案したものであり，二つは既存のアルゴリズムである．本論文では二つの既存アルゴリズムを詳しく書き直している．そして，第7章で計算実験の結果と考察を示す．最後に第8章で結論と今後の課題を述べる．
抄録	In this thesis, we address maximum-profit-rooted-subtree problem (MPRS). In the problem, given a connected undirected graph, a root vertex, each vertex’s nonnegative income, and each edge’s non-negative cost, we aim to find a rooted tree in which the total profit is maximized. The problem can be applied to various real-life situations such as cable television service and supply of energy (gas, water and electricity etc.). This important problem had been proposed by “Kobayashis (2003)” for the first time. The main contributions of this research are to prove that the MPRS is NP-hard, formulate the MPRS as a mixed integer programming problem, and propose a heuristic algorithm. The MPRS is classified as an optimization problem. In optimization problems, an objective function and constraint equations are given. Under the constraints, we find a maximum or minimum value of the objective function. Combinatorial optimization problem is also classified as an optimization problem, and the solutions are represented by combination or permutation. Moreover, a part of combinatorial optimization problems can be formulated as a network. Our problem is positioned here. Using the ideas and terminologies in graph theory, this problem is referred to as maximum-profit-rooted-subtree problem, and we call this MPRS for short. Chapter 1 is an introduction, and we outline the background and organization of this thesis. Next, in chapter 2, we definite terminologies. In chapter 3, we formulate the MPRS as a combinatorial optimization problem. Moreover, practical usages and previous researches are overviewed. In chapter 4, we formulate the MPRS as a mixed integer programming problem. In chapter 5, we prove that the MPRS is NP-hard. In chapter 6, we introduce three heuristic algorithms, one of which has been proposed by us. Though the other algorithms are existing, we rewrite these in detail. In chapter 7, we show the results of computational experiments and perform considerations. Finally, in chapter 8, we conclude our research giving future works.
資源タイプ	Thesis
インデックス	資料タイプ別＞学位論文＞修士論文＞工学研究科
インデックス	114 工学部 (旧) ・工学研究科＞学位論文＞修士論文