Reducción del problema
La resolución del problema, constituye otro enfoque para resolver el problema. La principal idea de este enfoque es razonar hacia atrás desde el problema a solucionar, estableciendo sucesivamente varios subproblemas triviales cuya solución es obvia.
Un operador reductor de problemas transforma la descripción de un problema en un conjunto de descripciones de problemas reducidos (sucesor). Para un problema dado hay muchos operadores de reducción que son suceptibles de aplicar. Cada uno produce un conjunto alternativo de subproblemas; puede que alguno de los subproblemas no sea solucionable, sin embargo por ello se debe intentar varios operadores para que se produzca un conjunto cuyos componentes sean todos solucionables. Por lo tanto esto requiere de un nuevo proceso de búsqueda. La reducción del problema a un conjunto de problemas sucesivos se puede expresar de forma conveniente con una estructura tipo grafo.
Supóngase que el problema » A » se puede resolver con la resolución de tres subproblemas » B «, » C » y » D «; un arco AND quedará marcado sobre todos los arcos de entrada de los nodos » B «, » C «, y » D «. Los nodos » B «, » C «, y » D » se denominan nodos AND. Por otra parte si el problema » B » se puede resolver con la resolución de cualquiera de los subproblemas » E » y » F » se emplea un arco OR.
En este tipo de resolución se usaron los métodos de búsqueda de primero en anchura y primero en profundidad que son para grafos de tipo OR, con los que quisieron encontrar un camino simple desde el nodo de salida hasta el nodo objetivo.
