Qual è la differenza tra un "algoritmo combinatorio" e un "algoritmo lineare"?

Question

O meglio, qual è la definizione di algoritmo combinatorio e algoritmo lineare, risp.?

Per chiarire perché ovviamente i primi soccorritori hanno frainteso la domanda: non sto cercando una definizione di un algoritmo che gira in tempo lineare rispetto a tempo non lineare. Un algoritmo lineare è in qualche modo correlato alla programmazione lineare, che è una tecnica per trovare o approssimare soluzioni a problemi di ottimizzazione lineare.

Poiché i problemi NP-hard sono così difficili, c'è un intero campo che cerca di trovare soluzioni approssimative. Il problema del venditore ambulante, ad esempio, ha diverse soluzioni approssimative che funzionano in tempo polinomiale e producono una soluzione che rientra in un determinato limite della migliore soluzione.

Alcuni di questi algoritmi approssimativi sono chiamati algoritmi lineari, altri algoritmo combinatorio; e quest'ultimo sembra essere preferito (perché?). Questi sono i due concetti che vorrei capire.

Answer 1

Il problema riguarda la formulazione del problema.

Proprio come hai detto che il Problema del commesso viaggiatore (TSP) è NP-difficile proprio perché ha una formulazione discreta del problema (il venditore visita una città o no in un determinato momento). Questa formulazione discreta pone il problema, ed è un algoritmo, combinatorio . (Nota che non tutti i problemi combinatori sono NP-difficili; considera gli algoritmi di ordinamento.)

Tuttavia, il rilassamento della programmazione lineare (LP) di TSP si traduce in un algoritmo lineare . Questo perché il problema è stato riformulato in modo tale che il venditore visiti una città in una determinata percentuale del tempo. Il motivo principale per l'utilizzo di un rilassamento LP è perché la versione rilassata può essere risolta in polinomio . Tuttavia, la soluzione al rilassamento dell'LP non è necessariamente una soluzione al problema originale.

Answer 2

Un algoritmo lineare tende a funzionare con un solo set di dati: "Prendi tutti i numeri nel set a, raddoppia e metti il ??risultato nel set b". Il numero di operazioni è uguale al conteggio degli articoli nel set a

Uno combinatorio funziona su combinazioni di insiemi: "Per ogni numero nell'insieme a, calcola la somma di quel numero e di ogni numero nell'insieme b e stampa sullo schermo". Il numero di operazioni è il prodotto della dimensione dell'insieme a e della dimensione dell'insieme b.

Answer 3

Algoritmi combinatori "esplodono" man mano che il loro input cresce. Gli algoritmi lineari diventano proporzionali al loro input, mentre gli algoritmi combinatori diventano proporzionali a un esponente (o peggio) o al loro input: elencando tutti i possibili percorsi attraverso un grafico, per esempio.