講演抄録/キーワード |
講演名 |
2009-01-29 14:15
MAX-LFS解法と後処理の改良により性能強化されたペトリネットのマーキング構成問題解法 ○石井稔久・田岡智志・渡邉敏正(広島大) CST2008-44 |
抄録 |
(和) |
ペトリネットのマーキング構成問題(MCP: Marking Construction Problem)は,
「ペトリネット $N$, 初期マーキング $M_i$, 目標マーキング $M_t$ が与えられた時,$M_i$からトランジションの発火により遷移可能なマーキングのうちで$M_t$に最も近いマーキングを求めよ」という問題である.
MCPは一般にNP-困難であり, 2種類の解法の枠組みとして,
(i) MAX-LFS解法を利用した解法,
(ii) MAX-LFS解法を利用しない解法がある.
$MCHF_k$または$MCGT_k$がそれぞれの枠組みの解法の中で高精度である ($k$はある整数).
本稿では,(i)に関して$MCHF_1$の改良版である$MC\_feideq\_gt_k$を提案する.
また,(ii)に関しては発火トランジションの新しい選択指標{\em access}値を導入し,これに基づく解法$MCA$を提案する.
さらに$MC\_feideq\_gt_k$の後処理$MCGT_k$を$MCA$に置き換えた解法
$MC\_feideq\_a$を提案する.
既存解法と3つの提案解法を計算機実験により性能比較をする. |
(英) |
The marking construction problem ({\bf MCP}) of Petri nets is defined as
follows.
``Given a Petri net $N$, an initial marking $M_i$ and a target marking $M_t$, find a marking that is closest to $M_t$ among those which can be reached from $M_i$ by firing transitions.''
MCP is known to be NP-hard, and two schemas of algorithm design are known depending on whether any algorithm for MAX-LFS is utilized or not.
$MCHF_k$ in the first schema and $MCGT_k$ is the second one are known to
have the highest capability in each schema.
As for the first schema, an algorithm $MC\_feideq\_gt_k$ is proposed as
an improved version of $MCHF_1$.
As for the second schema, we introduce a new measure {\em access} to be
used in selecting on enable transition for rational firing, and an algorithm
$MCA$ is proposed by incorporating {\em access} value.
Furthermore, an algorithm $MC\_feideq\_a$ is proposed by replacing the
post-processing $MCGT_k$ of $MC\_feideq\_gt_k$ with $MCA$.
The three proposed algorithms are implemented and we compare their
capability with existing algorithms through computing experiments. |
キーワード |
(和) |
ペトリネット / マーキング構成問題 / 可達問題 / 発見的解法 / 計算機実験 / / / |
(英) |
Petri nets / marking construction problems / reachability problems / heuristic algorithms / computing experiments / / / |
文献情報 |
信学技報, vol. 108, 2009年1月. |
資料番号 |
|
発行日 |
2009-01-22 (CST) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CST2008-44 |
|