Respuestas a las preguntas del examen de ingreso al doctorado de la Universidad de Jilin Inteligencia computacional 2001
Responda las siguientes preguntas (30 puntos)
1. ¿Qué es la búsqueda en amplitud? ¿Cuáles son las ventajas de la búsqueda en amplitud? ¿Cuáles son las desventajas?
2. Explique el significado y la diferencia de los símbolos lógicos "" y "→".
3. Proporcione un ejemplo de derivación incompleta de la resolución de entrada.
4. Sean S = {p (x) y Q (f (a)} un conjunto de cláusulas. Por favor dé un ejemplo en el que I sea una interpretación común de S, en lugar de su interpretación de Herbrand.
4. p>
5. Dé un ejemplo de que la fórmula no es equivalente a su paradigma Skolem.
6 ¿Qué es el algoritmo A*? ¿Los dos algoritmos? ¿Algoritmo A*?
2. Resuelve los siguientes problemas (30 puntos)
1. Supongamos que el problema de ocho caracteres tiene una función de evaluación: f(n)= d(n)+w(n); donde d(n) es la profundidad del nodo N en el árbol de búsqueda, W(n) es el número de bits "no en su lugar" en el nodo N. Intente obtener el siguiente gráfico; proceso de búsqueda para el nodo inicial y el nodo de destino, etiquete cada nodo. El valor de la función de evaluación y la ruta general de la solución se utilizan para calcular la penetración del proceso de búsqueda. 2 6
1 8 7
3 4 5
8 6
2 1 7
2. Convierta la fórmula G a la forma normal de Skolem y proporcione El conjunto de cláusulas de G..
3. Utilice el sistema de deducción directa basado en reglas para demostrar los siguientes problemas:
Hechos conocidos. ; dos reglas,; Objetivo. Proceso y/o diagrama.
3. Demuestre la primera forma del teorema de Herbrand: Supongamos que S es un conjunto de cláusulas, entonces S es insatisfactorio si y sólo si todo árbol semántico completo. correspondiente a S tiene un árbol semántico cerrado finito (15 puntos)
4 Resuma el proceso α-β, tome el siguiente árbol de juego como ejemplo y realice la poda α-β en orden de prioridad. el nodo secundario izquierdo y señale que la poda ¿Dónde ocurre la rama, dónde está la poda α y dónde está la poda β? En la figura, □ representa el punto máximo y ○ representa el punto mínimo
<. p>5. ¿Cuál es la deducción por resolución del conjunto andamiado? Intente demostrar la integridad de la deducción por reducción del conjunto andamiado del conjunto de cláusulas básicas (10 puntos)Principios de inteligencia artificial de 2003
1. Describa el proceso del algoritmo de búsqueda de gráficos; el problema de ocho caracteres tiene dos funciones de evaluación: f 1(n)= d(n)+w(n); )+3S( n). Donde d(n) es la profundidad del nodo n en el árbol de búsqueda, W(n) es el número de dígitos "mal colocados" en el nodo n y P(n) es la suma de las distancias. de cada dígito de la posición objetivo S(. n) es la puntuación de secuencia obtenida de la siguiente manera: para los números en el círculo exterior no central, caminando en el sentido de las agujas del reloj, si el número que sigue a un número no es su número sucesor en el objetivo estado, este número obtiene 2 puntos; de lo contrario, obtiene 0 puntos. Para la posición central, si hay un número, obtiene 1; si no hay ningún número, obtiene 0. Luego agregue todos los puntajes anteriores para obtener el puntaje de secuencia; S (n). El estado inicial y el estado objetivo existentes se describen a continuación: Dibújelos. Los respectivos diagramas de proceso de búsqueda heurística indican el valor de la función de evaluación de cada nodo en el diagrama e indican el orden de expansión del nodo. Calcule sus respectivas permeabilidades y coeficientes de ramificación efectivos. (40 puntos)
3 4 5
2 6
1 8 7
3 4 5
8 6
2 1 7
2. Resuma el proceso minimax y el proceso α-β de búsqueda de juegos. Tome el siguiente árbol de juegos como ejemplo para dar los valores de cada uno. nodo de los dos procesos Valor de retorno y ruta buscada (dibuje dos diagramas de proceso). Para el proceso α-β, la poda α-β se realiza en orden de prioridad al nodo secundario izquierdo. ¿Dónde podar, dónde podar α y dónde podar β? Cambios en el valor de retorno que indica el nodo donde ocurrió la poda y el nodo original. En la figura, □ representa el punto máximo y ○ representa el punto mínimo. (20 puntos)
Tres. (27 puntos)
1. Suponga un conjunto de cláusulas, encuentre el dominio H de S, el conjunto atómico de S y el conjunto de cláusulas de ejemplo básico.
2. Utilice el algoritmo de la unidad para determinar si el conjunto de expresiones w = {q (f (a), g (x)) y q (y, y)} se puede unificar. la unidad más general.
3. Utiliza la deducción tabular para demostrar que * * * tiene la misma implicación.
4. Supongamos que S es un conjunto de cláusulas de lógica proposicional y P es el símbolo atómico que aparece en S. Por lo tanto, las cláusulas de S se pueden dividir en tres partes: la parte que contiene la palabra P y la parte que contiene ~P Parte de esta palabra, no hay parte P o ~ S3 de la palabra P. Demuestre que S es insatisfactorio si y solo si S1' y S2' son insatisfactorios. (8 puntos)
5. Dé un ejemplo de un sistema de deducción anticipada basado en reglas incompleto. (5 puntos)
Principios de Inteligencia Artificial 2002
1. Responda brevemente las siguientes preguntas (24 puntos)
1. un ejemplo para explicar Los componentes básicos de los sistemas de producción.
2. ¿Qué es el algoritmo A*? ¿Cuáles son las principales propiedades del algoritmo A*?
3. En el sistema de deducción basado en reglas, ¿qué es una sustitución compuesta? ¿Por qué debería considerar la compatibilidad de reemplazo?
4. En un sistema de deducción anticipada basado en reglas, ¿qué forma necesitan las reglas y los objetivos?
5. ¿Está completo el sistema de deducciones anticipadas basado en reglas? ¿Se completó la derivación inversa? ¿Se ha completado la deducción bidireccional?
6. En la búsqueda heurística, la función de evaluación generalmente se define como f (n) = g (n) + h (n), indicando el significado de cada parte de la definición y explicando por qué esta definición es usado.
7. En el algoritmo de unidad, si W es un conjunto de expresiones no vacías y D es un conjunto de diferencias de W, entonces, cuando D tiene qué forma, W no se puede unificar.
8. ¿Cuáles son los métodos de representación del conocimiento más utilizados? Responde brevemente las características de cada uno.
2. Juzgue si está bien o mal (14 puntos)
1. Cualquier punto f(n)≤f*(s) en la tabla abierta eventualmente será seleccionado como. una extensión por el nodo del algoritmo A*.
2. Si se satisface la restricción monótona, el valor F de la secuencia de nodos expandida por el algoritmo A* aumenta monótonamente.
3. Supongamos que θ y λ son dos sustituciones, entonces θ? λ=λ?θ.
4. El conjunto de expresiones w = {p (f (x), g (y, z), z), p (y, h (k (x)), f (z)} es Uniforme.
5. La permeabilidad y el coeficiente de ramificación efectiva son medidas de complejidad espacial de la capacidad heurística del método de búsqueda de gráficos.
6. Si y solo si I se interpreta como cada cláusula, entonces el caso base C 'de cada cláusula C en S es falsificado por I.
7 ¿Es siempre falsa cualquier fórmula en lógica de primer orden? se puede determinar mediante el método de reducción
3 (12 puntos)
1, si e = q (y, f (y, g (x)), θ = {a. /x, b/y, y/z}, λ = {a/x, z/y, f (x)/z}, encuentre eθ, eλ λ
2. Resuelve el problema de las cuatro reinas. Entre ellos, la función diagonal diag (i, j) se usa para clasificar reglas. Si Diag (i, j) < Diag (m, n), entonces la regla Rij se coloca antes de la regla Rmn. en la clasificación. Diag (i, j) se define como la longitud de la diagonal más larga de la unidad utilizada (I, j). Si los valores de la función de diagnóstico son iguales, las reglas se ordenan aleatoriamente. >
Cuarto, utilice el método de reducción para demostrar que el siguiente conjunto de cláusulas no es satisfactorio (anote todo el proceso de reducción y los reemplazos utilizados en cada paso de la reducción).
(10 puntos)
5. Supongamos que el sistema de producción PS tiene un conjunto con estado DB = {a, b, c, d, e, f, g, h, I, m }, las reglas de producción son:
a→b, c→m, g→h, a→c, d→e, h→i, a→d, e→f, m→i , b→g, f→m
Supongamos que A es el estado inicial, el costo de aplicación de la regla es 1 y el valor de la función heurística de cada estado es:
País a b c d e f g h m
valor h 1 1 8 2 2 2 4 4 10 4
Utilice el algoritmo a para dibujar el gráfico de búsqueda y el árbol de búsqueda antes y después de la expansión del nodo C. Es necesario marcar el Orden de expansión y valor de la función de evaluación del nodo en el gráfico. Y escriba los elementos en la lista cerrada y en la lista abierta antes de que se expanda el nodo C. (15 puntos)
6. = {p (g (x), z), ~ p ( f (y), h (a)}, encuentre el conjunto atómico de S y el árbol semántico de S. Si le da a S una explicación I de la siguiente manera:
D={1, 2} a g(1)g( 2)f(1)f(2)h(1)h(2)P(1,1) P(2,2) P (2,1) P(1,2)
2 2 1 1 2 2 1
Por favor construye S correspondiente a H de I para explicar I*..(15 puntos)
Principios de Inteligencia Artificial 2002
7. Realice la poda alfa-beta en el siguiente árbol de juego en el orden en que se generan los nodos secundarios izquierdos primero. Indique dónde se produce la poda, dónde está el. poda alfa y dónde está la poda beta? Indique el valor de retorno del nodo donde se produjo la poda y el nodo inicial cambia, y la ruta buscada en la figura, □ representa el punto máximo y ○ representa el punto mínimo. ¿Cuál es el más eficiente en el proceso general de poda α-β?
Principios de Inteligencia de Inteligencia Artificial 2000
1 Responda brevemente las siguientes preguntas (24 puntos)
1. Describa el proceso del sistema de producción.
2. Responda la clasificación del sistema de producción y explique sus ventajas y desventajas. Los sistemas son intercambiables.
4. Explique las diferencias entre el proceso de búsqueda de gráficos no informativos y el proceso de búsqueda de gráficos heurísticos, y proporcione dos métodos típicos de búsqueda de gráficos no informativos.
5. -Explicación lógica de orden
6. Demostrar semánticamente que el conjunto de cláusulas es siempre falso. ¿Es suficiente considerar únicamente la interpretación de Herbrand del conjunto de cláusulas
7? Sistema de deducción basado en, ¿por qué deberíamos considerar la compatibilidad de las sustituciones? >
8. ¿Cuáles son los tipos generales de aprendizaje automático?
En segundo lugar, supongamos que el problema de ocho dígitos tiene una función de evaluación: f(n)= d(n)+w(n); donde d(n) es la profundidad del nodo N en el árbol de búsqueda, W(n) es el número de bits "no en su lugar" en el nodo N. La descripción del estado inicial existente y la descripción del estado objetivo son las siguientes:
3 4 5
2 6
1 8 7
3 4 5
8 6 7
2 1
Dibuje un diagrama de proceso de búsqueda heurístico, indique el valor de la función de evaluación de cada nodo en el diagrama e indique el orden de expansión de los nodos. (20 puntos)
En tercer lugar, utilice la deducción expresiva para demostrar que * * * tiene la misma implicación. (16 puntos)
4. Describe el algoritmo unitario y úsalo para encontrar w = {p (a, x, f (g (y)), p (z, f (z), La unidad más general de f (u ))} (Escribe los pasos de ejecución del algoritmo, 20 puntos)
5. Prueba el algoritmo A* para un problema de búsqueda de gráficos con una solución. para demostrar que antes de que termine el algoritmo A* En cualquier momento, siempre hay un nodo n' en la lista abierta, donde n' está en la ruta de solución óptima y satisface f(n')≤f *(s), donde s es el nodo inicial.
6. En el método de razonamiento de reducción, es incompleto utilizar solo la reducción binaria sin considerar factores.
(5 puntos)
Principio de Inteligencia Artificial xxxx año
1. Responde las siguientes preguntas (20 puntos)
1.
2. ¿Cuáles son los factores que afectan la capacidad heurística de un algoritmo?
3. Describir las reglas de poda del proceso α-β.
4. ¿Cuáles son las mejoras importantes al principio de discriminación?
5. Describir la forma general del estado inicial, las reglas y los objetivos del sistema de deducción anticipada basado en reglas.
2. Utilice la función de evaluación: f(n)=d(n)+W(n) para resolver el problema de ocho dígitos, donde d(n) es la profundidad del nodo n en el árbol de búsqueda, W(n) es el número de bits "no en su lugar" en el nodo n.
3 2 1
4 8
5 6 7
3 8 2
4 6 1
5 7
Dibuje un diagrama de proceso de búsqueda heurística, indique el valor de la función de evaluación de cada nodo en el diagrama e indique el orden de expansión de los nodos. (20 puntos)
En tercer lugar, describa el algoritmo de la unidad. Utilice este algoritmo para encontrar el conjunto de expresiones más general w = {r (x, x), r (f (a), g (y)}. Unidad. (20 puntos)
4. ¿Qué condiciones debe cumplir la función heurística cuando se utiliza el algoritmo AO*? La siguiente figura es un gráfico AND o, donde n0 es el nodo inicial, { n7, n8} es el conjunto de nodos objetivo, h es la función heurística, suponiendo que el costo del conector k es k. Utilice el algoritmo AO* para resolver el gráfico de solución óptima (20 puntos)
n n0 n1 n2 n3. : Si el conjunto de cláusulas base S no puede satisfacerse, entonces hay una deducción reductiva para derivar la cláusula vacía de S. (20 puntos)
Principios de Inteligencia Artificial xxxx año a
Primero, responde brevemente las siguientes preguntas
1. ¿Cuáles son las principales áreas de investigación de la inteligencia artificial?
2. ¿De qué partes se compone el sistema de producción? >3. ¿Cuáles son las estrategias de control del sistema de producción?
4. ¿Qué es la búsqueda en amplitud?
5. >6. ¿Cuáles son los factores que afectan la capacidad heurística de un algoritmo?
7. ¿Cuáles son los métodos básicos para medir la capacidad heurística de un método de búsqueda? conclusión de la cláusula C en el conjunto de cláusulas S? ¿Qué es la derivación?
9. ¿Qué es un sistema de producción intercambiable?
10 ¿Cuál es la sustitución unificada más general? p>
En segundo lugar, intente describir el proceso básico del sistema de producción descomponible
3. El estado inicial y el estado objetivo del rompecabezas de ocho dígitos conocido son:
1. 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
Supongamos que la función de evaluación es f(n)=d(n)+W(n), donde d(n) es la profundidad del nodo n en el árbol de búsqueda y W(n) es la número de bits "no en su lugar" en el nodo n Utilice esto La función dibuja un árbol de búsqueda, un algoritmo para resolver el problema, e indica el valor de la función de evaluación de cada nodo y el orden en que se seleccionan los nodos de expansión en el árbol.
4. Se conoce el AND o gráfico, donde n0 es Los nodos iniciales, {n7, n8} son el conjunto de nodos objetivo, h es la función heurística, suponiendo que el costo del conector k. es k.. Utilice el algoritmo AO* para resolver el gráfico de solución óptima
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1. 1 2 0 0
En quinto lugar, intenta demostrar que la fórmula es una fórmula establecida por deducción.
El resultado lógico.
Principios de Inteligencia Artificial xxxx año b
Primero, responde brevemente las siguientes preguntas
1. ¿Cuáles son los dos métodos principales de búsqueda sin gráficos de información?
2. Describe brevemente las ventajas y desventajas de diversas estrategias de búsqueda.
3. ¿Cuáles son los factores que afectan la capacidad heurística de un algoritmo?
4. ¿Cómo se definen las fórmulas en lógica de primer orden?
5. En lógica de primer orden, ¿cómo se define la interpretación de una fórmula?
6. ¿Qué dos paradigmas de fórmulas se utilizan comúnmente en lógica proposicional?
7. ¿Qué dos paradigmas de fórmulas se utilizan comúnmente en la lógica de primer orden?
8. ¿Cuál es el dominio de Herbrand del conjunto de cláusulas?
En segundo lugar, intente describir el algoritmo GRAPHSEARCH.
3. Se sabe que los estados inicial y objetivo del rompecabezas de ocho dígitos son:
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
Supongamos que la función de evaluación es f(n)= d(n)+W(n), donde d(n) es la profundidad del nodo n en el árbol de búsqueda, W(n) es el número de dígitos "no en su lugar" en el nodo n, use esta función para dibujar un árbol de búsqueda, una solución al algoritmo del problema e indica el valor de la función de evaluación de cada nodo y el orden en el que se seleccionan los nodos de expansión en el árbol.
Cuarto, escriba la forma normal Scholem de la siguiente fórmula:
5. Utilice el método de reducción para demostrar que el conjunto de cláusulas es insatisfactorio.
6. Utilice la estrategia de retroceso para resolver el problema de las cuatro reinas. Entre ellos, la función diagonal diag (i, j) se utiliza para la clasificación de reglas. Si Diag (i, j) < Diag (m, n), entonces la regla Rij se coloca antes de la regla Rmn en la clasificación. Diag (i, j) se define como la longitud de la diagonal más larga de la unidad utilizada (I, j).