Good Will Hunting-Szene mit einem komplizierten Problem am MIT

Unterschied zwischen Algorithmen und Heuristiken

Schauen wir uns die Grundstruktur des Algorithmus-Aufbaus anhand einiger interessanter Probleme und ihrer subtilen Aspekte an

Motivation

Im Laufe der Jahre wurde mir klar, dass es in der Informatik nicht um "Computer" oder "Programmierung" geht. Wir sind in dieser Falle gefangen, weil wir so an die vielen häufig verwendeten Wörter "Computer" und "Programmierung" gewöhnt sind. Informatik - Problemstudie. Angesichts des Problems besteht das Ziel eines Informatikers darin, einen Algorithmus zu entwickeln, eine schrittweise Liste, um mögliche Probleme anzugehen. Algorithmen sind begrenzte Prozesse, und wenn sie befolgt werden, werden wir das Problem lösen. Algorithmen sind mit wenigen Ausnahmen wirklich Lösungen, wie alles andere auf der Welt. Computer und Programmierung sind nur Werkzeuge, um dies zu erreichen.

Sobald ich überzeugt war, dass "Informatik ein Erlernen von Algorithmen ist", konnte ich es schnell mit Mathematik verknüpfen. In der Tat sind sie mehr als Zwillingsbrüder. Die Schönheit, die Sie jetzt sanft von einer Disziplin in eine andere wechseln können. Kurz gesagt, wenn ich sage, dass Mathematik auf Informatik basiert und dass Algorithmen eine andere Art sind, Mathematik darzustellen, werde ich keinen Fehler machen. Es ist Musik des Geistes.

Es ist problemlösend, intellektuell beherrschend und schön - das ist der Anstoß für mich, Algorithmen zu lernen. Ich bin sicher, dass Sie auch werden. Lassen Sie mich diesen Abschnitt mit zwei Zitaten abschließen, die eine gute Grundlage für die Forschung und zweifellos einen Denkanstoß bieten.

Dem Algorithmus muss vertraut werden. - Donald Knut (Mathematiker und Informatiker)
John von Neumann
Wenn die Leute nicht glauben, dass Mathematik einfach ist, dann weil sie nicht verstehen, wie kompliziert das Leben ist. - John von Neumann (Mathematik, Physik, Statistik, Wirtschaft und Informatik)

Einführung

Beginnen wir mit dem Problem. Das als Sortieren bekannte algorithmische Problem ist wie folgt definiert.

Die Unterscheidung zwischen einem Problem und einem Beispiel eines Problems ist entscheidend. In diesem Fall kann das Beispiel eine Reihe von Namen wie {Suvro, Bhavna, Jane, Mike, Ram, Richa} oder eine Liste von Zahlen wie {7, 12, 11, 101, 45} sein. Der "Sortieren" -Algorithmus ist jedoch ein häufiges Problem. Daher benötigen Sie eine allgemeine Lösung, die alle Zugriffsinstanzen akzeptiert und Ihnen die gewünschten Ergebnisse liefert. Es gibt verschiedene Algorithmen zur Lösung des Regelungsproblems, von denen einer als "Bearbeiten" bezeichnet wird.

Inertstion Animierten Fluss sortieren

List hinzufügen ist eine Sortiermethode, die mit einem einzelnen Artikel beginnt (einfach eine Liste erstellen) und dann den Rest der Artikel zur Bestellliste hinzufügt. Schauen Sie sich die Darstellung auf der linken Seite an.

Pythons Implementierung von Intstion Sort lautet wie folgt:

Interner Prozess zum Einfügen sortieren

Wir suchen immer nach Algorithmen, die genau, effizient und einfach zu implementieren sind. In dieser Einführung konzentrieren wir uns nur auf die Genauigkeit der Algorithmen.

Richtige Algorithmen werden häufig mit einem Korrektheitsnachweis versehen, was bedeutet, dass jedes Beispiel eines Problems, wie wir im obigen Beispiel gesehen haben, das gewünschte Ergebnis liefern sollte. Aber bevor wir fortfahren, lassen Sie uns zeigen, warum es niemals richtig ist und normalerweise nicht, warum es "offensichtlich" ist.

Ist mein Algorithmus klar oder korrekt?

Betrachten Sie das Problem, das häufig bei Herstellungs-, Transport- und Testprogrammen auftritt. Angenommen, Sie haben einen Roboter, der löten kann. Jetzt möchten Sie die elektronische Karte löten, die aus Chips und anderen Teilen besteht, die an der Platine befestigt werden müssen. Die offensichtliche Frage ist also, wie ein Roboter das Board umgehen und seine Funktion ausführen kann. Dies sollte effektiv durchgeführt werden, da viele Platinen innerhalb eines bestimmten Zeitraums hergestellt werden müssen und jede Platine viele solcher Lötstellen aufweist.

Die offizielle Beschreibung des Problems sieht so aus und wir müssen den Roboterarm programmieren.

Problem: Optimierung des Robotertyps

Einführung: S 'n' Point-Sammlung auf der Ebene

Ergebnis: Was ist der kürzeste Zyklustyp, um jeden Punkt in Satz C zu besuchen?

Angebot 1: Near Neighborhood ist heuristisch

Die vielleicht wichtigste Idee ist die Heuristik des nächsten Nachbarn. Von einem zufälligen p0-Punkt gehen wir zum nächsten Nachbarn p1. Beginnend mit P1 gehen wir zu seinem nächsten nicht erkannten Nachbarn (daher wird p0 nicht als Kandidat gezählt). Wir wiederholen alle Punkte bis zu einem Besuch und kehren dann zu unserem Ausgangspunkt p0 zurück, um die Tour abzuschließen.

Die Hauptidee hier ist es also, nahe gelegene Orte zu besuchen, bevor Sie lange Strecken besuchen, um die Reisezeit zu verkürzen. In der obigen Abbildung 1 funktioniert es sehr gut, ist aber auch nicht sehr klein, aber es ist ratsam, jedes Punktepaar (pi, pj) zweimal zu betrachten, wenn pi und das andere für pj hinzugefügt werden. Leider ist dieser Algorithmus NICHT ALLE.

Sicher, der Algorithmus findet den Typ, aber er bedeutet nicht einmal den kürzesten Typ. Schauen Sie sich die Situation an, in der alle Gedanken entlang einer Linie liegen (siehe Abbildung 2). Wenn wir bei 0 beginnen, springen wir weiter von links nach rechts ... die beste Tour könnte am linken Punkt beginnen. Wenn wir nach rechts gehen, besuchen Sie jeden Punkt und kehren schließlich zum ersten Punkt zurück.

Definition 2: Der nächste Nachbar ist heuristisch

Vielleicht brauchen wir einen anderen Ansatz. Es ist immer sehr begrenzt, zum nächsten Punkt zu gelangen. Somit ist es nicht möglich zu sagen, ob Algorithmen richtig oder falsch sind.

Es stellt sich die Frage, welcher Algorithmus zur Lösung dieses Problems geeignet ist. Nun, eine Antwort könnte klar sein, die mögliche Reihenfolge aller Punkte auflisten und dann die Reihenfolge auswählen, die die gesamte Länge minimiert. Somit ist uns garantiert, dass wir die kürzestmögliche Reise absolvieren.

Wir werden diese Gelegenheit nun erneut bewerten. Angenommen, Sie haben insgesamt 20 Punkte. Wir haben also 20, um alle möglichen Pfade mit 20 Punkten zu berechnen! (20 Fakultäten), das sind 18 verschiedene Größenordnungen von 10 Größen. Dies ist eine sehr große Zahl für einen Computer. Wenn n = 1000 ist, müssen wir möglicherweise auf einen weiteren Urknall warten, bevor der Computer alle Möglichkeiten bewerten und feststellen kann, welcher Pfad der kürzeste ist. .

Dieses Problem wird oft als TSP-Problem (Travelling Vendor) bezeichnet, und wir versuchen, einen effektiven Algorithmus zu finden, um dieses Problem anzugehen. Was jedoch derzeit die Hauptattraktion dieser Diskussion ist, ist der grundlegende Unterschied zwischen Algorithmen und Prinzipien. heuristisch. Algorithmen liefern immer das richtige Ergebnis, aber Heuristik kann sehr gut funktionieren, garantiert jedoch niemals eine vollständige Lösung.

Mehr zur Gültigkeit des Algorithmus

Schauen wir uns ein anderes Problem an, um unseren Geist im Hinblick auf die Gültigkeit des Algorithmus zu erweitern. Dies ist ein Problem bei der Planung. Angenommen, Sie sind der gefragteste Schauspieler / die gefragteste Schauspielerin und haben eine Liste mit Filmen, für die Sie sich anmelden müssen. Vorschläge kommen mit dem Start- und Enddatum des Projekts. Sie können nicht mehr zwei Projekte akzeptieren, die gleichzeitig miteinander kompatibel sind.

Das Ziel für einen Künstler wie Sie ist es, mit diesen Projekten so viel Geld wie möglich zu verdienen. Jedes Projekt zahlt das gleiche, was bedeutet, dass Sie nach der größten Anzahl von Projekten suchen, deren Zeit nicht kompatibel ist. Betrachten Sie die Darstellung dieses Planungsproblems.

Ausgabe - 3: Planungsproblem

Lassen Sie uns nun zum Beispiel das Problem offiziell identifizieren -

Problem: Probleme bei der Filmplanung

Einführung: Satz von n Intervallen auf der Linie.

Ergebnis: Was ist der größte Satz nicht überlappender Intervalle, die aus I ausgewählt werden können?

Ich bin mir sicher, dass es viele Ideen für die Entwicklung dieses Algorithmus geben wird. Das erste ist, dass Sie mit der Arbeit beginnen können, wenn der erste Job verfügbar ist. Dies bedeutet, dass Sie zum frühesten Startdatum beginnen müssen, wenn Sie nicht untätig bleiben möchten.

Algorithmus zur Auswahl des frühesten Startdatums

Warum ist das keine sehr gute Idee? Denken Sie an den ersten Job, er wird lange dauern und alle Geschäftsaussichten mit kürzeren Fristen zunichte machen. Dieses Szenario wird im Folgenden beschrieben.

Eine schlechte Idee mit dem frühesten Algorithmus, um loszulegen

Daher ist es für Sie selbstverständlich, sich für den kürzesten Job zu entscheiden und weiterhin auf Schritt und Tritt nach dem kürzesten Job zu suchen. Das Maximieren dieser Anzahl kann den Umsatz steigern. Definieren wir diese Heuristik formal.

Kurze Jobauswahl

Jetzt sieht dieser Ansatz gut aus, aber die kürzeren Jobs können uns auf die Hälfte des Gehalts beschränken. Betrachten Sie in diesem Fall das Bild unten.

Begrenzen Sie die Zahlung durch Auswahl von Kurzarbeit

Suchen wir also nach einem Algorithmus, der richtig und effizient ist -

Richtiger und effizienter Algorithmus für Filmplanungsprobleme

Schauen Sie sich in unserem Fall Depition -3 an, um zu sehen, wie Projekte aussortiert werden. Das Bild unten zeigt, wie ein Künstler Filme akzeptiert.

Das Problem der Filmplanung lösen

Reisen

  1. Es gibt immer einen signifikanten Unterschied in der Heuristik, mit Algorithmen, die immer genau sind und normalerweise gut funktionieren, aber keine Garantien haben.
  2. Die Genauigkeit des Algorithmus ist eine Funktion, die mit Vorsicht demonstriert werden muss.

Anmerkung des Autors

Dies ist der erste Artikel in der Reihe "Algorithmen und Datenstrukturen". Im nächsten Artikel werden wir einen mathematischen Kreis erstellen, der die Genauigkeit von Algorithmen demonstriert. Folgen Sie den Nachrichten, bleiben Sie informiert; Bleib bei uns ...

Viel Spaß beim Lernen :)

Referenzen

  1. Leitfaden zur Algorithmusentwicklung - Stephen Skiena, SUNY Stony Brook, Institut für Informatik, USA.
  2. Zugriff auf Algorithmen - Cormen, Leiserson, Rivest und Stein
  3. Algorithmen und Datenstrukturen mit Python - Brad Miller und David Ranum, Luther College