お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-01-27 15:00
上位M個の解が得られる疎結合モデルの離散最適化手法
加藤真志井上真郷早大NC2011-118
抄録 (和) 本研究では一般的な多体疎結合モデルの離散最適化問題(組合せ最適化問題)において,上位M種類の解を効率的かつ厳密に求める手法を提案する.従来手法では最上位の解のみを,また,最上位の解が複数ある場合は,その内の一つのみを求める手法が一般的であったが,本手法では,最上位の解集合(最適解集合),上位2番目の解集合と,上位$M$番目の解集合までを厳密に求めることができる.また,最適化の目的関数は,複数の任意の離散実数関数の和で表せるような広いクラスを想定した.目的関数の構造が密な結合を持っている場合は,提案手法を適用することは可能だが,全ての解候補を列挙するのに必要な指数的な計算量が必要となるため,メリットがない.また,本手法は予めどの程度の計算量,メモリ消費量が必要となるかを見積もることができる.更に,上位$M$番目までの解集合の要素数が指数的に増加する場合でも,このこと自体が直接にはトータルの計算量やメモリ消費量が指数的に増加させることにはならない手法である. 
(英) In this report, we propose an efficient method for obtaining exact M-best solutions of a discrete optimization problem (a combinatorial optimization problem) of a general sparsely connected multi-body model. Most of the conventional methods are intended for obtaining one of the best solutions, while the proposed method can answer all the sets of the top M solutions rigorously, e.g., the sets of the best solutions, the second best solutions, ..., and the M-best solutions. The class of the objective function of the proposed method is quite wide; which is defined as the summation of some discrete real functions. Even if the objective function has a densely connected structure, the proposed method is applicable, but its calculation cost would be of exponential order, thus having no advantage. Also, the proposed method can estimate both the calculation cost and the memory cost in advance. Furthermore, if the number of the solutions is of exponential order, it does not directly mean the calculation cost and/or the memory cost are of exponential order.
キーワード (和) 離散最適化 / 多体疎結合モデル / 厳密解 / / / / /  
(英) discrete optimization problem / combinatorial optimization problem / sparsely connected multi-body model / exact enumeration / / / /  
文献情報 信学技報, vol. 111, no. 419, NC2011-118, pp. 125-130, 2012年1月.
資料番号 NC2011-118 
発行日 2012-01-19 (NC) 
ISSN Print edition: ISSN 0913-5685    Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード NC2011-118

研究会情報
研究会 NC  
開催期間 2012-01-26 - 2012-01-27 
開催地(和) 公立はこだて未来大学 
開催地(英) Future University Hakodate 
テーマ(和) 一般、複雑系とニューロコンピューティング 
テーマ(英) General, Complex Systems and Neurocomputing 
講演論文情報の詳細
申込み研究会 NC 
会議コード 2012-01-NC 
本文の言語 日本語 
タイトル(和) 上位M個の解が得られる疎結合モデルの離散最適化手法 
サブタイトル(和)  
タイトル(英) The M-best Discrete Optimization Method for Sparsely Connected Multi-body Model 
サブタイトル(英)  
キーワード(1)(和/英) 離散最適化 / discrete optimization problem  
キーワード(2)(和/英) 多体疎結合モデル / combinatorial optimization problem  
キーワード(3)(和/英) 厳密解 / sparsely connected multi-body model  
キーワード(4)(和/英) / exact enumeration  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 加藤 真志 / Masashi Kato / カトウ マサシ
第1著者 所属(和/英) 早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.)
第2著者 氏名(和/英/ヨミ) 井上 真郷 / Masato Inoue / イノウエ マサト
第2著者 所属(和/英) 早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2012-01-27 15:00:00 
発表時間 25分 
申込先研究会 NC 
資料番号 NC2011-118 
巻番号(vol) vol.111 
号番号(no) no.419 
ページ範囲 pp.125-130 
ページ数
発行日 2012-01-19 (NC) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会