代数計算を用いた状態遷移関数の局所化による2値符号化モデルのための動的計画法の計算量の削減

カテゴリ: 部門大会

論文No: GS14-7

グループ名: 【C】平成20年電気学会電子・情報・システム部門大会講演論文集

発行日: 2008/08/20

タイトル(英語): Decreasing Computational Cost of Dynamic Programmings for Binary Coded Models by Algebraically Localizing State Transition Functions

著者名: 稲元 勉(神戸大学),太田能 (神戸大学),玉置 久(神戸大学),村尾 元(神戸大学)

著者名(英語): Tsutomu Inamoto(Kobe University),Chikara Ohta(Kobe University),Hisashi Tamaki(Kobe University),Hajime Murao(Kobe University)

キーワード: 離散事象システム|2値符号化モデル|計算機代数システム|エレベータ運行計画問題|discrete event system|binary coded model|computer algebra system|elevator operation problem

要約(日本語): 本稿では,ある状態からの遷移先状態数が,形式的には多いものの実質的には少ない確率的離散事象システムの計画問題に対する,システムの2値符号化モデルに基づいた動的計画法の計算量を,システムの状態遷移関数の代数的簡約化により減らせることを示す.遷移元状態をある部分状態空間に限定したとき,状態変数の一部が固定されているために,状態遷移はより単純な式で表される.これらの式を用いれば,ある状態から形式的に遷移しうる状態数が減少し,計算量の低減が可能となる.計算例では,エレベータ運行計画問題を対象とし,数式の簡約化のために計算機代数システムを利用することで,状態の列挙および最適な価値関数の計算にかかる時間を短縮できることを示す.

PDFファイルサイズ: 4,618 Kバイト