45. Aplicaciones en inteligencia artificial

// Búsqueda A* para navegación en malla 2D
class NodoA {
  constructor(x, y, padre = null, g = 0, h = 0) {
    this.x = x;
    this.y = y;
    this.padre = padre;
    this.g = g; // Costo desde inicio
    this.h = h; // Heurística a meta
  }

  f() {
    return this.g + this.h;
  }

  clave() {
    return `${this.x},${this.y}`;
  }
}

class BuscadorA {
  constructor(malla, meta) {
    this.malla = malla; // malla[y][x] = 0 libre, 1 obstáculo
    this.meta = meta;
  }

  heuristica(x, y) {
    // Distancia Manhattan a meta
    return Math.abs(x - this.meta[0]) + Math.abs(y - this.meta[1]);
  }

  vecinos(x, y) {
    const resultado = [];
    // 8 direcciones (incluidas diagonales)
    const direcciones = [
      [0, -1], [0, 1], [-1, 0], [1, 0],
      [-1, -1], [-1, 1], [1, -1], [1, 1]
    ];

    for (const [dx, dy] of direcciones) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < this.malla[0].length &&
          ny >= 0 && ny < this.malla.length &&
          this.malla[ny][nx] === 0) {
        resultado.push([nx, ny]);
      }
    }
    return resultado;
  }

  buscarA(inicio) {
    const abierto = [new NodoA(inicio[0], inicio[1], null, 0, 
                               this.heuristica(inicio[0], inicio[1]))];
    const cerrado = new Set();
    const visitados = new Map();

    while (abierto.length > 0) {
      // Encontrar nodo con menor f(n)
      let minIdx = 0;
      for (let i = 1; i < abierto.length; i++) {
        if (abierto[i].f() < abierto[minIdx].f()) {
          minIdx = i;
        }
      }

      const actual = abierto.splice(minIdx, 1)[0];

      if (actual.x === this.meta[0] && actual.y === this.meta[1]) {
        // Reconstruir camino
        const camino = [];
        let nodo = actual;
        while (nodo) {
          camino.unshift([nodo.x, nodo.y]);
          nodo = nodo.padre;
        }
        return camino;
      }

      cerrado.add(actual.clave());

      for (const [nx, ny] of this.vecinos(actual.x, actual.y)) {
        const clave = `${nx},${ny}`;
        if (cerrado.has(clave)) continue;

        const g = actual.g + 1;
        const h = this.heuristica(nx, ny);
        const nuevoNodo = new NodoA(nx, ny, actual, g, h);

        // ¿Ya fue visitado con mejor g?
        if (visitados.has(clave) && visitados.get(clave) <= g) {
          continue;
        }

        visitados.set(clave, g);
        abierto.push(nuevoNodo);
      }
    }

    return null; // No hay camino
  }
}

// Uso
const malla = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 1, 0],
  [0, 0, 0, 0, 0]
];

const buscador = new BuscadorA(malla, [4, 4]);
const camino = buscador.buscarA([0, 0]);
console.log("Camino A*:", camino);

// Árbol de decisión simple (clasificación binaria)
class NodoDecision {
  constructor(atributo = null, valor = null) {
    this.atributo = atributo;
    this.valor = valor;
    this.izquierda = null;
    this.derecha = null;
    this.clasificacion = null;
  }

  esHoja() {
    return this.clasificacion !== null;
  }
}

class ArbolDecision {
  constructor() {
    this.raiz = null;
  }

  // Calcular entropía (información de un conjunto)
  entropía(ejemplos) {
    const conteos = {};
    for (const ej of ejemplos) {
      const clase = ej.clase;
      conteos[clase] = (conteos[clase] || 0) + 1;
    }

    let entropia = 0;
    const total = ejemplos.length;
    for (const count of Object.values(conteos)) {
      const p = count / total;
      if (p > 0) entropia -= p * Math.log2(p);
    }
    return entropia;
  }

  // Ganancia de información al dividir por atributo
  gananciaInformacion(ejemplos, atributo, valor) {
    const izq = ejemplos.filter(e => e[atributo] < valor);
    const der = ejemplos.filter(e => e[atributo] >= valor);

    if (izq.length === 0 || der.length === 0) return 0;

    const total = ejemplos.length;
    const entropia_original = this.entropía(ejemplos);
    const entropia_nueva = 
      (izq.length / total) * this.entropía(izq) +
      (der.length / total) * this.entropía(der);

    return entropia_original - entropia_nueva;
  }

  // Entrenar árbol (ID3 simplificado)
  entrenar(ejemplos, atributos, nodo = null) {
    if (!nodo) nodo = new NodoDecision();

    // Caso base: todos los ejemplos tienen la misma clase
    const clases = new Set(ejemplos.map(e => e.clase));
    if (clases.size === 1) {
      nodo.clasificacion = ejemplos[0].clase;
      return nodo;
    }

    // Caso base: sin atributos
    if (atributos.length === 0) {
      const conteos = {};
      for (const ej of ejemplos) {
        conteos[ej.clase] = (conteos[ej.clase] || 0) + 1;
      }
      const masFrequente = Object.entries(conteos)
        .reduce((a, b) => a[1] > b[1] ? a : b)[0];
      nodo.clasificacion = masFrequente;
      return nodo;
    }

    // Seleccionar mejor atributo
    let mejorAtributo = null;
    let mejorGanancia = -1;
    let mejorValor = null;

    for (const atributo of atributos) {
      const valores = [...new Set(ejemplos.map(e => e[atributo]))];
      for (const valor of valores) {
        const ganancia = this.gananciaInformacion(ejemplos, atributo, valor);
        if (ganancia > mejorGanancia) {
          mejorGanancia = ganancia;
          mejorAtributo = atributo;
          mejorValor = valor;
        }
      }
    }

    if (mejorGanancia === 0) {
      const conteos = {};
      for (const ej of ejemplos) {
        conteos[ej.clase] = (conteos[ej.clase] || 0) + 1;
      }
      const masFrequente = Object.entries(conteos)
        .reduce((a, b) => a[1] > b[1] ? a : b)[0];
      nodo.clasificacion = masFrequente;
      return nodo;
    }

    nodo.atributo = mejorAtributo;
    nodo.valor = mejorValor;

    const ejemplosIzq = ejemplos.filter(e => e[mejorAtributo] < mejorValor);
    const ejemplosDer = ejemplos.filter(e => e[mejorAtributo] >= mejorValor);

    nodo.izquierda = this.entrenar(ejemplosIzq, atributos, new NodoDecision());
    nodo.derecha = this.entrenar(ejemplosDer, atributos, new NodoDecision());

    return nodo;
  }

  // Clasificar ejemplo
  clasificar(ejemplo, nodo = null) {
    if (!nodo) nodo = this.raiz;
    
    if (nodo.esHoja()) {
      return nodo.clasificacion;
    }

    if (ejemplo[nodo.atributo] < nodo.valor) {
      return this.clasificar(ejemplo, nodo.izquierda);
    } else {
      return this.clasificar(ejemplo, nodo.derecha);
    }
  }
}

// Uso
const arbol = new ArbolDecision();
const datos = [
  { edad: 25, ingresos: 30000, clase: "bajo" },
  { edad: 45, ingresos: 80000, clase: "alto" },
  { edad: 35, ingresos: 50000, clase: "medio" },
  { edad: 50, ingresos: 120000, clase: "alto" },
  { edad: 22, ingresos: 20000, clase: "bajo" }
];

arbol.raiz = arbol.entrenar(datos, ["edad", "ingresos"]);

console.log("Clasificar {edad: 30, ingresos: 40000}:", 
            arbol.clasificar({ edad: 30, ingresos: 40000 }));

// K-Means clustering
class KMeans {
  constructor(k, maxIteraciones = 100) {
    this.k = k;
    this.maxIteraciones = maxIteraciones;
    this.centros = [];
    this.asignaciones = [];
  }

  distanciaEuclidea(p1, p2) {
    return Math.sqrt(p1.reduce((sum, val, i) => 
      sum + Math.pow(val - p2[i], 2), 0));
  }

  inicializarCentros(datos) {
    // Seleccionar k puntos aleatorios
    const indices = new Set();
    while (indices.size < this.k) {
      indices.add(Math.floor(Math.random() * datos.length));
    }
    this.centros = Array.from(indices).map(i => [...datos[i]]);
  }

  asignarPuntos(datos) {
    this.asignaciones = datos.map(punto => {
      let minDist = Infinity;
      let clusterAsignado = 0;

      for (let i = 0; i < this.centros.length; i++) {
        const dist = this.distanciaEuclidea(punto, this.centros[i]);
        if (dist < minDist) {
          minDist = dist;
          clusterAsignado = i;
        }
      }
      return clusterAsignado;
    });
  }

  actualizarCentros(datos) {
    const nuevosCentros = [];

    for (let i = 0; i < this.k; i++) {
      const puntosCluster = datos.filter((_, j) => this.asignaciones[j] === i);
      
      if (puntosCluster.length === 0) {
        nuevosCentros.push(this.centros[i]);
      } else {
        const nuevoCentro = [];
        for (let d = 0; d < datos[0].length; d++) {
          const media = puntosCluster.reduce((sum, p) => sum + p[d], 0) / puntosCluster.length;
          nuevoCentro.push(media);
        }
        nuevosCentros.push(nuevoCentro);
      }
    }

    return nuevosCentros;
  }

  convergio(nuevosCentros) {
    const umbral = 1e-6;
    for (let i = 0; i < this.k; i++) {
      const dist = this.distanciaEuclidea(this.centros[i], nuevosCentros[i]);
      if (dist > umbral) return false;
    }
    return true;
  }

  entrenar(datos) {
    this.inicializarCentros(datos);

    for (let iter = 0; iter < this.maxIteraciones; iter++) {
      this.asignarPuntos(datos);
      const nuevosCentros = this.actualizarCentros(datos);

      if (this.convergio(nuevosCentros)) {
        console.log(`K-Means convergió en ${iter + 1} iteraciones`);
        break;
      }

      this.centros = nuevosCentros;
    }
  }

  predecir(punto) {
    let minDist = Infinity;
    let cluster = 0;

    for (let i = 0; i < this.centros.length; i++) {
      const dist = this.distanciaEuclidea(punto, this.centros[i]);
      if (dist < minDist) {
        minDist = dist;
        cluster = i;
      }
    }
    return cluster;
  }
}

// Uso
const kmeans = new KMeans(2);
const datos = [
  [1, 1], [1, 2], [2, 1],
  [10, 10], [10, 11], [11, 10]
];

kmeans.entrenar(datos);
console.log("Cluster de [2, 2]:", kmeans.predecir([2, 2]));
console.log("Cluster de [11, 11]:", kmeans.predecir([11, 11]));

// Minimax para Tic-Tac-Toe
class TicTacToe {
  constructor() {
    this.tablero = Array(9).fill(null);
    this.jugadorIA = "O";
    this.jugadorHumano = "X";
  }

  movimientosDisponibles() {
    return this.tablero
      .map((val, idx) => val === null ? idx : null)
      .filter(val => val !== null);
  }

  ganador() {
    const lineas = [
      [0, 1, 2], [3, 4, 5], [6, 7, 8],
      [0, 3, 6], [1, 4, 7], [2, 5, 8],
      [0, 4, 8], [2, 4, 6]
    ];

    for (const [a, b, c] of lineas) {
      if (this.tablero[a] && 
          this.tablero[a] === this.tablero[b] && 
          this.tablero[a] === this.tablero[c]) {
        return this.tablero[a];
      }
    }
    return null;
  }

  esTerminal() {
    return this.ganador() !== null || this.movimientosDisponibles().length === 0;
  }

  minimax(profundidad, esMaximizador) {
    const ganador = this.ganador();

    if (ganador === this.jugadorIA) return 10 - profundidad;
    if (ganador === this.jugadorHumano) return profundidad - 10;
    if (this.movimientosDisponibles().length === 0) return 0;

    if (esMaximizador) {
      let maxEval = -Infinity;
      for (const mov of this.movimientosDisponibles()) {
        this.tablero[mov] = this.jugadorIA;
        const eval_ = this.minimax(profundidad + 1, false);
        maxEval = Math.max(maxEval, eval_);
        this.tablero[mov] = null;
      }
      return maxEval;
    } else {
      let minEval = Infinity;
      for (const mov of this.movimientosDisponibles()) {
        this.tablero[mov] = this.jugadorHumano;
        const eval_ = this.minimax(profundidad + 1, true);
        minEval = Math.min(minEval, eval_);
        this.tablero[mov] = null;
      }
      return minEval;
    }
  }

  mejorMovimiento() {
    let mejorEval = -Infinity;
    let mejorMov = null;

    for (const mov of this.movimientosDisponibles()) {
      this.tablero[mov] = this.jugadorIA;
      const eval_ = this.minimax(0, false);
      this.tablero[mov] = null;

      if (eval_ > mejorEval) {
        mejorEval = eval_;
        mejorMov = mov;
      }
    }

    return mejorMov;
  }
}

// Uso
const juego = new TicTacToe();
console.log("Mejor movimiento inicial:", juego.mejorMovimiento()); // 4 (centro)

// Red neuronal simple (perceptrón multicapa)
class Red {
  constructor(capas) {
    this.capas = [];
    
    for (let i = 0; i < capas.length - 1; i++) {
      const capa = {
        pesos: Array(capas[i]).fill(null).map(() =>
          Array(capas[i + 1]).fill(null).map(() => Math.random() * 2 - 1)
        ),
        sesgos: Array(capas[i + 1]).fill(null).map(() => Math.random() * 2 - 1)
      };
      this.capas.push(capa);
    }
  }

  sigmoid(x) {
    return 1 / (1 + Math.exp(-Math.max(-500, Math.min(500, x))));
  }

  sigmoidDerivada(x) {
    return x * (1 - x);
  }

  propagarAdelante(entrada) {
    let activacion = [...entrada];
    this.activaciones = [activacion];

    for (const capa of this.capas) {
      const nuevaActivacion = Array(capa.sesgos.length).fill(0);

      for (let i = 0; i < activacion.length; i++) {
        for (let j = 0; j < capa.pesos[i].length; j++) {
          nuevaActivacion[j] += activacion[i] * capa.pesos[i][j];
        }
      }

      for (let j = 0; j < nuevaActivacion.length; j++) {
        nuevaActivacion[j] = this.sigmoid(nuevaActivacion[j] + capa.sesgos[j]);
      }

      this.activaciones.push(nuevaActivacion);
      activacion = nuevaActivacion;
    }

    return activacion;
  }

  propagarAtras(salida, tasaAprendizaje) {
    const L = this.capas.length;
    let delta = salida.map((out, i) => 
      (out - this.activaciones[L][i]) * this.sigmoidDerivada(this.activaciones[L][i])
    );

    for (let l = L - 1; l >= 0; l--) {
      const nuevoDelta = Array(this.activaciones[l].length).fill(0);

      for (let i = 0; i < this.activaciones[l].length; i++) {
        for (let j = 0; j < this.capas[l].pesos[i].length; j++) {
          this.capas[l].pesos[i][j] -= tasaAprendizaje * delta[j] * this.activaciones[l][i];
          nuevoDelta[i] += delta[j] * this.capas[l].pesos[i][j];
        }
      }

      for (let j = 0; j < this.capas[l].sesgos.length; j++) {
        this.capas[l].sesgos[j] -= tasaAprendizaje * delta[j];
      }

      if (l > 0) {
        delta = nuevoDelta.map((d, i) => d * this.sigmoidDerivada(this.activaciones[l][i]));
      }
    }
  }

  entrenar(datos, epocas = 100, tasaAprendizaje = 0.5) {
    for (let e = 0; e < epocas; e++) {
      for (const [entrada, salida] of datos) {
        this.propagarAdelante(entrada);
        this.propagarAtras(salida, tasaAprendizaje);
      }
    }
  }

  predecir(entrada) {
    return this.propagarAdelante(entrada);
  }
}

// Uso: XOR
const red = new Red([2, 4, 1]);
const datosXOR = [
  [[0, 0], [0]],
  [[0, 1], [1]],
  [[1, 0], [1]],
  [[1, 1], [0]]
];

red.entrenar(datosXOR, 1000, 1);

console.log("XOR(0,0):", red.predecir([0, 0])[0].toFixed(2)); // ~0.0
console.log("XOR(0,1):", red.predecir([0, 1])[0].toFixed(2)); // ~1.0
console.log("XOR(1,1):", red.predecir([1, 1])[0].toFixed(2)); // ~0.0

// Sistema simple de reglas (motor de inferencia)
class SistemaReglas {
  constructor() {
    this.reglas = [];
    this.hechos = new Set();
  }

  agregarRegla(condiciones, conclusiones) {
    this.reglas.push({ condiciones, conclusiones });
  }

  agregarHecho(hecho) {
    this.hechos.add(hecho);
  }

  hechosCoinciden(condiciones) {
    return condiciones.every(cond => this.hechos.has(cond));
  }

  ejecutarHastaFijo() {
    let cambios = true;

    while (cambios) {
      cambios = false;
      const nuevosHechos = new Set(this.hechos);

      for (const { condiciones, conclusiones } of this.reglas) {
        if (this.hechosCoinciden(condiciones)) {
          for (const conclusion of conclusiones) {
            if (!this.hechos.has(conclusion)) {
              nuevosHechos.add(conclusion);
              cambios = true;
            }
          }
        }
      }

      this.hechos = nuevosHechos;
    }
  }

  consultarHecho(hecho) {
    return this.hechos.has(hecho);
  }
}

// Uso: Diagnosis de enfermedad
const sistema = new SistemaReglas();

// Reglas médicas
sistema.agregarRegla(["fiebre", "tos"], ["posible_gripe"]);
sistema.agregarRegla(["posible_gripe", "dolor_cabeza"], ["probable_gripe"]);
sistema.agregarRegla(["fiebre", "dificultad_respiratoria"], ["posible_neumonía"]);
sistema.agregarRegla(["probable_gripe"], ["necesita_descanso"]);

// Hechos observados
sistema.agregarHecho("fiebre");
sistema.agregarHecho("tos");
sistema.agregarHecho("dolor_cabeza");

sistema.ejecutarHastaFijo();

console.log("¿Probable gripe?", sistema.consultarHecho("probable_gripe")); // true
console.log("¿Necesita descanso?", sistema.consultarHecho("necesita_descanso")); // true