billycalc

Cota inferior TSP

Calcula Cota inferior TSP online gratis con la fórmula exacta y un ejemplo resuelto. Sin registro.

Cota inferior TSP

Peso del árbol de expansión mínima W(MST)
Longitud del recorrido encontrado (heurística), 0 = ninguno
Cota inferior de la longitud del recorrido óptimo
100
OPT ≥ W(MST): al quitar una arista, el recorrido se convierte en un camino de expansión, que no pesa menos que el árbol de expansión mínima (pesos no negativos)Con la desigualdad triangular, recorrer el árbol da un recorrido ≤ 2·W(MST) y el algoritmo de Christofides ≤ 1,5·OPT; una cota inferior más ajustada son los 1-árboles de Held–KarpCalcula Cota inferior TSP online gratis con la fórmula exacta y un ejemplo resuelto. Sin registro.
Cota superior (recorrido del árbol, con desigualdad triangular)
200
El recorrido encontrado es peor que el óptimo como máximo en
30%

Más sobre: Cota inferior TSP

Qué calcula

La calculadora «Cota inferior TSP» calcula Cota inferior de la longitud del recorrido óptimo a partir de 2 parámetros: peso del árbol de expansión mínima w(mst), longitud del recorrido encontrado (heurística), 0 = ninguno.

Cálculos de IT estándar para desarrolladores y administradores.

Ejemplo de cálculo

Con los parámetros Peso del árbol de expansión mínima W(MST) = 100, Longitud del recorrido encontrado (heurística), 0 = ninguno = 130 el resultado es 100 (OPT ≥ W(MST): al quitar una arista, el recorrido se convierte en un camino de expansión, que no pesa menos que el árbol de expansión mínima (pesos no negativos)).

Cómo usar

  1. Introduce peso del árbol de expansión mínima w(mst) y longitud del recorrido encontrado (heurística), 0 = ninguno — cada campo de arriba se ajusta con un control deslizante.
  2. Cota inferior de la longitud del recorrido óptimo se calcula automáticamente mientras escribes.
  3. Consulta el ejemplo de abajo para ver la fórmula aplicada a números reales.
  4. Copia el resultado o guarda esta calculadora en marcadores.

Calculadoras relacionadas

Preguntas frecuentes

¿Cómo se calcula Cota inferior TSP?
La calculadora de Cota inferior TSP calcula Cota inferior de la longitud del recorrido óptimo a partir de peso del árbol de expansión mínima w(mst), longitud del recorrido encontrado (heurística), 0 = ninguno. Introduce tus valores arriba y se aplica la fórmula exacta al instante; abajo se muestra un ejemplo resuelto con números reales.
¿La calculadora de Cota inferior TSP es gratis?
Sí. Es totalmente gratuita, no requiere registro, funciona en tu navegador y no envía datos a ningún servidor.

Más calculadoras de esta categoría

Explora otras herramientas gratuitas

Volumen de resina (SLA)Adherencia a la cama de impresiónTiempo de enfriamientoMaterial de soporteDaño por segundo (DPS)EHP (PV efectivos)Tasa de golpe críticoTabla de botínReducción de daño (juego)Conversión de moneda de juegoCalculadora de IV de PokémonTirada d20 / probabilidad de dados