path: root/si/n2.lyx

#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
\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
No tenemos un método general determinista para resolver problemas, pero
 sí sistemas o métodos de resolución aplicables a muchos problemas para
 abordar problemas nuevos de forma sistemática.
 
\end_layout

\begin_layout Standard
Los métodos de búsqueda tienen una representación del dominio del problema,
 la situación inicial y el objetivo; operadores para transformar la situación
 del problema o dividirla en subproblemas de solución más sencilla, y una
 estrategia de control para seleccionar el operador a aplicar en cada paso.
 Una 
\series bold
trayectoria
\series default
 es una secuencia de operadores a aplicar en orden desde una situación,
 y una 
\series bold
solución
\series default
 del problema es una trayectoria desde una situación inicial a una final.
\end_layout

\begin_layout Standard
La representación puede ser:
\end_layout

\begin_layout Itemize
Un 
\series bold
espacio de estados
\series default
, un conjunto de situaciones posibles en el que distinguimos un subconjunto
 de estados iniciales y uno de estados finales.
\end_layout

\begin_deeper
\begin_layout Standard
Se puede tratar como un grafo (o multigrafo) dirigido donde los nodos son
 los estados y los arcos son posibles aplicaciones de un operador, la etiqueta
 del arco, para ir de un estado a otro.
 También se puede tratar como un árbol con raíz en cierto nodo en que los
 hijos de un nodo son los estados a los que se puede llegar desde este,
 o desde los que se puede llegar a este, aplicando un operador.
 En este caso puede haber varios nodos que se refieran al mismo estado,
 y sus subárboles correspondientes serían esencialmente iguales.
\end_layout

\begin_layout Standard
Buscar en un grafo en vez de en un árbol reduce el esfuerzo de buscar en
 el mismo subárbol varias veces, pero requiere comprobar para cada nodo
 si ha aparecido anteriormente.
\end_layout

\end_deeper
\begin_layout Itemize
Por 
\series bold
reducción
\series default
, descomposición del problema en subproblemas que a su vez se resuelven,
 hasta llegar a problemas de solución inmediata.
 La situación inicial es la formulación del problema, y cada problema puede
 ser:
\end_layout

\begin_deeper
\begin_layout Itemize

\series bold
Primitivo
\series default
 o 
\series bold
terminal
\series default
, de resolución inmediata.
\end_layout

\begin_layout Itemize

\series bold
Y
\series default
, con un solo operador que lo divide en un conjunto de 
\series bold
subproblemas secundarios
\series default
 de los que hay que resolver todos para resolver el problema.
\end_layout

\begin_layout Itemize

\series bold
O
\series default
, con varios operadores que lo llevan cada uno a un 
\series bold
subproblema alternativo
\series default
, y resolviendo uno se resuelve un problema.
\end_layout

\begin_layout Standard
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
hiperarcos
\series default
 o 
\series bold
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, siendo
 el caso base el antecesor de un hiperarco sin sucesores.
\end_layout

\begin_layout Standard
Un 
\series bold
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

, sea 
\begin_inset Formula $N\coloneqq \{S\subseteq V\mid (u,S)\in A\}$
\end_inset

, 
\begin_inset Formula $\bigcup N$
\end_inset

 es finito y, bien 
\begin_inset Formula $N$
\end_inset

 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 al menos dos hiperarcos es un nodo 
\series bold
O
\series default
, y si 
\begin_inset Formula $\bigcup N=\emptyset$
\end_inset

, es un 
\series bold
terminal
\series default
, en cuyo caso es una 
\series bold
primitiva
\series default
 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, es de tipo O con algún sucesor resoluble o tiene
 un único sucesor y este es 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\mid \exists(u,S)\in A\mid v\in S\})$
\end_inset

 es acíclico.
\end_layout

\end_deeper
\begin_layout Standard
El método a elegir depende de características del problema como:
\end_layout

\begin_layout Itemize
Si es 
\series bold
descomponible
\series default
 en subproblemas.
\end_layout

\begin_layout Itemize
Si es 
\series bold
recuperable
\series default
 (se pueden deshacer las operaciones una vez ejecutadas) o es 
\series bold
irrecuperable
\series default
.
\end_layout

\begin_layout Itemize
Si es obvio si una cierta solución es suficientemente buena para ser aceptada
 o hay que compararla con el resto de soluciones para elegir la mejor.
\end_layout

\begin_layout Itemize
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
Una búsqueda es 
\series bold
hacia delante
\series default
, 
\series bold
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
hacia atrás
\series default
, 
\series bold
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 hay estrategias de búsqueda bidireccionales.
\end_layout

\begin_layout Standard
El 
\series bold
emparejamiento
\series default
 consiste en determinar los operadores aplicables a una cierta situación,
 comprobando sus precondiciones.
 Esto puede acarrear otra búsqueda si las precondiciones contienen variables.
\end_layout

\begin_layout Standard
Una 
\series bold
heurística
\series default
 es una estrategia para hacer más sencilla la resolución de problemas.
 El 
\series bold
conocimiento heurístico
\series default
 es el usado por humanos para resolver problemas complejos.
 Una 
\series bold
técnica heurística
\series default
 es una serie de pasos para identificar una buena solución con pocos recursos,
 aunque no podamos garantizar encontrar la solución.
 Un caso es una 
\series bold
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 que se usa para decidir el operador a tomar.
\end_layout

\begin_layout Standard
En general no podemos obtener una solución satisfactoria a la primera y
 tenemos que usar 
\series bold
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.
 Esto suele ser lento, pero es un método universal y se puede combinar con
 técnicas heurísticas.
\end_layout

\end_body
\end_document