| 大会名称 |
|---|
| 2010年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2010 |
| 発行日 |
| 2010/8/20 |
| セッション番号 |
| 7A |
| セッション名 |
| アルゴリズム・コンピュテーション(3) |
| 講演日 |
| 2010/09/09 |
| 講演場所(会議室等) |
| A会場（総合学習プラザ1F 第5講義室） |
| 講演番号 |
| A-031 |
| タイトル |
| 最大利益根付木問題に対するヒューリスティックアルゴリズム |
| 著者名 |
| 千葉 英史, 古林 隆, 福馬 敏子, |
| キーワード |
| 抄録 |
| ケーブルテレビのようなサービスを受けるためには，センターと利用者をケーブルで連結する必要がある．そのとき，ケーブルの長さに比例したコストがかかるため，利用者からの収入とケーブルコストの両方を考慮して，ケーブルを連結するかどうかの判断が求められる．そこで本研究では，利益を最大化するための問題を考える．もし，全ての利用者にサービスを提供しなければならないならば，有向グラフにおける最小全域木問題へと帰着できるが，その必要が無い場合は，NP困難である．本研究では，いくつかのヒューリスティックアルゴリズムを提案し，計算機実験を通してそれらの効果を確かめた． |
| 本文pdf |
| PDF download (315.9KB) |