我正在开发高级 Petri 网编辑器/模拟器。首先,这里有一些词汇
circle = place
矩形 = 过渡
适当的整数 = token
过渡条件 = 守卫
我一直坚持通过过渡的守卫。 Guard 是一个条件,如果你想执行转换,它必须为真。我知道我应该以某种方式使用回溯,但我不知道在程序开始之前有多少地方进入转换,所以我不能使用 for 循环,因为我不知道我需要多少循环。
这是说明问题的图片
所以,我想从第一位取第一个 token ,从第二位取第一个 token ,然后尝试通过守卫,如果通过,则保存 token ,并打破循环,如果为假,则继续第二位的第二个 token ..ETC... 我终于用第一名的最后一个标记 (4) 和第二名的最后一个标记 (2) 通过了守卫。
我会知道如何编写代码,如果我有固定数量的地方进入转换,它看起来像这样
for token in place 1
for token in place 2
try pass guard
if (passed)
save tokens
break;
但正如我之前所说,我没有固定数量的地方进入过渡,所以我不能使用这种方法。 所以,基本上,我需要尝试 token 的组合,并尝试通过守卫 - 直到我通过守卫,或者直到我尝试了所有组合。 你有什么想法 ?伪代码就足够了。 顺便说一句,我使用这些数据结构
地方列表——普通java列表,List places = new ArrayList();
并且每个地方都有自己的token列表,List tokens = new ArrayList();
///编辑: guard 具有以下格式:
op1 rel op2, 其中 op1 是变量,op2 是常量或变量,rel 是关系 (<,>,=,...) 在 guard 中可以有多个条件与逻辑运算符 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
}
最初使用索引 = 0 调用函数。
希望这对您有所帮助。 :-)
关于java - 递归回溯,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10053775/