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
Podemos tratar la representación como un 
\series bold
grafo Y-O
\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 
\series bold
árbol Y-O
\series default
.
 
\end_layout

\begin_layout Standard
Un nodo es 
\series bold
resoluble
\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.
\end_layout

\end_deeper
\begin_layout Standard
El método a elegir depende de características 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
, esto es, 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; si es necesario tener mucho o 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
forward
\emph default
 o 
\emph on
bottom-up
\emph default
 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
backward
\emph default
 o 
\emph on
top-down
\emph default
 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.
\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.
 A veces 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 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
backtracking
\emph default
 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.
\end_layout

\end_body
\end_document