| 講演名 | 1998/4/24 ペトリネットの発火系列問題に対する発見的解法FSD 山内 雅弘, 橋本 通高, 渡邊 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文はペトリネットの発火系列問題(LFSと略記)に対する性能の良い発見的アルゴリズムFSDを提案し, その性能を実験的に評価する.ペトリネットの発火系列問題とは, ペトリネットPN, 初期マーキングM, 発火回数ベクトルX(その要素X(t)が各トランジションtの発火回数を表す)が与えられたとき, 各トランジションtがその中に合計で丁度X(t)回現れ, 且つMから順に発火可能であるトランジションの系列が存在するか否かを判定し, 存在するならばその様な1つの系列δを求める問題である.実験では, 解δの存在が保証されている8480個の入力例に対してFSDを適用した.その結果, FSDは7219個(85%)の入力例について実際にδを見つけ, 既存手法と比べて, 約3から10%改善された.特にステートマシンに対しては, 3900個の入力例全てについてその解を得ている.このことからFSDは高い能力を持つものと思われる. |
| 抄録(英) | The paper proposes a new heuristic algorithm FSD for the Legal Firing Sequence problem of Petri nets (LFS for short) and evaluates it experimentally. LFS is defined as follows. Given a Patri net PN, an initial marking M and a firing count vector V, find a firing sequence (a sequence of transitions) that is legal on M with respect to X. A component X(t) of a firing count vector X denotes the prescribed total firing number of a given transition t. We say that a firing sequence is legal on an initial marking M with respect to a given X if and only if the first transition of the sequence is firable on M, the rest can be fired one by one subsequently, and each transition t appears exactly X(t) times in the sequence. FSD is applied to 8480 test problems to each of which existence of an exact solution is guaranteed, and it finds an optimum solution to each of 7219 (85%) test problems showing 3 - 10% improvement from those existing algorithms. In particular, it optimally solves all 3900 test problems with PN being state machines. These experimental results show high capability of FSD. |
| キーワード(和) | ペトリネット / 発火系列 / 欠損サイフォン / 解不能サイフォン / 発見的解法 |
| キーワード(英) | Petri nets / firing sequences / deficient siphons / incompatible siphons / heuristic algorithms |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/4/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ペトリネットの発火系列問題に対する発見的解法FSD |
| サブタイトル（和） | |
| タイトル（英） | A Heuristic Algorithm FSD for the Legal Firing Sequence Problems of Petri Nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 発火系列 / firing sequences |
| キーワード(3)（和/英） | 欠損サイフォン / deficient siphons |
| キーワード(4)（和/英） | 解不能サイフォン / incompatible siphons |
| キーワード(5)（和/英） | 発見的解法 / heuristic algorithms |
| 第 1 著者 氏名（和/英） | 山内 雅弘 / Masahiro Yamauchi |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 橋本 通高 / Michitaka Hashimoto |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邊 敏正 / Toshimasa Watanabe |
| 第 3 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1998/4/24 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 36 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |