Introduction aux algorithmes avec java --Search (recherche de priorité de largeur)

Résumé de l'article

Il s'agit d'une série d'articles que j'ai compilés dans mon étude et mon mémo. Le troisième. Ceci est une suite de cet article. Introduction aux algorithmes avec java --Search (recherche prioritaire en profondeur) Dans cet article

• Recherche de priorité large

Je vais étudier sur.

Recherche de priorité de largeur

Il est également appelé BFS (recherche en largeur d'abord). (Largeur: largeur) J'écrirai ceci pendant mes études. Pour connaître la différence par rapport à la recherche de priorité de profondeur qui ressemble à un arbre, consultez cet article «Introduction aux algorithmes avec java-Search (Depth Priority Search)» S'il te plait donne moi.

Il semble être efficace pour des problèmes tels que la recherche de l'itinéraire le plus court d'un labyrinthe.

Il semble qu'une structure de données appelée file d'attente soit utilisée comme méthode de mise en œuvre. Recherche prioritaire approfondie, pile "premier entré, dernier sorti", Gardez à l'esprit que les recherches en largeur d'abord utilisent des files d'attente "premier entré, premier sorti".

De plus, la recherche de priorité en profondeur pourrait être mise en œuvre par récursive, mais il semble qu'elle soit impossible ou difficile à traiter dans l'ordre de la file d'attente si elle est récursive. Utilisez-vous la file d'attente? .. Je ne veux pas me souvenir de nouvelles bibliothèques ou types au début de mes études. .. .. Je n'ai pas l'impression de pouvoir l'utiliser tout de suite. ..

À propos, des piles et des files d'attente apparaîtront dans l'examen d'ingénieur de l'information de base, donc je pense que ça va, mais je ne sais pas! Pour ceux qui disent, cet article "Piles et files d'attente extrêmes! ~ Dossier spécial sur les idées et utilisations ~" semble être facile à comprendre, alors étudiez-le. Faisons le.

Pour le moment, l'exemple est facile à comprendre Dernière fois J'ai pensé essayer arc031-b implémenté dans DFS, mais il peut ne pas convenir à BFS. Je vais donc essayer un autre exemple.

Exemple: AtCoder --agc033-a "Darker and Darker"

H　W
A11 A12 ... A1W
:
AH1 AH2 ... AHW

[Exemple de réponse]

main.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// height
		int h = sc.nextInt();

		// width
		int w = sc.nextInt();

		//État des carrés
		char[][] masu = new char[h][w];

		//Préparer la file d'attente BFS
		Deque<XY> q = new ArrayDeque<>();

		//Recevoir des entrées& '#'EnQueue
		for (int i = 0; i < h; i++) {
			masu[i] = sc.next().toCharArray();
			for (int j = 0; j < w; j++) {
				if ('#' == masu[i][j]) {
					q.add(new XY(i, j, 0));
				}
			}
		}

		// ans
		int max_depth = 0;

		//Traitement principal BFS
		for (;;) {
			//Début de boucle infinie

			//Conditions de sortie
			if (q.size() < 1) {
				break;
			}

			//file d'attente pour retirer la file d'attente
			//méthode de sondage récupère de la file d'attente&Supprimer de la file d'attente
			XY xy = q.poll();
			int x = xy.x;
			int y = xy.y;
			int depth = xy.depth;

			//Enregistrer le nombre d'opérations
			if (depth >= max_depth) {
				max_depth = depth;
			}

			//Rendre la zone autour de la position actuelle noire
			if (x + 1 < w && masu[y][x + 1] == '.') {
				//Carré droit
				masu[y][x + 1] = '#';
				q.add(new XY(y, x + 1, depth + 1));
			}
			if (x - 1 >= 0 && masu[y][x - 1] == '.') {
				//Carré gauche
				masu[y][x - 1] = '#';
				q.add(new XY(y, x - 1, depth + 1));
			}
			if (y + 1 < h && masu[y + 1][x] == '.') {
				//Carré inférieur
				masu[y + 1][x] = '#';
				q.add(new XY(y + 1, x, depth + 1));
			}
			if (y - 1 >= 0 && masu[y - 1][x] == '.') {
				//Carré supérieur
				masu[y - 1][x] = '#';
				q.add(new XY(y - 1, x, depth + 1));
			}

		}

		System.out.println(max_depth);

	}
}

class XY {
	int y;
	int x;

	int depth;

	XY(int y, int x, int d) {
		this.x = x;
		this.y = y;
		depth = d;
	}
}

C'est comme ça. La politique est la suivante.

--Dans l'état initial, placez les informations du carré noir dans la file d'attente. (Coordonnées, combien de fois il est devenu noir (= profondeur))

• Obtenez des informations de la file d'attente et recherchez les carrés en haut, en bas, à gauche et à droite de cette coordonnée. S'il est blanc, rendez-le noir, augmentez la profondeur et stockez-le dans la file d'attente. Si c'est noir, je ne fais rien. --Répétez jusqu'à ce qu'il n'y ait plus de données de la file d'attente (≒ tout noir).

Dans cet ordre, les profondeurs sont toujours 0, 1, 2 ... et elles entrent dans la file d'attente dans l'ordre, donc la profondeur quand elle devient noire est la profondeur minimale de ce carré, donc une fois qu'il devient noir, c'est OK. Je suis reconnaissant pour cela.

À propos, est-ce une variante de la recherche de priorité de largeur ou est-il classé comme un type de BFS avec plusieurs points de départ? Cela semble être fait.

J'ai appris à utiliser la file d'attente plutôt que la recherche de priorité de largeur. Lol Je pense que j'utilise beaucoup la méthode de sondage de Deque, donc je veux vraiment m'en souvenir.

J'aimerais voir visuellement le mouvement lors de sa mise en œuvre avec la recherche de priorité de largeur cette fois-ci, mais comme j'ai appris de l'article précédent (je pensais que vous pouvez le comprendre, w) je vais m'arrêter. ** J'ai écrit des commentaires dans le code d'une manière facile à comprendre, veuillez donc les suivre. ** **

Si cela est écrit pour le moment, il semble que l'application fonctionnera. Le reste est un exercice problématique. Après avoir appris la théorie, pratiquez-la à plusieurs reprises et installez-vous en vous-même. Je veux suivre les chiffres.

C'est tout pour cette fois. La prochaine fois, je parlerai de la recherche peu complète. impatient de!