Código fuente de navegación unidimensional
I.Problema de 8 dígitos
El problema de ocho dígitos también se llama problema de las nueve casas. Hay 8 piezas de ajedrez en un tablero de ajedrez de 3 × 3. Cada pieza de ajedrez está marcada con un número del 1 al 8. Los números marcados en diferentes piezas de ajedrez son diferentes. También hay un espacio en el tablero de ajedrez y las piezas adyacentes al espacio se pueden mover al espacio. El problema a resolver es: dado un estado inicial y un estado objetivo, encontrar un paso móvil con el menor número de movimientos desde el estado inicial al estado objetivo. El llamado estado de un problema es la disposición de las piezas de ajedrez en el tablero. Después de que la pieza de ajedrez se mueva, el estado cambiará. Resolver el problema de ocho dígitos es en realidad encontrar una serie de estados de transición intermedios desde el estado inicial al estado objetivo.
Los problemas de ocho números generalmente se resuelven utilizando el método de búsqueda. Los métodos de búsqueda incluyen el método de búsqueda primero en amplitud, el método de búsqueda primero en profundidad y el algoritmo A*. Aquí comparamos el rendimiento de diferentes métodos de búsqueda resolviendo el problema de ocho dígitos de diferentes maneras.
2. Clase base del algoritmo de búsqueda
1. Representación del estado del problema de ocho dígitos
Un estado del problema de ocho dígitos es colocar ocho en el tablero de ajedrez. Cada pieza de ajedrez está representada por el número marcado en ella y el espacio está representado por 0. De esta manera, el estado de una pieza de ajedrez en el tablero se puede almacenar en una matriz unidimensional p [9]. comienza desde la esquina superior izquierda, de izquierda a derecha, de arriba a abajo. También se puede almacenar en una matriz bidimensional.
2. Nodo
En el algoritmo de búsqueda, el estado del problema se describe por nodos. Además de la matriz p [9] que describe el estado, también hay un puntero principal al final, que registra el número de nodo principal del nodo actual. Si un nodo V es generado por el cambio de estado del nodo U, entonces el nodo U es el nodo padre del nodo V. El último del nodo V registra el número del nodo U. Después de llegar al nodo objetivo, la ruta de búsqueda se puede encontrar a través de último.
3. Estructura jerárquica
En C, los nodos están representados por clases, que encapsulan las operaciones de datos relacionadas con los nodos.
Los diferentes algoritmos de búsqueda tienen ciertas características y personalidades individuales, por lo que aquí, todos los datos y funciones de los diferentes algoritmos de búsqueda se encapsulan en una clase base, y luego los diferentes algoritmos de búsqueda se implementan mediante herencia.
4. Reglas de expansión de nodos
La búsqueda consiste en expandir los nodos conocidos de acuerdo con ciertas reglas hasta que se encuentra el nodo de destino o no se pueden expandir todos los nodos.
La expansión de nodos de problemas numéricos debe cumplir con las reglas de movimiento de las piezas de ajedrez. De acuerdo con las reglas del movimiento de piezas de ajedrez, una pieza de ajedrez adyacente a un espacio se puede mover a un espacio a la vez, lo que en realidad puede considerarse como un espacio que se mueve en la dirección opuesta. La dirección del movimiento espacial puede ser derecha, abajo, izquierda o arriba y, por supuesto, no puede moverse fuera del límite. La posición de la pieza de ajedrez, es decir, el subíndice del elemento de la matriz que guarda el estado. Cuando se mueve un espacio, su posición cambia. Cuando no está fuera de los límites, después de mover espacios hacia la derecha, abajo, izquierda y arriba, las nuevas posiciones son las posiciones originales de 1, 3, -1 y -3 respectivamente. Si el espacio se mueve hacia la derecha, abajo, izquierda y arriba usando 0, 1, 2 y 3 respectivamente, los cambios de estado causados por el movimiento del espacio se reflejan intercambiando el número en la nueva posición de 0 en la matriz p. [] con 0.
La clase base del problema de 5,8 dígitos
La clase base y sus funciones miembro del problema de ocho dígitos se implementan de la siguiente manera:
#Definición número 9
Lucha de clases
{
Público:
TEight(){}
TEight(char * fname); // Construye nodos con datos de archivo
Virtual void Search() = 0 //Buscar
Protegido:
int p[Num] ;
int last, spac
static int q[Num], d[], total
void Printf();
Operador booleano = = (const TEight amp; t);
bool Extend(int I
};
int TEight::q[Num] ; //Guardar nodo de destino
int TEight::d[]={1, 3,-1,-3} //Dirección
int TEight::total = 0 ; //Paso
TEight::TEight(char *fname)
{
ifstream fin
fin.open(fname, IOs::in );
if (! fin)
{
cout lt lt"¡No se puede abrir el archivo de datos!"
Return;
}
int I;
for(I = 0; iltNum)//Obtener el nodo fuente
fin gt gtp[ i ];
fin gt gtspac
for(I = 0; iltNum)//Obtener el nodo objetivo
fin gt gtq[ i];
p>fin . close();
último =-1; /p>
Void TEight::Printf()//Ruta del archivo de resultados de impresión.
{
ofstream fout
fout.open("eight_result.txt ", IOs::ate | IOs::app);
fout lt lttotal lt; lt"t";
for(int I = 0; i ltNum)
fout lt lt" " " lt ltp[i];
p>
fout lt ltendl
fout
}
bool TEight:: operador = = (const. TEight amp; T) // Determina si los dos estados son iguales
{
for(int I = 0; iltNum)
if(T.p. [i]!=p [i ])
Devuelve 0
Devuelve 1;
}
bool ocho：：extender (int I)// Extensión
{
if(I = = 0 amp; ampspac3==2 || i==1.
ampspac gt cinco
| i = = 2 amperios ampspac 3 = = 0 | i = = 3 amperios ampspac lt3)
Devuelve 0;
int temp = espac
spac = d[I];
p[temp]= p[spac];
p[spac]= 0;
p>
Retorno 1;
}
La estructura del archivo de datos:
A * * * tres líneas, la La primera línea está separada por espacios. Los 9 números del 0 al 8 son el estado inicial. La segunda línea es el número y la posición del espacio (número 0). La tercera línea también tiene 9 números del 0 al 8 separados por espacios.
Tres. Tabla lineal
Durante el proceso de búsqueda, el método de búsqueda necesita utilizar una cola para almacenar los nodos intermedios buscados. Para encontrar la ruta desde el nodo inicial al nodo de destino después de encontrar el nodo de destino, es necesario conservar todos los nodos buscados. Por otro lado, para diferentes problemas, o incluso el mismo problema, en diferentes métodos de búsqueda, la cantidad de nodos que deben almacenarse varía mucho, por lo que aquí se utiliza una lista lineal vinculada como estructura de almacenamiento. Para adaptarse a diferentes problemas, la lista lineal está diseñada como una plantilla.
Plantilla lt clase tipo gtclass TList//Definición de anticipación de tabla lineal
Plantilla lt clase tipo gt clase TNode //Plantilla de clase de nodo de tabla lineal
{
Lista de clases de amigos ltType gt;
Público:
TNode(){}
TNode(tipo constante ampdat);
Privado:
TNode ltType gt*next;
Tipo de datos;
};
Plantilla tipo de clase lt Lista de categorías gt
{
Pública:
TList(){ Último = Primero = 0; Longitud = 0 }//Constructor
int Getlen()const { return Longitud;}// Función miembro, devuelve la longitud de la tabla lineal.
int Append(const Type & t); //Función miembro, agrega nodos desde el pie de página.
int Insert(const Type amp; t, int k); //Función miembro, insertar nodo
Escriba get data(int I); //Función miembro, devolver datos del nodo miembro.
void SetData(tipo constante ampt, int k); //Función miembro, establece miembros de datos del nodo.
Privado:
TNode ltType gt*first, *last; //miembro de datos, encabezado de tabla lineal y puntero de cola
int length; , longitud de tabla lineal
};
Plantilla lt tipo de clase gtint TList ltType gt* Append (tipo constante ampt)
{
Insertar (T, longitud);
Retorno 1;
}
Plantilla lt tipo de clase gtint TList ltType gt* insert (tipo constante ampt, int k)
{
TNode ltType gt* p = nuevo TNodelt.
Escriba gt;
p->; datos = T
if(primero)
{
if(k lt; = 0)
{
p->;Siguiente = Primero
primero = p;
}
if(k gt; longitud-1)
{
Último- gt; siguiente = p
Último = Último- gt;
Finalmente - gt; next = 0
}
if(k gt; 0 amp ampk lt longitud)
{
k-;
TNode ltType gt* q = primero;
mientras(k->0)
q = q- gt;
p->; siguiente = q-gt;
q->; siguiente = p;
Otro
{
primero = Último = p;
Primero - gt; siguiente = último a - gt;
}
longitud
retorno 1;
}
Plantilla lt tipo de clase gt tipo TList ltType gt* obtener datos(int k)
{
TNode ltType gt* p = primero;
mientras(k ->;0)
p = p-gt;Siguiente;
Devolver p-gt;data;
}
Plantilla lt tipo de clase gtvoid TList ltType gt* SetData (tipo constante ampt, int k)
{
TNode ltType gt* p = primero;
mientras (k->0)
p = p-gt; next;
p->data = T;
}
Las tablas lineales se almacenan por separado como archivos de encabezado.
Cuatro. Método de búsqueda en amplitud
Entre los métodos de búsqueda, el método de búsqueda en amplitud es el método preferido para encontrar la ruta más corta.
1. Pasos básicos del algoritmo de búsqueda en amplitud
1) Cree una cola, agregue el nodo inicial a la cola y establezca los punteros de cabecera y cola de la cola.
2) Saque el nodo al principio de la cola (señalado por el puntero principal) y expándalo, expanda los nodos secundarios y agregue estos nodos a la cola en el orden de expansión. .
3) Si el nuevo nodo expandido duplica el nodo en la cola, descarte el nuevo nodo y salte al paso 6.
4) Si el nuevo nodo expandido no duplica el nodo en la cola, registre su nodo principal, agréguelo a la cola y actualice el puntero de cola de la cola.
5) Si el nodo de extensión es el nodo de destino, se genera la ruta y el programa finaliza. De lo contrario, continúe con el siguiente paso.
6) Si el nodo al principio de la cola se puede expandir, regrese directamente al segundo paso. De lo contrario, apunte el puntero del encabezado de la cola al siguiente nodo y regrese al paso 2.
2. Salida de la ruta de búsqueda
Después de buscar el nodo de destino, es necesario generar la ruta de búsqueda. Cada nodo tiene un último campo de datos, que registra el nodo principal del nodo. Por lo tanto, al generar la ruta de búsqueda, comienza desde el nodo objetivo Q, busca su nodo principal según el último y luego encuentra su nodo principal según el. último de este nodo..., y finalmente encuentre el nodo inicial. La ruta de búsqueda es la ruta inversa desde el nodo inicial hasta el nodo de destino.
3. Estructura de clases TBFS basada en el método de búsqueda en amplitud
La clase TBFS del método de búsqueda en amplitud es una subclase de la clase TEight. La estructura de su clase y la implementación de sus funciones miembro son las siguientes:
Clase TBFS: alumbrado público
{
Público:
TBFS( ){}
TBFS(char * fname): TEight(fname){ }
Búsqueda virtual vacía();
Privado:
void Printl(TList lt; TBFS gt ampl);
int Repetir(TList lt; TBFS gt ampl);
int Find(); >
};
void TBFS::Printl(TList lt; TBFS gt ampl)
{
TBFS T = * this
if (T.last==-1)
Regresar;
Otros
{
t = L . datos(t . último);
T.printl(L);
T.printf();
}
}
int TBFS::Repeat(TList lt; TBFS gt ampl)
{
int n = L
for(I = 0;iltn;i)
if(L.GetData(i)==*this)
romper;
Devolver I;
}
int TBFS::Find()
{
for(int I = 0 ;iltNum)
if (p[i]!=q[i])
Devuelve 0
Devuelve 1
}
void TBFS::Search()
{
TBFS T = * this
TList ltTBFS gtl;
Longitud append(T);
int cabeza=0, cola = 0;
mientras(cabeza lt; = cola)
{
for(int I = 0; i lt4; i)
{
t = L. obtener datos(head);
if(T . Extend(I ) amp; ampT.Repeat(L)>tail)
{
T.last = head
Longitud anexar (T );
cola
}
if(T.Find())
{
T .printl(L);
T.printf();
Retorno;
}
}
head;
}
}
4. Desventajas del método de búsqueda en amplitud
La búsqueda en amplitud El método tiene solución cuando , siempre se garantiza el camino más corto, es decir, el camino con el menor número de pasos. Pero el mayor problema con el método de búsqueda en amplitud es que hay demasiados nodos para buscar, porque en el método de búsqueda en amplitud, cada nodo posible es el objeto de búsqueda.
A medida que aumenta la profundidad de los nodos en el árbol de búsqueda, el número de nodos de búsqueda aumenta rápidamente y se expande exponencialmente y, por lo tanto, el espacio de almacenamiento requerido y el tiempo de búsqueda también aumentan exponencialmente.
Algoritmo del verbo (abreviatura de verbo) A*
1. Búsqueda heurística
La búsqueda en amplitud y la búsqueda bidireccional en amplitud son búsquedas ciegas. , en el estado Son algoritmos muy adecuados cuando el espacio es pequeño, pero cuando el espacio de estados es grande, su eficiencia es demasiado baja y la solución a menudo se encuentra después de buscar una gran cantidad de nodos de estado irrelevantes, o incluso la solución no puede estar.
La búsqueda es un proceso de búsqueda heurístico. Para reducir la ceguera de la búsqueda y mejorar la precisión de los experimentos, se debe utilizar la búsqueda heurística. La llamada búsqueda heurística consiste en evaluar la posición de cada búsqueda, seleccionar la posición donde es más fácil alcanzar el objetivo y luego buscar hacia adelante desde esta posición. Esto puede omitir una gran cantidad de nodos irrelevantes en la búsqueda y mejorar la eficiencia. .
Algoritmo 2.A*
El algoritmo A* es un algoritmo de búsqueda heurístico de uso común.
En el algoritmo A*, la posición del nodo se evalúa a través de la función de evaluación. La función de evaluación del algoritmo A* se puede expresar como:
f'(n) = g'(n) h'(n)
Aquí f'(n) es la función de evaluación, g'(n) es el valor de la ruta más corta desde el punto inicial hasta el punto final (también llamado costo mínimo o costo mínimo), y h'(n) es el valor heurístico de la ruta más corta de n a la meta. Dado que f′(n) no se puede conocer de antemano, en realidad se utiliza la siguiente función de evaluación:
f(n) = g(n) h(n)
donde g (n) es el costo real desde el nodo inicial al nodo N, y h(n) es el costo estimado de la mejor ruta desde el nodo N al nodo objetivo. Aquí h(n) representa principalmente la información heurística de búsqueda, porque se conoce g(n). Utilice f(n) como una aproximación de f′(n), es decir, utilice g(n) en lugar de g′(n) y h′(n) en lugar de h′. Esto debe cumplir dos condiciones: (1) g(n)>=g'(n) (cumplido en la mayoría de los casos, puede ignorarse), f debe aumentar monótonamente. (2)h debe ser menor o igual al costo mínimo real h (n)
3 Pasos del algoritmo A*
El algoritmo A* es básicamente el mismo que. búsqueda en amplitud, pero un nodo Después de la expansión, se debe calcular su función de evaluación y los nodos que se expandirán deben ordenarse de acuerdo con la función de evaluación para garantizar que cada nodo expandido sea el nodo con la función de evaluación más pequeña.
Los pasos del algoritmo A* son los siguientes:
1) Establecer una cola, calcular la función de evaluación f del nodo inicial, poner en cola el nodo inicial y configurar la cola punteros de cabeza y cola.
2) Saque el nodo al principio de la cola (señalado por el puntero del encabezado de la cola). Si el nodo es el nodo de destino, se genera la ruta y el programa finaliza. De lo contrario, expanda el nodo.
3) Compruebe si el nuevo nodo expandido está duplicado con el nodo en la cola. Si está duplicado con un nodo que no se puede expandir (antes del puntero del encabezado de la cola), deséchelo; se duplica con el nodo que se va a expandir (después del puntero del encabezado de la cola), compare los tamaños de G en las funciones de evaluación de los dos nodos y retenga el nodo con un valor G más pequeño. Vaya al paso cinco.
4) Si el nuevo nodo expandido no se superpone con el nodo en la cola, de acuerdo con el tamaño de su función de evaluación f, insértelo en la posición apropiada del nodo que se expandirá después del nodo principal. en la cola, para que sigan Ordénelos en orden de pequeño a grande y, finalmente, actualice el puntero del final de la cola.
5) Si el nodo al principio de la cola se puede expandir, regrese directamente al segundo paso. De lo contrario, apunte el puntero del encabezado de la cola al siguiente nodo y regrese al paso 2.
4. Función de evaluación del algoritmo A* para problemas de ocho dígitos
En la función de evaluación, H se calcula principalmente. Para diferentes problemas, H tiene diferentes significados. Entonces, ¿qué significa la H en la pregunta de ocho dígitos? Un estado del problema de ocho dígitos es en realidad la disposición de los números del 0 al 8. Se almacena en una matriz p [9] y el subíndice de cada elemento de la matriz es la posición del número en la disposición. Por ejemplo, en un estado p[3]=7, entonces la posición del número 7 es 3.
Si la posición del número 3 en el estado objetivo es 8, entonces la distancia de desplazamiento del número 7 desde el estado objetivo es 3, porque debe moverse tres pasos para regresar a la posición del estado objetivo.
En problemas de ocho cifras, cada número puede tener nueve posiciones diferentes. Por lo tanto, existen distancias relativas de 9*9 entre cada número en cualquier estado y el mismo número en el estado objetivo. Estas distancias relativas se pueden calcular primero y almacenar en una matriz. De esta manera, siempre que conozca la posición del mismo dígito en los dos estados, puede encontrar su distancia relativa, que es la distancia de desplazamiento del dígito:
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
p>8 4 3 2 3 2 1 2 1 0
Por ejemplo, en un estado, la posición del número 8 es 3, y en otro estado, la posición es 7, entonces de la matriz 2 se puede encontrar en 3 filas y 7 columnas. Esta es la distancia de desplazamiento de 8 en los dos estados.
h en la función de evaluación es la suma de las distancias de desplazamiento de todos los números. Obviamente, para calcular la distancia de desplazamiento del mismo número en dos estados diferentes, es necesario conocer la posición del número en cada estado, lo que requiere escanear la matriz p [9]. Debido a que el estado cambia, la posición de cada número también cambia, por lo que cada vez que se calcula H, la matriz debe escanearse a lo largo de la línea para determinar la posición de cada número en la matriz. Para simplificar el cálculo, se utiliza una matriz para almacenar la posición de cada número en el estado, que cambia a medida que cambia el estado, de modo que no es necesario escanear la matriz de estado cada vez que se calcula H.
Por ejemplo, en un estado determinado, la posición del número 5 es 8. Si la posición se almacena en la matriz r[9], entonces r[5]=8.
Ahora use la matriz r[9] para almacenar la posición digital del estado actual y use la matriz s[9] para almacenar la posición digital del estado objetivo y luego la distancia de desplazamiento del estado actual. El número de estado I del estado objetivo es la fila central de la matriz. Los valores correspondientes de r [i] y la columna s [i].
5. Estructura de clases del algoritmo A*
La declaración de clases del algoritmo A* es la siguiente:
Clase TAstar: alumbrado público
{
Público:
TAstar(){} //Constructor
TAstar(char * fname); //Constructor con parámetros
Búsqueda virtual void(); //Un* método de búsqueda
Privado:
int f, g, h //Función de evaluación
int; r[Num]; //Matriz auxiliar que almacena la posición de cada dígito en el estado.
static int s[Num]; // Matriz auxiliar de almacenamiento para cada posición numérica en el estado objetivo.
Static int e[]; //Una matriz auxiliar utilizada para almacenar la distancia relativa de cada número.
void Printl(TList lt; TAstar gtl); //Función miembro, ruta de búsqueda de salida.
int Expend(int I); //Función miembro, función de expansión de estado del algoritmo A*
int Calcuf(); //Función miembro, función de evaluación de cálculo.
void sort(TList ltTAstar gt ampl, int k); // Función miembro, inserta los nodos recién expandidos en la cola de nodos que se expandirán en orden descendente de f.
int Repite(TList lt; TAstar gt ampl); //Función miembro, verifica si el nodo está repetido.
};
int TAstar::s[número], TAstar::e[número*número];
TAstar::TAstar(char *fnombre ): TEight(fname)
{
for(int I = 0; iltNum)
{
r[p[ I ]]= I; //Almacena la posición de cada número en el estado inicial.
s[q[I]]= i; //Almacena la posición de cada bit del estado objetivo.
}
ifstream fin
fin.open("eight_dis.txt", IOs::in //Abrir archivo de datos
<); p>if(!fin){
cout lt lt"¡No se puede abrir el archivo de datos!" > }
for(int I = 0; IltNum * NumI) //Lee el valor de distancia relativa de cada número.
fin gt gte[I];
fin .
f = g = h = 0; /p>
}
void TAstar::Printl(TList lt; TAstar gtl)
{
TAstar T = * this
if(T.last==-1) devuelve;
Otros
{
t = L . obtener datos(t . last);
T.printl(L);
T.printf()
}
}
int TAstar::Expend(int i)
{
If(Extend(i)) //El nodo es extensible.
{
int temp = r[p[r[0]]; // La posición digital cambia después de que cambia el estado y la posición cambiada se almacena.
r[p[r[0]]= r[0];
r[0]= temp;
}
Devuelve 0;
}
int TAstar::Calcuf()
{
h = 0;
for(int I = 0; IltNumI) //Calcular h de la función de evaluación.
h = e[Num * r[I] s[I]];
return g h
}
void TAstar; ::Ordenar(TList lt; TAstar gt ampl, int k)
{
int n = L
int
p>
for(I = k 1; i ltn; i)
{
TAstar T = L . obtener datos(I);
if(this-gt;f lt=T.f)
romper;
}
longitud insertar(*this,i);
}
int TAstar::Repeat(TList lt; TAstar gt ampl)
{
int n = L. Getlen() ;
int I;
for(I = 0;iltn;i)
if(L.GetData(i)==*esto)
Romper;
Regresar I;
}
void TAstar::Search()
{
TAstar T = * this//Nodo inicial
T . f = T . //Función de evaluación del nodo inicial
TList ltTAstar gtl; Crear cola
Longitud append (T); //El nodo inicial se agrega a la cola
int head=0, tail = 0 //Puntero de cabecera y cola de cola
while(head lt;=tail) // Bucle si la cola no está vacía.
{
for(int I = 0;i lt4;I) //Los espacios pueden moverse en dirección.
{
t = L . get data(head); //Ir al nodo principal de la cola
If(T.h==0) //Es el nodo objetivo.
{
T.printl(L); //Ruta de búsqueda de salida
T.printf() //Estado de destino de salida
Return; //Fin
}
If(t . expect(I))//Si el nodo es expandible,
{
int k = T . Repetir(L); //Devuelve el número de secuencia que se repite con el nodo extendido.
if(k lt; Head) //Si es un nodo que no se puede expandir,
Continuar //Descartar
T.last = head; //No Para los nodos que no se pueden expandir, registre el nodo principal.
T . f = T . Calcuf(); //Calcular f
if(k lt;=tail) //El nuevo nodo se duplica con el nodo expandible.
{
TAstar Temp = L . get data(k);
if(temp . g gt; T.g) //Compara la G de dos nodos valor.
Longitud SetData(T, k); //Mantener el valor G pequeño.
Continuar;
}
T.Sort(L, head); //Inserta el nuevo nodo en la cola de nodos expandible.
tail; //Mover el puntero de cola de cola hacia atrás.
}
}
head; // Un nodo no se puede expandir y el puntero del encabezado de la cola apunta al siguiente nodo.
}
}
Programa de prueba de verbos intransitivos
Prueba del algoritmo A*:
int main( )
{
TAstar aStar(" ocho . txt ");
Astar. search();
System("pauze");
Devuelve 0;
}
Datos en el archivo ocho.txt ( Estado inicial y estado objetivo):
A * * *Tres líneas, la primera línea tiene 9 números del 0 al 8 separados por espacios, este es el estado inicial. La segunda línea es el número y la posición del espacio (número 0). La tercera línea también tiene 9 números del 0 al 8 separados por espacios.
8 3 5 1 2 7 4 6 0
ocho
1 2 3 4 5 6 7 8 0
ocho_dis.txt Datos en (utilizados por la función de estimación)
0 1 2 1 2 3 2 3 4
1 0 1 2 1 2 3 2 3
2 1 0 3 2 1 4 3 2
1 2 3 0 1 2 1 2 3
2 1 2 1 0 1 2 1 2
3 2 1 2 1 0 3 2 1
2 3 4 1 2 3 0 1 2
3 2 3 2 1 2 1 0 1
4 3 2 3 2 1 2 1 0
El resultado en Eight_Result.txt (el resultado después de ejecutar).
7. Resultados de la operación del algoritmo
654380. El algoritmo BFS solo se puede aplicar cuando el número de pasos para llegar al nodo objetivo es pequeño. Si el número de pasos excede los 15, significa que el tiempo de ejecución es demasiado largo y en realidad no tiene ningún efecto.
2. Para el mismo estado solucionable generado aleatoriamente, el algoritmo BFS es el más lento, el algoritmo DBFS es más lento y el algoritmo A* es más rápido. Sin embargo, en 15 pasos, no hay mucha diferencia entre el algoritmo DBFS y el algoritmo A*. Después de 15 pasos, a medida que aumenta el número de pasos, las ventajas del algoritmo A* se hacen evidentes gradualmente. El algoritmo A* es más de 5 veces más rápido que el algoritmo DBFS y aumenta a medida que aumenta el número de pasos. Después de más de 25 pasos, DBFS también pierde valor debido a un tiempo de ejecución demasiado prolongado.
3. En términos generales, cada vez que el número de pasos en movimiento aumenta en 1, el tiempo de ejecución del programa aumentará más de 5 veces. Debido a las características del problema de ocho dígitos en sí, la cantidad de nodos que deben verificarse crece exponencialmente a medida que aumenta la cantidad de pasos. Incluso utilizando el algoritmo A*, es difícil resolver el problema de una gran cantidad de pasos en movimiento.
8. Solubilidad del problema
Un estado del problema de ocho dígitos es en realidad la disposición de 0~9. Para cualquier estado inicial y objetivo dados, no existe necesariamente una solución, es decir, es posible que no se alcance el estado objetivo desde el estado inicial. Debido a que hay dos permutaciones: permutaciones impares y permutaciones pares, las permutaciones impares no se pueden convertir en permutaciones pares y viceversa.
Si la disposición aleatoria de un número del 0 al 8 es 871526340, entonces F(X) se utiliza para representar el número de números menores que él. La suma de F(X) de todos los números es Y=. ∑(F(X)). Si Y es un número impar, la disposición de los números originales se llama número impar; si Y es un número par, se llama número par.
Por ejemplo, 871526340.
y = 0 0 0 1 1 3 2 3 0 = 10
10 es un número par, por lo que es un número par. 871625340
y = 0 0 0 1 1 2 2 3 0 = 9
9 es un número impar, por lo que es un número impar.
Así puedes comprobar si el estado inicial y el estado objetivo son los mismos antes de ejecutar el programa.
Si son iguales el problema está solucionado y se debe buscar el camino. De lo contrario no hay solución.
PD: Organizado desde Internet