最適系列分割問題に対する効率的分枝限定法の構築と諸特性解析
スポンサーリンク
概要
- 論文の詳細を見る
頂点が連続的な番号を保持し,始点が初期番号,終点が最終番号となり,両端点が異なるグラフをG(V,E)とする.本論文における最適系列グラフ分割問題はグラフGに対して,各頂点に与えられた重みの総和がブロックサイズP(>0)以下であり,かつ,部分集合の頂点番号が連続的に保持される条件のもとで,カットされる辺のコストの和が最小となるよう分割する問題である.本問題の一つの応用例としては,プログラムを一定の大きさの単位で記憶領域に割当を行うペーシングの手法が考えられる.本論文では動的計画法による最適系列分割問題に対して,探索法および限定操作の観点から改善の余地があるものと考え,分枝限定法の手法を導入することによって効率的算法を構成する.さらに得られた算法の数値実験にもとづいて算法の特性と性能評価を行い,理論的計算量についても論じる.以上より,漸近的計算量は等しいが,細分化禁止則,反復回数の減少,同レベルの優越関係による削除,下界値による限定などの探索空間の実際の紋り込みによって計算量の負担を軽減することが可能であることを示す.
- 一般社団法人情報処理学会の論文
- 1994-03-15
著者
関連論文
- 協調フィルタリングに基づく推薦システムにおける格付け寄与度の提案(インタラクション/インタフェース応用,ソフトウェアエージェントとその応用論文)
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : MovieLensでの格付けデータに基づく検証(社会システムと知能)
- 小型自律飛行船シミュレーションの実装及び効果検証
- 5ZA-8 地震災害関連情報の分析に基づく風評被害対策に関する考察(防災と情報,学生セッション,コンピュータと人間社会)
- 2-S-9 新潟中越沖地震における風評被害対策と売上推移(観光とOR(2))
- 2-S-10 メディアの動向を意識した風評被害対策に関する考察(観光とOR(2))
- 2-S-11 自然災害における近隣観光地の風評被害 : モデル、被害度指標、災害ポータル(観光とOR(2))
- N-016 風評被害対策に向けた話題分析に関する基礎研究(教育・人文科学,一般論文)
- 5H-4 風評被害の抑制・防止に向けた地震災害情報の分析(危機管理情報システム,一般セッション,コンピュータと人間社会)
- 待ち行列ネットワークにおける最適成長計画問題とその解法
- エージェントの意思を取り入れた混雑情報の提示とその効果(セッション : 社会システムと知能(群ユーザモデルと知的支援), 「社会システムにおける知能」及び一般)
- エージェントの意思を取り入れた混雑情報の提示とその効果(社会システムと知能(群ユーザモデルと知的支援), 「社会システムにおける知能」及び一般)
- テーマパーク問題における混雑状況の提示とその効果(社会システムにおける知能 : 実環境におけるマルチエージェント社会)
- テーマパーク問題における混雑状況の提示とその効果(社会システムにおける知能(実環境におけるマルチエージェント社会))(「社会システムにおける知能」及び一般)
- 大型疎線形計画問題に対する Reid の基底更新方法の改善
- 大型疎線形計画問題に対するReidのバンプ縮小方法の基本的性質
- 数理モデルによるDNAメモリの容量解析
- 組合せ最適化問題に対する時系列解析を用いたアニーリング法への応用
- 1-B-8 コーシー分布適応型粒子群最適化法の提案(離散最適化(2))
- Iterated Multiple Lake Gameにおける社会的ジレンマに対するプレイヤー群の挙動に関する考察
- X-Economyシステムによる電力市場のモデル化とその実装
- LF-006 セルの入出力観測に基づくセルオートマトンの定量的分析(人工知能・ゲーム)
- ブログによる情報収集と推薦技術を用いた飲食店情報サイトの構築(セッション7:ウェブにおける情報処理)
- ブログによる情報収集と推薦技術を用いた飲食店情報サイトの構築(セッション7:ウェブにおける情報処理,社会システムと知能)
- 集合行為問題におけるタグメカニズムと協調の形成に関する考察
- 1-D-11 AR(1)による近傍構造解析を用いたアニーリング法への応用(離散・組合せ最適化(4))
- AR(1)モデルによる組合せ最適化問題の近傍に対する汎用的解析と応用
- 郡市医師会におけるテレビ会議システム導入可能性の検討 : 北海道医師会をモデルとした費用効果の試算
- 遺伝子概念学習のための支援ツールに関する検討
- 概念学習に対する遺伝的アルゴリズムの局所探索に関する考察
- 帰納と対話の併用による概念知識ベースの構築
- 遺伝的アルゴリズムを用いた概念学習に関する考察
- 遺伝的アルゴリズムによる選言概念獲得アルゴリズム
- GAによる Neural Network の段階的生成と応用
- ユーザ間・アイテム間協調フィルタリングの適応的な融合手法 : MovieLensでの格付けデータに基づく検証(社会システムと知能)
- X-Economyシステムによる電力市場のモデル化とその実装
- 抗原抗体反応のモデル化と挙動に関する基礎研究
- 抗原抗体反応の細胞モデルに関する基礎研究
- 時間制約付き飛行プランに基づく小型自律飛行船制御
- 待ち行列ネットワークにおける最適成長計画問題とその解法
- 待ち行列ネットワークにおける待ち時間を最小化する構造設計(ネットワーク品質・制御)
- 待ち行列ネットワークにおけるリンク張り替えによる構造最適化(セッション9:ネットワークと知能)
- 成長する待ち行列ネットワークにおけるトポロジー生成規則の最適性(ネットワークが創発する知能)
- 2-F-1 待ち行列ネットワークの複雑ネットワーク理論を用いた最適設計(情報・通信)
- リンクコストを考慮しない待ち行列ネットワークの最適設計(セッション1: ネットワーク)
- リンクコストを考慮しない待ち行列ネットワークの最適設計(ネットワーク, 「社会システムにおける知能」及び一般)
- 待ち行列ネットワークにおけるリンク張り替えによる構造最適化(セッション9:ネットワークと知能,社会システムと知能)
- アートツーリズムを支援するコミュニティWebの構築(セッション : 一般(知識処理), 「社会システムにおける知能」及び一般)
- アートツーリズムを支援するコミュニティ Web の構築(一般(知識処理), 「社会システムにおける知能」及び一般)
- 組織評価における能力成熟度モデルの適用 : 観光関係部局の調査結果について(社会・人間系の情報システム)
- BSC戦略マップ構造モデリングに基づく観光戦略策定の検討(社会システムにおける知能 : 社会システムのモデル化)
- BSC戦略マップ構造モデリングに基づく観光戦略策定の検討(社会システムにおける知能(社会システムのモデル化))(「社会システムにおける知能」及び一般)
- 北海道観光に関する情報収集とニーズ調査 : WWWを利用した情報提供の現状(データマイニング)
- 観光情報に関する概念形成セッションの提案と考察(統合オペレーション(4))
- 北海道「遊」産業情報におけるWebマイニング(統合オペレーション(3))
- 最適系列分割問題への遺伝的アルゴリズムの適用 : 個体の形質遺伝に関する考察
- AR(1)モデルによる組合せ最適化問題の近傍に対する解析
- 連続最適化問題に対するコーシー分布型SAによるアプローチ
- 連続最適化問題に対するコーシー分布型SAの提案
- 1-E-5 AR(1)モデルによる近傍構造解析の汎用性に対する検証(組合せ最適化(1))
- 1-E-6 連続最適化問題におけるコーシー分布を適用したSA(組合せ最適化(1))
- 組合せ最適化問題に対する近傍集合の解析
- 2-C-5 擬似コーシー分布型近傍による高速化SAへの試み(組合せ最適化)
- 2-C-1 組合せ最適化問題における近傍集合の特性(離散最適化(3))
- ヒューリスティック手法における解析と評価
- AR(1)プロセスを用いた Local Search に対する確率的解析(組合せ最適化(4))
- Parallel Tabu Search for Graph Multi-Partitioning Problem
- New Ant System Algorithm by Ant-Tabu Agents
- グラフ分別問題の解構造とAR(1)モデル(組合せ最適化(1))
- AR(1)モデルによる Local Search の性能評価(組合せ)
- Local Searchの確率的解析による性能評価
- メタ戦略の評価分析と並列Tabu Searchアルゴリズムの提案
- 遺伝的アルゴリズムによる最適系列分割問題の解法
- コーシー適応型粒子群再構築最適化法の提案
- 系列分割問題に対する確率的複合移動によるSimulated Annealing法の適用
- グラフ分割問題に対するメタ戦略の並列化
- 1-B-1 散布探索適応型粒子群最適化法の提案(確率アルゴリズム)
- 複合型アントエージェントによる巡回セールスマン問題
- アントシステムアルゴリズムのTSPへの試作と改善の試み(組合せ最適化(1))
- 要素間に先行順位をもつシステム要素の配置問題に対する厳密解法と近似解法の提案
- 要素間に先行順位をもつシステムの配置問題
- A Simulated Annealing Algorithm for the Sequential Partitioning Problem of Directed Acyclic Graphs
- Tabu Search法による無閉路有向グラフの最適系列分割問題の解法
- Simulated Annealing的手法を取り入れた無閉路有向グラフの最適系列分割問題の解法(メタ戦略(1))
- Tabu Searchによる無閉路有向グラフの最適系列分割問題と特性評価
- Tabu Searchを用いた無閉路有向グラフ系列分割問題の近似解法
- Tabu Searchによる無閉路有向グラフの最適系列分割問題の効率評価
- 半順序の最適系列分割問題の構造と算法構成
- Tabu Searchによる半順序の系列分割問題
- 最適系列分割問題に対する効率的分枝限定法の構築と諸特性解析
- 半順序系列分割問題における既約化による効率評価
- 無閉路有向グラフにおける系列分割問題の算法構成
- 1-E-6 コーシー適応型散布探索粒子群最適化法の性能(待ち行列・確率モデル)
- Local Searchに対する汎用的な確率的解析モデル
- 1-F-10 Local Searchに対する汎用的な確率的解析への試み(確率モデル(3))
- 2-F-12 モチベーション教育におけるOR例題の重要性(最適化(2))
- Local Searchに対する汎用的な確率的解析モデル(一般)
- 1-F-1 Discrete PSOにおける改善アプローチ(離散最適化(1))
- 2-B-1 研究部会「OR普及のためのモティベーション教育」と「複雑系とOR」平成25年度活動中間報告(経営情報と教育)
- 1-G-4 再構築型粒子群最適化法の提案(最適化(2))