lunes, 22 de julio de 2019

Torres de Hanoi

Torres de Hanoi con Diferentes Algoritmos


Tablas de Solución:
Búsqueda por Anchura
L N Sucesores
A A B,C
B,C B D,E
C,D,E C F,G
D,E,F,G D H,I
E,F,G,H,I E J,K
F,G,H,I,J,K F L,M
Búsqueda por Profundidad
A A B,C
B,C B D,E
D,E,C D H,I
H,I,E,F,G H --------------
I,E,F,G I --------------
E,F,G E J,K
J,K,F,G J ------------
K,F,G K ------------
F,G F L,M
Profundidad Iterativa
Abiertos Actuales Hijos PROF
A A -- 1
A A B,C 2
B,C B -- 2
B,C B D,E 3
C,D,E C F,G 3
D,E,F,G D -- 3
D,E,F,G D H,I 4
E,F,G,H,I E J,K 4
F,G,H,I,J,K F L,M 4

SRB

Sistema Basado en Reglas 

Ejercicio

Sistema SBR


Encadenamiento hacia adelante:

Encadenamiento hacia atras

domingo, 21 de julio de 2019

Ejercicio A*


OBJETIVO

Iniciar en el punto S y llegar al punto  G por medio del algortimo A* es decir hallar la solución con el menor costo posible.

Grafo y Heurística correspondiente:
 Arbol Generado por A*


Algoritmo de Solución

Representación del Conocimiento


Taller Representación Conocimiento

1.    En que consiste la representación del conocimiento:

Resultado de imagen para representacion del conocimiento

Es un área de la inteligencia artificial cuyo objetivo fundamental es representar el conocimiento de una manera que facilite sacar conclusiones a partir de dicho conocimiento. Analiza cómo pensar formalmente cómo usar un sistema de símbolos para representar un dominio de lo que se puede hablar, junto con funciones que permitan realizar un razonamiento formal sobre los objetos. Generalmente, se usa algún tipo de lógica para proveer una semántica formal de cómo las funciones de razonamiento se aplican a los símbolos del dominio del discurso, además de proveer operadores como cuantificadores, operadores modales, etc. Esto, junto a una teoría de interpretación, dan significado a las frases en la lógica.

Para complementar la definición de en que consiste, se puede tomar como el substituto de lo que existe en el mundo real o imaginario, un conjunto de cometidos ontológicos, es decir saber cómo pensar acerca del mundo.
·          Una representación del conocimiento es fundamentalmente un sucedáneo, un sustituto para el objeto en sí, usado para activar una entidad a efectos de determinar las consecuencias, pensando en lugar de actuando, o sea, razonando acerca del mundo en lugar de tomando acción en él.

·         Es un grupo de compromisos ontológicos, una respuesta a la pregunta sobre los términos en que se debe pensar acerca del mundo.
·         Es una teoría fragmentaria del razonamiento inteligente, expresado en términos de tres componentes: 

(i) El concepto fundamental de la representación del razonamiento inteligente; 
(ii) El conjunto de inferencias que la representación sanciona;
(iii) El conjunto de inferencias que recomienda.

Es un medio para una computación pragmáticamente eficiente, el entorno computacional 
en que el pensamiento tiene lugar. Una contribución para esta eficiencia pragmática viene
dada por la guía que una representación provee para organizar información, de modo que 
facilite hacer las inferencias recomendadas.
Es un modo de expresión humana, un lenguaje en el que se dicen cosas sobre el mundo.

Muchas de las actividades humanas consideradas “inteligentes” se basan en la explotación de gran cantidad de información, hechos, experiencias y conocimientos más o menos específicos de un ámbito particular. En consecuencia, una parte importante de las labores de investigación y desarrollo (I&D), en el campo de la IA consiste en la concepción de formalismos que permiten el desarrollo de sistemas basados en conocimiento (SBC) y, específicamente, el estudio de las distintas maneras de definir y crear sus bases (Santos, 1998). El proceso de conversión de los conocimientos acerca de un tema en un formato particular es denominado “representación de conocimientos”. Una vez el conocimiento ha sido representado adecuadamente puede utilizarse en un sistema inteligente que con el empleo de herramientas de análisis, tratamiento y manipulación automática tiene la capacidad de inducir o deducir nuevos conocimientos.

2.    Para que sirve:
Tiene la intención de definir mecanismos para representar el conocimiento por medio de símbolos y facilitar de este modo su tratamiento. Estos mecanismos son los encargados de nutrir sistemas inteligentes dirigidos a resolver tareas complejas que requieren razonar sobre un determinado dominio de aplicación. Muchas veces, la eficacia de los sistemas inteligentes depende de una buena representación de los datos, de la información o del conocimiento del dominio en el cual actúen. Por lo tanto, estamos ante un área clave en el campo de la ingeniería informática.

Para entender mejor porque estas características representan una buena representación del conocimiento, piensa en como una enciclopedia (por ejemplo, Wikipedia) está estructurada. Hay millones de artículos (cobertura), que están organizados en categorías, tipos de contenido, y temas similares (comprensible por humanos). Redirección diferentes títulos, pero mismo contenido al mismo artículo (consistencia). Es eficiente, es fácil añadir o actualizar páginas, y permite a los usuarios consultar la base de conocimiento en sus teléfonos u ordenadores de escritorio.

3.    Formas de representación:

Resultado de imagen para como hacer representacion del conocimiento

Perceptrón

Perceptron

El modelo biológico más simple de un perceptrón es una neurona y viceversa. Es decir, el modelo matemático más simple de una neurona es un perceptrón. La neurona es una célula especializada y caracterizada por poseer una cantidad indefinida de canales de entrada llamados dendritas y un canal de salida llamado axón. Las dendritas operan como sensores que recogen información de la región donde se hallan y la derivan hacia el cuerpo de la neurona que reacciona mediante una sinapsis que envía una respuesta hacia el cerebro, esto en el caso de los seres vivos.

Una neurona sola y aislada carece de razón de ser. Su labor especializada se torna valiosa en la medida en que se asocia a otras neuronas, formando una red. Normalmente, el axón de una neurona entrega su información como "señal de entrada" a una dendrita de otra neurona y así sucesivamente. 

El perceptrón usa una matriz para representar las redes neuronales y es un discriminador terciario que traza su entrada x (un vector binario) a un único valor de salida f(x) (un solo valor binario) a través de dicha matriz.



Donde w es un vector de pesos reales y W*X es el producto escalar (que computa una suma ponderada).  U es el 'umbral', el cual representa el grado de inhibición de la neurona, es un término constante que no depende del valor que tome la entrada.


El valor de  f(x)= (0,1) se usa para clasificar x como un caso positivo o un caso negativo, en el caso de un problema de clasificación binario. El umbral puede entenderse como una manera de compensar la función de activación, o una forma de fijar un nivel mínimo de actividad a la neurona para considerarse como activa. La suma ponderada de las entradas debe producir un valor mayor que U para cambiar la neurona de estado 0 a 1.

El perceptrón puede utilizarse con otros tipos de perceptrones o de neurona artificial, para formar una red neuronal artificial más compleja.

EJERCICIO PERCEPTRÓN
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <unistd.h>

using namespace std;

class Perceptron{
public:
Perceptron();
void Calcular(void);
~Perceptron();
};

Perceptron::Perceptron()
{
printf("Iniciando Perceptron\n");
}

Perceptron::~Perceptron()
{
 printf("\n\nPerceptron Finalizado\n");
}

void Perceptron::Calcular(void)
{
srand(time(NULL));
float rangos[] = {-0.98,-0.87,-0.65,-0.75,0.45,0.95,-0.32,-0.28,-0.11,-0.06,0.023,0.23,0.23,0.46,0.67,0.78, 0.75,0.82,0.98};
float aprendizaje[] = {0.023,0.23,0.233,0.467,0.675,0.788, 0.752,0.823,0.987};
float Umbral,defumbral,factor;
int i;

 int x1[] = {-1,1,-1,1,-1,1};
 int x2[] = {1,-1,-1,1,1,-1};
 int x3[] = {1,1,-1,-1,-1,1};
 int x4[] = {1,1,1,-1,1,1};
 int x5[] = {1,1,1,1,1,1};
 int x6[] = {1,1,1,1,1,1};

 int result[] = {1,1,-1,-1,-1,1};
 float w[6] = {rangos[rand() % 18],rangos[rand() % 18],rangos[rand() % 18],rangos[rand() % 18],rangos[rand() % 18],rangos[rand() % 18]};

 factor = rangos[rand() % 18];
 Umbral = rangos[rand() % 18];
 defumbral = 1;

 int verdad = 0;
 int op;
 int cont = 0;
 int n = 0;

// Entrenamiento
 while(verdad == 0){
  n++;
  for(i=0;i<6;i++){
   op = ((x1[i]*w[0])+(x2[i]*w[1])+(x3[i]*w[2])+(x4[i]*w[3])+(x5[i]*w[4])+(x6[i]*w[5])) + (defumbral*Umbral);
   if(op >= 0){
    op = 1;
   }
   else{
    op = -1;
   }
   if(op != result[i]){
    w[0] = w[0] + (6*factor)*(x1[i]*result[i]);
    w[1] = w[1] + (6*factor)*(x2[i]*result[i]);
    w[2] = w[2] + (6*factor)*(x3[i]*result[i]);
    w[3] = w[3] + (6*factor)*(x4[i]*result[i]);
    w[4] = w[4] + (6*factor)*(x5[i]*result[i]);
    w[5] = w[5] + (6*factor)*(x6[i]*result[i]);
    
    Umbral = Umbral + (6*factor)*(defumbral*result[i]);
   }
  }
  for(i=0;i<6;i++){
   op = ((x1[i]*w[0])+(x2[i]*w[1])+(x3[i]*w[2])+(x4[i]*w[3])+(x5[i]*w[4])+(x6[i]*w[5])) + (defumbral*Umbral);
   if(op == result[i]){
    cont++;
   }
   if(cont == 6){
    verdad = 1;
   }
  }
  if(n > 900000000){
   printf("Demasiadas epocas realizadas\n");
   printf("Es necesario intentar nuevamente con otros pesos.\n");
   exit(1);
  }
 }


//RESULTADO

 printf("\nFINALIZANDO ENTRENAMIENTO...\n");
 printf("\n--------------- DATOS RESULTANTES --------------------------------\n\n");
 printf("# Total de epocas: (%i)\n",n);
 printf("Valor Peso 1 w[1]\t\t--> %2.2f\n",w[0]);
 printf("Valor Peso 2 w[2]\t\t--> %2.2f\n",w[1]);
 printf("Valor Peso 3 w[3]\t\t--> %2.2f\n",w[2]);
 printf("Valor Peso 4 w[4]\t\t--> %2.2f\n",w[3]);
 printf("Valor Peso 5 w[5]\t\t--> %2.2f\n",w[4]);
 printf("Valor Peso 6 w[6]\t\t--> %2.2f\n",w[5]);
 printf("Valor Umbral(Polarizacion)\t\t--> %2.2f\n",Umbral);

 for(i=0;i<6;i++){
  op = ((x1[i]*w[0])+(x2[i]*w[1])+(x3[i]*w[2])+(x4[i]*w[3])+(x5[i]*w[4])+(x6[i]*w[5])) + (defumbral*Umbral);
  if(op >= 0){
   op = 1;
  }
  else{
   op = -1;
   }
printf("\nEntradas: (%2i,%2i,%2i,%2i,%2i,%2i) --> Salida: %2i",x1[i],x2[i],x3[i],x4[i],x5[i],x6[i],op);
  if(op != result[i]){
   printf("\nDemasiadas epocas realizadas\n");
   printf("Es necesario intentar nuevamente con otros pesos.\n");
   exit(1);
   Calcular();
   }
 }
}

int main()
{
Perceptron x;
x.Calcular();
return 0;
}



Minimax


ALGORITMO MINIMAX

Este algoritmo de decisión se utiliza para minimizar la pérdida máxima aplicada en juegos entre adversarios. La Información es completa ya que cada jugador conoce el estado del otro, y puede elegir el mejor movimiento para cada jugador, suponiendo que el contrincante escogerá el peor. Devuelve la acción correspondiente al movimiento mejor posible, es decir, el movimiento que conduce al resultado con la mejor utilidad, conforme al axioma que el oponente juega para minimizar la utilidad. Las funciones Valor-Max y el Valor-Min pasan por el árbol de juegos enteró, por todos los caminos hacia las hojas, para determinar el valor que le llega a un estado.

El algoritmo MINIMAX es un procedimiento recursivo y el corte de la recursión está dado por alguna de las siguientes condiciones: Gana algún jugador Se han explorado N capas, siendo N el límite establecido Se ha agotado el tiempo de exploración Se ha llegado a una situación estática donde no hay grandes cambios de un nivel a otro.
De forma más detallada, la idea consiste en comenzar en la posición actual del juego y usar el generador de movimientos legales para generar las posibles posiciones sucesivas hasta un cierto límite de niveles (si es posible porque el juego lo permita, se desarrolla el árbol completo de juego hasta las posiciones finales). A continuación, se aplica una función de evaluación estática, que es capaz de decir lo bueno o malo que es cada estado, a los últimos estados obtenidos y se elige la mejor posición para el jugador correspondiente, llevando los valores un nivel hacia atrás para continuar la evaluación en todos los niveles anteriores.

Habitualmente, se suele trabajar con una función de evaluación que devuelve valores positivos para indicar buenas situaciones para el jugador que hace uso del algoritmo, y valores negativos para indicar buenas situaciones para el adversario. Así planteado, el objetivo es maximizar el valor de esta función estática sobre las posibles jugadas que se pueden hacer desde la posición actual del juego.
De este mecanismo es de donde viene el nombre del algoritmo: dada la función evaluadora estática, el jugador que hace uso del algoritmo intenta maximizar su valor, mientras que el adversario intenta minimizarlo. En un árbol de juego donde los valores de la función evaluadora se calculan en relación al jugador maximizante, se maximiza y minimiza alternadamente de un nivel a otro hasta llegar al nivel actual de juego.

Formalmente, los pasos del algoritmo Minimax son:

  1. Generación del árbol de juego: Se generan todos los nodos hasta llegar a un estado terminal (si no podemos afrontar la generación del árbol completo, es posible aplicar los pasos siguientes sobre una sección del mismo, aunque entonces no podremos asegurar la optimalidad de los resultados).
  2. Se calculan los valores de la función de evaluación para cada nodo terminal del árbol construido.
  3. Se evalúan los nodos superiores a partir del valor de los inferiores. Según si estos nodos pertenecen a un nivel MAX o un nivel MIN, se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente.
  4. Se repite el paso 3 hasta llegar al nodo superior.
  5. Se selecciona la jugada-nodo directamente accesible desde la jugada actual que optimiza el valor de la evaluación.
PODA ALFA-BETA
La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.
El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

EJEMPLO




EJERCICIO 
Algoritmo MiniMax
posición inicial 



PASOS DEL ALGORITMO MINIMAX
1. Generar el árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.
2. Calcular los valores de la función de utilidad para cada nodo terminal.
3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de MINIMAX.
4. Elegir la jugada valorando los valores que han llegado al nivel superior.
Posición final 
EJERCICIO MINIMAX

#include<bits/stdc++.h> 
#include <iostream>

using namespace std; 
   
  class Minimax{                                    //Clase Minimax
  private:
    const int MAX = 1000;               //Valores para alfa y beta
    const int MIN = -1000;    
public:
Minimax();
int proceso(int, int, int, bool, int[], int, int);
~Minimax();
  };
   
Minimax::Minimax()
{
cout<<"Construyendo Arbol"<<endl;
}  

Minimax::~Minimax()
{
cout<<"Destruyendo Arbol"<<endl;
}

int Minimax::proceso(int niveles, int depth, int nodeIndex, bool maximizingPlayer, int values[], int alpha,  int beta) 
  { 
      
    if (depth == niveles) 
        return values[nodeIndex]; 
  
    if (maximizingPlayer)         //Función que realiza el proceso del MINIMAX
    { 
        int best = MIN; 
  
        for (int i = 0; i < 2; i++) 
        { 
              
            int val = proceso(niveles, depth + 1, nodeIndex * 2 + i, false, values, alpha, beta); 
            best = max(best, val); 
            alpha = max(alpha, best); 
  
            
            if (beta <= alpha) 
                break; 
        } 
        return best; 
    } 
    else
    { 
        int best = MAX; 
  
        for (int i = 0; i < 2; i++) 
        { 
            int val = proceso(niveles, depth + 1, nodeIndex * 2 + i, true, values, alpha, beta); 
            best = min(best, val); 
            beta = min(beta, best); 
   
            if (beta <= alpha) 
                break; 
        } 
        return best; 
    } 
   
int main() 
Minimax x;     //Objeto Minimax
int cant;
int MIN, MAX;
int par ;
do{
cout<<"Ingrese el numero de nodos del nivel final del arbol: ";
cin>>cant;
par = cant % 2;
if(par != 0){
cout<<"El numero de nodos debe ser par"<<endl;
}
}while(par != 0);
    int prof= log2(cant);
int values[cant]; 
for(int i=0; i<cant; i++){
cout<<"Ingrese un valor para el "<<i+1<<" nodo: ";
cin>>values[i];
}
    cout<<endl<<"El valor optimo para este arbol es: "<< x.proceso(prof, 0, 0, true, values, MIN, MAX);
cout<<endl; 
    return 0;