Para comprender el problema de 15puzzle, aprendí sobre la búsqueda de profundidad y la búsqueda de amplitud primero. Primero discutamos la búsqueda de profundidad (DFS). El propósito de la profundidad primero es priorizar la búsqueda de rutas que estén más alejadas desde el vértice inicial, mientras que la búsqueda de amplitud primero es buscar primero las rutas que estén más cercanas al vértice inicial. Me pregunto cuál es la diferencia entre la búsqueda de profundidad y retroceso. En Baidu, se dice que el retroceso es un tipo de búsqueda profunda, pero la diferencia es que el retroceso no retiene el árbol de búsqueda. Entonces, ¿qué pasa con la búsqueda de amplitud (BFS)? ¿Cuáles son sus aplicaciones? Respuesta: La ruta más corta, el problema de la división de vinos, ocho problemas digitales, etc. Volvamos al grano, aquí simplemente he implementado una búsqueda amplia y una búsqueda profunda usando Java. Entre ellos, la búsqueda profunda se implementa utilizando Graph + Stack, y la búsqueda amplia se implementa utilizando Graph + Queue. El código es el siguiente:
1. Cree una nueva clase NodirectionGraph que represente "gráfico no dirigido"
paquete com.wly.algorithmbase.dataStructure;/** * gráfico no dirigido * @author wly * */public class nodirectionGraph {private int mmaxSize; // El número máximo de vértices contenidos en el gráfico de gráfico privado [] vértexlist; // el vértice de vértices privado intu. private int nVertex;//The number of vertices currently saved public NoDirectionGraph(int maxSize) {mMaxSize = maxSize;vertexList = new GraphVertex[mMaxSize];indicatorMat = new int[mMaxSize][mMaxSize];nVertex = 0;//Initialize the adjacency matrix element to 0 for (int j = 0; j <mmaxSize; j ++) {for (int k = 0; k <mmaxSize; k ++) {indicatormat [j] [k] = 0;}} public void addvertex (Graphvertex v) {if (nvertex <mMaxSize) {vertexlist [nvertex ++] = v; v;} else {System.out.println ("--- Inserción fallida, el número de vértices ha alcanzado el límite superior!");}}/*** Modifique la matriz de adyacencia y agregue un nuevo borde* @param start* @param end*/public void (int inicio, int end) {indicatormat [inicio] [end] = 1; indicatormat [end] [end] [start] adjacency matrix*/public void printIndicatorMat() {for (int[] line:indicatorMat) {for (int i:line) {System.out.print(i + " ");}System.out.println();}}/** * Depth priority traversal* @param vertexIndex Index represents the starting point to traverse, that is, the number of rows in the adjacency matriz de la gráfica */public void dfs (int VertexIndex) {ArrayStack stack = new ArrayStack (); // 1. Agregue el elemento de búsqueda a la pila vértice [VertexIndex] .setVisited (true); stack.push (vérticeDex); int nextvertexIndex = getNextverTexIndex (VertexIndex); mientras (! stack.isEmpty ()) {// presione continuamente la pila y salga de la pila hasta que la pila esté vacía (el elemento de búsqueda no aparece la pila) if (nextverTexIndex! = -1) {vertexList [nextvertexIndex] .SetVisted (true); stack.push (nextvertexIndex); stack.printeLems ();} {stack.pop ();} // recuperar si el elemento superior actual contiene otros nodos no atravesados if (! stack.isEmpty ()) {nextvertexIndex = getNextversexIndex (stack.peek ());}}}/** * Obtener la línea donde el próximo vértice del vertex actual se encuentra * @param columna * @retreturn */público público INT. {for (int i = 0; i <indicatormat [columna] .length; i ++) {if (indicatormat [columna] [i] == 1 &&! vertexlist [i] .isVisited ()) {return i;}} return -1;}/*** Breadth -First Traversal* @Param Vertexindex representa el punto de partida a TRAVEREDE, que es, lo que es, lo que es, el número de ráfaga de pan, lo que es, lo que es el número de RAWS de Breadth, que es el número de RAWS de la gran cantidad de RAWS de Breadth, que es el número de RAWS de BreetTh Bread, que es el número de RAWS de la gran cantidad de RAWS de BreadTh. La matriz de adyacencia de la gráfica*/public void bfs (int vérticexIndex) {Chainqueue queue = new Chainqueue (); vertexList [VERTEXIndex] .SetVisited (true); queue.insert (new QueUeNode (vertexIndex); int nextEverxIndex = getNextverxIndex (vertexindex); while (! queue.isEmpty ()) {if (nextvertexIndex! = -1) {verTexList [nextverTexIndex] .setVisited (true); queue.insert (new QueUeDe (nextverxIndex));} else {queue.remove ();} if (! Queue.isempty ()) {nextvertExEx getNextverTexIndex (queue.peek (). Data); queue.printelems ();}}}}2. Luego hay un ArrayStack que se simula con una matriz
paquete com.wly.algorithmbase.dataStructure;/***Use matrices para implementar la estructura de pila*@author wly**/public class ArrayStack {private int [] tarray; private int topIndex = -1; // indicar la posición de índice del elemento superior actual de la apuesta intacciones privadas de apila Array genérico ***/Tarray = new int [capacidad_step];}/***El método para aparecer en el elemento superior*@return*/public int pop () {if (isEmpty ()) {System.out.println ("Error, el elemento en la pila está vacío, no puede pop"); return -1;} else {int i = Tarray [topIndex]; tArray [topIndex--] = -1; // borra el retorno del elemento pop i;}}/*** Inserte un elemento en el stack* @param t*/public void Push (int t) {// verificar si la pila es si (topindex == (tarray.length-1)) {// extiende int [tarray.length + capacidad_step]; para (int i = 0; i <tarray.length; i ++) {Temparray [i] = Tarray [i];} Tarray = Temparray; {if (isEmpty ()) {System.out.println ("Error, el elemento en la pila está vacío, no se puede mirar"); return -1;} else {return Tarray [topIndex];}}/*** verifique si el piloto actual está vacío* @return*/público boolean isEtimty () {return (topindex <0);}/*** Elements in the imprime*/treid the imprime in the imprime el stint*/treid the imprime in the imprime* printelems () {for (int i = 0; i <= topIndex; i ++) {System.out.print (Tarray [i]+"");} System.out.println ();}}3. Chainqueue en una cola simulada con listas vinculadas
paquete com.wly.algorithmbase.dataStructure;/** * Use la lista vinculada para implementar la cola * * @author wly * */public class Chainqueue {private QueUenode Head; // apunte al jefe del jefe de cola privada de la cola privada; // apunte a la cola de la cola del tamaño de la cola de nuevo = 0; nodo a la cola de la cola*/public void Insert (queueNode nodo) {// Por supuesto, también puede escribir esto, agregar tail.prev = node if (head == null) {head = node; tail = head;} else {node.next = tail; tail.prev = node; // conexión bidirectional para asegurarse de que ese head.prevev no es vacío vacío = nodo;} size ++;}/*** Eliminar el nodo del cabezal de la cola*/public queueNode remove () {if (! isEmpty ()) {QueUenode temp = head = head.prev; size-; return temp;} else {System.out.println ("Operación de excepción actual está vacía!"); vacía * * * @return */public boolean isEtimty () {if (size> 0) {return false;} else {return true;}}/** * return el primer nodo de la cola, pero no eliminar */public queueNode Peek () {if (! isEtimty ()) {return; La cola actual está vacía! "); return null;}}/*** return the size de la cola** @return*/public int size () {return size;}/*** Imprimir elementos en la cola*/public void imprimeLems () {QueUeNode tempnode = head; while (tempnode! = null) {system.print (tempnode.print (tempnode.dates "); tempnode = tempnode.prev;} system.out.println ();}}/** * class de nodo * * @author wly * */class queueNode {QueUeNode previos; queueNode next; int data; public queueNode (int data) {this.data = data;} int getData () setData (int data) {this.data = data;}@anular public String toString () {// TODO Método generado automático stub super.ToString (); return data + "";}}4. Test test_bfs_dfs
paquete com.wly.algorithmbase.search; import com.wly.algorithmbase.dataStructure.graphvertex; import com.wly.algorithmbase.dataStructure.nodirectionGraph;/** * Búsqueda de profundidad basada en gráficos * @Author wly * */public class test_bfs_dfs {public void void Main (String (] string [] string [] string [] String [] {// Inicializar los datos de prueba NodirectionGraph Graph = new NodirectionGraph (7); Graph.addvertex (new Graphvertex ("A")); Graph.addvertex (new Graphvertex ("b")); gráfico.Addvertex (new Graphvertex ("c")); Graph.Addvertex (new Graxverx ("d")); Graph.Addvertex (new Graphverx ("C")); Graph.Addvertex (new GraphvertEx ("D")); Graph.Addvertex (new Graphverx ("C")); Graph.Addvertex (new GraphvertEx ("D")); Graph.Addvertex (new Graphverx ("C")); Grap. GraphvertEx ("E")); Graph.Addvertex (nuevo GraphvertEx ("F")); Graph.AdDvertex (new GraphvertEx ("G")); Graph.Addedge (0, 1); Graph.Addedge (0, 2); Graph.addedge (1, 3) ;addedge (1, 4); Graph.addedge (3, 6); Graph.addedge (2, 2, gráfico. 5); System.out.println ("-Matriz adyacente de gráfico-"); gráfico GraphvertEx ("B")); Graph.AdDvertex (nuevo GraphvertEx ("C")); Graph.AdDvertex (new GraphvertEx ("D")); Graph.AdDvertex (new GraphvertEx ("E")); Graph.AdDvertex (New GraphVerEx ("F")); Graph.AdDvertex (new GraphvertEx ("G")); Graph. 1); Graph.Addedge (0, 2); Graph.addedge (1, 3); Graph.Addedge (1, 4); Graph.Addedge (3, 6); Graph.addedge (2, 5); System.out.println ("-Búsqueda de prioridad de ancho-"); gráfico (0);}}La estructura gráfica probada aquí es la siguiente:
Los resultados de la operación son los siguientes:
--Adjacent matrix of graph-- 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Aquí necesitamos explicar los resultados de ejecución de la búsqueda profunda y la búsqueda amplia anterior, donde 0, 1, 2, 3 ... corresponde a A, B, C, D respectivamente ... es un poco confuso, por favor perdóname ~~
Oh ~~~
Resumir
Lo anterior es todo el contenido de este artículo sobre la implementación de la programación de Java de la búsqueda de profundidad gráfica primero y el código completo de búsqueda de amplitud. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!