Suche nach allen möglichen Pfaden

Question

Ich habe ein Problem, alle möglichen Wege zu finden.

a a a b

b a a a

a b b a

von Reisen Punkt bei 0,0 2,3 Ausgangspunkt am Ende. Ich muss alle möglichen Wege bekommen.

Mögliche Bewegungen, die ich tun kann, sind nach unten und bewegt sich nach rechts.

Lassen Sie mich Ihnen sagen, wo ich feststecke. Ich versuche, mit einer rekursiven Funktion zu tun. Ich beginne mit Punkt bei 0,0 und bewege mich nach rechts, wann immer ich kann, und bewege mich nur dann abwärts, wenn ich muss.

Meine rekursive Funktion:

public static move(int i,int j) 
{ 
    if(possible(x,y+1)) 
    { 
     move(x,y+1); 
     move(x+1,y); 
    } 

} 


public static bool possible(int i,int j) 
     { 
      if((i >=0 && i<3) && (j>=0 && j<4)) 
       return true; 
      else 
       return false; 

     } 

Nicht sicher meine rekursive Move-Funktion. Muss es noch erweitern. Ich verstehe nicht genau, wie ich es umsetzen soll.

Ich bin in der Lage, bis zu den Eckknoten mit dieser Move-Methode zu durchlaufen, aber ich brauche diese Funktion, um zurückzuverfolgen, wann immer alle möglichen Bewegungen von der Ecke oben rechts (0,4) erreicht wird.

Answer 1

public void MoveUp(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveUp(e.CurrentPosition.Y)) ... 
    } 
    public void MoveDown(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveDown(e.CurrentPosition.Y)) ... 
    } 
    public void MoveLeft(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveLeft(e.CurrentPosition.X)) ... 
    } 
    public void MoveRight(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveRight(e.CurrentPosition.X)) ... 
    } 
    private bool CanMoveUp(double y) => (y - 1) > 0; 
    private bool CanMoveDown(double y) => (y + 1) < 4; 
    private bool CanMoveLeft(double x) => (x - 1) > 0; 
    private bool CanMoveRight(double x) => (x + 1) < 4; 

Diese Werte können nicht richtig sein, aber der Code ist wiederverwendbar und leicht zu pflegende im Falle Sie wollen würde keine andere mögliche Hindernisse für die Bewegung hinzuzufügen, die Sie leicht die Ergänzungen zu jeder Methode hinzufügen könnte.

Answer 2

Es ist schwer, die Farm nicht zu verschenken und hilfsbereit zu sein. Sie sollten die Entscheidungslogik zu 3 Grenzfunktionen

inBoundsX x 
    // return true if x is in bounds, false otherwise 

inBoundsY y 
    // return true if y is in bounds, false otherwise 

inBoundsXY x,y 
    // return true if x and y are in bounds, false otherwise 

Ihre rekursive Funktion sollte immer den Anfangszustand bestätigt es gegeben, dann entscheiden brechen, welcher Weg weiter zu bewegen.

move x,y 
    if inBoundsXY x,y 
     print I am here x,y 
     // use InboundsX, InboundsY to decide next move. 

Answer 3

Sie müssen anhalten und einen großen Schritt zurück machen.

Der erste Schritt sollte mit der Signatur der Methode kommen. Was ist die Problemstellung?

Suche alle möglichen Pfade

Nicht erwähnt: von einem bestimmten Ausgang koordinieren.

So benötigt das Verfahren einen Satz von Pfaden zurückzukehren:

static Set<Path> AllPaths(Coordinate start) { /* a miracle happens */ } 

OK, jetzt kommen wir weiter; Jetzt ist klar, was wir brauchen. Wir brauchen eine Menge Dinge, und wir brauchen einen Pfad, und wir brauchen Koordinaten.

Was ist eine Koordinate?ein Paar Ganzzahlen:

struct Coordinate 
{ 
    public int X { get; } 
    public int Y { get; } 
    public Coordinate(int x, int y) : this() 
    { 
    this.X = x; 
    this.Y = y; 
    } 
} 

Fertig. Also knall den Stapel. Was ist ein Pfad? Ein Pfad kann leer sein, oder es kann ein erster Schritt gefolgt von einem Pfad sein:

Erledigt.

Jetzt implementieren Sie Set<T>. Sie müssen die Operationen "alle Elemente" und "Union dies mit einem anderen, um ein Drittel zu produzieren" haben. Stellen Sie sicher, dass die Sätze unveränderlich sind. Sie möchten einen Satz nicht ändern, wenn Sie ihm neue Gegenstände hinzufügen. Sie möchten ein anderes Set. Genauso wie du 3 nicht in 4 änderst, wenn du 1 hinzufügst; 3 und 4 sind unterschiedliche Nummern.

Jetzt haben Sie alle Werkzeuge, die Sie benötigen, um das Problem tatsächlich zu lösen; Jetzt können Sie implementieren

static Set<Path> AllPaths(Coordinate start) 
{ 
    /* a miracle happens */ 
} 

Also, wie funktioniert das? Denken Sie daran, dass alle rekursiven Funktionen die gleiche Form haben:

• Lösen Sie den trivialen Fall
• Wenn wir nicht in einem trivialen Fall sind, reduzieren das Problem auf einen kleineren Fall lösen sie rekursiv, und kombinieren Lösungen.

Also was ist der triviale Fall?

static Set<Path> AllPaths(Coordinate start) 
{ 
    /* Trivial case: if the start coordinate is at the end already 
     then the set consists of one empty path. */ 

Implementieren Sie das.

Und was ist der rekursive Fall?

/* Recursive case: if we're not at the end then either we can go 
     right, go down, or both. Solve the problem recursively for 
     right and/or down, union the results together, and add the 
     current coordinate to the top of each path, and return the 
     resulting set. */ 

Implementieren Sie das.

Die Lektionen sind hier:

• Machen Sie eine Liste aller Substantive im Problem: set, Weg, koordinieren und so weiter.
• Machen Sie einen Typ, der jede repräsentiert. Halten Sie es einfach und stellen Sie sicher, dass Sie genau die Operationen implementieren, die jeder Typ benötigt.
• Nun, da Sie eine Abstraktion für jedes Substantiv implementiert haben, können Sie damit beginnen, Algorithmen zu entwerfen, die die Abstraktionen verwenden, mit der Gewissheit, dass sie funktionieren.
• Denken Sie an die Grundregeln der Rekursion: Lösen Sie den Basisfall, wenn Sie können; Wenn nicht, lösen Sie die kleineren rekursiven Fälle und kombinieren Sie die Lösungen.