递归回溯

Question

我正在开发高级培养皿网络编辑器/模拟器。首先，这里有一些词汇

圆圈=位置

矩形=过渡

就地整数 = 标记

过渡状态=防护

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

所以，我想从第一位获取第一个令牌，从第二位获取第一令牌，然后尝试通过守卫，如果通过，则保存令牌，并打破循环，如果为假，继续使用第二位的第二令牌..等等…我最终使用第一位的最后一个令牌（4）和第二位最后一个符号（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是关系(

----编辑：

所以我尝试实现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等等...有人知道为什么会这样吗？

编辑：现在它运行良好。

Answer 1

那么像这样的东西呢：

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 是一个地点列表，[] 是空列表。请注意，您需要始终复制列表，以免最终弄乱它们。

最后，不需要配对。如果您保留在开始时传递到算法中的原始位置列表，您就知道标记[i]是为原始位置[i]选择的。

但是如果你愿意，你可以保留tokensPlaces对来代替token，比如:

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 个，并创建 1 个 for 循环。因此，在地点列表为空之后，我们有n个嵌套循环，其中n是地点的数量，据我所知，这就是你正在寻找的。

您可以通过以下方式启动该方法：

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

这样，您可以保持原始位置不变，并且当您到达递归中的基本情况时，即当您尝试确定传递保护时，您可以将令牌[i]分配给原始位置[i]。因此，您并不真正需要这些对。

Answer 2

您可以自己进行循环管理。我的意思是：你需要一个类来描述每个地方的迭代状态。让我们称之为state_of_place。它由两个值组成：一个current_index和一个max_index。

接下来，您将有一个名为iteration_admin的类，它由一个state_of_place数组和一个类似iteration _in_progress的布尔值组成。创建时，布尔值设置为TRUE。您将创建尽可能多的state_of_place对象。Current_ index将为0，max_。

iteration_admin类需要一个方法来表示循环变量的增量。让我们称之为increment()。如果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 is true
• 通过使用state_of_place元素中的current_index值为 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
}

Answer 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
}

最初调用索引 = 0 的函数。

希望这有所帮助。:-)