4

高レベルのペトリネット エディター/シミュレーターを開発しています。最初に、ここで少し語彙を紹介します

円＝場所

長方形 =トランジション

適切な整数 =トークン

遷移中の状態 =ガード

そして、私はトランジションのガードを通過することに行き詰まっています。Guard は、遷移を実行する場合に true にする必要がある条件です。どういうわけかバックトラッキングを使用する必要があることは知っていますが、プログラムの開始前にトランジションに入る場所の数がわからないため、必要なループの数がわからないため、for ループを使用できません。

これが問題を説明する写真です ここに画像の説明を入力

したがって、1 位から最初のトークンを取得し、2 位から最初のトークンを取得し、ガードを通過した場合はパスし、トークンを保存し、ループを破り、false の場合は 2 位の 2 番目のトークンを続行します..など...最終的に、1 位の最後のトークン (4) と 2 位の最後のトークン (2) でガードをパスします。

これをコーディングする方法を知っているでしょう。遷移に入る場所の数が一定であれば、次のようになります

for token in place 1
     for token in place 2
        try pass guard
        if (passed) 
            save tokens
             break;

しかし、前に言ったように、トランジションに入る場所の数が一定ではないので、このアプローチは使用できません。したがって、基本的には、トークンの組み合わせを試して、ガードを通過するようにする必要があります-ガードを通過するまで、またはすべての組み合わせを試すまで。あなたはなにか考えはありますか ？擬似コードで十分です。ちなみに私はこれらのデータ構造を使用しています

場所のリスト - 通常の Java リスト、場所のリスト = new ArrayList();

各場所には独自のトークンのリストがあります。 List tokens = new ArrayList();

///編集: ガードの形式は次のとおりです。

op1 rel op2、op1 は変数、op2 は定数または変数、rel は関係 (<、>、=、... ) op3 rel op4 ...

- - 編集：

だから私はRushilアルゴリズムを実装しようとしましたが、それはかなりバグが多いので、SSCCEを投稿して試してみて、少し助けてください。

まず、Place クラスを作成します。

public class Place {
public List<Integer> tokens ;

//constructor
public Place() {

  this.tokens = new ArrayList<Integer>();  
}

}

そして、クラスをテストします：

public class TestyParmutace {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    // TODO code application logic here

    List<Place> places = new ArrayList<Place>();

    Place place1 = new Place();
    place1.tokens.add(1);
    place1.tokens.add(2);
    place1.tokens.add(3);
    places.add(place1); //add place to the list

    Place place2 = new Place();
    place2.tokens.add(3);
    place2.tokens.add(4);
    place2.tokens.add(5);
    places.add(place2); //add place to the list

    Place place3 = new Place();
    place3.tokens.add(6);
    place3.tokens.add(7);
    place3.tokens.add(8);
    places.add(place3); //add place to the list


//so we have
    //P1 = {1,2,3}
    //P2 = {3,4,5}
    //P3 = {6,7,8}


    List<Integer> tokens = new ArrayList<Integer>();

    Func(places,0,tokens);

}

/**
 * 
 * @param places list of places
 * @param index index of current place
 * @param tokens list of tokens
 * @return true if we passed guard, false if we did not
 */


public static boolean Func( List<Place> places, int index, List<Integer> tokens) 

{

if (index >= places.size())
{

// if control reaches here, it means that we've recursed through a particular combination
// ( consisting of exactly 1 token from each place ), and there are no more "places" left



String outputTokens = "";
for (int i = 0; i< tokens.size(); i++) {

    outputTokens+= tokens.get(i) +",";
}
System.out.println("Tokens: "+outputTokens);

if (tokens.get(0) == 4 && tokens.get(1) == 5 && tokens.get(2) == 10) {
System.out.println("we passed the guard with 3,5,8");
return true;
}

else {
    tokens.remove(tokens.get(tokens.size()-1));
    return false;
}

}

Place p = places.get(index);

for (int i = 0; i< p.tokens.size(); i++)
{

tokens.add(p.tokens.get(i));
//System.out.println("Pridali sme token:" + p.tokens.get(i));

if ( Func( places, index+1, tokens ) ) return true;

}
if (tokens.size()>0)
tokens.remove(tokens.get(tokens.size()-1));

return false;

}
}

このコードの出力は次のとおりです。

Tokens: 1,3,6,
Tokens: 1,3,7,
Tokens: 1,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 2,3,6,
Tokens: 2,3,7,
Tokens: 2,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,
Tokens: 3,3,6,
Tokens: 3,3,7,
Tokens: 3,3,8,
Tokens: 3,4,6,
Tokens: 3,4,7,
Tokens: 3,4,8,
Tokens: 4,5,6,
Tokens: 4,5,7,
Tokens: 4,5,8,

ですから、1,3,6 や 1,3,7 のようにいくつかの組み合わせは正しいのですが、4,5,8 はまったくナンセンスです。完全に欠落している組み合わせもあります..2、4、6などのように...誰もがなぜこのようになっているのか分かりますか?

編集:今では正常に動作しています。

4

4 に答える 4

3

再帰的なアプローチはそれを簡単にします:

boolean Func( ListOfPlaces places, int index ) // index points to the current "place"
{

 If index >= NumberOfTokens (if index points to a place, which doesn't exist)
   {
   // if control reaches here, it means that we've recursed through a particular combination ( consisting of exactly 1 token from each place ), and there are no more "places" left. You have all the tokens you need, in your stack.

   try pass guard; if passed, save tokens and return true

   else, remove token last added to the stack & and return false
   }

 place p = places[index] 

 foreach token in p
 {
   add token to your stack
   if ( Func( places, index+1 ) ) return true
 }

 remove last token added to the stack
 return false
}

最初に index = 0 で関数を呼び出します。

お役に立てれば。:-)

于 2012-04-07T14:24:59.237 に答える
0

このようなものはどうですか：

method getPassed(places, tokens):
    if places are empty:
        try pass guard
            if (passed) 
                save tokens
                return true
            else return false
    else:
        for token in places[0]:
            if getPassed(places[1:].clone(), tokens.clone().append(token)):
                break

getPassed(places, []) の呼び出しで開始します。ここで、places は場所のリストで、[] は空のリストです。リストを台無しにしないように、常にリストをコピーする必要があることに注意してください。

結局、ペアは必要ありません。最初にアルゴリズムに渡す元の場所のリストを保持している場合は、originalPlaces[i] に対して token[i] が選択されていることがわかります。

ただし、必要に応じて、トークンの代わりに tokenPlaces ペアを保持できます。次のようになります。

method getPassed(places, tokenPlacePairs):
    if places are empty:
        try pass guard
            if (passed) 
                save tokens
                return true
            else return false
    else:
        for token in places[0]:
            if getPassed(places[1:].clone(), tokens.clone().append((token, places[0]))):
                break

編集：まだ混乱していますが、これで明確になることを願っています。for ループを再帰的に生成しようとしています。したがって、場所に要素が 2 つしかない場合は、提案どおりになります。

for token in place 1
     for token in place 2
        try pass guard
        if (passed) 
            save tokens
             break;

つまり、リストから最初の場所を取得し、「for token in place 1」ループを作成します。次に、場所リストからその場所を切り取り、現在のトークンをトークン リストに追加します。この再帰呼び出しは、「for token in place 2」ループを実行するようになりました。等々。再帰呼び出しごとに、桁数を 1 減らし、for ループを 1 つ作成します。したがって、場所のリストが空になった後、n 個のネストされたループがあります。ここで、n は場所の数であり、私が理解している限り、これはあなたが探していたものです。

このメソッドは次の方法で開始できます。

originalPlaces = places.clone()
getPassed(places, [])

このようにして、originalPlaces を変更せずに保持し、再帰で基本ケースに到達したとき、つまりガードの通過を決定しようとするときに、tokens[i] を originalPlaces[i] に割り当てることができます。したがって、実際にはペアは必要ありません。

于 2012-04-07T11:16:15.960 に答える
0

Transition に isEnabled() メソッドと input/outputArcs があるとします。

public boolean isEnabled() {
    // check for some special input/output conditions (no arcs, etc.)
    // return false if invalid

    // check to see if all input arcs are enabled
    for (Arc inputArc : inputArcs)
        if (!inputArc.isEnabled())
            return false;
    // should check if there's a guard first...
    return guard.evaluate();  // do the selection of tokens from inputs here and evaluate
}
于 2012-04-07T15:09:30.113 に答える
0

ループ管理は自分で行うことができます。つまり、各場所の反復ステータスを表すクラスが必要になるということです。これを state_of_place と呼びましょう。current_index と max_index の 2 つの値で構成されます。

次に、私が iteration_admin と名付けたクラスを作成します。これは、state_of_place の配列と、iteration_in_progress などと呼ばれるブール値で構成されます。作成時に、ブール値は TRUE に設定されます。場所と同じ数の state_of_place オブジェクトを作成します。Current_index は 0 になり、max_index はその場所のトークンの数になります。

iteration_admin クラスには、ループ変数の増分を表すメソッドが必要です。それをインクリメント（）と呼びましょう。このメソッドは、current_index がまだ max_index を下回っている場合、state_of_place 要素の current_index を最大のインデックスでインクリメントします。current_index が max_index と等しい場合、現在のインデックスは 0 に設定され、state_of_place の現在のインデックスを次に低いインデックスでインクリメントする必要があります。そのインデックスが max_index に達した場合は、0 に設定され、次に低いインデックスがインクリメントされます。もちろん、state_of_place[0] だけは例外です。その要素 current_index がその max_index を超える場合、ブール値の iteration_in_progress は FALSE に設定されます。これは、トークンのすべての組み合わせが使用されたことを意味します。

さて、ガードを試すためのコードは

  • タイプ iteration_admin のオブジェクトを初期化します
  • iteration_admin.iteration_in_progress が TRUE の間
  • state_of_place 要素の current_index 値を使用して pass() メソッドの引数リストを作成します
  • pass() を呼び出す
  • 渡されない場合は、 iteration_admin.increment() メソッドを呼び出します
  • 終了する

編集:疑似コードでアイデアを表現しようとしています。抽象的な疑似コードというよりは、Java と PL/SQL の混合のように見えるのではないかと心配しています。それでも、私のテキストによる説明よりもいくらか明確になるはずです。

   // iteration state for one place
class state_of_a_place 
{
   integer current_index;
   integer max_index;
}

   // iteration administration for one transition
class iteration_admin
{
   boolean iteration_in_progress
   state_of_a_place[] state_of_places

   procedure increment
   {
         // move index through tokens
      FOR i IN state_of_places.count-1 .. 0 LOOP     
         IF state_of_places[i].current_index < state_of_places[i].max_index THEN
            state_of_places[i].current_index += 1
            return
         ELSE
            state_of_places[i].current_index = 0
            IF i = 0 THEN
               iteration_in_progress = FALSE
            END IF
         END IF
      END FOR         
   }
}

handle_transition (list_of_places)
{
      // initialize an object of type iteration_admin
   iteration_admin ia
   ia.iteration_in_progress = TRUE
   FOR i IN 0..list_of_places.count LOOP
      ia.state_of_places[i].current_index = 0
      ia.state_of_places[i].max_index = list_of_places[i].number_of_tokens
   END FOR

   WHILE ia.iteration_in_progress LOOP
         // build the argument list for the pass() method 
      token[] arguments
      FOR i IN 0..list_of_places.count LOOP
         arguments[i] = list_of_places[i].token[ia.state_of_places[i].current_index]
      END FOR

         // try to pass the guard
      call pass(arguments)
      IF (passed)
         // do whatever you need to do here
      ELSE
         ia.increment()
      END IF         
   END WHILE
}
于 2012-04-07T14:59:13.933 に答える