#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