diff options
| author | Juan Marín Noguera <juan.marinn@um.es> | 2021-07-12 19:41:43 +0200 |
|---|---|---|
| committer | Juan Marín Noguera <juan.marinn@um.es> | 2021-07-12 19:41:53 +0200 |
| commit | 7f6946f98125b1b427135dfdf87576be654ab4db (patch) | |
| tree | d77f06f667722e16486e7e2da769f22bf9418ab8 | |
| parent | 6ec63727b831a49824c0d1705af9db68ac3fb596 (diff) | |
Errata en SSII
| -rw-r--r-- | si/n1.lyx | 10 | ||||
| -rw-r--r-- | si/n2.lyx | 54 | ||||
| -rw-r--r-- | si/n3.lyx | 430 | ||||
| -rw-r--r-- | si/n4.lyx | 22 | ||||
| -rw-r--r-- | si/n5.lyx | 91 | ||||
| -rw-r--r-- | si/n6.lyx | 234 | ||||
| -rw-r--r-- | si/n7.lyx | 84 |
7 files changed, 647 insertions, 278 deletions
@@ -280,7 +280,7 @@ WATSON de IBM entiende preguntas en cualquier idioma, busca respuestas en su base de datos y elige la más plausible en menos de 3 segundos con un enfoque multialgorítmico, capaz de aprendizaje por observación de respuestas. - Gano contra campeones humanos en el concurso televisivo + Ganó contra campeones humanos en el concurso televisivo \begin_inset Quotes cld \end_inset @@ -305,10 +305,10 @@ spam \lang spanish ; ayudar a detectar fraude; buscar rutas en GPS; reconocer el habla, la escritura, dibujos, imágenes; así como en domótica, conducción, navegación, - sillas de ruedas, asistentes personales, aspiradoras, exploración del espacio, - guías de museos, deportes, diagnósticos médicos, diseño de fármacos, cirugía, - inversiones financieras, películas, literatura, pintura, y como traductores - y asistentes personales. + sillas de ruedas, asistentes personales, traductores, aspiradoras, exploración + del espacio, guías de museos, deportes, diagnósticos médicos, diseño de + fármacos, cirugía, inversiones financieras, películas, literatura, pintura, + etc. \end_layout \end_body @@ -251,7 +251,8 @@ antecesor \series bold resoluble \series default - si es antecesor de un hiperarco cuyos sucesores son todos resolubles. + si es antecesor de un hiperarco cuyos sucesores son todos resolubles, siendo + el caso base el antecesor de un hiperarco sin sucesores. \end_layout \begin_layout Standard @@ -267,20 +268,36 @@ Y-O \begin_inset Formula $u\in V$ \end_inset +, sea +\begin_inset Formula $N:=\{S\subseteq V:(u,S)\in A\}$ +\end_inset + , -\begin_inset Formula $\{S\subseteq V:(u,S)\in A\}$ +\begin_inset Formula $\bigcup N$ +\end_inset + + es finito y, bien +\begin_inset Formula $N$ \end_inset - es unipuntual o todos sus hiperarcos tienen un único sucesor. - Si es unipuntual con al menos dos sucesores, es un nodo + es unipuntual, bien todos sus elementos son unipuntuales. + Si es unipuntual con al menos dos sucesores, +\begin_inset Formula $u$ +\end_inset + + es un nodo \series bold Y \series default -; si tiene algún hiperarco con un único sucesor, es un nodo +; si tiene al menos dos hiperarcos es un nodo \series bold O \series default -, y de lo contrario es un +, y si +\begin_inset Formula $\bigcup N=\emptyset$ +\end_inset + +, es un \series bold terminal \series default @@ -288,9 +305,11 @@ terminal \series bold primitiva \series default - si es antecesor de un hiperarco sin sucesores. + si es resoluble, si y sólo si es antecesor de un hiperarco sin sucesores. + No se consideran nodos con un único sucesor. Así, un nodo es resoluble si es una primitiva, es de tipo Y con todos sus - sucesores resolubles o es de tipo O con algún sucesor resoluble. + sucesores resolubles, es de tipo O con algún sucesor resoluble o tiene + un único sucesor y este es resoluble. Un \series bold árbol Y/O @@ -304,7 +323,7 @@ primitiva \end_deeper \begin_layout Standard -El método a elegir depende de características como: +El método a elegir depende de características del problema como: \end_layout \begin_layout Itemize @@ -320,7 +339,7 @@ Si es \series bold recuperable \series default -, esto es, se pueden deshacer las operaciones una vez ejecutadas, o es + (se pueden deshacer las operaciones una vez ejecutadas) o es \series bold irrecuperable \series default @@ -333,8 +352,8 @@ Si es obvio si una cierta solución es suficientemente buena para ser aceptada \end_layout \begin_layout Itemize -Si el conocimiento base es consistente; si es necesario tener mucho o solo - ayuda a restringir la búsqueda. +Si el conocimiento base es consistente, y si es necesario tener mucho o + este solo ayuda a restringir la búsqueda. \end_layout \begin_layout Standard @@ -381,7 +400,7 @@ top-down \lang spanish si parte de la situación final y aplica operadores al revés hasta llegar a la situación inicial. - También existen estrategias de búsqueda bidireccionales. + También hay estrategias de búsqueda bidireccionales. \end_layout \begin_layout Standard @@ -391,8 +410,7 @@ emparejamiento \series default consiste en determinar los operadores aplicables a una cierta situación, comprobando sus precondiciones. - A veces esto puede acarrear otra búsqueda si las precondiciones contienen - variables. + Esto puede acarrear otra búsqueda si las precondiciones contienen variables. \end_layout \begin_layout Standard @@ -417,7 +435,7 @@ técnica heurística función heurística \series default , que estima lo próximo que se encuentra un estado o subproblema a un estado - final o problema primitivo y se usa para decidir el operador a tomar. + final o problema primitivo, y que se usa para decidir el operador a tomar. \end_layout \begin_layout Standard @@ -433,8 +451,8 @@ backtracking \emph default \lang spanish sobre el grafo o el árbol de representación. - En general esto es lento, pero es un método universal y se puede combinar - con técnicas heurísticas. + Esto suele ser lento, pero es un método universal y se puede combinar con + técnicas heurísticas. \end_layout \end_body @@ -82,8 +82,8 @@ algorithm2e \begin_layout Standard Los algoritmos de búsqueda que veremos operan sobre un grafo o árbol de - búsqueda, esto es, un grafo dirigido o árbol que representa un espacio - de estados o una reducción (en cuyo caso sería un árbol o grafo Y-O). + búsqueda, un grafo dirigido o árbol que representa un espacio de estados + o una reducción (en cuyo caso sería un árbol o grafo Y-O). En cada nodo, además de almacenar el estado, almacenamos el nodo padre y la acción que se ha aplicado a este para obtener el nodo, lo que describe un camino. @@ -105,11 +105,11 @@ El entorno es \series bold observable \series default - si siempre conocemos todo el estado, + si siempre conocemos todo el estado; \series bold determinista \series default - si sabemos el resultado de cualquier secuencia de acciones desde un estado, + si sabemos el resultado de cualquier secuencia de acciones desde un estado; \series bold estático @@ -152,15 +152,15 @@ Podemos representar un problema de búsqueda en un espacio de estados como \begin_inset Formula $v$ \end_inset -; un estado inicial +; \begin_inset Formula $s\in V$ \end_inset -, y un conjunto computable de estados finales + es un estado inicial, y \begin_inset Formula $F\subseteq V$ \end_inset -. + es un conjunto computable de estados finales. Entonces una solución es un camino de \begin_inset Formula $s$ \end_inset @@ -470,6 +470,10 @@ Primero en profundidad con profundidad iterativa \begin_inset Formula $O(b^{d})$ \end_inset + para +\begin_inset Formula $d>1$ +\end_inset + y en espacio \begin_inset Formula $O(bd)$ \end_inset @@ -499,7 +503,8 @@ Suponemos \begin_inset Formula $\omega(A)\subseteq\mathbb{R}^{\geq0}$ \end_inset -.Una +. + Una \series bold función heurística \series default @@ -507,7 +512,7 @@ función heurística \begin_inset Formula $h:V\to\mathbb{R}^{\geq0}$ \end_inset - estima el menor peso de un camino de un nodo dado a un nodo objetivo de + estima el menor peso de un camino de un nodo dado a un nodo objetivo, de forma que \begin_inset Formula $h(F)=\{0\}$ \end_inset @@ -560,9 +565,9 @@ voraz \series default o \series bold -primero el mejor +primero el mejor: \series default -: + \begin_inset Formula $f(P)=h(\text{final}(P))$ \end_inset @@ -581,9 +586,9 @@ primero el mejor \begin_layout Itemize \series bold -A* +A*: \series default -: + \begin_inset Formula $f(P)=\omega(P)+h(\text{final}(P))$ \end_inset @@ -604,12 +609,8 @@ admisible \series bold optimista \series default - si, para -\begin_inset Formula $v\in V$ -\end_inset - -, -\begin_inset Formula $h(v)\leq\min\omega({\cal P}_{v,F})$ + si +\begin_inset Formula $\forall v\in V,h(v)\leq\min\omega({\cal P}_{v,F})$ \end_inset , y es @@ -657,7 +658,7 @@ Demostración: cumple \begin_inset Formula \[ -f(R)=\omega(R)+h(\text{final}(R))\leq\omega(R)+\min\omega({\cal P}_{\text{final}(R),F})\overset{S\in{\cal P}_{\text{final}(R),F}}{\leq}\omega(P)=c, +f(R)=\omega(R)+h(\text{final}(R))\leq\omega(R)+\min\omega({\cal P}_{\text{final}(R),F})\overset{S\in{\cal P}_{\text{final}(R),F}}{\leq}\omega(RS)=c, \] \end_inset @@ -676,15 +677,18 @@ f(R)=\omega(R)+h(\text{final}(R))\leq\omega(R)+\min\omega({\cal P}_{\text{final} \end_inset cumple -\begin_inset Formula $\omega(Q)\leq f(Q)\leq c$ +\begin_inset Formula $\omega(Q)\leq\omega(Q)+h(\text{final}(Q))=f(Q)\leq c$ \end_inset y tiene pues longitud máxima \begin_inset Formula $c/p$ \end_inset -, luego hay una cantidad finita de nodos así y el algoritmo siempre llega - a una solución con coste +, luego hay una cantidad finita de caminos con +\begin_inset Formula $f(Q)\leq c$ +\end_inset + + y el algoritmo siempre llega a una solución con coste \begin_inset Formula $c$ \end_inset @@ -788,7 +792,7 @@ Si \end_inset es -\begin_inset Formula $f(P_{j})=\omega(P_{j})+h(v_{j})=\omega(P_{i})+\omega(v_{i}\cdots v_{j})+h(v_{j})\geq\omega(P_{i})+h(v_{i})=f(P_{i})$ +\begin_inset Formula $f(P_{i})=\omega(P_{i})+h(v_{i})\leq\omega(P_{i})+\omega(v_{i}\cdots v_{j})+h(v_{j})=\omega(P_{j})+h(v_{j})=f(P_{j})$ \end_inset . @@ -802,7 +806,7 @@ Métodos limitados en memoria Cuando A* es óptimo, es el método óptimo más eficiente en tiempo, pero en general usa una frontera de tamaño exponencial y se queda pronto sin espacio. Algunos métodos usan menos espacio sin sacrificar optimalidad y completitud - a cambio de un mayor coste de ejecución: + a cambio de un mayor tiempo de ejecución: \end_layout \begin_layout Standard @@ -996,7 +1000,7 @@ lSSi{$ \backslash text{ \backslash -rm fallo}(t):=r$}{$b +rm fallo}(t):=r$}{$f_b \backslash gets t$} \end_layout @@ -1136,8 +1140,8 @@ Concretamente se elimina el nodo más antiguo dentro de los de mayor valor . Esto se hace así para evitar entrar en un bucle cuando todos los nodos - tienen el valor, y funciona si hay más de un nodo, pero si solo hay un - nodo esto significa que el camino solución está ocupando toda la memoria + tienen el mismo valor, y funciona si hay más de un nodo, pero si solo hay + un nodo esto significa que el camino solución está ocupando toda la memoria y no es representable en memoria. \end_layout @@ -1194,23 +1198,28 @@ Podemos representar un problema de reducción como una tupla \begin_inset Formula $(V,A,\omega,s)$ \end_inset - donde +, donde \begin_inset Formula $(V,A)$ \end_inset - es un grafo YO acíclico con -\begin_inset Formula $\{(u,S):u\in V\}$ + es un grafo Y/O acíclico con +\begin_inset Formula $V$ +\end_inset + + contable y tanto +\begin_inset Formula $\{S\subseteq V:(u,S)\in V\}$ \end_inset - finito y recursivamente enumerable a partir de + como cada uno de sus elementos finito y recursivamente enumerable a partir + de \begin_inset Formula $u$ \end_inset -, +; \begin_inset Formula $\omega:A\to\mathbb{R}^{\geq0}$ \end_inset - es una función de coste y + es una función de coste, y \begin_inset Formula $s\in V$ \end_inset @@ -1279,7 +1288,7 @@ noprefix "false" \end_inset , que va expandiendo nodos y eliminando nodos resolubles e irresolubles - de la frontera hasta que el nodo inicial sea de uno de los dos tipos. + de la frontera hasta clasificar el nodo inicial. \end_layout \begin_layout Standard @@ -1298,7 +1307,7 @@ status open \backslash Entrada{Problema de reducción $(V,A, \backslash -omega,s)$.} +omega,s)$ con $s$ no primitivo.} \end_layout \begin_layout Plain Layout @@ -1320,7 +1329,7 @@ gets \backslash }$ \backslash -; +tcp*{Caminos frontera} \end_layout \begin_layout Plain Layout @@ -1331,7 +1340,7 @@ gets \backslash emptyset$ \backslash -; +tcp*{Nodos irresolubles} \end_layout \begin_layout Plain Layout @@ -1342,11 +1351,103 @@ gets \backslash emptyset$ \backslash +tcp*{Nodos resolubles y su hiperarco siguiente} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwFunction{Resolucion}{{}resolución} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwProg{Func}{función}{}{fin} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Func{ +\backslash +Resolucion{$R,s$}}{ +\end_layout + +\begin_layout Plain Layout + + $N +\backslash +gets R(s)$ +\backslash ; \end_layout \begin_layout Plain Layout + $(V_0,A_0) +\backslash +gets( +\backslash +{s +\backslash +}, +\backslash +{(s,N) +\backslash +})$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lPara{$n +\backslash +in N$}{$(V_n,A_n) +\backslash +gets +\backslash +text{ +\backslash +Resolucion{ +\backslash +ensuremath{R,n}}}$} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $(V_0 +\backslash +cup +\backslash +bigcup_{n +\backslash +in N}V_n,A_0 +\backslash +cup +\backslash +bigcup_{n +\backslash +in N}A_n)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + \backslash Mientras{$F @@ -1380,6 +1481,8 @@ subseteq V:(u_n,S) in A \backslash }$ +\backslash +; \end_layout \begin_layout Plain Layout @@ -1404,7 +1507,9 @@ emptyset$}{ $i \backslash -gets n$; +gets n$ +\backslash +; \end_layout \begin_layout Plain Layout @@ -1464,7 +1569,9 @@ gets i-1$ \backslash -Para{$v +SSi{$ +\backslash +exists v \backslash in N:(v, \backslash @@ -1475,76 +1582,61 @@ in A$}{ \begin_layout Plain Layout - $i -\backslash -gets n$ -\backslash -; -\end_layout - -\begin_layout Plain Layout - \backslash -Repetir{$ +lPara{$v +\backslash +in N:(v, \backslash -forall(u_i,S) +emptyset) \backslash -in A,S +in A$}{añadir $(v, \backslash -nsubseteq R$}{ +emptyset)$ a $R$} \end_layout \begin_layout Plain Layout - Añadir $u_i$ a $R$ + $i +\backslash +gets n$ \backslash ; \end_layout \begin_layout Plain Layout - + \backslash -lSSi{$i=0$}{ -\end_layout - -\begin_layout Plain Layout - - $A' +Mientras{$ \backslash -gets +exists(u_i,S) \backslash -{ +in A:S \backslash -text{todos los hiperarcos del camino }P +subseteq \backslash -}$ +text{ \backslash -; +rm Dom}R$}{ \end_layout \begin_layout Plain Layout - $V' -\backslash -gets -\backslash -text{vértices referenciados por }A'$ + Añadir $(u_i,S)$ a $R$ \backslash ; \end_layout \begin_layout Plain Layout - + \backslash -Devolver{$(V',A')$} -\end_layout - -\begin_layout Plain Layout - - } +lSSi{$i=0$}{ +\backslash +Devolver +\backslash +Resolucion{$R,s$}} \end_layout \begin_layout Plain Layout @@ -1563,7 +1655,9 @@ gets i-1$ \begin_layout Plain Layout - Borrar de $F$ los nodos que contienen un vértice de $R$ + Borrar de $F$ los nodos que contienen un vértice de $ +\backslash +text{Dom}R$ \backslash ; \end_layout @@ -1605,6 +1699,12 @@ name "alg:search-generic-yo" \end_inset Algoritmo genérico de búsqueda en árboles Y/O. + En la versión de clase, +\begin_inset Formula $R$ +\end_inset + + no guarda el hiperarco siguiente de los nodos y la solución se extrae pues + por arte de magia. \end_layout \end_inset @@ -1642,7 +1742,7 @@ Primero en profundidad \series bold De profundidad limitada \series default -: Como la búsqueda en profundidad pero con un límite de profundidad. +: Como primero en profundidad pero con límite de profundidad. \end_layout \begin_layout Subsection @@ -1654,7 +1754,7 @@ Usamos una función heurística \begin_inset Formula $h:V\to\mathbb{R}^{\geq0}$ \end_inset - que estima el coste mínimo de una solución a partir de un grafo. + que estima el coste mínimo de una solución a partir de un nodo. Si \begin_inset Formula $h$ \end_inset @@ -1713,6 +1813,13 @@ emptyset$.} \begin_layout Plain Layout + +\backslash +SetKwFunction{Resolucion}{{}resolución} +\end_layout + +\begin_layout Plain Layout + $R \backslash gets @@ -1721,7 +1828,7 @@ gets \backslash }$ \backslash -; +tcp*{Por resolver} \end_layout \begin_layout Plain Layout @@ -1732,7 +1839,7 @@ gets \backslash emptyset$ \backslash -; +tcp*{Completados} \end_layout \begin_layout Plain Layout @@ -1741,33 +1848,47 @@ $w_s \backslash gets h(s)$ \backslash -; +tcp*{Coste estimado} \end_layout \begin_layout Plain Layout \backslash -lPara{$v +SSi{$(s, \backslash -in V$}{$b_s +emptyset) +\backslash +in A$}{ +\end_layout + +\begin_layout Plain Layout + + $b_s \backslash gets \backslash -emptyset$} +emptyset$ +\backslash +tcp*{Conector siguiente} \end_layout \begin_layout Plain Layout - -\backslash -lSSi{$s$ es primitiva}{$C + $C \backslash gets \backslash {s \backslash -}$} +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +} \end_layout \begin_layout Plain Layout @@ -1778,7 +1899,7 @@ Mientras{$s \backslash notin C \backslash -land c_s +land w_s \backslash leq F$}{ \end_layout @@ -1787,9 +1908,11 @@ leq F$}{ Tomar $n \backslash -in R$ con $b_n= +in R \backslash -emptyset$ +setminus +\backslash +text{Dom}b$ \backslash ; \end_layout @@ -1806,7 +1929,9 @@ in{ \backslash cal P}(V):(n,S) \backslash -in A$ +in A +\backslash +}$ \backslash ; \end_layout @@ -1856,15 +1981,18 @@ uSSi{$u$ es primitiva}{ \begin_layout Plain Layout - $C -\backslash -gets C + $b_u \backslash -cup +gets \backslash -{u +emptyset$ \backslash -}$ +; +\end_layout + +\begin_layout Plain Layout + + Añadir $u$ a $C$ \backslash ; \end_layout @@ -1903,15 +2031,7 @@ gets h(u)$ \begin_layout Plain Layout - $R -\backslash -gets R -\backslash -cup -\backslash -{u -\backslash -}$ + Añadir $u$ a $R$ \backslash ; \end_layout @@ -1928,22 +2048,22 @@ cup \begin_layout Plain Layout - $P + $M \backslash gets \backslash -{u +{n \backslash }$ \backslash -; +tcp*{Modificados} \end_layout \begin_layout Plain Layout \backslash -Mientras{$P +Mientras{$M \backslash neq \backslash @@ -1954,22 +2074,22 @@ emptyset$}{ Tomar $u \backslash -in P$ y sacarlo de $P$ +in M$ sin sucesores en $M$ y sacarlo de $M$ \backslash ; \end_layout \begin_layout Plain Layout - Tomar el $S:(u,S) + Tomar el $S$ con $(u,S) \backslash -in A$ con mínimo $ +in A$ de menor $ \backslash omega(u,S)+ \backslash sum_{v \backslash -in S}c_v$ +in S}w_v$ \backslash ; \end_layout @@ -1984,7 +2104,7 @@ omega(u,S)+ \backslash sum_{v \backslash -in S}c_v$ +in S}w_v$ \backslash ; \end_layout @@ -2004,20 +2124,16 @@ gets S$ \backslash lSSi{$S \backslash -subseteq C$}{$C -\backslash -gets C -\backslash -cup -\backslash -{Pu -\backslash -}$} +subseteq C$}{añadir $u$ a $C$} \end_layout \begin_layout Plain Layout - Añadir a $P$ los antecesores $v$ con $u + Añadir a $M$ los $v +\backslash +in +\backslash +text{Dom}b$ con $u \backslash in b_v$ \backslash @@ -2038,9 +2154,9 @@ in b_v$ \backslash -Devolver un grafo que contenga el nodo $s$, el conector $b_s$, los sucesores - $(n_i)_i$ de $b_s$, sus conectores $b_{n_i}$, etc., de forma recursiva hasta - llegar a primitivas +Devolver +\backslash +Resolucion{$b,s$} \backslash ; \end_layout @@ -2075,16 +2191,16 @@ Método YO*. \begin_layout Standard Para modelar procesos físicos en los que un subproblema puede tener que - resolverse dos o más veces, se pueden modificar el método YO* para trabajar + resolverse dos o más veces, se puede modificar el método YO* para trabajar con grafos que tengan ciclos, contando el coste de resolverlos varias veces, pero esto no es apropiado para problemas con procesos de resolución distintos. \end_layout \begin_layout Standard -Además, estamos suponiendo que la resolución de un subproblema no afecta - a la de otro, pero en muchos problemas sí que afecta, por lo que en vez - de esto se usan métodos de planificación. +Además, hemos supuesto que la resolución de un subproblema no afecta a la + de otro, pero en muchos problemas sí que afecta, por lo que en vez de esto + se usan métodos de planificación. \end_layout \begin_layout Section @@ -2100,29 +2216,39 @@ Si un problema tiene solución a profundidad \begin_inset Formula $N$ \end_inset - nodos (no se cuenta el nodo inicial), el + nodos (sin contar el nodo inicial), el \series bold factor de ramificación eficaz \series default - es el que un árbol con igual número de hijos en cada nodo tendría que tener - para que hubiera -\begin_inset Formula $N+1$ + es un +\begin_inset Formula $b^{*}\in\mathbb{R}^{\geq0}$ +\end_inset + + tal que +\begin_inset Formula $N=b^{*}+(b^{*})^{2}+\dots+(b^{*})^{d}$ +\end_inset + +, ya que cuando +\begin_inset Formula $b^{*}\in\mathbb{N}$ \end_inset - nodos con altura máxima +, un árbol de altura \begin_inset Formula $d$ \end_inset -, un -\begin_inset Formula $b^{*}\in\mathbb{R}^{\geq0}$ + con +\begin_inset Formula $b^{*}$ \end_inset - tal que -\begin_inset Formula $N=b^{*}+(b^{*})^{2}+\dots+(b^{*})^{d}$ + hijos en cada nodo de nivel menor que +\begin_inset Formula $d$ +\end_inset + + tiene tamaño +\begin_inset Formula $N+1$ \end_inset . - \end_layout \begin_layout Standard @@ -2135,13 +2261,13 @@ Una buena heurística debería producir valores de \end_inset . - Una forma de obtener + Podemos estimar un \begin_inset Formula $b^{*}$ \end_inset - es generar y resolver muchos problemas del mismo tipo con el método a usar, - comparando por ejemplo con BFS o búsqueda en profundidad iterativa para - tener un caso base. + medio generando y resolviendo muchos problemas del mismo tipo con el método + a usar, comparando por ejemplo con BFS o búsqueda en profundidad iterativa + para tener un caso base. \end_layout \begin_layout Standard @@ -2201,7 +2327,7 @@ problema 8-puzzle , dejando una casilla libre; como transiciones el movimiento a la casilla libre de una pieza adyacente vertical u horizontalmente, con coste 1, y - el estado final es uno en que, al concatenar las filas, aparecen los números + como estado final uno en que, al concatenar las filas, aparecen los números del 1 al 8 en orden, con la casilla libre al principio o al final según el modo de juego. \end_layout @@ -2239,7 +2365,7 @@ problema relajado \end_inset y -\begin_inset Formula $\omega'|_{V}=\omega$ +\begin_inset Formula $\omega'|_{A}=\omega$ \end_inset , con lo que el coste de una solución óptima en el problema relajado es @@ -88,25 +88,25 @@ Búsqueda local \end_layout \begin_layout Standard -En muchos problemas, como en diseño de circuitos u optimización de redes, +En muchos problemas, como el diseño de circuitos o la optimización de redes, solo importa el estado objetivo, no cómo se llega a él. \end_layout \begin_layout Standard Los métodos que veremos operan con un único estado actual, no suelen recordar los caminos, usan muy poca memoria y pueden encontrar soluciones razonables - en espacios de estados grandes o continuos en que los algoritmos clásicos + en espacios de estados grandes o continuos en los que los algoritmos clásicos no son adecuados. \end_layout \begin_layout Standard Podemos considerar el espacio de estados como un paisaje donde la posición es un estado y la elevación viene dada por una función objetivo a maximizar - o minimizar; supondremos que maximizar. + o minimizar; supondremos que a maximizar. \end_layout \begin_layout Standard -Por ejemplo, en el +Para el \series bold problema de las 8 reinas \series default @@ -155,8 +155,7 @@ ascensión de colinas de reinicio aleatorio \series default consiste en ejecutar la ascensión de colinas repetidamente con distintos estados iniciales. - Es completa con probabilidad 1, aunque no garantiza terminar, en espacios - de estados finitos + En espacios de estados finitos \begin_inset Foot status open @@ -167,7 +166,8 @@ En general cuando caer en un estado final tiene probabilidad no nula y ascender \end_inset -, y es muy eficaz. +, es completa con probabilidad 1, aunque no garantiza terminar, y es muy + eficaz. \end_layout \begin_layout Subsection @@ -227,7 +227,7 @@ to \backslash mathbb{R}^{ \backslash -geq0}$.} +geq0}$ monótono decreciente.} \end_layout \begin_layout Plain Layout @@ -1104,7 +1104,7 @@ geq \backslash beta$}{ \backslash -Devolver $i$} +Devolver $v$} \end_layout \begin_layout Plain Layout @@ -1191,13 +1191,13 @@ in A$}{ \begin_layout Plain Layout - $i + $v \backslash gets \backslash min \backslash -{i, +{v, \backslash MaxValor{$i, \backslash @@ -88,13 +88,13 @@ El \series bold conocimiento \series default - consiste en descripciones declarativas explícitas formadas por conceptos + consiste en descripciones declarativas explícitas, formadas por conceptos y relaciones entre los conceptos específicos a un dominio de aplicación, - y en métodos genéricos de resolución de problemas, formados por + junto con métodos genéricos de resolución de problemas, formados por \series bold técnicas de razonamiento \series default - que usan las relaciones entre conceptos para inferir conclusiones y una +, que usan las relaciones entre conceptos para inferir conclusiones, y una estructura de control para aplicar las técnicas. Por ejemplo, se puede representar el conocimiento por cláusulas de lógica de predicados de primer orden, y entonces una técnica de razonamiento es @@ -252,7 +252,7 @@ recuperación Muchas veces se selecciona un módulo completo, y se usa meta-conocimiento para elegir el siguiente módulo a cargar. Si hay varios métodos de resolución, se puede usar meta-conocimiento para - usar el más apropiado. + elegir el más apropiado. \end_layout \begin_layout Standard @@ -292,7 +292,7 @@ redundante \series default si se representa el mismo de varias formas, lo que permite una aplicación más efectiva porque algunas formas de conocimiento son más adecuadas para - ciertos casos que otras pero aumenta el volumen de datos. + ciertos casos que otras, pero aumenta el volumen de datos. \end_layout \begin_layout Section @@ -379,7 +379,7 @@ Una base de conocimiento \series default con las reglas del dominio. - La ejecución de una acción puede modificar de la base de hechos, normalmente + La ejecución de una acción puede modificar la base de hechos, normalmente añadiendo hechos inferidos. \end_layout @@ -397,9 +397,8 @@ red de inferencia \end_layout \begin_layout Standard -Un hecho que sea se representa como una flecha que va hacia la entrada de - las reglas que lo tengan como antecedente, posiblemente dividiéndose en - el camino. +Un hecho se representa como una flecha que va hacia la entrada de las reglas + que lo tengan como antecedente, posiblemente dividiéndose en el camino. Si el hecho es resultado del consecuente de una única regla, la flecha parte del consecuente; si lo es de varias reglas, parte de un rectángulo y se dibujan flechas de dichas reglas al rectángulo, y si no lo es de ninguna @@ -628,9 +627,9 @@ monótona . Las lógicas clásicas son monótonas, pero la monotonía no es apropiada cuando - el conocimiento es incompleto, pues puede que haya que hacer suposiciones - por defecto que puedan invalidarse cuando se tenga más conocimiento, ni - cuando el mundo es cambiante. + el conocimiento es incompleto o el mundo es cambiante, pues puede que haya + que hacer suposiciones por defecto que puedan invalidarse cuando se tenga + más conocimiento. \end_layout \begin_layout Standard @@ -790,8 +789,8 @@ Factores de certeza Para razonar con hechos con fiabilidad o precisión limitada o sobre los que no estamos seguros, se suele incorporar la incertidumbre a una lógica que no la incluye. - Esto se suele hacer con probabilidades y redes bayesianas, basadas probabilidad - condicionada e independencia de sucesos. + Esto se suele hacer con probabilidades y redes bayesianas, basadas en probabili +dad condicionada e independencia de sucesos. \end_layout \begin_layout Standard @@ -885,7 +884,7 @@ Con esto, cada regla \begin_inset Formula $h\to e$ \end_inset - lleva un factor de certeza asociado + lleva asociado un factor de certeza \begin_inset Formula $\text{FC}(h,e)$ \end_inset @@ -893,7 +892,7 @@ Con esto, cada regla \begin_inset Formula $h$ \end_inset - en la base de hechos lleva un factor de certeza + en la base de hechos lleva asociado un factor de certeza \begin_inset Formula $\text{FC}(h,\bot)$ \end_inset @@ -902,10 +901,36 @@ Con esto, cada regla \end_inset es la situación particular, y las reglas son: -\begin_inset Foot +\begin_inset Formula +\begin{align*} +\text{FC}(h_{1}\land h_{2},e) & =\min\{\text{FC}(h_{1},e),\text{FC}(h_{2},e)\},\\ +\text{FC}(h_{1}\lor h_{2},e) & =\max\{\text{FC}(h_{1},e),\text{FC}(h_{2},e)\},\\ +\text{FC}(h,e) & =\text{FC}(h,s)\max\{0,\text{FC}(s,e)\},\\ +\text{FC}(h,e_{1}\land e_{2}) & =\begin{cases} +\text{FC}(h,e_{1})+\text{FC}(h,e_{2})-\text{FC}(h,e_{1})\text{FC}(h,e_{2}), & \text{FC}(h,e_{1}),\text{FC}(h,e_{2})\geq0;\\ +\text{FC}(h,e_{1})+\text{FC}(h,e_{2})+\text{FC}(h,e_{1})\text{FC}(h,e_{2}), & \text{FC}(h,e_{1}),\text{FC}(h,e_{2})\leq0;\\ +\frac{\text{FC}(h,e_{1})+\text{FC}(h,e_{2})}{1-\min\{|\text{FC}(h,e_{1})|,|\text{FC}(h,e_{2})|\}}, & \text{FC}(h,e_{1})\text{FC}(h,e_{2})\leq0. +\end{cases} +\end{align*} + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT status open \begin_layout Plain Layout + + +\backslash +begin{sloppypar} +\end_layout + +\end_inset + En las diapositivas, las dos primeras reglas aparecen como \begin_inset Formula $\text{FC}(h,e_{1}\land e_{2})=\min\{\text{FC}(h,e_{1}),\text{FC}(h,e_{2})\}$ \end_inset @@ -914,31 +939,25 @@ En las diapositivas, las dos primeras reglas aparecen como \begin_inset Formula $\text{FC}(h,e_{1}\lor e_{2})=\max\{\text{FC}(h,e_{1}),\text{FC}(h,e_{2})\}$ \end_inset -, pero esto tendría menos sentido aún que las reglas que realmente usamos, - que son las que se muestran. -\end_layout +, lo que tiene aún menos sentido que las reglas que realmente usamos, que + son las que se muestran. + Las dos primeras reglas se usan para evaluar el factor de certeza de antecedent +es de reglas; la tercera para obtener el factor de certeza del consecuente + de una regla sabiendo el de su antecedente, y la cuarta para combinar factores + de certeza obtenidos por distintas reglas. +\begin_inset ERT +status open -\end_inset +\begin_layout Plain Layout -\begin_inset Formula -\begin{align*} -\text{FC}(h_{1}\land h_{2},e) & =\min\{\text{FC}(h_{1},e),\text{FC}(h_{2},e)\},\\ -\text{FC}(h_{1}\lor h_{2},e) & =\max\{\text{FC}(h_{1},e),\text{FC}(h_{2},e)\},\\ -\text{FC}(h,e) & =\text{FC}(h,s)\max\{0,\text{FC}(s,e)\},\\ -\text{FC}(h,e_{1}\land e_{2}) & =\begin{cases} -\text{FC}(h,e_{1})+\text{FC}(h,e_{2})-\text{FC}(h,e_{1})\text{FC}(h,e_{2}), & \text{FC}(h,e_{1}),\text{FC}(h,e_{2})\geq0;\\ -\text{FC}(h,e_{1})+\text{FC}(h,e_{2})+\text{FC}(h,e_{1})\text{FC}(h,e_{2}), & \text{FC}(h,e_{1}),\text{FC}(h,e_{2})\leq0;\\ -\frac{\text{FC}(h,e_{1})+\text{FC}(h,e_{2})}{1-\min\{|\text{FC}(h,e_{1})|,|\text{FC}(h,e_{2})|\}}, & \text{FC}(h,e_{1})\text{FC}(h,e_{2})\leq0. -\end{cases} -\end{align*} +\backslash +end{sloppypar} +\end_layout \end_inset -Las dos primeras se usan para evaluar el factor de certeza de antecedentes - de reglas; la tercera para obtener el factor de certeza del consecuente - de una regla sabiendo el de su antecedente y la cuarta para combinar factores - de certeza obtenidos por distintas reglas. + \end_layout \begin_layout Section @@ -115,8 +115,7 @@ frame problem \series bold cualificación \series default - es qué necesita la regla que se cumpla para poder ejecutable, y el de la - + es qué debe cumplirse para poder ejecutar una regla, y el de la \series bold ramificación \series default @@ -244,8 +243,8 @@ En el caso de reglas tipo STRIPS, aplicar una regla hacia atrás genera un Para obtenerlo, unificamos un subconjunto de los literales del objetivo con la fórmula de adición, aplicamos el unificador a todo el objetivo y la regla y tomamos la conjunción de la fórmula de precondición de la regla - con la regresión de los literales del objetivo que no aparecen en el subconjunt -o unificado. + con la regresión de los literales del objetivo que no están en el subconjunto + de literales que se unificó con la regla de adición. La \series bold regresión @@ -271,7 +270,7 @@ Pila de objetivos \begin_layout Standard STRIPS usa una planificación lineal mediante una pila de subobjetivos con - el algoritmo + el Algoritmo \begin_inset CommandInset ref LatexCommand ref reference "alg:strips" @@ -281,6 +280,16 @@ noprefix "false" \end_inset + o +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:stripshit" +plural "false" +caps "false" +noprefix "false" + +\end_inset + , que puede usar heurísticas para ordenar los literales de un objetivo compuesto al apilarlos y para elegir qué unificador usar y qué regla elegir para un objetivo simple. @@ -432,7 +441,7 @@ cdots l_n$ } \backslash -uEnOtroCaso{ +EnOtroCaso{ \end_layout \begin_layout Plain Layout @@ -504,6 +513,217 @@ Método de planificación de STRIPS. \end_layout +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +estado:=estado-inicial; plan:=[ ]; pila:=[ ]; +\end_layout + +\begin_layout Plain Layout +apilar objetivo en pila; +\end_layout + +\begin_layout Plain Layout +repetir hasta que pila esté vacía +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + +si el objetivo en la cima de la pila se empareja con descripción del estado + entonces +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +quitar de la pila y aplicar la sustitución a las expresiones que están debajo +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + +sino, si el objetivo en la cima de pila es conjunción de objetivos entonces +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +seleccionar un orden de los sub-objetivos y apilarlos en pila +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + +sino, si resueltos todos los sub-objetivos pero no resuelto objetivo entonces +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +reconsiderar objetivo compuesto y apilarlos en la pila +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + +sino, si la cima de pila es un objetivo simple +\begin_inset Quotes cld +\end_inset + +sg +\begin_inset Quotes crd +\end_inset + + entonces +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +elegir operador +\begin_inset Quotes cld +\end_inset + +OP +\begin_inset Quotes crd +\end_inset + + cuya lista de adición se empareja con +\begin_inset Quotes cld +\end_inset + +sg +\begin_inset Quotes crd +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +reemplazar el objetivo +\begin_inset Quotes cld +\end_inset + +sg +\begin_inset Quotes crd +\end_inset + + con el operador +\begin_inset Quotes cld +\end_inset + +OP +\begin_inset Quotes crd +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +apilar precondiciones de +\begin_inset Quotes cld +\end_inset + +OP +\begin_inset Quotes crd +\end_inset + + en pila +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + +sino, si la cima de la pila es un operador +\begin_inset Quotes cld +\end_inset + +OP +\begin_inset Quotes crd +\end_inset + + entoncces +\end_layout + +\begin_layout Plain Layout +\begin_inset space \quad{} +\end_inset + + +\begin_inset space \quad{} +\end_inset + +estado:=aplicar(OP,estado); plan=[plan;OP] +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:stripshit" + +\end_inset + +Versión de mierda del algoritmo STRIPS que aparece en las diapositivas y + por la que pueden preguntar. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + \begin_layout Section Planificación de orden parcial \end_layout @@ -551,7 +771,7 @@ Cuando una acción \end_inset o de otro ancestro que no aparezca en la lista de supresión de otra acción - posterior en el camino, pero si el motivo que vaya antes es que + posterior en el camino, pero si el motivo de que vaya antes es que \begin_inset Formula $B$ \end_inset @@ -279,10 +279,7 @@ matriz de costos Entonces el estimador de coste de una mala clasificación es \begin_inset Formula \[ -\sum_{i=1}^{n}\sum_{\begin{subarray}{c} -j=1\\ -j\neq i -\end{subarray}}^{n}a_{ij}c_{ij}. +\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}c_{ij}. \] \end_inset @@ -356,7 +353,7 @@ Resolución de problemas \end_layout \begin_layout Standard -Un programa para resolver problemas puede recordar la estructura del programa +Un programa para resolver problemas puede recordar la estructura del problema que ha resuelto, los métodos usados para resolverlo y su solución, generalizar la experiencia y usarla para resolver problemas similares. \end_layout @@ -442,7 +439,8 @@ Si \begin_inset Formula $D\subseteq{\cal P}(I)$ \end_inset - un conjunto finito de elementos de la base de datos, el + un conjunto finito de descripciones de elementos de la base de datos, el + \series bold soporte \series default @@ -466,12 +464,8 @@ precisión \begin_inset Quotes cld \end_inset -si -\begin_inset Formula $X$ -\end_inset - entonces -\begin_inset Formula $Y$ +\begin_inset Formula $X\Rightarrow Y$ \end_inset @@ -495,20 +489,43 @@ cobertura \end_inset . -\begin_inset Foot -status open - -\begin_layout Plain Layout -Las diapositivas usan la notación de mierda + Las diapositivas usan la notación de mierda \begin_inset Formula $|X|:=|\{e\in D:X\subseteq e\}|$ \end_inset . + \end_layout +\begin_layout Standard +Para obtener reglas con buenos valores de soporte y confianza, primero ejecutamo +s el algoritmo a priori (algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:a-priori" +plural "false" +caps "false" +noprefix "false" + \end_inset - +) para obtener un conjunto +\begin_inset Formula ${\cal L}$ +\end_inset + + de conjuntos de ítems frecuentes y luego tomamos las reglas +\begin_inset Formula $r\in\bigcup_{L\in{\cal L}}\{X\Rightarrow L\setminus X\}_{X\subseteq L}$ +\end_inset + + con +\begin_inset Formula $c(r)\geq p$ +\end_inset + +, donde +\begin_inset Formula $p$ +\end_inset + + es la precisión mínima. \end_layout \begin_layout Standard @@ -565,7 +582,7 @@ gets \backslash }_{i \backslash -in D,s( +in I,s( \backslash {i \backslash @@ -741,36 +758,5 @@ Algoritmo a priori. \end_layout -\begin_layout Standard -Para obtener reglas con buenos valores de soporte y confianza, primero ejecutamo -s el algoritmo a priori (algoritmo -\begin_inset CommandInset ref -LatexCommand ref -reference "alg:a-priori" -plural "false" -caps "false" -noprefix "false" - -\end_inset - -) para obtener los conjuntos de ítems frecuentes en -\begin_inset Formula ${\cal L}$ -\end_inset - - y luego tomamos las reglas -\begin_inset Formula $r\in\bigcup_{L\in{\cal L}}\{X\Rightarrow L\setminus X\}_{X\subseteq L}$ -\end_inset - - con -\begin_inset Formula $c(r)\geq p$ -\end_inset - -, donde -\begin_inset Formula $p$ -\end_inset - - es la precisión mínima. -\end_layout - \end_body \end_document |
