billycalc

Limite inferiore TSP

Calcola Limite inferiore TSP online gratis con la formula esatta e un esempio risolto. Senza registrazione.

Limite inferiore TSP

Peso dell'albero ricoprente minimo W(MST)
Lunghezza del giro trovato (euristica), 0 = nessuno
Limite inferiore della lunghezza del giro ottimo
100
OPT ≥ W(MST): togliendo un arco il giro diventa un cammino ricoprente, che non pesa meno dell'albero ricoprente minimo (pesi non negativi)Con la disuguaglianza triangolare, percorrere l'albero dà un giro ≤ 2·W(MST) e l'algoritmo di Christofides ≤ 1,5·OPT; un limite inferiore più stretto sono gli 1-alberi di Held–KarpCalcola Limite inferiore TSP online gratis con la formula esatta e un esempio risolto. Senza registrazione.
Limite superiore (visita dell'albero, con disuguaglianza triangolare)
200
Il giro trovato è peggiore dell'ottimo al massimo del
30%

Maggiori informazioni: Limite inferiore TSP

Cosa calcola

La calcolatrice «Limite inferiore TSP» calcola Limite inferiore della lunghezza del giro ottimo da 2 parametri: peso dell'albero ricoprente minimo w(mst), lunghezza del giro trovato (euristica), 0 = nessuno.

Calcoli informatici standard per sviluppatori e amministratori.

Esempio di calcolo

Con i parametri Peso dell'albero ricoprente minimo W(MST) = 100, Lunghezza del giro trovato (euristica), 0 = nessuno = 130 il risultato è 100 (OPT ≥ W(MST): togliendo un arco il giro diventa un cammino ricoprente, che non pesa meno dell'albero ricoprente minimo (pesi non negativi)).

Come si usa

  1. Inserisci peso dell'albero ricoprente minimo w(mst) e lunghezza del giro trovato (euristica), 0 = nessuno — ogni campo sopra è regolabile con un cursore.
  2. Limite inferiore della lunghezza del giro ottimo viene calcolato automaticamente mentre digiti.
  3. Guarda l'esempio qui sotto per vedere la formula applicata a numeri reali.
  4. Copia il risultato o aggiungi questa calcolatrice ai preferiti.

Calcolatrici correlate

Domande frequenti

Come si calcola Limite inferiore TSP?
La calcolatrice Limite inferiore TSP calcola Limite inferiore della lunghezza del giro ottimo da peso dell'albero ricoprente minimo w(mst), lunghezza del giro trovato (euristica), 0 = nessuno. Inserisci i tuoi valori sopra e la formula esatta viene applicata all'istante; un esempio risolto con numeri reali è mostrato di seguito.
La calcolatrice Limite inferiore TSP è gratuita?
Sì. È completamente gratuita, non richiede registrazione, funziona nel tuo browser e non invia dati ad alcun server.

Altre calcolatrici in questa categoria

Esplora altri strumenti gratuiti

Viewport (vw/vh)CSS GridFlexboxPageSpeed (TTI / FCP)Blocco monousoRobustezza della chiave RSASHA-1 / SHA-256 / SHA-512Entropia della passwordTempo di attacco a forza brutaGeneratore di password casualiCosto del filamento 3DCosto di stampa 3D (DIY)