Backtracking mit Rekursion

Question

Ich entwickle High-Level-Petri-Net-Editor/Simulator. Zunächst ist hier ein kleines Vokabular

Kreis = Ort

Rechteck = Übergang

ganze Zahlen anstelle = Token

Zustand im Übergang = Wache

Und ich bin fest Beim Überschreiten der Wache des Übergangs. Guard ist eine Bedingung, die wahr sein muss, wenn Sie den Übergang ausführen möchten. Ich weiß, dass ich backtracking irgendwie verwenden sollte, aber ich weiß nicht, wieviele Plätze den Übergang vor dem Programmanfang betreten, also kann ich nicht für Schleifen verwenden, da ich nicht weiß, wieviele von ihnen ich brauchen werde.

Hier ist das Bild, dass das Problem, ich will erste Token nehmen So

zeigt vom ersten Platz, erste Token von dem zweiten Platz, dann versuchen die Wache zu übergeben, wenn übergeben, dann Token speichern, und brechen Sie die Schleife, wenn falsch, mit zweiten Token des zweiten Platzes fortsetzen .. etc ... Ich übergeben schließlich Wache mit letzten Token (4) des ersten Platzes, und letzte Token (2) des zweiten Platzes.

Ich würde wissen, wie das codieren, wenn ich den Übergang konstante Zahl der Plätze hatte Eingabe, würde es wie folgt aussieht

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

aber wie ich schon sagte, ich nicht konstante Zahl der Plätze haben Übergang Eingabe , also kann ich diesen Ansatz nicht verwenden. Also, im Grunde muss ich Kombinationen von Tokens versuchen und versuchen, die Wache zu übergeben - bis ich die Wache übergeben, oder bis ich alle Kombinationen ausprobiert. Haben Sie irgendwelche Ideen? Pseudocode wäre genug. Nebenbei verwende ich diese Datenstruktur

Liste der Orte - normale Java-Liste, Liste Orte = neue ArrayList();

und jeder Ort hat seine eigene Liste von Token, List tokens = new ArrayList();

/// EDIT: die Wache hat folgendes Format:

op1 rel op2, wo op1 variabel ist, und op2 konstant oder variabel ist, rel Beziehung (<,>, =, ... op1 rel op2 & & op3 rel op4 ...

---- EDIT:

Beispiel -) es kann mit dem logischen Operator UND verbunden mehrere Bedingungen in der Hut sein

Also habe ich versucht, den Rushil-Algorithmus zu implementieren, aber es ist ziemlich fehlerhaft, also gebe ich SSCCE ein, damit du es ausprobieren und vielleicht ein wenig helfen kannst.

Zunächst Platz Klasse erstellen:

public class Place { 
public List<Integer> tokens ; 

//constructor 
public Place() { 

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

} 

Und dann testen Klasse:

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; 

} 
} 

und hier ist der Ausgang dieses Code:

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, 

Also, Sie sehen, einige Kombinationen sind korrekt, wie 1,3,6 und 1,3,7 ... aber 4,5,8 ist absoluter Unsinn, da 4 nicht einmal an erster Stelle steht ... und ther Es gibt auch Kombinationen, die komplett fehlen ... wie 2,4,6 etc ... jeder sieht warum ist das so?

EDIT: Jetzt funktioniert es gut.

Answer 1

Was ist so etwas wie dieses:

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 

es Beginnen Sie mit Aufruf getPassed (Orte, []), wo Orte eine Liste von Orten und [] ist leere Liste. Beachten Sie, dass Sie die Listen immer kopieren müssen, damit Sie sie nicht in Unordnung bringen.

Am Ende, keine Notwendigkeit für Paare. Wenn Sie die Liste der ursprünglichen Orte beibehalten, die Sie am Anfang in den Algorithmus eingeben, wissen Sie, dass token [i] für originalPlaces [i] ausgewählt wurde.

Aber wenn Sie wollen, können Sie tokenPlaces Paare anstelle von Token, so etwas wie dies halten:

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: Noch einige Verwirrung, hoffentlich wird dies deutlich machen. Ich versuche, die for-Schleifen rekursiv zu generieren. Also, wenn Orte nur zwei Elemente hat, erhalten Sie, wie Sie vorgeschlagen:

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

Also, was es tut, ist, dass sie den ersten Platz in der Liste nimmt und schafft die „für Token anstelle 1“ Schleife. Dann schneidet es den Ort von der Ortsliste ab und fügt das aktuelle Token der Token-Liste hinzu. Dieser rekursive Aufruf führt nun die Schleife "für Token an Ort und Stelle 2" durch. Und so weiter. Bei jedem rekursiven Aufruf verringern wir die Anzahl der Stellen um 1 und erstellen 1 für Schleife. Daher haben wir, nachdem die Platzliste leer ist, n verschachtelte Schleifen, wobei n die Anzahl der Plätze ist und soweit ich weiß, ist es genau das, wonach Sie gesucht haben.

Sie können die Methode auf folgende Weise einleiten:

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

Auf diese Weise können die originalPlaces unverändert halten und Sie können Token zuweisen [i] zu originalPlaces [i], wenn Sie zum Basisfall erhalten in die Rekursion, dh wenn du versuchst, den vorbeikommenden Wächter zu bestimmen. Daher brauchst du die Paare nicht wirklich.

Answer 2

Ein rekursive Ansatz wäre es leicht machen:

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 
} 

Rufen Sie die Funktion zunächst mit dem Index = 0.

Hoffnung, das hilft. :-)

Answer 3

Sie könnten die Schleifenverwaltung selbst durchführen. Was ich meine ist: Sie würden eine Klasse benötigen, um den Iterationsstatus für jeden Ort darzustellen. Lässt es sich state_of_place nennen. Es würde aus zwei Werten bestehen: einem current_index und einem max_index.

Als nächstes hätten Sie eine Klasse, die ich iteration_admin nennen würde, die aus einem Array von state_of_place und einem Booleschen Element wie iteration_in_progress besteht. Nach der Erstellung wird der Boolesche Wert auf TRUE gesetzt. Sie würden so viele state_of_place-Objekte erstellen, wie es Orte gibt. Current_index wäre 0, max_index wäre die Anzahl der Token an diesem Ort.

Die Klasse iteration_admin benötigt eine Methode, um das Inkrement von Schleifenvariablen darzustellen. Lässt es inkrement() aufrufen. Diese Methode würde den current_index des state_of_place-Elements mit dem höchsten Index inkrementieren, wenn der current_index immer noch unter dem max_index liegt. Wenn der current_index gleich dem max_index ist, wird der aktuelle Index auf 0 gesetzt und der aktuelle Index des state_of_place mit dem nächstniedrigeren Index muss inkrementiert werden. Wenn dieser Max_index erreicht hat, wird er auf 0 gesetzt und der nächst niedrigere wird inkrementiert, und so weiter. Die einzige Ausnahme ist natürlich state_of_place [0]. Wenn diese Elemente current_index ihren max_index überschreiten würden, wird die boolesche iteration_in_progress auf FALSE gesetzt. Dies würde bedeuten, dass alle Tokenkombinationen verwendet wurden.

nun Ihren Code für den Versuch, die Wache würde

• iteration_admin
• ein Objekt vom Typ initialisieren, während iteration_admin.iteration_in_progress TRUE ist
• unter Verwendung der Argumentliste für den Pass() -Methode bauen CURRENT_INDEX die Werte in den Elementen state_of_place
• Anrufdurchlauf()
• wenn nicht bestanden, rufen die iteration_admin.increment() Methode
• Ende, während

EDIT: Der Versuch, die Idee in Pseudo-Code auszudrücken. Ich fürchte, es sieht eher wie eine Mischung aus Java und PL/SQL aus als abstrakter Pseudocode. Trotzdem sollte es etwas klarer sein als meine Textbeschreibung.

// 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 4

Angenommen Transition hat eine isEnabled() -Methode sowie Eingabe/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 
}