═══════════════════════════════════════════════════════════
ESTRATEGIAS PARA PROBLEMAS NP-COMPLETOS
═══════════════════════════════════════════════════════════

1. CASO PROMEDIO (Backtracking optimizado):
  Complejidad: Exponencial teórica
  Práctica: Rápido en instancias típicas
  Garantía: Solución ÓPTIMA (si termina)
  Problema: Peor caso sigue siendo exponencial

  Ejemplo: Sudoku con poda inteligente
  - Peor caso: horas
  - Caso típico: < 1 segundo

2. HEURÍSTICAS (Sin garantías):
  Complejidad: Polinomial o mejor
  Práctica: Muy rápido
  Garantía: NINGUNA formal
  Ventaja: Funciona bien en práctica

  Ejemplo: Hill Climbing para TSP
  - Tiempo: O(n²)
  - Calidad: 10-30% sobre óptimo típico
  - Riesgo: Óptimos locales

3. APROXIMACIÓN (Con garantías):
  Complejidad: Polinomial
  Práctica: Eficiente
  Garantía: Factor α del óptimo
  Trade-off: Nunca óptima, pero cerca

  Ejemplo: 2-aproximación para Vertex Cover
  - Tiempo: O(|E|)
  - Calidad: ≤ 2 × óptimo SIEMPRE
  - Predecible: Peor caso acotado

def vertex_cover_approx(graph):
    """
    Algoritmo de 2-aproximación para Vertex Cover

    Garantía: |solución| ≤ 2 × |óptimo|
    Tiempo: O(|E|) - lineal en aristas

    Args:
        graph: grafo con aristas

    Returns:
        cover: conjunto de vértices (cubierta)
    """
    cover = set()
    edges = set(graph.edges)  # Copiar aristas

    print("Algoritmo de 2-aproximación para Vertex Cover\n")
    print("Paso a paso:\n")

    step = 1
    while edges:
        # Seleccionar arista arbitraria
        u, v = edges.pop()

        print(f"Paso {step}: Seleccionar arista ({u}, {v})")
        print(f"  Agregar vértices {u} y {v} a la cubierta")

        # Agregar ambos extremos a la cubierta
        cover.add(u)
        cover.add(v)

        # Eliminar todas las aristas incidentes a u o v
        edges_to_remove = {e for e in edges if u in e or v in e}
        edges -= edges_to_remove

        print(f"  Eliminar {len(edges_to_remove)} aristas cubiertas")
        print(f"  Aristas restantes: {len(edges)}")
        print()

        step += 1

    return cover

# Ejemplo de uso
print("="*60)
print("VERTEX COVER: ALGORITMO DE 2-APROXIMACIÓN")
print("="*60 + "\n")

class Graph:
    def __init__(self):
        self.vertices = set()
        self.edges = []

    def add_edge(self, u, v):
        self.vertices.add(u)
        self.vertices.add(v)
        self.edges.append((u, v))

    def __repr__(self):
        return f"Vértices: {sorted(self.vertices)}\nAristas: {self.edges}"

# Crear grafo de ejemplo
G = Graph()
edges_input = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (1, 6), (2, 4)]

for u, v in edges_input:
    G.add_edge(u, v)

print("Grafo:")
print(G)
print()

print("Visualización:")
print("""
    1 --- 2
    |     |\\
    |     | 3
    |     |/
    6 --- 5 --- 4
""")

print("="*60)

# Ejecutar algoritmo
cover = vertex_cover_approx(G)

print("="*60)
print("RESULTADO:")
print("="*60)
print(f"Cubierta encontrada: {sorted(cover)}")
print(f"Tamaño: {len(cover)}")

# Verificar que es cubierta válida
print("\nVerificación:")
for u, v in edges_input:
    if u in cover or v in cover:
        print(f"  Arista ({u},{v}): ✓ cubierta por {u if u in cover else v}")
    else:
        print(f"  Arista ({u},{v}): ✗ NO cubierta")

print("\n" + "="*60)
print("ANÁLISIS DE GARANTÍA:")
print("="*60)
print("""
¿Por qué es 2-aproximación?

Observación clave: Cada arista seleccionada requiere AL MENOS
uno de sus extremos en el óptimo.

Si seleccionamos k aristas:
  - Agregamos 2k vértices a nuestra solución
  - El óptimo necesita al menos k vértices
  - Ratio: 2k / k = 2

Por tanto: |solución| ≤ 2 × |óptimo|

En este ejemplo:
  - Nuestra solución: 6 vértices
  - Óptimo probable: 3-4 vértices
  - Ratio: 6/3 = 2 o 6/4 = 1.5
  - Dentro de la garantía ✓
""")

import random
import math

def tsp_cost(tour, distances):
    """Calcular costo total del tour"""
    cost = 0
    n = len(tour)
    for i in range(n):
        cost += distances[tour[i]][tour[(i + 1) % n]]
    return cost

def two_opt_swap(tour, i, j):
    """Generar vecino intercambiando segmento [i:j]"""
    new_tour = tour[:i] + tour[i:j+1][::-1] + tour[j+1:]
    return new_tour

def simulated_annealing_tsp(distances, T_initial=1.0, T_min=0.001,
                            alpha=0.95, iter_per_temp=100):
    """
    Simulated Annealing para TSP

    Args:
        distances: matriz de distancias
        T_initial: temperatura inicial
        T_min: temperatura mínima
        alpha: factor de enfriamiento
        iter_per_temp: iteraciones por temperatura

    Returns:
        mejor_tour, mejor_costo, historia
    """
    n = len(distances)

    # Solución inicial: orden aleatorio
    current_tour = list(range(n))
    random.shuffle(current_tour)
    current_cost = tsp_cost(current_tour, distances)

    # Mejor solución encontrada
    best_tour = current_tour[:]
    best_cost = current_cost

    # Historia para visualización
    history = [(0, current_cost, best_cost)]

    T = T_initial
    iteration = 0

    print(f"Iniciando SA para TSP con {n} ciudades")
    print(f"Costo inicial: {current_cost:.2f}\n")

    while T > T_min:
        improvements_at_T = 0

        for _ in range(iter_per_temp):
            iteration += 1

            # Generar vecino (2-opt swap)
            i = random.randint(0, n - 2)
            j = random.randint(i + 1, n - 1)

            new_tour = two_opt_swap(current_tour, i, j)
            new_cost = tsp_cost(new_tour, distances)

            delta = new_cost - current_cost

            # Decidir aceptación
            if delta < 0:
                # Mejora: siempre aceptar
                current_tour = new_tour
                current_cost = new_cost
                improvements_at_T += 1

                # Actualizar mejor
                if current_cost < best_cost:
                    best_tour = current_tour[:]
                    best_cost = current_cost
            else:
                # Empeoramiento: aceptar con probabilidad
                acceptance_prob = math.exp(-delta / T)
                if random.random() < acceptance_prob:
                    current_tour = new_tour
                    current_cost = new_cost

            history.append((iteration, current_cost, best_cost))

        # Reportar progreso
        print(f"T={T:.4f} | Costo actual: {current_cost:.2f} | "
              f"Mejor: {best_cost:.2f} | Mejoras: {improvements_at_T}")

        # Enfriar
        T *= alpha

    print(f"\n{'='*60}")
    print(f"Finalizado: Mejor costo = {best_cost:.2f}")

    return best_tour, best_cost, history

# Ejemplo de uso
print("="*60)
print("SIMULATED ANNEALING PARA TSP")
print("="*60 + "\n")

# Crear instancia TSP pequeña
n = 8
distances = [[0] * n for _ in range(n)]

# Generar distancias aleatorias simétricas
random.seed(42)
for i in range(n):
    for j in range(i + 1, n):
        dist = random.randint(10, 100)
        distances[i][j] = dist
        distances[j][i] = dist

print(f"Instancia TSP con {n} ciudades")
print("\nMatriz de distancias:")
print(f"{'':>4}", end="")
for i in range(n):
    print(f"{i:>4}", end="")
print()

for i in range(n):
    print(f"{i:>3}", end=" ")
    for j in range(n):
        if i == j:
            print(f"{'·':>4}", end="")
        else:
            print(f"{distances[i][j]:>4}", end="")
    print()

print("\n" + "="*60)
print("EJECUTANDO SIMULATED ANNEALING:")
print("="*60 + "\n")

# Ejecutar SA
best_tour, best_cost, history = simulated_annealing_tsp(
    distances,
    T_initial=10.0,
    T_min=0.01,
    alpha=0.95,
    iter_per_temp=50
)

print("\n" + "="*60)
print("RESULTADO FINAL:")
print("="*60)
print(f"Mejor tour: {best_tour}")
print(f"Costo: {best_cost:.2f}")

# Comparar con greedy
print("\n" + "="*60)
print("COMPARACIÓN CON GREEDY:")
print("="*60)

def greedy_tsp(distances):
    """TSP greedy: siempre ir a ciudad más cercana no visitada"""
    n = len(distances)
    tour = [0]
    unvisited = set(range(1, n))

    while unvisited:
        current = tour[-1]
        nearest = min(unvisited, key=lambda city: distances[current][city])
        tour.append(nearest)
        unvisited.remove(nearest)

    return tour, tsp_cost(tour, distances)

greedy_tour, greedy_cost = greedy_tsp(distances)

print(f"Greedy cost:  {greedy_cost:.2f}")
print(f"SA cost:      {best_cost:.2f}")
print(f"Mejora:       {((greedy_cost - best_cost) / greedy_cost * 100):.1f}%")

"""
CONFIGURACIÓN DE SIMULATED ANNEALING

1. TEMPERATURA INICIAL (T₀):
  Objetivo: Permitir exploración amplia inicial

  Heurística: Aceptar ~80-90% de empeoramientos al inicio

  Cálculo: T₀ = -Δ_promedio / ln(P_inicial)
  donde:
  - Δ_promedio = cambio promedio de costo
  - P_inicial = probabilidad inicial deseada (0.8-0.9)

  Típico: T₀ = 1.0 a 100.0 (normalizar costos)

2. TEMPERATURA FINAL (T_min):
  Objetivo: Criterio de parada

  Típico: T_min = 0.001 × T₀
  O: temperatura donde P(aceptar peor) < 0.01

3. FACTOR DE ENFRIAMIENTO (α):
  Objetivo: Controlar velocidad de descenso

  Fórmula: T\_{i+1} = α × T_i

  Típico: α = 0.85 - 0.99
  - α = 0.85: enfriamiento rápido (menos iteraciones)
  - α = 0.95: enfriamiento lento (más exploración)
  - α = 0.99: muy lento (mejor calidad, más tiempo)

  Trade-off: Calidad vs Tiempo

4. ITERACIONES POR TEMPERATURA:
  Objetivo: Alcanzar equilibrio térmico

  Heurística: Proporcional al tamaño del problema

  Típico:
  - Mínimo: 100 iteraciones
  - Ideal: n × log(n) donde n = tamaño
  - TSP-50: 200-500 iteraciones
  - TSP-100: 500-1000 iteraciones

5. ESQUEMAS DE ENFRIAMIENTO:

  a) GEOMÉTRICO (más común):
  T\_{i+1} = α × T_i

  b) LINEAL:
  T\_{i+1} = T_i - δ

  c) LOGARÍTMICO (teóricamente óptimo, muy lento):
  T_i = T₀ / log(1 + i)

  d) EXPONENCIAL:
  T_i = T₀ × e^(-i/τ)

EJEMPLO DE CONFIGURACIÓN:

# Para TSP pequeño (n ≤ 20):

T_initial = 10.0
T_min = 0.01
alpha = 0.95
iter_per_temp = 100

# Para TSP mediano (20 < n ≤ 100):

T_initial = 100.0
T_min = 0.001
alpha = 0.97
iter_per_temp = n \* 10

# Para TSP grande (n > 100):

T_initial = 1000.0
T_min = 0.0001
alpha = 0.99
iter_per_temp = n \* 5
"""