#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, 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\mid (v,w)\in A\}$
\end_inset

 es finito y recursivamente enumerable a partir de 
\begin_inset Formula $v$
\end_inset

; 
\begin_inset Formula $s\in V$
\end_inset

 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

 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

 para 
\begin_inset Formula $d>1$
\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 
\begin_inset Formula $\forall v\in V,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(RS)=c,
\]

\end_inset

 por lo que siempre se procesa antes una solución óptima que una no óptima.
 Sea ahora 
\begin_inset Formula $p\coloneqq \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\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 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

 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}\coloneqq v_{0}\cdots v_{i}$
\end_inset

, para 
\begin_inset Formula $i<j$
\end_inset

 es 
\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

.
\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 tiempo 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 fallo.}
\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_{
\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_u
\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
;
\end_layout

\begin_layout Plain Layout

		$r
\backslash
gets
\backslash
text{
\backslash
RBFS{
\backslash
ensuremath{Pb,
\backslash
min(
\backslash
{f_v
\backslash
}_{v
\backslash
in N
\backslash
setminus
\backslash
{b
\backslash
}}
\backslash
cup
\backslash
{f_{
\backslash
text{limit}}
\backslash
})}}}$
\backslash
;
\end_layout

\begin_layout Plain Layout

		
\backslash
lSSi{$
\backslash
text{
\backslash
rm fallo}(t)
\backslash
coloneqq r$}{$f_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

$f_s
\backslash
gets h(s)$
\backslash
;
\end_layout

\begin_layout Plain Layout


\backslash
RBFS{$(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 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

\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 Y/O acíclico con 
\begin_inset Formula $V$
\end_inset

 contable y tanto 
\begin_inset Formula $\{S\subseteq V\mid (u,S)\in V\}$
\end_inset

 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 
\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\coloneqq (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')\coloneqq (\{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')\coloneqq \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 clasificar el nodo inicial.
\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)$ con $s$ no primitivo.}
\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
tcp*{Caminos frontera}
\end_layout

\begin_layout Plain Layout

$I
\backslash
gets
\backslash
emptyset$
\backslash
tcp*{Nodos irresolubles}
\end_layout

\begin_layout Plain Layout

$R
\backslash
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
\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
}$
\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$
\backslash
;
\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
SSi{$
\backslash
exists v
\backslash
in N:(v,
\backslash
emptyset)
\backslash
in A$}{
\end_layout

\begin_layout Plain Layout

		
\backslash
lPara{$v
\backslash
in N:(v,
\backslash
emptyset)
\backslash
in A$}{añadir $(v,
\backslash
emptyset)$ a $R$}
\end_layout

\begin_layout Plain Layout

		$i
\backslash
gets n$
\backslash
;
\end_layout

\begin_layout Plain Layout

		
\backslash
Mientras{$
\backslash
exists(u_i,S)
\backslash
in A:S
\backslash
subseteq
\backslash
text{
\backslash
rm Dom}R$}{
\end_layout

\begin_layout Plain Layout

			Añadir $(u_i,S)$ a $R$
\backslash
;
\end_layout

\begin_layout Plain Layout

			
\backslash
lSSi{$i=0$}{
\backslash
Devolver
\backslash
Resolucion{$R,s$}}
\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 $
\backslash
text{Dom}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.
 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


\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 primero en profundidad pero con 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 nodo.
 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


\backslash
SetKwFunction{Resolucion}{{}resolución}
\end_layout

\begin_layout Plain Layout

$G
\backslash
gets
\backslash
{s
\backslash
}$
\backslash
tcp*{Generados}
\end_layout

\begin_layout Plain Layout

$C
\backslash
gets
\backslash
emptyset$
\backslash
tcp*{Completados}
\end_layout

\begin_layout Plain Layout

$w_s
\backslash
gets h(s)$
\backslash
tcp*{Coste estimado}
\end_layout

\begin_layout Plain Layout


\backslash
SSi{$(s,
\backslash
emptyset)
\backslash
in A$}{
\end_layout

\begin_layout Plain Layout

	$b_s
\backslash
gets
\backslash
emptyset$
\backslash
tcp*{Conector siguiente}
\end_layout

\begin_layout Plain Layout

	$C
\backslash
gets
\backslash
{s
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

}
\end_layout

\begin_layout Plain Layout


\backslash
Mientras{$s
\backslash
notin C
\backslash
land w_s
\backslash
leq F$}{
\end_layout

\begin_layout Plain Layout

	Tomar $n
\backslash
in G
\backslash
setminus
\backslash
text{Dom}b$
\backslash
tcp*{{
\backslash
rm Esta es la frontera.}}
\end_layout

\begin_layout Plain Layout

	$N
\backslash
gets
\backslash
{S
\backslash
in{
\backslash
cal P}(V):(n,S)
\backslash
in A
\backslash
}$
\backslash
;
\end_layout

\begin_layout Plain Layout

	
\backslash
uSSi{$N=
\backslash
emptyset$}{
\end_layout

\begin_layout Plain Layout

		$w_n
\backslash
gets 0$
\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

				$b_u
\backslash
gets
\backslash
emptyset$
\backslash
;
\end_layout

\begin_layout Plain Layout

				Añadir $u$ a $C$
\backslash
;
\end_layout

\begin_layout Plain Layout

				$w_u
\backslash
gets0$
\backslash
;
\end_layout

\begin_layout Plain Layout

			} 
\backslash
EnOtroCasoSi{$u
\backslash
notin G$}{
\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

			Añadir $u$ a $G$
\backslash
;
\end_layout

\begin_layout Plain Layout

		}
\end_layout

\begin_layout Plain Layout

	}
\end_layout

\begin_layout Plain Layout

	$M
\backslash
gets
\backslash
{n
\backslash
}$
\backslash
tcp*{Modificados}
\end_layout

\begin_layout Plain Layout

	
\backslash
Mientras{$M
\backslash
neq
\backslash
emptyset$}{
\end_layout

\begin_layout Plain Layout

		Tomar $u
\backslash
in M$ sin sucesores en $M$ y sacarlo de $M$
\backslash
;
\end_layout

\begin_layout Plain Layout

		$c
\backslash
gets(w_u,[u
\backslash
in C])$
\backslash
tcp*{{
\backslash
rm $[P]$ devuelve un booleano que indica si $P$ es cierto.}}
\end_layout

\begin_layout Plain Layout

		Tomar el $S$ con $(u,S)
\backslash
in A$ de menor $
\backslash
omega(u,S)+
\backslash
sum_{v
\backslash
in S}w_v$
\backslash
;
\end_layout

\begin_layout Plain Layout

		$w_u
\backslash
gets
\backslash
omega(u,S)+
\backslash
sum_{v
\backslash
in S}w_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$}{añadir $u$ a $C$}
\end_layout

\begin_layout Plain Layout

		
\backslash
lSSi{$c
\backslash
neq(w_u,[u
\backslash
in C])$}{%
\end_layout

\begin_layout Plain Layout

			añadir a $M$ los $v
\backslash
in
\backslash
text{Dom}b$ con $u
\backslash
in b_v$%
\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
Resolucion{$b,s$}
\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 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, 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
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 (sin contar el nodo inicial), el 
\series bold
factor de ramificación eficaz
\series default
 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

, un árbol de altura 
\begin_inset Formula $d$
\end_inset

 con 
\begin_inset Formula $b^{*}$
\end_inset

 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
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

.
 Podemos estimar un 
\begin_inset Formula $b^{*}$
\end_inset

 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
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
 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

\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'|_{A}=\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)\coloneqq \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