billycalc

Limite inferior TSP

Calcule Limite inferior TSP online grátis com a fórmula exata e um exemplo resolvido. Sem cadastro.

Limite inferior TSP

Peso da árvore geradora mínima W(MST)
Comprimento do circuito encontrado (heurística), 0 = nenhum
Limite inferior do comprimento do circuito ótimo
100
OPT ≥ W(MST): sem uma aresta, o circuito vira um caminho gerador, que não pesa menos que a árvore geradora mínima (pesos não negativos)Com a desigualdade triangular, percorrer a árvore dá um circuito ≤ 2·W(MST) e o algoritmo de Christofides ≤ 1,5·OPT; um limite inferior mais justo vem das 1-árvores de Held–KarpCalcule Limite inferior TSP online grátis com a fórmula exata e um exemplo resolvido. Sem cadastro.
Limite superior (percurso da árvore, com desigualdade triangular)
200
O circuito encontrado é pior que o ótimo em no máximo
30%

Mais sobre: Limite inferior TSP

O que calcula

A calculadora «Limite inferior TSP» calcula Limite inferior do comprimento do circuito ótimo a partir de 2 parâmetros: peso da árvore geradora mínima w(mst), comprimento do circuito encontrado (heurística), 0 = nenhum.

Cálculos de TI padrão para desenvolvedores e administradores.

Exemplo de cálculo

Com os parâmetros Peso da árvore geradora mínima W(MST) = 100, Comprimento do circuito encontrado (heurística), 0 = nenhum = 130 o resultado é 100 (OPT ≥ W(MST): sem uma aresta, o circuito vira um caminho gerador, que não pesa menos que a árvore geradora mínima (pesos não negativos)).

Como usar

  1. Digite peso da árvore geradora mínima w(mst) e comprimento do circuito encontrado (heurística), 0 = nenhum — cada campo acima é ajustável com um controle deslizante.
  2. Limite inferior do comprimento do circuito ótimo é calculado automaticamente conforme você digita.
  3. Confira o exemplo abaixo para ver a fórmula aplicada a números reais.
  4. Copie o resultado ou salve esta calculadora nos favoritos.

Calculadoras relacionadas

Perguntas frequentes

Como calcular Limite inferior TSP?
A calculadora de Limite inferior TSP calcula Limite inferior do comprimento do circuito ótimo a partir de peso da árvore geradora mínima w(mst), comprimento do circuito encontrado (heurística), 0 = nenhum. Digite seus valores acima e a fórmula exata é aplicada na hora; abaixo há um exemplo resolvido com números reais.
A calculadora de Limite inferior TSP é gratuita?
Sim. É totalmente gratuita, não exige cadastro, funciona no seu navegador e não envia dados para nenhum servidor.

Mais calculadoras desta categoria

Explore outras ferramentas gratuitas

Floyd-WarshallTeorema mestreLargura de banda Mbps ↔ MB/sMTU / MSSComplexidade Big-OMargem/Preenchimento (auto)Cifra de VigenèreCP de PokémonMana de Magic the GatheringÁrvore geradora mínima (Prim/Kruskal)Mochila (DP)Distância de edição (Levenshtein)