java – 使用递归进行回溯

2023-03-09 10:28:36

我正在开发高级petri网编辑器/模拟器.起初,这里有一点词汇

圈=地方

矩形=过渡

整数到位=代币

转型条件=警卫

而且我坚持不懈地通过过渡的后卫. Guard是一个条件,如果要执行转换,则需要为true.我知道我应该以某种方式使用回溯,但我不知道在程序开始之前进入转换的位数,所以我不能用于循环,因为我不知道我需要多少个.

这是说明问题的图片

所以,我想从第一个位置获取第一个令牌,从第二个位置获取第一个令牌,然后尝试传递防护,如果通过,则保存令牌,并打破循环,如果为false,则继续使用第二个位置的第二个令牌.等等…
我终于用第一名的最后一个标记(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();

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

///编辑：
警卫有以下格式：

op1 rel op2,
其中op1是变量,op2是常量或变量,rel是关系(<,>,=,…)
与逻辑运算符AND连接的保护可以有几个条件 – 例如：
op1 rel op2&& 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绝对是胡说八道,因为4甚至不是第一个……而且那里也是完全缺失的组合……如2,4,6等……任何人都明白为什么会这样？

编辑：现在它工作正常.

解决方法:

递归方法可以很容易：

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调用该函数.

希望这可以帮助.

码农公寓

相关文章