Was ist der Unterschied zwischen einem ‚kombinatorischen Algorithmus‘ und einem ‚linearen Algorithmus‘?

Question

Oder besser gesagt, was ist die Definition eines kombinatorischen Algorithmus und ein linearer Algorithmus, resp.

Um deutlich zu machen, weil offensichtlich die Ersthelfer die Frage falsch verstanden: Ich bin nicht für eine Definition eines Algorithmus sucht vs nicht-lineare Zeit in linearer Zeit. Ein linearer Algorithmus irgendwie im Zusammenhang mit dem linearen Programmierung, die eine Technik zum Auffinden oder Annähern Lösungen zu Optimierungsproblemen linear ist.

Da NP-harten Probleme so hart sind, gibt es eine ganze Feld versuchen, Näherungslösungen zu finden. Das Reiseproblem zum Beispiel hat mehrere Näherungslösungen, die in polynomieller Zeit laufen und eine Lösung herzustellen, die innerhalb einer Grenze der besten Lösung gegeben ist.

Einige dieser Annäherung Algorithmen sind ein linearer Algorithmus, andere einen kombinatorischen Algorithmus genannt; und letztere zu bevorzugen scheint (Warum?). Dies sind die beiden Konzepte, die ich möchte verstehen.

Answer 1

Das Problem ist einer der Problemformulierung.

Wie Sie gesagt reisenden Handelsvertreter Problem (TSP) ist NP-hard , gerade weil es eine diskrete Problemformulierung (der Verkäufer entweder besucht eine Stadt oder nicht zu einem bestimmten Zeitpunkt) hat. Diese diskrete Formulierung macht das Problem, und es ist Algorithmus, kombi . (Beachten Sie, dass nicht alle kombinatorischen Probleme sind NP-hart,. Betrachten Sortieralgorithmen)

Allerdings ist die Linear-Programmierung (LP) Entspannung von TSP führt zu einem linear Algorithmus. Dies liegt daran, das Problem so neu formuliert wurde, dass der Verkäufer eine Stadt ein gewisser Anteil an der Zeit besucht. Der Hauptgrund für die Verwendung einer LP Entspannung ist, weil die entspannte Version in lösende Polynom Zeit. Allerdings ist die Lösung für die Entspannung LP nicht unbedingt eine Lösung für das ursprüngliche Problem.

Answer 2

Ein linearer Algorithmus neigt dazu, mit nur einem Satz von Daten zu arbeiten - ‚Nehmen Sie alle Zahlen in set a, verdoppeln sie, und das Ergebnis in Satz b setzen‘. Die Anzahl der Operationen ist gleich die Anzahl der Elemente im Set a

Ein kombinatorisch arbeitet man auf Kombinationen von Sätzen - ‚Für jede Nummer eines in gesetzt, wobei die Summe dieser Zahl ausrechnen und jeden in der Serie b und drucken zu Bildschirm‘. Die Anzahl der Operationen ist das Produkt aus der Größe des Satzes ein und der Größe des Satzes b.

Answer 3

Die kombinatorische Algorithmen „explodieren“, wie ihr Eingang wächst. Lineare Algorithmen wächst proportional zu ihrer Eingabe, während der kombinatorischen Algorithmen zu einem Exponenten proportional wächst (oder schlechter) oder dessen Eingang. Alle möglichen Pfade durch einen Diagramm aufzählt, zum Beispiel