| 大会名称 |
| 2018年 総合大会 |
| 大会コ－ド |
| 2018G |
| 開催年 |
|
2018
|
| 発行日 |
|
|
| セッション番号 |
|
N-1
|
| セッション名 |
|
非線形問題
|
| 講演日 |
|
2018/3/21
|
| 講演場所(会議室等) |
|
５号館 2Ｆ 5203セミナー室
|
| 講演番号 |
|
N-1-20
|
| タイトル |
|
K番目の最短経路を使用したグラフ的シュタイナー木構築法
|
| 著者名 |
|
◎△藤田実沙, 木村貴幸, 藤原寛太郎, 池口 徹,
|
| キーワード |
|
グラフ的シュタイナー木問題, 組合せ最適化, 構築法
|
| 抄録 |
|
我々は既に，組合せ最適化問題の一つであるグラフ的シュタイナー木問題に対するカオスダイナミクスを用いた解法を提案した．提案手法は良い性能を示すものの，完全グラフとなる問題例では性能が劣化することを確認している．またその原因は，構築した初期解が深い局所解となっていることも明らかにした．初期解の構築法として，頂点間の最短経路に基づいてシュタイナー木を構築するShortest Path Heuristicがある．完全グラフとなる問題例に対してこれを適用すると，必須点同士を接続する重みが大きい辺からなるシュタイナー木が出力されてしまう．そこで本稿では，必須点間のK番目の最短経路に基づいてシュタイナー木を構築する手法を提案する．これにより，必須点と必須点でない頂点を接続する重みが小さい辺からなるシュタイナー木の出力を実現したので報告する．
|
| 本文pdf |
|
PDF download
|
