4

我正在开发高级 Petri 网编辑器/模拟器。首先，这里有一点词汇

圆圈=地方

矩形 =过渡

就地整数 =标记

过渡条件 =守卫

我坚持通过过渡的守卫。Guard 是一个条件，如果要执行转换，则必须为真。我知道我应该以某种方式使用回溯，但我不知道在程序开始之前进入转换的位置数量，所以我不能使用 for 循环，因为我不知道我需要多少个循环。

这是说明问题的图片 在此处输入图像描述

所以，我想从第一个地方拿第一个令牌，从第二个地方拿第一个令牌，然后尝试通过警卫，如果通过，然后保存令牌，并打破循环，如果为假，继续第二个地方的第二个令牌..等等...我终于以第一名的最后一个令牌（4）和第二名的最后一个令牌（2）通过了守卫。

我会知道如何编码，如果我有恒定数量的地方进入过渡，它看起来像这样

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

但正如我之前所说，我没有固定数量的地方进入过渡，所以我不能使用这种方法。所以，基本上，我需要尝试令牌的组合，并尝试通过警卫 - 直到我通过警卫，或者直到我尝试了所有组合。你有什么想法 ？伪代码就足够了。顺便说一句，我使用这些数据结构

地点列表 - 普通 java 列表，List places = new ArrayList();

并且每个地方都有自己的token列表，List tokens = new ArrayList();

///编辑：守卫具有以下格式：

op1 rel op2，其中 op1 是变量，op2 是常量或变量，rel 是关系 (<,>,=,...) 保护中可以有多个条件与逻辑运算符 AND 连接 - 例如：op1 rel op2 && op3 相对 op4 ...

- - 编辑：

所以我尝试实现 Rusil 算法，但它有很多错误，所以我发布了 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 绝对是胡说八道，因为 4 甚至不是放在首位...也是完全缺失的组合......像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

What about something like this:

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

Start it with call getPassed(places, []), where places is a list of places and [] is empty list. Note that you need to copy the lists always, so that you don't end up messing them up.

In the end, no need for pairs. If you keep the original places list you pass into the algorithm at the beginning, you know that token[i] was selected for originalPlaces[i].

But if you want to, you can keep tokenPlaces pairs instead of tokens, so something like this: 

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

EDIT: Still some confusion, hopefully this will make it clear. I am trying to generate the for loops recursively. So if places has only 2 elements, you get as you suggested:

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

So what it does is that it takes the first place from the list and creates the "for token in place 1" loop. Then it cuts of that place from the places list and adds the current token to the tokens list. This recursive call now does the "for token in place 2" loop. And so on. Every recursive call we decrease the number of places by 1 and create 1 for loop. Hence, after the places list is empty we have n nested loops, where n is the number of places and as far as I understand, this is what you were looking for.

You can initiate the method in the following way:

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

This way you can keep the originalPlaces unchanged and you can assign tokens[i] to originalPlaces[i] when you get to the base case in the recursion, i.e. when you try to determine the passing the guard. Hence you do not really need the pairs.

于 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。

接下来，您将有一个我将命名为iteration_admin 的类，它由一个state_of_place 数组和一个称为iteration_in_progress 之类的布尔值组成。创建后，布尔值设置为 TRUE。您将创建与地点一样多的 state_of_place 对象。Current_index 将是 0，max_index 将是那个地方的令牌数。

迭代管理类需要一个方法来表示循环变量的增量。让我们称之为增量（）。如果 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，则 boolean iteration_in_progress 将设置为 FALSE。这意味着，所有令牌组合都已使用。

现在，您尝试守卫的代码将

  • 初始化一个迭代管理类型的对象
  • 而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 回答