diff options
| -rw-r--r-- | si/n.lyx | 95 | ||||
| -rw-r--r-- | si/n2.lyx | 133 | ||||
| -rw-r--r-- | si/n3.lyx | 2278 |
3 files changed, 2490 insertions, 16 deletions
@@ -9,6 +9,9 @@ \input{../defs} \end_preamble \use_default_options true +\begin_modules +algorithm2e +\end_modules \maintain_unincluded_children false \language spanish \language_package default @@ -139,7 +142,29 @@ Diapositivas de clase, Universidad de Murcia. \end_layout \begin_layout Itemize -Wikipedia, the Free Encyclopedia ( + +\lang english +Stuart +\lang spanish + J. + +\lang english +Russell +\lang spanish + & Peter Norvig (2010). + +\emph on +\lang english +Artificial Intelligence, A Modern Approach. + Third Edition. +\end_layout + +\begin_layout Itemize + +\lang english +Wikipedia, the Free Encyclopedia +\lang spanish + ( \begin_inset Flex URL status open @@ -153,6 +178,7 @@ https://en.wikipedia.org/ ). \emph on +\lang english Semantic Networks \emph default , @@ -166,6 +192,59 @@ And–or tree . \end_layout +\begin_layout Itemize + +\lang english +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +begin{sloppypar} +\end_layout + +\end_inset + +G. + Veera Raghavaiah +\lang spanish + (2010). + +\emph on +\lang english +Problem Reduction with AO* Algorithm +\emph default +\lang spanish + ( +\begin_inset Flex URL +status open + +\begin_layout Plain Layout + +https://artificialintelligence-notes.blogspot.com/2010/07/problem-reduction-with-a +o-algorithm.html +\end_layout + +\end_inset + +). +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +end{sloppypar} +\end_layout + +\end_inset + + +\end_layout + \begin_layout Chapter Introducción \end_layout @@ -194,5 +273,19 @@ filename "n2.lyx" \end_layout +\begin_layout Chapter +Estrategias de búsqueda +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n3.lyx" + +\end_inset + + +\end_layout + \end_body \end_document @@ -182,31 +182,124 @@ subproblema alternativo \end_layout \begin_layout Standard -Podemos tratar la representación como un +Un +\series bold +grafo YO +\series default + es un par +\begin_inset Formula $(V,A)$ +\end_inset + + donde +\begin_inset Formula $V$ +\end_inset + + es un conjunto de nodos y +\begin_inset Formula $A\subseteq V\times{\cal P}(V)$ +\end_inset + + es un conjunto de \series bold -grafo Y-O +hiperarcos \series default -, un grafo dirigido en que cada nodo es de uno de los 3 tipos, los primitivos - no son el inicial de ningún arco y los Y son el inicial de algún arco. - Dibujamos los nodos primitivos con un doble círculo y los nodos Y con un - arco, cóncavo hacia el propio nodo, que cruza las flechas que lo unen con - los sucesores, generalmente sin pasarse de las flechas de los extremos. - Del mismo modo podemos usar un + o \series bold -árbol Y-O +conectores \series default . - + Si +\begin_inset Formula $(a,S)$ +\end_inset + + es un conector, +\begin_inset Formula $a$ +\end_inset + + es su +\series bold +antecesor +\series default + y los nodos de +\begin_inset Formula $S$ +\end_inset + + son sus +\series bold + sucesores +\series default +. + Un +\series bold + +\begin_inset Formula $k$ +\end_inset + +-conector +\series default + es un conector con +\begin_inset Formula $k$ +\end_inset + + sucesores. + Para dibujar un grafo YO, dibujamos un punto con una etiqueta, o un círculo, + para cada nodo, y para cada hiperarco trazamos flechas del antecesor a + cada sucesor. + Si hay al menos dos sucesores, hacemos un arco, cóncavo hacia el antecesor, + que une las flechas, y si no hay ninguno en vez de esto representamos el + nodo antecesor con un doble círculo. + Un nodo es +\series bold +resoluble +\series default + si es antecesor de un hiperarco cuyos sucesores son todos resolubles. \end_layout \begin_layout Standard -Un nodo es +Un \series bold -resoluble +grafo Y/O +\series default + o +\series bold +Y-O +\series default + es un grafo YO en que para cada +\begin_inset Formula $u\in V$ +\end_inset + +, +\begin_inset Formula $\{S\subseteq V:(u,S)\in A\}$ +\end_inset + + es unipuntual o todos sus hiperarcos tienen un único sucesor. + Si es unipuntual con al menos dos sucesores, es un nodo +\series bold +Y \series default - si es primitivo; es Y y todos sus sucesores son resolubles, o es O y al - menos uno de sus sucesores es resoluble, entendiéndose una recursión bien - fundada. +; si tiene algún hiperarco con un único sucesor, es un nodo +\series bold +O +\series default +, y de lo contrario es un +\series bold +terminal +\series default +, en cuyo caso es una +\series bold +primitiva +\series default + si es antecesor de un hiperarco sin sucesores. + 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. + Un +\series bold +árbol Y/O +\series default + es un grafo Y/O para el que el grafo no dirigido +\begin_inset Formula $(V,\{(u,v)\in V\times V:\exists(u,S)\in A:v\in S\})$ +\end_inset + + es acíclico. \end_layout \end_deeper @@ -255,12 +348,16 @@ dirigida por datos \series default , \emph on +\lang english forward \emph default +\lang spanish o \emph on +\lang english bottom-up \emph default +\lang spanish si parte de la situación inicial y aplica los operadores hasta llegar al objetivo, y es \series bold @@ -272,12 +369,16 @@ dirigida por objetivos \series default , \emph on +\lang english backward \emph default +\lang spanish o \emph on +\lang english top-down \emph default +\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. @@ -327,8 +428,10 @@ exploración \series default , haciendo algún tipo de \emph on +\lang english 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. diff --git a/si/n3.lyx b/si/n3.lyx new file mode 100644 index 0000000..25dfd6e --- /dev/null +++ b/si/n3.lyx @@ -0,0 +1,2278 @@ +#LyX 2.3 created this file. For more info see http://www.lyx.org/ +\lyxformat 544 +\begin_document +\begin_header +\save_transient_properties true +\origin unavailable +\textclass book +\use_default_options true +\begin_modules +algorithm2e +\end_modules +\maintain_unincluded_children false +\language spanish +\language_package default +\inputencoding auto +\fontencoding global +\font_roman "default" "default" +\font_sans "default" "default" +\font_typewriter "default" "default" +\font_math "auto" "auto" +\font_default_family default +\use_non_tex_fonts false +\font_sc false +\font_osf false +\font_sf_scale 100 100 +\font_tt_scale 100 100 +\use_microtype false +\use_dash_ligatures true +\graphics default +\default_output_format default +\output_sync 0 +\bibtex_command default +\index_command default +\paperfontsize default +\spacing single +\use_hyperref false +\papersize default +\use_geometry false +\use_package amsmath 1 +\use_package amssymb 1 +\use_package cancel 1 +\use_package esint 1 +\use_package mathdots 1 +\use_package mathtools 1 +\use_package mhchem 1 +\use_package stackrel 1 +\use_package stmaryrd 1 +\use_package undertilde 1 +\cite_engine basic +\cite_engine_type default +\biblio_style plain +\use_bibtopic false +\use_indices false +\paperorientation portrait +\suppress_date false +\justification true +\use_refstyle 1 +\use_minted 0 +\index Index +\shortcut idx +\color #008000 +\end_index +\secnumdepth 3 +\tocdepth 3 +\paragraph_separation indent +\paragraph_indentation default +\is_math_indent 0 +\math_numbering_side default +\quotes_style french +\dynamic_quotes 0 +\papercolumns 1 +\papersides 1 +\paperpagestyle default +\tracking_changes false +\output_changes false +\html_math_output 0 +\html_css_as_file 0 +\html_be_strict false +\end_header + +\begin_body + +\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). + 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. + También podemos almacenar el coste del camino y la profundidad (longitud + del camino) desde el nodo raíz. + Un método de búsqueda es +\series bold +completo +\series default + si siempre que exista una solución la encuentra, y es +\series bold +óptimo +\series default + si además la solución encontrada es de coste mínimo. +\end_layout + +\begin_layout Standard +El entorno es +\series bold +observable +\series default + si siempre conocemos todo el estado, +\series bold +determinista +\series default + si sabemos el resultado de cualquier secuencia de acciones desde un estado, + +\series bold +estático +\series default + si, al encontrar un camino solución, podemos ejecutarlo sin observar los + cambios y llegar a la solución, y +\series bold +discreto +\series default + si solo hay un número finito de acciones posibles desde cada estado. + Suponemos un entorno observable, determinista, estático y discreto, y omitimos + aspectos como el tiempo límite para obtener la solución, el gasto en combustibl +e, la presión en el brazo robot, etc. +\end_layout + +\begin_layout Section +Estrategias en un espacio de estados +\end_layout + +\begin_layout Standard +Podemos representar un problema de búsqueda en un espacio de estados como + una tupla +\begin_inset Formula $(V,A,\omega,s,F)$ +\end_inset + + donde +\begin_inset Formula $(V,A,\omega)$ +\end_inset + + es una red dirigida de tamaño contable en la que queremos minimizar el + peso del camino y, para todo +\begin_inset Formula $v\in V$ +\end_inset + +, +\begin_inset Formula $\{w\in V:(v,w)\in A\}$ +\end_inset + + es finito y recursivamente enumerable a partir de +\begin_inset Formula $v$ +\end_inset + +; un estado inicial +\begin_inset Formula $s\in V$ +\end_inset + +, y un conjunto computable de estados finales +\begin_inset Formula $F\subseteq V$ +\end_inset + +. + Entonces una solución es un camino de +\begin_inset Formula $s$ +\end_inset + + a un estado de +\begin_inset Formula $F$ +\end_inset + +, y los algoritmos de búsqueda tienen la forma del algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:search-generic" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +, con ligeras variaciones. +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Problema de búsqueda en espacio de estados $(V,A, +\backslash +omega,s,F)$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Camino solución o $ +\backslash +emptyset$.} +\end_layout + +\begin_layout Plain Layout + +$L +\backslash +gets((s))$ +\backslash +tcp*{Lista de caminos { +\backslash +bf frontera}.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Mientras{$L +\backslash +neq +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + Extraer último elemento $P$ de $L$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +uSSi{$(i:= +\backslash +text{final}(P)) +\backslash +in F$}{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $P$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\backslash +EnOtroCaso{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$j +\backslash +in V:(i,j) +\backslash +in A$}{ +\end_layout + +\begin_layout Plain Layout + + Insertar $Pj$ en $L$ en orden dado por la estrategia +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $ +\backslash +emptyset$ +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:search-generic" + +\end_inset + +Algoritmo genérico de búsqueda en árboles. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Llamamos +\series bold +nodos cerrados +\series default + a los nodos del árbol o grafo de búsqueda que han sido considerados y expandido +s (se han calculado sus nodos hijo) y +\series bold +nodos frontera +\series default + a los que han sido generados pero no expandidos. +\end_layout + +\begin_layout Subsection +Búsqueda a ciegas +\end_layout + +\begin_layout Standard +Algunas estrategias son: +\end_layout + +\begin_layout Itemize + +\series bold +Primero en anchura +\series default +: Los nodos se insertan al principio en una cola, explorando sucesivamente + cada nivel del árbol. + Es completa pero no óptima, con complejidad en tiempo y espacio +\begin_inset Formula $O(b^{d+1})$ +\end_inset + +, donde +\begin_inset Formula $d$ +\end_inset + + es la profundidad de la solución y +\begin_inset Formula $b$ +\end_inset + + es el +\series bold +factor de ramificación +\series default +, el número de hijos por nodo no hoja. +\end_layout + +\begin_layout Itemize + +\series bold +De costo uniforme +\series default +: Los nodos se insertan de menor a mayor peso del camino. + Si +\begin_inset Formula $\omega(A)$ +\end_inset + + tiene una cota inferior +\begin_inset Formula $\delta>0$ +\end_inset + +, es completa, óptima y con complejidad en tiempo y espacio +\begin_inset Formula $O(b^{c/\delta})$ +\end_inset + +, donde +\begin_inset Formula $c$ +\end_inset + + es el peso del camino a la solución óptima. +\end_layout + +\begin_layout Itemize + +\series bold +Primero en profundidad +\series default +: Los nodos se insertan al final en una pila. + No es completa ni óptima, y tiene complejidad en tiempo +\begin_inset Formula $O(b^{h})$ +\end_inset + +, siendo +\begin_inset Formula $h$ +\end_inset + + la altura del árbol, y en espacio +\begin_inset Formula $O(bh)$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +De profundidad limitada +\series default +: Como la búsqueda primero en profundidad pero limitando la profundidad + a un cierto +\begin_inset Formula $p$ +\end_inset + +. + No es óptima, y es completa si y sólo si hay una solución en un nivel menor + o igual a +\begin_inset Formula $p$ +\end_inset + +. + La complejidad es +\begin_inset Formula $O(b^{p})$ +\end_inset + + en tiempo y +\begin_inset Formula $O(bp)$ +\end_inset + + en espacio. +\end_layout + +\begin_layout Itemize + +\series bold +Primero en profundidad con profundidad iterativa +\series default +: Se parte de búsqueda de profundidad limitada (a 0) y se repite la búsqueda + con un límite mayor (en 1) hasta encontrar la solución. + Es completa pero no óptima, con complejidad en tiempo +\begin_inset Formula $O(b^{d})$ +\end_inset + + y en espacio +\begin_inset Formula $O(bd)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Si el árbol tiene muchos estados repetidos es preferible operar sobre el + grafo de búsqueda, manteniendo una lista de estados visitados para no volver + a insertarlos en la frontera y en su lugar, opcionalmente, sustituir los + caminos a estos en los nodos frontera por otros de menor peso. +\end_layout + +\begin_layout Subsection +Búsqueda heurística +\end_layout + +\begin_layout Standard +Podemos usar heurísticas específicas al problema para decidir el siguiente + nodo a expandir e, incluso, qué nodos no tener en cuenta, podando el árbol + de búsqueda. +\end_layout + +\begin_layout Standard +Suponemos +\begin_inset Formula $\omega(A)\subseteq\mathbb{R}^{\geq0}$ +\end_inset + +.Una +\series bold +función heurística +\series default +, +\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 + forma que +\begin_inset Formula $h(F)=\{0\}$ +\end_inset + +. + +\end_layout + +\begin_layout Standard +Sea +\begin_inset Formula ${\cal P}_{s,V}$ +\end_inset + + el conjunto de caminos de +\begin_inset Formula $s$ +\end_inset + + a un estado en +\begin_inset Formula $V$ +\end_inset + +, una +\series bold +función de evaluación +\series default + +\begin_inset Formula $f:{\cal P}_{s,V}\to\mathbb{R}$ +\end_inset + + asigna un menor valor a los nodos más prometedores para expandir, y podemos + ordenar los nodos de menor a mayor valor de +\begin_inset Formula $f$ +\end_inset + + en una cola con prioridad. +\end_layout + +\begin_layout Standard +Algunos algoritmos de búsqueda heurísticos: +\end_layout + +\begin_layout Itemize + +\series bold +Búsqueda avara +\series default +, +\series bold +voraz +\series default + o +\series bold +primero el mejor +\series default +: +\begin_inset Formula $f(P)=h(\text{final}(P))$ +\end_inset + +. + La complejidad en tiempo y espacio es +\begin_inset Formula $O(b^{m})$ +\end_inset + +, pero con una buena +\begin_inset Formula $h$ +\end_inset + + el consumo de tiempo y espacio disminuye mucho. +\end_layout + +\begin_layout Itemize + +\series bold +A* +\series default +: +\begin_inset Formula $f(P)=\omega(P)+h(\text{final}(P))$ +\end_inset + +, el coste del camino del inicio al nodo más el coste estimado del nodo + al objetivo. +\end_layout + +\begin_layout Standard +Una heurística +\begin_inset Formula $h$ +\end_inset + + es +\series bold +admisible +\series default + u +\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})$ +\end_inset + +, y es +\series bold +pesimista +\series default + en otro caso. + Si +\begin_inset Formula $h$ +\end_inset + + es admisible y +\begin_inset Formula $\omega(A)$ +\end_inset + + tiene una cota inferior positiva, la búsqueda A* guiada por +\begin_inset Formula $h$ +\end_inset + + es óptima. + +\series bold +Demostración: +\series default + Sea +\begin_inset Formula $c$ +\end_inset + + el coste de las soluciones óptimas, toda solución no óptima +\begin_inset Formula $Q$ +\end_inset + + cumple +\begin_inset Formula $f(Q)=\omega(Q)+h(\text{final}(Q))=\omega(Q)+0>c$ +\end_inset + +, y todo prefijo +\begin_inset Formula $R$ +\end_inset + + de una solución óptima +\begin_inset Formula $RS$ +\end_inset + + 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, +\] + +\end_inset + + por lo que siempre se procesa antes una solución óptima que una no óptima. + Sea ahora +\begin_inset Formula $p:=\inf\omega(A)>0$ +\end_inset + +, todo +\begin_inset Formula $Q\in{\cal P}_{s,V}$ +\end_inset + + con +\begin_inset Formula $f(Q)\leq c$ +\end_inset + + cumple +\begin_inset Formula $\omega(Q)\leq 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 +\begin_inset Formula $c$ +\end_inset + + y termina. +\end_layout + +\begin_layout Standard +Si +\begin_inset Formula $h$ +\end_inset + + es admisible y +\begin_inset Formula $\omega(A)$ +\end_inset + + tiene cota inferior positiva, A* guiado por +\begin_inset Formula $h$ +\end_inset + + sobre el grafo de búsqueda es óptimo si, cuando se encuentra un estado + repetido por un camino con coste menor al que teníamos antes, sustituimos + el camino anterior por el nuevo en los nodos cerrados y frontera que lo + tengan como prefijo. + Si esto no se hace, el algoritmo no garantiza optimalidad, pues puede ignorar + el camino óptimo si en este aparece un estado repetido. +\end_layout + +\begin_layout Standard +Una heurística +\begin_inset Formula $h$ +\end_inset + + es +\series bold +consistente +\series default + si para +\begin_inset Formula $u,v\in V$ +\end_inset + + tales que existe un camino de +\begin_inset Formula $u$ +\end_inset + + a +\begin_inset Formula $v$ +\end_inset + +, +\begin_inset Formula $h(u)\leq\min\omega({\cal P}_{u,v})+h(v)$ +\end_inset + +, y es +\series bold +monótona +\series default + si para +\begin_inset Formula $(u,v)\in A$ +\end_inset + +, +\begin_inset Formula $h(u)\leq\omega(u,v)+h(v)$ +\end_inset + +. + Estas condiciones son equivalentes y más fuertes que la admisibilidad. +\end_layout + +\begin_layout Standard +Si +\begin_inset Formula $h$ +\end_inset + + es consistente, +\begin_inset Formula $f$ +\end_inset + + es la función de evaluación de A* guiado por +\begin_inset Formula $h$ +\end_inset + + y +\begin_inset Formula $v_{0}\cdots v_{n}$ +\end_inset + + es un camino en +\begin_inset Formula $(V,A)$ +\end_inset + +, +\begin_inset Formula $(f(v_{0}\cdots v_{i}))_{i=0}^{n}$ +\end_inset + + es monótona creciente. + En efecto, sea +\begin_inset Formula $P_{i}:=v_{0}\cdots v_{i}$ +\end_inset + +, para +\begin_inset Formula $i<j$ +\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})$ +\end_inset + +. +\end_layout + +\begin_layout Subsection +Métodos limitados en memoria +\end_layout + +\begin_layout Standard +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: +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Problema de búsqueda en espacio de estados $(V,A, +\backslash +omega,s,F)$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Camino solución o $ +\backslash +emptyset$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwFunction{RBFS}{{}RBFS} +\end_layout + +\begin_layout Plain Layout + + +\backslash +SetKwProg{Func}{función}{}{fin} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Func{ +\backslash +RBFS{$(P,f_0),f_{ +\backslash +text{limit}}$}}{ +\end_layout + +\begin_layout Plain Layout + + $u:= +\backslash +text{final}(P)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$u +\backslash +in F$}{ +\backslash +Devolver{$P$}} +\end_layout + +\begin_layout Plain Layout + + $N:= +\backslash +{v +\backslash +in V:(u,v) +\backslash +in A +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$N= +\backslash +emptyset$}{ +\backslash +Devolver fallo($+ +\backslash +infty$)} +\end_layout + +\begin_layout Plain Layout + + +\backslash +lPara{$v +\backslash +in N$}{$f_v +\backslash +gets +\backslash +max +\backslash +{ +\backslash +omega(Pv)+h(v), f_0 +\backslash +}$} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Repetir{$r$ no sea un fallo}{ +\end_layout + +\begin_layout Plain Layout + + Elegir $b +\backslash +in N$ con $f_b$ mínimo +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$f_b > f_{ +\backslash +text{limit}}$}{ +\backslash +Devolver fallo($f_b$)} +\end_layout + +\begin_layout Plain Layout + + Elegir el menor $a +\backslash +in +\backslash +{f_v +\backslash +}_{v +\backslash +in N +\backslash +setminus +\backslash +{b +\backslash +}}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $r +\backslash +gets +\backslash +text{ +\backslash +RBFS{ +\backslash +ensuremath{(Pb, f_b),a}}}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$ +\backslash +text{ +\backslash +rm fallo}(t):=r$}{$b +\backslash +gets t$} +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $r$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +RBFS{$((s),h(s)),+ +\backslash +infty$} +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:rbfs" + +\end_inset + +Búsqueda primero el mejor recursiva. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\series bold +Búsqueda primero el mejor recursiva +\series default + o +\series bold +con memoria acotada +\series default +: Algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:rbfs" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +. + Al inspeccionar un nodo, calcula los valores de +\begin_inset Formula $f$ +\end_inset + + para sus hijos y expande el que tenga el menor valor, pero poniendo como + límite el valor del siguiente mejor para evitar expandir nodos por encima + de ese valor. + Además, cuando no se encuentra una solución suficientemente buena a partir + de un hijo, su valor +\begin_inset Formula $f$ +\end_inset + + se actualiza al del mejor hijo de este. +\end_layout + +\begin_deeper +\begin_layout Standard +El método es óptimo para las mismas condiciones que A*. + Su complejidad en espacio es +\begin_inset Formula $O(bd)$ +\end_inset + +, pero en tiempo es peor que A* y dependiendo de la exactitud de la función + heurística tendrá que reevaluar más o menos nodos. +\end_layout + +\end_deeper +\begin_layout Itemize + +\series bold +A*MS +\series default + o +\series bold +A* con memoria acotada simplificado +\series default +: Como A* pero, cuando la memoria se llena, elimina el nodo con mayor valor + de +\begin_inset Formula $f$ +\end_inset + +. +\begin_inset Foot +status open + +\begin_layout Plain Layout +Concretamente se elimina el nodo más antiguo dentro de los de mayor valor + de +\begin_inset Formula $f$ +\end_inset + + y se procesa el nodo más nuevo dentro de los de menor valor de +\begin_inset Formula $f$ +\end_inset + +. + 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 + y no es representable en memoria. +\end_layout + +\end_inset + + Entonces guarda en el nodo padre el valor del hijo eliminado para reiniciar + desde ahí cuando el resto de caminos sean peores. +\end_layout + +\begin_layout Standard +Una heurística +\begin_inset Formula $h$ +\end_inset + + es +\series bold + +\begin_inset Formula $\varepsilon$ +\end_inset + +-admisible +\series default + para un +\begin_inset Formula $\varepsilon>0$ +\end_inset + + si para +\begin_inset Formula $v\in V$ +\end_inset + + es +\begin_inset Formula $h(v)\leq\min\omega({\cal P}_{v,F})+\varepsilon$ +\end_inset + +. + Para ciertos problemas solo podemos diseñar de forma efectiva heurísticas + no admisibles, pero una heurística +\begin_inset Formula $\varepsilon$ +\end_inset + +-admisible nos permite obtener una solución que queda a +\begin_inset Formula $\varepsilon$ +\end_inset + + de una solución óptima. +\end_layout + +\begin_layout Section +Estrategias en un problema de reducción +\end_layout + +\begin_layout Standard +Podemos representar un problema de reducción como una tupla +\begin_inset Formula $(V,A,\omega,s)$ +\end_inset + + donde +\begin_inset Formula $(V,A)$ +\end_inset + + es un grafo YO acíclico con +\begin_inset Formula $\{(u,S):u\in V\}$ +\end_inset + + 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 +\begin_inset Formula $s\in V$ +\end_inset + + es la situación inicial. +\end_layout + +\begin_layout Standard +Entonces, si +\begin_inset Formula $s$ +\end_inset + + es resoluble en +\begin_inset Formula $(V,A)$ +\end_inset + +, dado un +\begin_inset Formula $c:=(s,\{v_{1},\dots,v_{n}\})\in A$ +\end_inset + + tal que todos los +\begin_inset Formula $v_{i}$ +\end_inset + + son resolubles, un +\series bold +grafo solución +\series default + de +\begin_inset Formula $(V,A,\omega,s)$ +\end_inset + + es +\begin_inset Formula $(V',A'):=(\{s,v_{1},\dots,v_{n}\}\cup\bigcup_{i}V_{i},c\cup\bigcup_{i}A_{i})$ +\end_inset + +, donde +\begin_inset Formula $(V_{i},A_{i})$ +\end_inset + + es el grafo solución de +\begin_inset Formula $v_{i}$ +\end_inset + +, y el coste de la solución es +\begin_inset Formula $\omega(V',A'):=\omega(c)+\sum_{i}\omega(V_{i},A_{i})$ +\end_inset + +. + Nótese que esta definición puede contar el coste de alguno de los conectores + más de una vez. +\end_layout + +\begin_layout Subsection +Búsqueda a ciegas +\end_layout + +\begin_layout Standard +Los algoritmos tienen la forma del algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:search-generic-yo" +plural "false" +caps "false" +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. +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Problema de reducción $(V,A, +\backslash +omega,s)$.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Solución o $ +\backslash +emptyset$.} +\end_layout + +\begin_layout Plain Layout + +$F +\backslash +gets +\backslash +{(s) +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +$I +\backslash +gets +\backslash +emptyset$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +$R +\backslash +gets +\backslash +emptyset$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Mientras{$F +\backslash +neq +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + Extraer último $P=u_0 +\backslash +cdots u_n$ de $F$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $N +\backslash +gets +\backslash +bigcup +\backslash +{S +\backslash +subseteq V:(u_n,S) +\backslash +in A +\backslash +}$ +\end_layout + +\begin_layout Plain Layout + + +\backslash +lPara{$v +\backslash +in N$}{insertar $Pv$ en $F$ en orden dado por la estrategia} +\end_layout + +\begin_layout Plain Layout + + +\backslash +uSSi{$N= +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + $i +\backslash +gets n$; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Repetir{exista $(u_i,S) +\backslash +in A$ con $S$ disjunto de $I$}{ +\end_layout + +\begin_layout Plain Layout + + Añadir $u_i$ a $I$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$i=0$}{ +\backslash +Devolver $ +\backslash +emptyset$} +\end_layout + +\begin_layout Plain Layout + + $i +\backslash +gets i-1$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + Borrar de $F$ los nodos que contienen un vértice de $I$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$v +\backslash +in N:(v, +\backslash +emptyset) +\backslash +in A$}{ +\end_layout + +\begin_layout Plain Layout + + $i +\backslash +gets n$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Repetir{para $(u_i,S) +\backslash +in A$ sea $S +\backslash +nsubseteq R$}{ +\end_layout + +\begin_layout Plain Layout + + Añadir $u_i$ a $R$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$i=0$}{ +\end_layout + +\begin_layout Plain Layout + + $A' +\backslash +gets +\backslash +{ +\backslash +text{todos los hiperarcos del camino }P +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $V' +\backslash +gets +\backslash +text{vértices referenciados por }A'$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver{$(V',A')$} +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + $i +\backslash +gets i-1$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + Borrar de $F$ los nodos que contienen un vértice de $R$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Devolver $ +\backslash +emptyset$ +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:search-generic-yo" + +\end_inset + +Algoritmo genérico de búsqueda en árboles Y/O. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Algunas estrategias son: +\end_layout + +\begin_layout Itemize + +\series bold +Primero en anchura +\series default +: Inserta los nodos al principio en una cola. +\end_layout + +\begin_layout Itemize + +\series bold +Primero en profundidad +\series default +: Inserta los nodos al final en una pila. +\end_layout + +\begin_layout Itemize + +\series bold +De profundidad limitada +\series default +: Como la búsqueda en profundidad pero con un límite de profundidad. +\end_layout + +\begin_layout Subsection +Búsqueda heurística +\end_layout + +\begin_layout Standard +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. + Si +\begin_inset Formula $h$ +\end_inset + + es monótona y existe un grafo solución del problema, el método +\series bold +YO* +\series default + (algoritmo +\begin_inset CommandInset ref +LatexCommand ref +reference "alg:yo-star" +plural "false" +caps "false" +noprefix "false" + +\end_inset + +) es óptimo. +\end_layout + +\begin_layout Standard +\begin_inset Float algorithm +wide false +sideways false +status open + +\begin_layout Plain Layout +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +Entrada{Problema de reducción $(V,A, +\backslash +omega,s)$, heurística $h:V +\backslash +to +\backslash +mathbb{R}^{ +\backslash +geq0}$ y valor futilidad $F>0$, de modo que si el coste estimado de las + soluciones supera $M$ la búsqueda termina.} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Salida{Grafo solución o $ +\backslash +emptyset$.} +\end_layout + +\begin_layout Plain Layout + +$R +\backslash +gets +\backslash +{s +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +$C +\backslash +gets +\backslash +emptyset$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + +$w_s +\backslash +gets h(s)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lPara{$v +\backslash +in V$}{$b_s +\backslash +gets +\backslash +emptyset$} +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$s$ es primitiva}{$C +\backslash +gets +\backslash +{s +\backslash +}$} +\end_layout + +\begin_layout Plain Layout + + +\backslash +Mientras{$s +\backslash +notin C +\backslash +land c_s +\backslash +leq F$}{ +\end_layout + +\begin_layout Plain Layout + + Tomar $n +\backslash +in R$ con $b_n= +\backslash +emptyset$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $N +\backslash +gets +\backslash +{S +\backslash +in{ +\backslash +cal P}(V):(n,S) +\backslash +in A$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +uSSi{$N= +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + $w_n +\backslash +gets F$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\backslash +EnOtroCaso{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +Para{$u +\backslash +in +\backslash +bigcup N$}{ +\end_layout + +\begin_layout Plain Layout + + +\backslash +uSSi{$u$ es primitiva}{ +\end_layout + +\begin_layout Plain Layout + + $C +\backslash +gets C +\backslash +cup +\backslash +{u +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $w_u +\backslash +gets0$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\backslash +EnOtroCasoSi{$u +\backslash +notin R$}{ +\end_layout + +\begin_layout Plain Layout + + $w_u +\backslash +gets h(u)$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + $R +\backslash +gets R +\backslash +cup +\backslash +{u +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + + $P +\backslash +gets +\backslash +{u +\backslash +}$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +Mientras{$P +\backslash +neq +\backslash +emptyset$}{ +\end_layout + +\begin_layout Plain Layout + + Tomar $u +\backslash +in P$ y sacarlo de $P$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + Tomar el $S:(u,S) +\backslash +in A$ con mínimo $ +\backslash +omega(u,S)+ +\backslash +sum_{v +\backslash +in S}c_v$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $w_u +\backslash +gets +\backslash +omega(u,S)+ +\backslash +sum_{v +\backslash +in S}c_v$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + $b_u +\backslash +gets S$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + +\backslash +lSSi{$S +\backslash +subseteq C$}{$C +\backslash +gets C +\backslash +cup +\backslash +{Pu +\backslash +}$} +\end_layout + +\begin_layout Plain Layout + + Añadir a $P$ los antecesores $v$ con $u +\backslash +in b_v$ +\backslash +; +\end_layout + +\begin_layout Plain Layout + + } +\end_layout + +\begin_layout Plain Layout + +} +\end_layout + +\begin_layout Plain Layout + + +\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 +\backslash +; +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "alg:yo-star" + +\end_inset + +Método YO*. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\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 + 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. +\end_layout + +\begin_layout Section +Funciones heurísticas +\end_layout + +\begin_layout Standard +Si un problema tiene solución a profundidad +\begin_inset Formula $d$ +\end_inset + + y un método la encuentra tras generar +\begin_inset Formula $N$ +\end_inset + + nodos (no se cuenta 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$ +\end_inset + + nodos con altura máxima +\begin_inset Formula $d$ +\end_inset + +, 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 + +. + +\end_layout + +\begin_layout Standard +Una buena heurística debería producir valores de +\begin_inset Formula $b^{*}$ +\end_inset + + lo más bajos posible, teniendo en cuenta que siempre es +\begin_inset Formula $b^{*}\geq1$ +\end_inset + +. + Una forma de obtener +\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. +\end_layout + +\begin_layout Standard +Dadas dos heurísticas +\begin_inset Formula $h_{1},h_{2}:V\to\mathbb{R}^{\geq0}$ +\end_inset + +, +\begin_inset Formula $h_{1}$ +\end_inset + + +\series bold +domina +\series default + a +\begin_inset Formula $h_{2}$ +\end_inset + + si +\begin_inset Formula $h_{1}(v)\geq h_{2}(v)$ +\end_inset + + para todo +\begin_inset Formula $v\in V$ +\end_inset + +. + Entonces A* nunca expandirá más nodos con +\begin_inset Formula $h_{1}$ +\end_inset + + que con +\begin_inset Formula $h_{2}$ +\end_inset + +, por lo que será más rápido con +\begin_inset Formula $h_{1}$ +\end_inset + + si el tiempo de ejecución de +\begin_inset Formula $h_{1}$ +\end_inset + + es razonable. +\end_layout + +\begin_layout Standard +El +\series bold +problema 8-puzzle +\series default + tiene como estado una ordenación de 8 piezas numeradas en una cuadrícula + de +\begin_inset Formula $3\times3$ +\end_inset + +, 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 + del 1 al 8 en orden, con la casilla libre al principio o al final según + el modo de juego. +\end_layout + +\begin_layout Standard +Algunas heurísticas son el número de piezas mal colocadas y la suma de las + distancias Manhattan de cada pieza a su posición objetivo. + La segunda domina a la primera y ambas son monótonas y mucho mejores que + la búsqueda a ciegas. +\end_layout + +\begin_layout Standard +Dado un problema por espacio de estados +\begin_inset Formula $(V,A,\omega,s,F)$ +\end_inset + +, un +\series bold +problema relajado +\series default + es un problema +\begin_inset Formula $(V',A',\omega',s,F')$ +\end_inset + + con +\begin_inset Formula $V\subseteq V'$ +\end_inset + +, +\begin_inset Formula $A\subseteq A'$ +\end_inset + +, +\begin_inset Formula $F\subseteq F'$ +\end_inset + + y +\begin_inset Formula $\omega'|_{V}=\omega$ +\end_inset + +, con lo que el coste de una solución óptima en el problema relajado es + una heurística admisible para el problema original. + Las heurísticas anteriores se han obtenido así, la segunda permitiendo + que las piezas se puedan mover a cualquier casilla adyacente aunque esté + ocupada y la primera permitiendo además que las piezas se puedan mover + a cualquier casilla. + Escribir un problema en lenguaje formal permite construir problemas relajados + de forma automática eliminando restricciones. +\end_layout + +\begin_layout Standard +Dadas las heurísticas +\begin_inset Formula $h_{1},\dots,h_{m}$ +\end_inset + + para un mismo problema, +\begin_inset Formula $h(v):=\max_{i=1}^{m}h_{i}$ +\end_inset + + es una heurística que domina a todas las +\begin_inset Formula $h_{i}$ +\end_inset + +, es admisible si las +\begin_inset Formula $h_{i}$ +\end_inset + + lo son y es consistente si las +\begin_inset Formula $h_{i}$ +\end_inset + + lo son. +\end_layout + +\end_body +\end_document |