Verwendung von Java-Datenstrukturen und -Algorithmen zur Implementierung von Rekursion und Backtracking

1. Was ist Rekursion?

Einfach ausgedrückt: Bei der Rekursion ruft sich eine Methode selbst auf und übergibt bei jedem Aufruf unterschiedliche Variablen. Die Rekursion hilft Programmierern bei der Lösung komplexer Probleme und macht den Code prägnant.

Schauen Sie sich ein praktisches Anwendungsszenario an: Labyrinthproblem (Backtracking), Rekursion (Rekursion)

Ich werde zwei kleine Fälle auflisten, um Ihnen das Verständnis der Rekursion zu erleichtern.

? Summe der Bälle Korbproblem (Google-Programmierwettbewerb).

• Rekursion wird auch in verschiedenen Algorithmen verwendet, z. B. Schnellsortierung, Zusammenführungssortierung, binäre Suche, Divide-and-Conquer-Algorithmus usw.

• Die Probleme, die mit dem Stack gelöst werden sollen -> Der Code ist relativ prägnant.

Wichtige Regeln für die Rekursion

• Wenn eine Methode ausgeführt wird, wird ein neuer geschützter unabhängiger Raum (Stapelraum) erstellt.

• Die lokalen Variablen der Methode sind unabhängig und beeinflussen sich nicht gegenseitig, wie z. B. die Variable n.

• Wenn in der Methode eine Referenztypvariable (z. B. ein Array) verwendet wird, werden die Daten des Referenztyps gemeinsam genutzt.

Rekursion muss sich den Bedingungen zum Beenden der Rekursion nähern, andernfalls handelt es sich um eine unendliche Rekursion, ein StackOverflowError wird angezeigt und Sie sind tot :).

• Wenn eine Methode die Ausführung abschließt oder auf eine Rückgabe stößt, gibt sie das Ergebnis an denjenigen zurück, der sie aufruft. Gleichzeitig schließt die Methode auch die Ausführung ab.

• 2. Code-Fall 1 – Labyrinthproblem

• Erläuterung: Der Weg, den der Ball nimmt, hängt mit der vom Programmierer festgelegten Wegfindungsstrategie zusammen, das heißt: der Wegfindungssequenz von oben, unten, links , und rechts beziehen sich auf den Ball. Wenn Sie einen Pfad auswählen, können Sie zuerst (unten rechts, oben links) verwenden und ihn dann in (oben rechts, unten links) ändern, um zu sehen, ob sich der Pfad ändert. Test auf Backtracking-Phänomene.

public static void test(int n) {
    if (n > 2) {
	    test(n - 1);
    }
    System.out.println("n=" + n);
}
 
public static int factorial(int n) {
    if (n == 1) {
        return 1;
    } else {
        return factorial(n - 1) * n;
    }
}

3. Code-Fall 2 – Acht-Damen-Problem

• Das Acht-Damen-Problem ist ein altes und berühmtes Problem und ein typischer Fall eines Backtracking-Algorithmus. Dieses Problem wurde 1848 vom internationalen Schachspieler Max Bethel aufgeworfen: Platzieren Sie acht Damen auf einem 8×8-Schachgitter, damit sie sich nicht gegenseitig angreifen können, das heißt: Es dürfen keine zwei Damen auf der gleichen Position sein in Reihen, Spalten oder Diagonalen?

Die erste Königin wird zuerst in die erste Reihe und erste Spalte gelegt.

Platzieren Sie die zweite Königin in der zweiten Reihe und der ersten Spalte und stellen Sie dann fest, ob sie in Ordnung ist. Wenn nicht, platzieren Sie sie weiterhin in der zweiten und dritten Spalte und platzieren Sie dann alle Spalten, um eine geeignete zu finden .

Fahren Sie mit der dritten Königin oder der ersten und zweiten Spalte fort... bis die 8. Königin in einer konfliktfreien Position platziert werden kann, kann dies als korrekte Lösung angesehen werden.

Wenn eine korrekte Lösung gefunden wurde und der Stapel auf den vorherigen Stapel zurückgerollt wird, beginnt er mit der Rückverfolgung, d. h., die erste Königin wird in die erste Spalte eingefügt und alle richtigen Lösungen werden angezeigt.

Gehen Sie dann zurück und platzieren Sie weiterhin die erste Königin in der zweiten Spalte und führen Sie die Schritte 1, 2, 3 und 4 in einer Schleife aus.

package com.szh.recursion;
 
/**
 * 走迷宫问题
 */
public class MiGong {
 
    //使用递归回溯来给小球找路, 说明:
    //1. map 表示地图
    //2. i,j 表示从地图的哪个位置开始出发 (1,1)
    //3. 如果小球能到 map[6][5] 位置，则说明通路找到.
    //4. 约定：当 map[i][j] 为 0 表示该点没有走过; 当为 1 表示墙; 2 表示通路可以走;
    //5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
    public static boolean setWay(int[][] map, int i, int j) {
        //此时走到了迷宫终点
        if (map[6][5] == 2) {
            return true;
        } else {
            if (map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 下->右->上->左  走
                map[i][j] = 2;
                if (setWay(map, i + 1, j)) { //下
                    return true;
                } else if (setWay(map, i, j + 1)) { //右
                    return true;
                } else if (setWay(map, i - 1, j)) { //上
                    return true;
                } else { //左
                    return true;
                }
            } else { //map[i][j] != 0, 即只能为1、2。 1表示墙（无法走），2表示已经走过了，所以此时直接返回false
                return false;
            }
        }
    }
 
    //修改找路的策略，改成 上->右->下->左
    public static boolean setWay2(int[][] map, int i, int j) {
        if(map[6][5] == 2) { // 通路已经找到ok
            return true;
        } else {
            if(map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 上->右->下->左
                map[i][j] = 2;
                if(setWay2(map, i - 1, j)) { //上
                    return true;
                } else if (setWay2(map, i, j + 1)) { //右
                    return true;
                } else if (setWay2(map, i + 1, j)) { //下
                    return true;
                } else { //左
                    return true;
                }
            } else {
                return false;
            }
        }
    }
 
    public static void main(String[] args) {
        //先创建一个二维数组，模拟迷宫 (地图)
        int[][] map = new int[8][7];
        //使用迷宫中的部分格子表示墙体（置1）
        //第一行和最后一行置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //第一列和最后一列置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //多添加两块墙体
        map[3][1] = 1;
        map[3][2] = 1;
//      map[1][2] = 1;
//		map[2][2] = 1;
        //输出地图查看
        System.out.println("原始迷宫地图为：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
 
        //使用递归回溯走迷宫
        setWay(map, 1, 1);
//        setWay2(map, 1, 1);
        System.out.println("小球走过，并标识过的地图的情况：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Tatsächlich können Sie den Backtracking-Prozess durch Debuggen des Codes sehen, daher werde ich nicht mehr sagen.

Das obige ist der detaillierte Inhalt vonVerwendung von Java-Datenstrukturen und -Algorithmen zur Implementierung von Rekursion und Backtracking. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!