2.4 Prioritäts-Warteschlangen Viele Anwendungen erfordern, dass wir Elemente mit Schlüssel in der Reihenfolge verarbeiten, aber nicht unbedingt in voller Sortierreihenfolge und nicht unbedingt alle auf einmal. Oft sammeln wir einen Satz von Gegenständen, verarbeiten dann den einen mit dem größten Schlüssel, dann sammeln vielleicht mehr Gegenstände, verarbeiten dann den einen mit dem aktuellsten Schlüssel und so weiter. Ein geeigneter Datentyp in einer solchen Umgebung unterstützt zwei Operationen: das Maximum entfernen und einfügen. Ein solcher Datentyp wird als Prioritätswarteschlange bezeichnet. Prioritäts-Warteschlangen sind durch das Entfernen der maximalen und Insert-Operationen gekennzeichnet. Nach Konvention werden wir die Schlüssel nur mit einer weniger () Methode vergleichen, wie wir es für die Sortierung getan haben. Wenn also Datensätze doppelte Schlüssel haben können, bedeutet maximal ein Datensatz mit dem größten Schlüsselwert. Um die API zu vervollständigen, müssen wir auch Konstruktoren und einen Test bei leerer Operation hinzufügen. Für Flexibilität verwenden wir eine generische Implementierung mit einem generischen Typ Key, der vergleichbare implementiert. Programm TopM. java ist ein Prioritäts-Warteschlangen-Client, der ein Befehlszeilen-Argument M nimmt. Liest Transaktionen von der Standard-Eingabe und druckt die M größten Transaktionen aus. Elementare Implementierungen Die grundlegenden Datenstrukturen, die wir in Abschnitt 1.3 besprochen haben, geben uns vier unmittelbare Ausgangspunkte für die Implementierung von Prioritätsschlangen. Array-Darstellung (ungeordnet). Vielleicht basiert die einfachste Prioritäts-Warteschlangen-Implementierung auf unserem Code für Pushdown-Stacks. Der Code für das Einfügen in die Prioritätswarteschlange ist der gleiche wie für den Stapel. Um das Maximum zu entfernen. Wir können Code wie die innere Schleife der Auswahl sortieren, um das maximale Element mit dem Element am Ende auszutauschen und dann das zu löschen, wie wir es mit Pop () für Stacks gemacht haben. Programm UnorderedArrayMaxPQ. java implementiert eine Prioritätswarteschlange mit diesem Ansatz. Array-Darstellung (bestellt). Ein anderer Ansatz besteht darin, Code für den Einfügen hinzuzufügen, um größere Einträge um eine Position nach rechts zu verschieben, so dass die Einträge im Array in der Reihenfolge (wie beim Einfügen sortieren). So ist das größte Element immer am Ende, und der Code zum Entfernen des Maximums in der Prioritätswarteschlange ist der gleiche wie für Pop im Stack. Programm OrderedArrayMaxPQ. java implementiert eine Prioritätswarteschlange mit diesem Ansatz. Verknüpfte Listendarstellungen (ungeordnet und umgekehrt). In ähnlicher Weise können wir mit unserem Link-Listen-Code für Pushdown-Stacks beginnen, indem du entweder den Code für pop () ändere, um das Maximum oder den Code für push () zu finden und zurückzugeben, um Gegenstände in umgekehrter Reihenfolge zu halten und den Code für Pop () zu Aufheben und den ersten (maximalen) Eintrag in der Liste zurückgeben. Alle soeben erörterten elementaren Implementierungen haben die Eigenschaft, dass entweder die Einfügung oder die Entfernung der maximalen Operation im schlimmsten Fall die lineare Zeit annimmt. Eine Implementierung zu finden, bei der beide Operationen schnell garantiert werden, ist eine interessantere Aufgabe, und es ist das Hauptthema dieses Abschnitts. Haufendefinitionen. Der Binärhaufen ist eine Datenstruktur, die die grundlegenden Prioritäts-Warteschlangenoperationen effizient unterstützen kann. In einem Binärhaufen werden die Elemente in einem Array gespeichert, so dass jeder Schlüssel größer als (oder gleich) der Tasten an zwei anderen spezifischen Positionen ist. Im Gegenzug muss jeder dieser Schlüssel größer sein als zwei weitere Tasten und so weiter. Diese Bestellung ist leicht zu sehen, wenn wir die Schlüssel als in einer binären Baumstruktur mit Kanten von jedem Schlüssel zu den beiden Schlüsseln sehen, die kleiner sind. Definition. Ein Binärbaum ist hap-geordnet, wenn der Schlüssel in jedem Knoten größer als (oder gleich) die Schlüssel in diesem Knoten zwei Kinder (falls vorhanden) ist. Aussage. Der größte Schlüssel in einem Haufen-geordneten Binärbaum wird an der Wurzel gefunden. Wir können die Heap-Ordering-Beschränkung auf jeden binären Baum verhängen. Es ist besonders zweckmäßig, einen kompletten Binärbaum wie den folgenden zu benutzen. Wir stellen komplette Binärbäume sequentiell innerhalb eines Arrays dar, indem wir die Knoten mit der Ebenenreihenfolge setzen. Mit der Wurzel an Position 1, seine Kinder an den Positionen 2 und 3, ihre Kinder in den Positionen 4, 5, 6 und 7, und so weiter. Definition. Ein binärer Haufen ist ein Satz von Knoten mit Schlüsseln, die in einem kompletten, heapgeordneten Binärbaum angeordnet sind, der in einer Reihenfolge in einem Array dargestellt ist (nicht mit dem ersten Eintrag). In einem Haufen befindet sich der Elternteil des Knotens in der Position k in der Position k2 und umgekehrt sind die beiden Kinder des Knotens in der Position k in den Positionen 2k und 2k 1. Wir können aufwärts und abwärts gehen, indem wir eine einfache Arithmetik auf Arrayindizes machen : Um den Baum von ak zu bewegen, setzen wir k auf k2, um den Baum hinunterzugehen, den wir k auf 2k oder 2k1 setzen. Algorithmen auf Haufen. Wir repräsentieren einen Haufen der Größe N im privaten Array pq der Länge N1, mit pq0 unbenutzt und der Haufen in pq1 bis pqN. Wir greifen nur über private Helferfunktionen auf weniger () und exch () zu. Die Heap-Operationen, die wir betrachten, indem wir zunächst eine einfache Modifikation machen, die den Heap-Zustand verletzen könnte, dann durch den Haufen reisen und den Haufen entsprechend ändern, um sicherzustellen, dass die Haufen-Bedingung überall erfüllt ist. Wir beziehen uns auf diesen Prozess als reheapifying. Oder Wiederherstellung der Heap-Reihenfolge. Bottom-up reheapify (schwimmen). Wenn der Heap-Befehl verletzt wird, weil ein Knoten-Schlüssel größer wird als der Knoten-Eltern-Schlüssel, dann können wir Fortschritte machen, um die Verletzung zu beheben, indem wir den Knoten mit seinem Elternteil austauschen. Nach dem Austausch ist der Knoten größer als seine beiden Kinder (einer ist der alte Elternteil und der andere ist kleiner als der alte Elternteil, weil es ein Kind dieses Knotens war), aber der Knoten kann immer noch größer sein als sein Elternteil. Wir können diese Verletzung auf die gleiche Weise beheben, und so weiter, den Haufen hinauf, bis wir einen Knoten mit einem größeren Schlüssel oder der Wurzel erreichen. Top-down heapify (Spüle). Wenn der Heap-Befehl verletzt wird, weil ein Knoten-Schlüssel kleiner wird als einer oder beide dieser Knoten-Kinder-Schlüssel, dann können wir Fortschritte machen, um die Verletzung zu beheben, indem wir den Knoten mit dem größeren seiner beiden Kinder austauschen. Dieser Schalter kann eine Verletzung des Kindes verursachen, die wir diese Verletzung auf die gleiche Weise beheben, und so weiter, den Haufen hinunter, bis wir einen Knoten erreichen, bei dem beide Kinder kleiner oder der Boden sind. Heap-basierte Prioritätswarteschlange. Diese sink () und swim () Operationen bilden die Grundlage für eine effiziente Implementierung der Priority-Queue API, wie unten dargestellt und implementiert in MaxPQ. java und MinPQ. java. Einfügen. Wir fügen das neue Element am Ende des Arrays hinzu, erhöhen die Größe des Heaps und schwimmen dann durch den Heap mit diesem Element, um den Heap-Zustand wiederherzustellen. Maximal entfernen. Wir nehmen das größte Stück von der Oberseite, setzen das Einzelteil vom Ende des Haufens an die Oberseite, dekrementieren die Größe des Haufens und sinken dann durch den Haufen mit diesem Einzelteil, um den Haufenzustand wieder herzustellen. Aussage. In einer N-Item-Prioritäts-Warteschlange erfordern die Heap-Algorithmen nicht mehr als 1 lg N für Insert und nicht mehr als 2 lg N vergleicht, um das Maximum zu entfernen. Praktische Überlegungen. Wir schließen unsere Studie der Haufenprioritäts-Warteschlangen-API mit einigen praktischen Überlegungen ab. Multiway Haufen. Es ist nicht schwer, unseren Code zu modifizieren, um Haufen zu erstellen, die auf einer Array-Darstellung von kompletten Heap-geordneten ternären oder daryistischen Bäumen basieren. Es gibt einen Kompromiß zwischen den niedrigeren Kosten aus der reduzierten Baumhöhe und den höheren Kosten für die Suche nach dem größten der drei oder d Kinder an jedem Knoten. Array-Größenänderung. Wir können einen No-Argument-Konstruktor hinzufügen, Code für Array-Verdopplung in insert (). Und Code für Array-Halbierung in delMax (). Genauso wie wir für Stapel in Abschnitt 1.3. Die logarithmischen Zeitgrenzen werden amortisiert, wenn die Größe der Prioritätswarteschlange beliebig ist und die Arrays verkleinert werden. Unveränderlichkeit der Schlüssel. Die Prioritätswarteschlange enthält Objekte, die von Clients erstellt werden, aber davon ausgeht, dass der Client-Code die Schlüssel nicht ändert (was die Heap-Invarianten ungültig machen könnte). Index-Prioritäts-Warteschlange. In vielen Anwendungen ist es sinnvoll, den Kunden zu erlauben, auf Artikel zu verweisen, die sich bereits in der Prioritätswarteschlange befinden. Eine einfache Möglichkeit, dies zu tun ist, einen einzelnen Integer-Index mit jedem Element zu verknüpfen. IndexMinPQ. java ist eine haufenbasierte Implementierung dieses API IndexMaxPQ. java ist ähnlich, aber für maximal orientierte Prioritätswarteschlangen. Multiway. java ist ein Client, der mehrere sortierte Eingangsströme zu einem sortierten Ausgabestream zusammenführt. Wir können jede Prioritätswarteschlange verwenden, um eine Sortiermethode zu entwickeln. Wir setzen alle Schlüssel ein, die in eine minimal orientierte Prioritätswarteschlange sortiert werden sollen, und dann wiederholt das Minimum entfernen, um sie alle in der Reihenfolge zu entfernen. Wenn Sie einen Heap für die Prioritätswarteschlange verwenden, erhalten wir Heapsort. Wir konzentrieren uns auf die Aufgabe der Sortierung, wir verlassen den Begriff, die Haufen Darstellung der Priorität Warteschlange zu verstecken und verwenden Sie swim () und sinken () direkt. Auf diese Weise können wir ein Array sortieren, ohne dass ein zusätzlicher Platz benötigt wird, indem der Haufen innerhalb des zu sortierenden Arrays beibehalten wird. Heapsort bricht in zwei Phasen: Haufenbau. Wo wir das Original-Array in einen Haufen reorganisieren und die Sortierung. Wo wir die Gegenstände aus dem Haufen in absteigender Reihenfolge ziehen, um das sortierte Ergebnis zu bauen. Haufenbau. Wir können diese Aufgabe rechtzeitig proportional zu N lg N durchführen, indem wir von links nach rechts durch das Array gehen, indem wir mit swim () umgehen, um sicherzustellen, dass die Einträge links vom Scan-Zeiger einen Heap-geordneten kompletten Baum bilden, wie aufeinanderfolgend Prioritäts-Warteschlangen-Einfügungen. Eine schlaue Methode, die viel effizienter ist, ist von rechts nach links zu gehen, mit sink (), um Subhaps zu machen, wie wir gehen. Jede Position im Array ist die Wurzel einer kleinen Subhap Sink () Werke oder solche Subhaps, wie gut. Wenn die beiden Kinder eines Knotens Haufen sind, dann ruft der Sink () auf diesem Knoten den Teilbaum dort einen Haufen. Abwärts sortieren Die meisten Arbeiten während des Heapsortes werden während der zweiten Phase durchgeführt, wo wir die größten verbleibenden Gegenstände aus dem Haufen entfernen und sie in die Array-Position verwandeln lassen, wenn der Haufen schrumpft. Heap. java ist eine vollständige Implementierung von Heapsort. Unten ist eine Spur des Inhalts des Arrays nach jedem Waschbecken. Aussage. Sink-basierte Heap-Konstruktion ist lineare Zeit. Aussage. Heapsort Benutzer weniger als 2n lg n vergleichen und tauschen, um n Artikel zu sortieren. Die meisten Gegenstände werden beim Absteigen in den Haufen eingefügt. Gehen Sie den ganzen Weg bis zum Boden. Wir können so Zeit sparen, indem wir den Scheck vermeiden, ob der Gegenstand seine Position erreicht hat, indem er einfach den größeren der beiden Kinder fördert, bis der Boden erreicht ist und dann den Haufen in die richtige Position zurückzieht. Diese Idee schneidet die Anzahl der Vergleiche um den Faktor 2 auf Kosten der zusätzlichen Buchhaltung. Angenommen, die Sequenz (wo ein Buchstabe bedeutet Einfügen und ein Asterisk bedeutet, das Maximum zu entfernen) wird auf eine anfänglich leere Prioritätswarteschlange angewendet. Geben Sie die Reihenfolge der zurückgegebenen Werte an, indem Sie die maximalen Operationen entfernen. Lösung. R R P O T Y I I U Q E U (E links auf PQ) Kritisieren Sie die folgende Idee: Um zu implementieren finden Sie das Maximum in konstanter Zeit, warum nicht behalten Sie den maximal eingesetzten Wert so weit, dann geben Sie diesen Wert für das Maximum zu finden. Lösung. Muss den maximalen Wert nach dem Entfernen der maximalen Operation neu klettern. Geben Sie vorrangige Warteschlangen-Implementierungen ein, die das Einfügen unterstützen und das Maximum entfernen. Eine für jede der folgenden zugrundeliegenden Datenstrukturen: ungeordnetes Array, geordnetes Array, ungeordnete verknüpfte Liste und geordnete verknüpfte Liste. Geben Sie für jede Ihrer vier Implementierungen eine Tabelle der Worst-Case-Schranken aus der vorherigen Übung. Teillösung. OrderedArrayMaxPQ. java und UnorderedArrayMaxPQ. java Ist ein Array, das in absteigender Reihenfolge einen max-orientierten Heap sortiert wird. Antworten. Ja. Angenommen, dass Ihre Anwendung eine riesige Anzahl von Insert-Operationen haben wird, aber nur wenige entfernen die maximalen Operationen. Welche Prioritäts-Warteschlange-Implementierung wäre Ihrer Meinung nach am effektivsten: Heap, ungeordnetes Array, geordnetes Array Antwort. Ungeordnetes Array Einfügen ist konstante Zeit. Angenommen, Ihre Anwendung wird eine riesige Anzahl von finden die maximale Operationen, aber eine relativ kleine Anzahl von Insert und entfernen Sie die maximale Operationen. Welche Prioritäts-Warteschlangen-Implementierung sind Ihrer Meinung nach am effektivsten: Haufen, ungeordnetes Array, geordnetes Array Antwort. Geordnetes Array Finden Sie das Maximum ist konstante Zeit. Was ist die minimale Anzahl von Gegenständen, die während eines Entfernens der maximalen Operation in einem Haufen der Größe N ohne doppelte Schlüssel ausgetauscht werden müssen Geben Sie einen Haufen der Größe 15, für die das Minimum erreicht wird. Beantworten Sie die gleiche Frage für zwei und drei aufeinanderfolgende entfernen Sie die maximalen Operationen. Teilweise Antwort (A) 2. Entwerfen Sie einen linearen Zeitzertifizierungsalgorithmus, um zu überprüfen, ob ein Array pq ein min-orientierter Haufen ist. Lösung. Siehe die Methode isMinHeap () in MinPQ. java. Beweisen Sie, dass die Sink-basierte Heap-Konstruktion höchstens 2 n vergleicht und höchstens n Austausch. Lösung. Es genügt zu beweisen, dass die sinkbasierte Heap-Konstruktion weniger als n Austausch verwendet, weil die Anzahl der Vergleiche höchstens die doppelte Anzahl der Börsen ist. Zur Vereinfachung geht man davon aus, dass der Binärhaufen perfekt ist (d. h. ein binärer Baum, in dem jeder Level vollendet ist) und hat die Höhe h. Wir definieren die Höhe eines Knotens in einem Baum, um die Höhe des Teilbaums zu sein, der an diesem Knoten verwurzelt ist. Ein Schlüssel in der Höhe k kann mit höchstens k Tasten unter ihm ausgetauscht werden, wenn er nach unten versenkt wird. Da gibt es 2 h minus k Knoten in der Höhe k. Die Gesamtzahl der Austausche ist höchstens: Die erste Gleichheit ist für eine nicht standardisierte Summe, aber es ist einfach zu verifizieren, dass die Formel über mathematische Induktion gilt. Die zweite Gleichheit gilt, weil ein perfekter Binärbaum der Höhe h 2 h 1 minus 1 Knoten hat. Vorausgesetzt, dass das Ergebnis gilt, wenn der Binärbaum nicht perfekt ist, erfordert ein bisschen mehr Pflege. Sie können dies mit der Tatsache tun, dass die Anzahl der Knoten in der Höhe k in einem binären Haufen auf n Knoten höchstens endlich ist (n 2 k 1). Alternative Lösung Wiederum wird der Einfachheit halber angenommen, dass der Binärhaufen perfekt ist (d. h. ein binärer Baum, in dem jede Ebene abgeschlossen ist). Wir definieren die Höhe eines Knotens in einem Baum, um die Höhe des Teilbaums zu sein, der an diesem Knoten verwurzelt ist. Zuerst beachten Sie, dass ein binärer Haufen auf n Knoten n minus 1 Links hat (weil jede Verknüpfung die Muttergesellschaft eines Knotens ist und jeder Knoten eine übergeordnete Verbindung außer dem Root hat). Sinking ein Knoten der Höhe k erfordert höchstens k Austausch. Wir werden K-Links zu jedem Knoten in der Höhe k aufladen. Aber nicht unbedingt die Links auf dem Weg, wenn man den Knoten sinkt. Stattdessen berechnen wir den Knoten die K-Links auf dem Weg vom Knoten, der links-rechts-rechts-rechts - geht. Zum Beispiel wird in dem nachstehenden Diagramm der Wurzelknoten die 4 roten Verbindungen aufgeladen, wobei der blaue Knoten die 3 blauen Verbindungen und so weiter geladen wird. Beachten Sie, dass kein Link mehr als einem Knoten aufgeladen wird. (In der Tat gibt es zwei Links, die keinem Knoten zugeordnet sind: der rechte Link aus dem Root und der übergeordnete Link vom unteren rechten Knoten.) Somit ist die Gesamtzahl der Austausche höchstens n. Da es höchstens 2 Vergleiche pro Umtausch gibt, beträgt die Anzahl der Vergleiche höchstens 2 n. Kreativprobleme Berechnungszahlentheorie Schreiben Sie ein Programm CubeSum. java, das alle Integer des Formulars a 3 b 3 ausdruckt, wobei a und b ganze Zahlen zwischen 0 und N in sortierter Reihenfolge sind, ohne übermäßigen Platz zu verwenden. Das heißt, anstatt ein Array der N 2 Summen zu berechnen und zu sortieren, baut eine minimal orientierte Prioritätswarteschlange auf, die anfangs (0 3 0, 0), (1 3 1, 0), (2 3 2) , 0). (N & sub3; N, 0). Dann, während die Prioritätswarteschlange nicht leer ist, entfernen Sie das kleinste Element (i 3 j 3. i, j), drucken Sie es und dann, wenn j 3 (j1) 3. i, j1). Verwenden Sie dieses Programm, um alle verschiedenen Integer a, b, c und d zwischen 0 und 106 zu finden, so dass ein 3 b 3 c 3 d 3. z. B. 1729 93 103 13 123. Finden Sie das Minimum. Füge eine Min () - Methode zu MaxPQ. java hinzu. Ihre Umsetzung sollte konstante Zeit und konstanten zusätzlichen Platz verwenden. Lösung Fügen Sie eine zusätzliche Instanzvariable hinzu, die auf den minimalen Eintrag verweist. Aktualisiere es nach jedem Aufruf zum Einfügen (). Setzen Sie es auf Null zurück, wenn die Prioritätswarteschlange leer ist. Dynamisch-mediane Suche. Entwerfen Sie einen Datentyp, der Insert in logarithmischer Zeit unterstützt, den Median in konstanter Zeit finden und den Median in logarithmischer Zeit entfernen. Lösung Halten Sie den Medianschlüssel in v verwenden Sie einen max-orientierten Haufen für Schlüssel weniger als die Taste von v verwenden Sie eine min-orientierte Haufen für Schlüssel größer als die Taste von v. Um einzufügen, fügen Sie den neuen Schlüssel in den entsprechenden Haufen, ersetzen v mit Der Schlüssel aus diesem Haufen extrahiert. Untere Grenze Beweisen Sie, dass es unmöglich ist, eine Implementierung der MinPQ API zu entwickeln, so dass sowohl die Einfügung als auch die Minimierungsgarantie für die Verwendung von N log log N vergleicht. Lösung. Dies würde einen N-Log-Log-N-Vergleichs-basierten Sortieralgorithmus ergeben (die N Items einfügen und dann das Minimum wiederholt entfernen), wobei der Satz von Abschnitt 2.3 verletzt wird. Index-Prioritäts-Warteschlange-Implementierung. Implementieren Sie IndexMaxPQ. java, indem Sie MaxPQ. java wie folgt ändern: Ändern Sie pq, um Indizes zu halten, fügen Sie ein Array-Schlüssel hinzu, um die Schlüsselwerte zu halten, und fügen Sie ein Array hinzu qp das ist das Inverse von pq mdash qpi gibt die Position von i in pq (die Index j, so dass pqj i ist). Ändern Sie dann den Code, um diese Datenstrukturen zu pflegen. Verwenden Sie die Konvention, dass qpi -1 ist, wenn ich nicht in der Warteschlange ist und eine Methode enthält (), die diese Bedingung testet. Sie müssen die Helper-Methoden exch () und weniger () aber nicht sinken () oder schwimmen () ändern. Web-Übungen Bester, durchschnittlicher und schlimmster Fall von Heapsort. Was ist der beste Fall, durchschnittliche Fall und schlimmsten Fall Anzahl der Vergleiche für Haufen eines Arrays der Länge N Lösung. Wenn wir Duplikate zulassen, ist der beste Fall die lineare Zeit (N gleiche Schlüssel), wenn wir Duplikate nicht zulassen, der beste Fall ist N lg N vergleicht (aber der beste Fall Eingang ist nichttrivial). Die durchschnittliche und schlechteste Fallzahl der Vergleiche beträgt 2 N lg N vergleicht. Siehe die Analyse von Heapsort für Details. Der beste und schlimmste Fall der Heapate. Was ist die am wenigsten und die meisten Zahlen, die erforderlich sind, um eine Reihe von N Items Solution zu heapifizieren. Das Heapifizieren eines Arrays von N Items in absteigender Reihenfolge erfordert 0 Austausche und N - 1 vergleicht. Das Heapifizieren eines Arrays von N Items in aufsteigender Reihenfolge erfordert N Austausche und 2N vergleicht. Taxikennummern Finden Sie die kleinsten ganzen Zahlen, die als die Summe der Würfel der Ganzzahlen auf zwei verschiedene Arten (1.729), drei verschiedene Arten (87.539.319), vier verschiedene Arten (6,963,472,309,248), fünf verschiedene Wege (48,988,659,276,962,496) und sechs verschiedene Arten (24,153,319,581,254,312,065,344) ausgedrückt werden können ). Solche Ganzzahlen heißen Taxicab-Nummern nach der berühmten Ramanujan-Geschichte. Die kleinsten ganzen Zahlen, die als die Summe der Würfel der ganzen Zahlen auf sieben verschiedene Arten ausgedrückt werden können, sind derzeit unbekannt. Schreiben Sie ein Programm Taxicab. java, das in einem Befehlszeilenparameter N liest und alle nichttrivialen Lösungen eines 3 b 3 c 3 d 3 ausdruckt, so dass a, b, c und d kleiner oder gleich N sind. Computational Zahlentheorie Finden Sie alle Lösungen für die Gleichung a 2b 2 3c 3 4d 4, für die a, b, c und d weniger als 100.000 sind. Hinweis. Benutze einen kleinen Haufen und einen maximalen Haufen. Interruptbehandlung. Bei der Programmierung eines Echtzeit-Systems, das unterbrochen werden kann (z. B. per Mausklick oder drahtloser Verbindung), ist es notwendig, die Interrupts sofort zu beachten, bevor Sie mit der aktuellen Aktivität fortfahren. Wenn die Interrupts in derselben Reihenfolge behandelt werden sollen, kommen sie an, dann ist eine FIFO-Warteschlange die entsprechende Datenstruktur. Wenn jedoch unterschiedliche Interrupts unterschiedliche Prioritäten haben (z. B.), dann brauchen wir eine Prioritätswarteschlange. Simulation von Warteschlangen. MM1-Warteschlange für doppelte parallele Warteschlangen, etc. Schwierig, komplexe Warteschlangen-Netzwerke mathematisch zu analysieren. Verwenden Sie stattdessen die Simulation, um die Verteilung der Wartezeiten usw. zu verknüpfen. Benötigen Sie die Prioritätswarteschlange, um festzustellen, welches Ereignis als nächstes verarbeitet werden soll. Zipf-Verteilung Verwenden Sie das Ergebnis der vorherigen Übung (en), um aus der Zipfian-Verteilung mit den Parametern s und N abzutasten. Die Verteilung kann ganzzahlige Werte von 1 bis N annehmen und nimmt den Wert k mit der Wahrscheinlichkeit 1ks Summe (i 1 bis N) 1 an . Beispiel: Worte in Shakespeares spielen Hamlet mit s ungefähr gleich 1. Zufälliger Prozess. Beginne mit N Bins, jeder bestehend aus einem Ball. Zufällig wählen Sie eine der N Bälle und bewegen Sie den Ball zu einem Bin zufällig, so dass die Wahrscheinlichkeit, dass ein Ball in einem Bin mit m Kugeln platziert wird, ist mN. Was ist die Verteilung der Kugeln, die nach vielen Iterationen resultieren Verwenden Sie die oben beschriebene Stichprobenmethode, um die Simulation effizient zu machen. Nächste Nachbarn. Angesichts der N-Vektoren x 1. X 2 X N der Länge M und ein anderer Vektor x der gleichen Länge, finden die 20 Vektoren, die am nächsten zu x sind. Kreis auf einem Stück Papier gezeichnet. Schreiben Sie ein Programm, um den Radius eines Kreises zu finden, der auf den Ursprung zentriert ist und 32 Punkte mit ganzzahligen x - und y-Koordinaten berührt. Hinweis: Suchen Sie nach einer Zahl, die als die Summe von zwei Quadraten auf verschiedene Weise ausgedrückt werden kann. Antwort: Es gibt zwei pythagoreische Tripel mit Hypotenuse 25: 152 202 252, 72 242 252, die 20 solcher Gitterpunkte ergeben, es gibt 22 verschiedene pythagoreische Triples mit Hypotenuse 5,525, was zu 180 Gitterpunkten führt. 27.625 ist der kleinste radius, der mehr als 64 berührt. 154.136.450 hat 35 pythagoreische triples. Perfekte Kräfte. Schreiben Sie ein Programm PerfectPower. java, um alle perfekten Kräfte auszudrucken, die als 64-Bit lange Integer dargestellt werden können: 4, 8, 9, 16, 25, 27. Eine perfekte Leistung ist eine Zahl, die als ab für ganze Zahlen geschrieben werden kann Und b ge 2. Fließkomma-Additionen. Hinzufügen von N Gleitkommazahlen, Vermeidung von Rundungsfehlern. Löschen Sie die kleinsten zwei: fügen Sie zwei hinzu und setzen Sie sie wieder ein. Erstbezug für Behälterverpackung. 1710 OPT 2, 119 OPT 4 (absteigend). Verwenden Sie den maximalen Turnierbaum, in dem die Spieler N Bins und die verfügbare Kapazität sind. Stack mit minmax. Entwerfen Sie einen Datentyp, der Push, Pop, Größe, Min und Max unterstützt (wobei min und max die minimalen und maximalen Elemente auf dem Stack sind). Alle Operationen sollten im schlimmsten Fall konstant sein. Hinweis: Verknüpfen Sie mit jedem Stapeleintrag die minimalen und maximalen Positionen, die sich derzeit auf dem Stapel befinden. Warteschlange mit minmax. Entwerfen Sie einen Datentyp, der Enqueue, Dequeue, Größe, Min und Max unterstützt (wobei min und max die minimalen und maximalen Punkte in der Warteschlange sind). Alle Operationen sollten konstant zeitgeschrieben werden. Hinweis: mach die vorherige Übung und simuliere eine Schlange mit zwei Stapeln. 2i 5j Drucknummern des Formulars 2i 5j in aufsteigender Reihenfolge. Min-Max-Haufen. Entwerfen Sie eine Datenstruktur, die min und max in konstanter Zeit unterstützt, einfügen, min löschen und max in logarithmischer Zeit löschen, indem Sie die Elemente in ein einzelnes Array der Größe N mit den folgenden Eigenschaften setzen: Das Array stellt einen vollständigen Binärbaum dar. Der Schlüssel in einem Knoten auf einer gleichmäßigen Ebene ist kleiner als (oder gleich) der Schlüssel in seinem Teilbaum der Schlüssel in einem Knoten auf einer ungeraden Ebene ist größer als (oder gleich) die Tasten in seinem Teilbaum. Beachten Sie, dass der Maximalwert am Root gespeichert ist und der Minimalwert bei einer der Wurzeln children. Lösung gespeichert wird. Min-Max Heaps und Generalized Priority Queues Bereich Mindestabfrage. Bei einer Sequenz von N Items ist eine minimale Abfrage von Index i bis j der Index des minimalen Elements zwischen i und j. Entwerfen einer Datenstruktur, die die Sequenz von N Elementen in linearer Zeit vorverarbeitet, um die Mindestabfragen in logarithmischer Zeit zu unterstützen. Beweisen Sie, dass ein vollständiger Binärbaum mit N Knoten genau Decke (N2) Blattknoten (Knoten ohne Kinder) hat. Maximale Prioritätswarteschlange mit min. Was ist die Reihenfolge des Wachstums der Laufzeit, um einen minimalen Schlüssel in einem maximal-orientierten Binärhaufen zu finden. Lösung Linearmdashthe minimale Schlüssel könnte in jedem der Decke (N2) Blattknoten sein. Maximale Prioritätswarteschlange mit min. Entwerfen Sie einen Datentyp, der Insert-und Remove-the-Maximum in logarithmischen Zeit zusammen mit sowohl max ein min in konstanter Zeit unterstützt. Lösung. Erstellen Sie einen max-orientierten Binärhaufen und speichern Sie auch den bislang eingesetzten Minimalschlüssel (der niemals erhöht wird, wenn dieser Haufen nicht leer wird). Kth größtes Element größer als x. Bei einem maximal orientierten Binärhaufen entwerfen Sie einen Algorithmus, um zu bestimmen, ob das k-te größte Element größer oder gleich x ist. Ihr Algorithmus sollte zeitlich proportional zu k laufen. Lösung Wenn der Schlüssel im Knoten größer oder gleich x ist, rekursiv sowohl den linken Teilbaum als auch den rechten Teilbaum durchsuchen. Stoppen, wenn die Anzahl des erforschten Knotens gleich k ist (die Antwort ist ja) oder es gibt keine weiteren Knoten zu erkunden (nein). Kth kleinste Artikel in einem min-orientierten Binärhaufen. Entwerfen Sie einen k log k Algorithmus, um das kth kleinste Element in einem min-orientierten Binärhaufen H zu finden, der N Items enthält. Lösung. Bauen Sie einen neuen, min-orientierten Haufen H. Wir werden nicht ändern H. Legen Sie die Wurzel von H in H zusammen mit seinem Heap-Index 1. Jetzt wiederholen Sie die minimale Item x in H und legen Sie in H die beiden Kinder von x aus H Das k-te Element aus H ist das kth kleinste Element in H. Randomized Warteschlange. Implementieren Sie eine RandomQueue, so dass jede Operation garantiert wird, um höchstens logarithmische Zeit zu nehmen. Hinweis. Kann sich nicht verdoppeln. Kein einfacher Weg mit verknüpften Listen, um ein zufälliges Element in O (1) Zeit zu lokalisieren. Verwenden Sie stattdessen einen vollständigen Binärbaum mit expliziten Links. FIFO-Warteschlange mit zufälliger Löschung. Implementieren Sie einen Datentyp, der die folgenden Operationen unterstützt: Einfügen eines Elements. Löschen Sie den Artikel, der zuletzt hinzugefügt wurde. Und löschen Sie ein zufälliges Einzelteil. Jede Operation sollte im schlimmsten Fall (höchstens) logarithmische Zeit nehmen. Lösung Verwenden Sie einen vollständigen Binärbaum mit expliziten Links, um die lange Integer-Priorität i dem i-ten Element zuzuordnen, das der Datenstruktur hinzugefügt wurde. Top k Summen von zwei sortierten Arrays. Bei zwei sortierten Arrays a und b, jeder der Länge N, finden Sie die größten k Summen der Form ai bj. Hinweis. Mit einer Prioritäts-Warteschlange (ähnlich dem Taxicab-Problem) können Sie einen O (k log N) - Algorithmus erreichen. Überraschenderweise ist es möglich, es in O (k) Zeit zu tun, aber der Algorithmus ist kompliziert. Empirische Analyse des Haufenaufbaus. Empirisch vergleichen die linear-time-bottom-up-Heap-Konstruktion gegenüber der naiven linearithmischen Zeit-Top-Down-Heap-Konstruktion. Achten Sie darauf, es über eine Reihe von Werten von N. LaMarca und Ladner zu berichten, dass aufgrund der Cache-Lokalität der naive Algorithmus in der Praxis besser ausführen kann als der cleverere Ansatz für große Werte von N (wenn der Haufen nicht mehr in die Cache), obwohl die letzteren führt viele weniger Vergleich und Austausch. Empirische Analyse von Mehrwegehaufen. Empirisch vergleichen die Leistung von 2- 4- und 8-Wege-Haufen. LaMarca und Ladner schlagen mehrere Optimierungen vor, unter Berücksichtigung von Caching-Effekten. Empirische Analyse von Haufen. Empirisch vergleichen die Leistung von 2- 4- und 8-Wege-Heapsort. LaMarca und Ladner schlagen mehrere Optimierungen vor, unter Berücksichtigung von Caching-Effekten. Ihre Daten zeigen, dass ein optimierter (und speicherabgestimmter) 8-Wege-Heapsort doppelt so schnell sein kann wie der klassische Heapsort. Heapify durch Einfügungen. Angenommen, Sie bündeln einen Binärhaufen auf N-Tasten, indem Sie den nächsten Schlüssel wiederholt in den Binärhaufen einfügen. Zeigen Sie, dass die Gesamtzahl der Vergleiche höchstens Antwort ist. Die Anzahl der Vergleiche beträgt höchstens lg 1 lg 2. Lg N lg (N) N lg N. Heapify untere Grenze. (Gonnet und Munro) Zeigen Sie, dass jeder vergleichbasierte Algorithmus für den Aufbau eines binären Haufens auf N Tasten mindestens 1.3644 N im schlimmsten Fall hat. Antworten . Verwenden Sie ein Informationstheoretisches Argument, ala Sortierung untere Grenze. Es gibt N mögliche Haufen (Permutation der N Integers) auf N verschiedenen Tasten, aber es gibt viele Haufen, die der gleichen Reihenfolge entsprechen. Zum Beispiel gibt es zwei Haufen (c a b und c b a), die den 3 Elementen entsprechen. Für einen guten Überblick über sequentielle Musterabbau-Algorithmen können Sie dieses Umfragepapier lesen. (Fournier-Viger et al., 2016a) für den Abbau von häufigen periodischen Mustern in einer Folge von Transaktionen (eine Transaktionsdatenbank)) der PHM-Algorithmus (Fournier-Viger et al., 2016b.). Der PHM-Algorithmus (Fournier-Viger et al., 2016b) ) Für den Abbau von periodischen Hochleistungsmustern (periodische Muster, die einen hohen Gewinn erzielen) in einer Folge von Transaktionen (eine Transaktionsdatenbank), die Dienstprogramminformationen enthalten. High-Utility Pattern Mining Association Rule Mining ein Algorithmus zum Abbau aller Assoziationsregeln in einer Transaktionsdatenbank ( Aggressal amp Srikant, 1994) ein Algorithmus für die Abbau aller Assoziationsregeln mit der Liftmaßnahme in einer Transaktionsdatenbank (angepasst von Agrawal amp Srikant, 1994), einen Algorithmus zum Abbau der IGB-informativen und generischen Basis von Assoziationsregeln in einer Transaktionsdatenbank (Gasmi et Al. 2005) ein Algorithmus für den Abbau von vollkommen sporadischen Assoziationsregeln (Koh amp Roundtree, 2005) ein Algorithmus für den Abbau geschlossener Assoziationsregeln (Szathmary et al. 2006). Ein Algorithmus für den Mining minimaler nicht redundanter Assoziationsregeln (Kryszkiewicz, 1998), der Indirekte Algorithmus für den Abbau von indirekten Assoziationsregeln (Tan et al. 2000 Tan et 2006), den FHSAR-Algorithmus zum Verstecken sensibler Assoziationsregeln (Weng et al. 2008), dem TopKRules-Algorithmus (Fournier-Viger, 2012b. Powerpoint) Der TNR-Algorithmus für die Mining-Top-k-nicht-redundanten Assoziationsregeln (Fournier-Viger 2012d. Powerpoint) Clustering des ursprünglichen K-Means-Algorithmus (MacQueen, 1967) Die Algorithmen von Bisecting K-Means (Steinbach et al., 2000) für die Dichte-basierte Clusterung des DBScan-Algorithmus (Ester et al., 1996), der Optik-Algorithmus, um eine Cluster-Reihenfolge von Punkten zu extrahieren, die dann zur Erzeugung von DBScan-Style-Clustern verwendet werden können Und mehr (Ankerst et al, 1999) ein hierarchischer Clustering-Algorithmus ein Tool namens Cluster Viewer für die Visualisierung von Clustern ein Tool namens Instance Viewer für die Visualisierung der Eingabe von Clustering-Algorithmen Zeitreihen-Mining ein Algorithmus für die Berechnung der gleitenden Durchschnitt einer Zeitreihe (zu entfernen Rauschen) ein Algorithmus zur Berechnung der stückweise aggregierten Approximation einer Zeitreihe (zur Reduzierung der Anzahl von Datenpunkten einer Zeitreihe) ein Algorithmus zur Aufteilung von Zeitreihen in Segmente einer gegebenen Länge ein Algorithmus zur Aufteilung von Zeitreihen in eine gegebene Anzahl von Segmentiert den SAX-Algorithmus für die Umwandlung einer Zeitreihe in eine Sequenzdatenbank (um traditionelle Algorithmen für den sequentiellen Regelabbau und den sequentiellen Musterabbau auf Zeitreihen anzuwenden) (Lin et al. 2007) ein Tool namens Time Series Viewer zur Visualisierung von Zeitreihen Außerdem ist es auch möglich, die meisten Clustering-Algorithmen, die in SPMF (K-Means, Bisecting K-Means, DBScan, OPTICS, Hierarchical Clustering) angeboten werden, auf Zeitreihen anzuwenden. Klassifizierung des ID3-Algorithmus für den Aufbau von Entscheidungsbäumen (Quinlan, 1986) Textabbau ein Algorithmus zur Klassifizierung von Textdokumenten unter Verwendung eines Naive Bayes-Klassifikatoransatzes (S. Raghu, 2015) ein Algorithmus für Clustering-Texte mit dem tfidf-Maß (S. Raghu, 2015) Datenstrukturen Ein Werkzeug zur Erstellung einer synthetischen Transaktionsdatenbank Ein Werkzeug zur Erzeugung einer synthetischen Sequenzdatenbank Ein Werkzeug zur Erzeugung einer synthetischen Sequenzdatenbank mit Zeitstempeln Ein Werkzeug zur Berechnung von Statistiken über eine Transaktionsdatenbank Ein Werkzeug zur Berechnung von Statistiken über eine Sequenzdatenbank Ein Werkzeug zum Umwandeln Eine Sequenzdatenbank zu einer Transaktionsdatenbank Ein Werkzeug zum Konvertieren einer Transaktionsdatenbank in eine Sequenzdatenbank Ein Werkzeug zum Konvertieren einer Textdatei in eine Sequenzdatenbank (jede Sätze wird eine Sequenz) Ein Werkzeug zum Konvertieren einer Sequenzdatenbank in verschiedenen Formaten (CSV, KOSARAK , BMS, IBM.) Zu einer Sequenz-Datenbank im SPMF-Format Ein Tool zum Konvertieren einer Transaktionsdatenbank in verschiedenen Formaten (CSV. ) to a transaction database in SPMF format A tool for converting time-series to a sequence database A tool to generate utility values for a transaction database A tool to add timestamps to a sequence database A tool for removing utility information from a database having utility information A tool to resize a database in SPMF format (a text file) using a percentage of lines of data from an original database. A tool for visualizing time-series Visual map of algorithms You can visualize the relationship between the various data mining algorithms offered in SPMF by clicking on this map (last updated. 20150912 - SPMF 0.97) :In 1986 I made a computer model of coordinated animal motion such as bird flocks and fish schools. It was based on three dimensional computational geometry of the sort normally used in computer animation or computer aided design. I called the generic simulated flocking creatures boids. The basic flocking model consists of three simple steering behaviors which describe how an individual boid maneuvers based on the positions and velocities its nearby flockmates: Separation . steer to avoid crowding local flockmates Alignment . steer towards the average heading of local flockmates Cohesion . steer to move toward the average position of local flockmates Each boid has direct access to the whole scenes geometric description, but flocking requires that it reacts only to flockmates within a certain small neighborhood around itself. The neighborhood is characterized by a distance (measured from the center of the boid) and an angle, measured from the boids direction of flight. Flockmates outside this local neighborhood are ignored. The neighborhood could be considered a model of limited perception (as by fish in murky water) but it is probably more correct to think of it as defining the region in which flockmates influence a boids steering. a boids neighborhood A slightly more elaborate behavioral model was used in the early experiments. It included predictive obstacle avoidance and goal seeking. Obstacle avoidance allowed the boids to fly through simulated environments while dodging static objects. For applications in computer animation, a low priority goal seeking behavior caused the flock to follow a scripted path. In cooperation with many coworkers at the Symbolics Graphics Division and Whitney Demos Productions, we made an animated short featuring the boids model called Stanley and Stella in: Breaking the Ice . This film was first shown at the Electronic Theater at SIGGRAPH 87. There was a technical paper on boids published at the same conference. In the course notes for SIGGRAPH 88 there was an informal paper about obstacle avoidance. Since 1987 there have been many other applications of the boids model in the realm of behavioral animation. The 1992 Tim Burton film Batman Returns was the first. It contained computer simulated bat swarms and penguin flocks which were created with modified versions of the original boids software developed at Symbolics. Andy Kopra (then at VIFX , which later merged with Rhythm amp Hues ) produced realistic imagery of bat swarms. Andrea Losch (then at Boss Films) and Paul Ashdown created animation of an army of penguins marching through the streets of Gotham City. As luck would have it, Chris Langton organized the original ground-breaking Artificial Life Workshop a few months after the boids paper was published in 1987. A helpful go-between got word to Chris and he let me give an informal presentation on boids at the Workshop. The boids model has become an oft-cited example of principles of Artificial Life. Flocking is a particularly evocative example of emergence: where complex global behavior can arise from the interaction of simple local rules. In the boids model (and related systems like the multi-agent steering behavior demos ) interaction between simple behaviors of individuals produce complex yet organized group behavior. The component behaviors are inherently nonlinear, so mixing them gives the emergent group dynamics a chaotic aspect. At the same time, the negative feedback provided by the behavioral controllers tends to keep the group dynamics ordered. The result is life-like group behavior. A significant property of life-like behavior is unpredictability over moderate time scales. For example at one moment, the boids in the applet above might be flying primarily from left to right. It would be all but impossible to predict which direction they will be moving (say) five minutes later. At very short time scales the motion is quite predictable: one second from now a boid will be traveling in approximately the same direction. This property is unique to complex systems and contrasts with both chaotic behavior (which has neither short nor long term predictability) and ordered ( static or periodic ) behavior. This fits with Langtons 1990 observation that life-like phenomena exist poised at the edge of chaos. The boids model is an example of an individual-based model. a class of simulation used to capture the global behavior of a large number of interacting autonomous agents. Individual-based models are being used in biology, ecology, economics and other fields of study. Note that the straightforward implementation of the boids algorithm has an asymptotic complexity of O(n 2 ). Each boid needs to consider each other boid, if only to determine if it is not a nearby flockmate. However it is possible to reduce this cost down to nearly O(n) by the use of a suitable spatial data structure which allows the boids to be kept sorted by their location. Finding the nearby flockmates of a given boid then requires examining only the portion of the flock which is within the general vicinity. Using such algorithmic speed-ups and modern fast hardware, large flocks can be simulated in real time, allowing for interactive applications. new Online resources related to boids Other computational models of group motion Computer animation Eurythmy by Susan Amkraut and Michael Girard contained the first procedural animation of flocks when it was shown at the Film amp Video Show of SIGGRAPH 85. It is available on SIGGRAPH Video review (SVR Issue 21, Entry 2). Some imagery from the final version appear on this page from Ars Electronica 89 . Amkraut and Girard also created flocking and herding in the 1993 VR production Menagerie . Jessica Hodgins and colleagues at Georgia Techs GVU have created several physically-based models of group behaviors such as herding one-legged hoppers and a pack of bicyclists. Disneys The Lion King (1994) included a wildebeest stampede by Kiran Joshi, MJ Turner, et al. . Here are two stampede-related items from Brian Tiemanns excellent The Lion King WWW Archive. Lion King production notes (search for second occurrence of stampede ) Stampede sequence (QuickTime Movie, 21.9 MB. Also available as low res QT (1.2 MB) and MPEG1 (28.7 MB)) Xiaoyuan Tu implemented a realistic, physically-based model of fish schooling as part of her dissertation research on artificial animals. See also: Tu and Terzopoulos. Artificial Fishes: Physics, Locomotion, Perception, Behavior , ACM Computer Graphics, Proceedings of SIGGRAPH94, July 1994. A non-technical article called Fishes of the Silicon Sea. by Gene Levinson which appeared in The World amp I Magazine. While at Santa Barbara Studios, Mark Wendell used the Dynamation particle system software to create animation of flocking space creatures for Elogium an episode of Star Trek: Voyager . Course CS206 at George Washington University includes an assignment to implement a Behavioral Motion Control System like boids. You can see some of the students animations from: 1997. 1998 and 1999. new Games, Interactive graphics and virtual reality Rip-Off (1980) a video arcade game designed by Tim Skelly featured a group of three autonomous enemy tanks which exhibited coordinated group motion. They avoided collisions with each other and would seek the goal objects (canisters), or if they got too close, the player controlled vehicles. The combination of goal seeking and collision avoidance produced a motion like flocking. For more details, read Tim Skellys own description of the behavior. See also this Rip-Off screenshot and this page about an emulator. new Plasm: A Fish Sample (1985) by PeterBroadwell . Rob Myers. Robin Schaufler, Eva Manolis. et al., premiered at the SIGGRAPH 85 art show. On at least one occasion, a school accidentally arose in this virtual fish tank. Parallel Bird Flocking Simulation (1993) by Helmut Lorek and Matthew White. Describes an implementation of boids using up to 50 parallel Transputer processors to simulate flocks of up to 100 boids at interactive rates (6 frames per second or better). The simulation included obstacle avoidance. The full article is available in PDF. new The Virtual Fishtank introduces visitors to the sciences of complexity, artificial life and related fields. It is an online version of a project that started as an installation at The Computer Museum in Boston. Its goal is to introduce visitors to the sciences of complexity and artificial life. The original project was jointly developed by the MIT Media Lab (see their project page) and NearLife Inc. (see their recent projects page). Virtual Great Barrier Reef. A theoretical approach towards an evolving, interactive VR environment using a distributed DOME and CAVE System (1998) by Scot Thrane Refsland. Takeo Ojika. Tom Defanti. Andy Johnson. Jason Leigh. Carl Loeffler. and Xiaoyuan Tu in Proceedings of Virtual Worlds 98. Paris, France, July 1-3, 1998. Also available in PDF . Robotics Maja Mataric heads The Interaction Lab at the University of Southern California which studies robotic group behaviors. See also Majas dissertation and these videos of robots performing various group behaviors, including flocking. (Some press clippings from WIRED and CNN. And see this delightful story about Maja (the second paragraph)) Cooperative Mobile Robotics: Antecedents and Directions by Y. Uny Cao, Alex S. Fukunaga, and Andrew B. Kahng (UCLA 1996) surveys research in robot groups. The Robot Sheepdog Project by Richard Vaughan et al. provides an interesting contrast to much of the work cited on this page: the flockingherding involved is of natural animals while a robot plays a role similar to a sheepdog. As is done when training real sheepdogs, ducks are used here as a less challenging stand-in for sheep. Read the delightful paper for more detail. See also Neil Sumpter s pages about the vision research related to robo-sheepdog. The Examination and Exploration of Algorithms and Complex Behaviour to Realistically Control Multiple Mobile Robots (1997) by Duncan Crombie. examines algorithms to control multiple mobile robots, focuses on behaviors that can be obtained through local control, and demonstrates createing complex behaviours with simple algorithms. new Self-Organization in Large Populations of Mobile Robots (1993) by Cem Uumlnsal Describes the use of a homogeneous population of robots, an Army-ant swarm, for transportation of material. Investigates both spatial and behaviroal self-organization. new Social Behavior in The Ants a community of cubic-inch microrobots which form a structured robotic community capable of task such as clustering, following the leader, and playing tag. new Distributed Ant Robotics a collection of publication and resources by Israel Wagner new Collective Locomotion (1998) by Pierre Arnaud of the LAMI Collective Robotics Group. Includes papers and Labot. a Java demonstation applet. new Calculating Swarms (2000) by Ivars Peterson (in Science News ) discusses swarm intelligence, emergent computation and collective robotics. new Aerospace (coordinated groups of aircraft or spacecraft) Subsumptive Architecture of Populous Satellite Constellations (1995) by Brian J. Mork discusses potential applications and designs for groups of reactive communicating satellites: design goals are embedded in the constellation rather than individual satellites, and the constellation exhibits emergent behavior. new Solar-Powered Ultralight Aircraft Designed To Fly in Formation (1996) describes early test of a potential fleet of solar-powered autonomous aircraft that fly at high altitude in V formations like geese, and this press release of the test flight of a prototype. Birds Inspire Formation-Flying Satellites (1999), US Air Force press release describing the US AFRLs Technology Satellite of the 21st Century (TechSat 21 ) program, including plans for a system of formation-flying satellites that can quickly adapt to rapidly changing mission requirements. See also Space Missions Using Satellite Clusters. new Education (about distributed and complex systems) Mitchel Resnick developed StarLogo a programmable modeling environment for exploring the behaviors of decentralized systems such as bird flocks, traffic jams, and ant colonies. For more information see Mitchels book Turtles, Termites, and Traffic Jams OK, while not strictly a computational model of group motion, Schools are for Fish is a collection of participatory activities for young students to help them learn about group motion and complex systems. Artificial life and Evolutionary computation (Not) Evolving Collective Behaviours in Synthetic Fish by Nahum Zaera, Dave Cliff. and Janet Bruten. Published in From Animals to Animats 4 (SAB96) . An Investigation Into Computational Flocking Techniques (1999) by Phil Pocknell investigates flocking (herding) under the influence of a predator. Specifically, it models a situation very much like the interaction between a sheep-dog and a flock of sheep, such as in a sheep-dog trial. See the Tadpoids applet, and the related Pest Control applet. new Behavioural Simulation in Voxel Space (1997) by Hongwen Zhang and Brian Wyvill uses as its example a group of butterflies navigating by olfactory sensors. Based on Zhangs 1996 Ph. D. thesis. See the full paper in PDF. new Art As part of this MFA work, Terry Franguiadakis created a virtual reality art piece called Swallows of Capistrano which included a flock of swallows that would fly over to eat food dispensed from the users 3d wand. At SIGGRAPH 93 Ken Rinaldo s Emergent Systems presented The Flock. a robotic art installation composed of reactive sculptural and musical elements. EIDEA ( Environment for the Interactive Design of Emergent Art . by John Mitchell and Robb Lovell ) is an art piece based on artificial life which includes a flock of birds. An art piece called A Flock of Words by Doris Vila. Robert Rowe and Eric L. Singer. performed at NYU in 1995, and another version installed that same year in Bonn under the title Opera Clones. It was also presented at the SIGGRAPH 96 Applications venue. Emergence is the system underlying the 1997 and 1998 installations known as The Bush Soul by Rebecca Allen et al. This interactive 3D world is full of autonomous objects and characters, including flock-like groups. Biology Ornithologist Frank Heppner and mathematician Ulf Grenander describe a model of flocking and roosting in A Stochastic Nonlinear Model for Coordinated Bird Flocks (1990) appearing in The Ubiquity of Chaos edited by Saul Krasner. The EcoTools project uses individual-based models to study animal behavior and ecological issues. Models of schooling fish and flocking birds have been created in EcoTools. There is also a Java-based fish school simulation at this site. Physics Tamaacutes Vicsek published an analysis of flocking particles in Physical Review Letters on August 7, 1995, which focused on transitions in collective behavior. (I will provide a more complete description here when I better understand Prof. Vicseks work.) J Dana Eckart implemented a cellular automata model of flocking using his Cellular system based on Vicseks work. Work by Yu-hai Tu and John Toner published in Physical Review Letters (Volume 75, page 4326, December 4, 1995) includes a proof that motion of a flock or herd is essential to its collective ability to align. That is, group alignment is not possible with local perception in the absence of motion. Surprises in Nonequilibrium Critical Phenomena: From Flocking Dynamics to Chemical Reactions (0.7 MB gzipped Postscript) by Yu-hai Tu presented at the 1996 Santa Fe Workshop on Nonequilibrium Phase Transitions . Flocks, Herds, and Schools: A quantitative theory of flocking by Toner and Tu in Physical Review E, October 1998, Volume 58, Issue 4, pp. 4828-4858. See the AIP summary: Birds of a Feather: The Physics of Flocks. this summary from Academic Press. and this article from Newsweek . Physics of Flocks (Part 1 and Part 2 ) by Karl Kruszelnicki. transcripts and audio recordings from Great Moments in Science on the Australian Broadcasting Corporation. Search, optimization and visualization techniques inspired by flocks and swarms Particle Swarm Optimization (and see the original 1995 PSO paper by James Kennedy and Russ Eberhart ) searchs a multidimensional solution space. Somewhat like a genetic algorithm, but the PSOs search points move as a swarm through the space with a velocity, altered by steering accelerations. See also this PSO demo applet . The use of Flocks to drive a Geographic Analysis Machine (1998) by James Macgill and Stan Openshaw. uses a flock model, with communication between boids, to better search for clusters in spacial datasets, just as a natural flock provides better foraging than individual birds could manage. See this demo applet. Ant Colony Optimization introduced in 1992 by Marco Dorigo . studies artificial systems that take inspiration from the behavior of real ant colonies and which are used to solve function or combinatorial optimization problems. Information Retrieval in the World-Wide Web: Making Client-based searching feasible (1994) by Paul De Bra and Reinier Post. uses a school of fish metaphor to search the web. Information Flocking by Glenn Proctor is a data visualization technique that portrays datapoints as fish that school through a 3d space, revealing correlations in the data by their motion and clustering. See the paper Information Flocking: Data Visualisation in Shared Worlds Using Emergent Behaviours (1998, PDF 91KB) by Glenn Proctor and Chris Winter. new Ant-based Load Balancing in Telecommunications Networks (1996) by Ruud Schoonderwoerd. Owen Holland. Janet Bruten and Leon Rothkrantz. See also these related links: Theres an ant in my phone (1998) by Mark Ward in New Scientist, British Telecom: Notes from the Ant Colony (1997) by Julia Flynn in BusinessWeek, and Collective Intelligence for Network Control. new Other emergent, collective behavior Amorphous Computing HomePage a research group exploring the question: How do we obtain coherent behavior from the cooperation of large numbers of unreliable parts that are interconnected in unknown, irregular, and time-varying ways new Swarm Intelligence. Payman Arabshahi s page of links on emergent computation by swarms of simple agents. new Other topics. John Mee s term report on software to simulate the movement of a flock of birds . G. Keith Still has developed a system called Legion to simulate the motion of large crowds of people. It can handle crowds of more than 100,000 people. See also these related pages. and these articles by Sheryl Canter in PC Magazine from April 1996 and May 1996 . A page of Java-based demos by the Biological Model Simulation group at Keio University. The demos are in 2d and include basic schooling, predation, interactive feeding, and schooling with two species. Animation Science Corporation sells tools to model the motion of large crowds with their Rampage software, based on an efficient engine for interacting particle systems . Daniel Bullok wrote a fishtank simulation as a class project. An introduction called Complexity and Social Behaviour and a computational model of resource-deprived termites by Octavio Miramontes A Flocking-Strategy for a programmable multi-agent shell VehicleGuide by Jan Beutler Jonathan Robbins page The Boids is the report from his Science Project -- his 8th grade Science Project, mind you. (Yikes Kids these days) Simulation of Herding with Dynamics by Howard Zhang uses a simple spring-mass model of animal bodies and simulates herding on the plane. This report contains good diagrams and descriptions of the implementation of component steering behaviors. The Computational Beauty of Nature is the web site for a book of the same name by Gary W. Flake (shop for the book here ). He implemented boids and added another rule which cause the boids to attempt to maintain a clear view ahead of them. This resulted in flocks which form the classic V formations of migrating geese. See the Java demonstration . In a class project called A-Life Foodchain Simulation Leon Blackwell extends a boid-like model to include predator-prey interactions. The Duck Pond: Following, Flocking and Herding a 1977 class project by Brian OConnor. Includes source code and animations. (Although there seem to be access problems for some of the files.) E Pluribus Unum (the January 1999 installment of Brian Hayes column on Computing Science in American Scientist ) talks about emergence using examples such as flocks, schools, herds, traffic jams, ant colonies, and forest fires. An attempt to replicate the main findings of Craig Reynoldss (1987) Boids by Harry Brignull, reports on a project to implement boids using the POPBUGS package by Chris Thornton. Includes diagrams of the resulting group motion and source code. Flocking, Boids and Tag (1998) by Aron Helser. This class project involved an interactive flock which plays the game of tag and allows the use to either ride along passively with a member of the flock, or take control and pilot the boid. new GOIDS Project a study of flocking geese objects (1999) by Cathryn J Polinsky. Presentation slides for a Senior Project called Flight Simulation of Flocking Geese Using Particle Set Animation new Natural flocks, herds, and schools Some seminal papers from the (hardcopy) literature: The Structure and Function of Fish Schools (1982) by Brian Partridge in Scientific American. June 1982, pages 114-123. The Chorus Line Hypothesis of Manoeuvre Coordination in Avian Flocks (1984) by Wayne Potts. in Nature. Volume 309, May 24, 1984, pages 344-345. Animal Groups in Three Dimensions: How Species Aggregate (1997) edited by Julia K. Parrish and William M. Hamner. A collection of papers related to a 1991 workshop on measuring and modeling animal aggregations. Use this link to shop for the book. A 22 second movie of a school of anchovies (160x120 pixels, in JPEG (1.1 Mb) and Quicktime (1.8 Mb) formats) swimming in the Kelp Forest tank at the Monterey Bay Aquarium from a page of fish videos at FINS. See also the live Kelp Cam view of this tank. Here are some other flockherdschool pictures on the web: schooling anchovies. school from below. crowded fish. orca and herring. herd of running Akhalteke. school of spadefish. Gallimimuses flock (Jurassic Park). V formation of geese. herd of wild asses. wildebeest herd. herring schooling (MPEG, 0.5 Mb) . herring school turning (MPEG, 1.0 Mb) . Temple Grandins interesting site on behavior of livestock and other subjects, contains a section on Recommended Basic Livestock Handling which covers topics such as: Understanding Flight Zone and Point of Balance Moving Cattle out of Pens and Sorting new Low Stress Methods for Moving Cattle on Pastures. new each of which contain pictures and diagrams on geometrical relationships between herds of livestock, the shapes of their enclosures, and the positions of human handlers. William H. Calvins book The Ascent of Mind discusses the predation on herds of early humans in Chapter 8: Hand-Ax Heaven (you may wish to search for the first occurance of herd ). Lessons from Geese. on the structure of migratory goose flocks, and folksy thoughts on applying these ideas to groups of humans. V formations . at the bottom of Jim Rible s page about the Canada Goose there is a discussion about the mixed evidence for an aerodynamic explanation of the V formations often seen in migrating ducks and geese. See also the cited references. A page by Uwe Kils illustrating how individual fish in a school benefit from reduced predation due to optical confusion . An essay called Migration Advantages of Shoaling by Tony J. Pritcher in his book Behaviour of Teleost Fishes describes research by Uwe Kils into the effect he calls synchrokinesis whereby small movements of individuals copied through the shoal provide an accurate movement towards better conditions. (Contrast this with the work of Toner and Tu (above) which suggests that individual errors are damped out by interaction with the rest of the group.) Vigilance, Flock Size, and Flock Geometry: Information Gathering by Western Evening Grosbeaks (1995) by Marc Bekoff a field ethology study of how the size and relative positioning of this bird affect the vigilance (scanning) behavior of individuals in the group. new Cutting horses and herding dogs . these two types of trained animal behaviors have evolved into modern sport competitions. Their origin was to assist humans raising stock animals, and they can still be found in this role today. Both are related to herding behavior in special ways. The job of a herding dog (stockdog, sheepdog) is to help a shepherd contain and control a herd of stock animals (especially sheep, goats or cattle). A herding dog uses its understanding of the stock animals herding behavior to be able to move the whole group as a unit. For more information see: The Stockdog Server. Dog-Play: Herding and The Herding Page new The cutting horse derived from the American cowboy culture and is specifically trained to handle cattle. A cutting horses skill is in being able to defeat the cattles herding instinct, allowing it to separate off (cut) one individual at a time. The site of the National Cutting Horse Association includes history and videos of the sport. new (There is additional source code for Java implementations listed on the boids applet page .) Boids This is the original 1986-1988 implementation, written in Symbolics Common Lisp, and based on Symbolics S-Geometry 3d modeling system and S-Dynamics animation system. (Modern versions of those applications are available from Winged Edge Technologies. see: Mirai Modeling and Mirai Animation. Your browser may not recognize this file as Lisp source code and try to reformat it as filled text. If so use View Page Source or equivalent, or download the file.) C Boids This platform-independent boids implementation by Christopher Kline includes C source code and an Inventor-based binary executable demo for SGI machines. These boids support both flocking and obstacle avoidance. Buzzz An After Dark screen saver module for Macintosh computers by Simon Fraser. This very nice package implements a parameterized version of boids including several species of creatures (wasps, birds, fish, sheep. ) based on altering the parameters. There are control panels that allow you to experiment with the parameters. For other sources of this software see Simons AD page. boids. exe by Juumlrgen Schmitz. Version 1.0 of a Windows application featuring three distinct species of flocking birds and nice control panels for adjusting their parameters. See the readme file for more information. SchoolView This is a screen saver for NeXT computers by David Lambert based on the boids model. C code and related files are available for FTP. See the readme file for details. A-Quarium A screen saver for Windows by Ric Colasanti. A-Quarium is a fish tank simulator somewhat related to boids. . a fish will try to swim with a close neighbour if it is of the same species, and will try to swim away if it is of a different species. The behaviour of the fish tank is an emergent property of all the individual fish actions. Max Boids There is an implementation of boids for MAX. an interactive real-time graphic programming environment, from IRCAM and Opcode. Boppers This Windows 3.1 software originally accompanied the book Artificial Life Lab by Rudy Rucker. Waite Group Press, 1993, now out of print. It includes an implementation of boids and related ALife models. Imagine Flock 3D A commercial IPAS plug-in for 3D Studio from CBL Technology. Stones Mac Boids This is an application for a PowerPC Macintosh using QD3D. Other versions exist for 68000 Macs with FPU, and as After Dark modules. See the main page by Stone (Ishihama Yoshiaki) for other alife-related Mac and Java software. MatFas Boids 0.1 Mattias Fagerlund wrote this very nice 2D implementation of boids for Windows 95 or WindowsNT and provides both executable and source code. A screen shot on the web page shows the interactive slider controls and a large flock flying around several obstacles. Boids: DirectX Flocking Sample A boids implementation by Stephen Coy has been included in the DirectX sample code since version 5. Stephen suggests that better source code is included with DMBoids the DirectMusic demo based on boids. Boids for Apprentice A boids demo based on Christopher Klines implementation (see above) is included in Eric Powers s OpenGLOpenInventor tool called Apprentice which is free for non-commercial, educational use. Cool School By David S. Hooper. Cool School simulates a school of fish and predators using behavioral modeling. The O(n 2 ) cost of the naive boids algorithm is reduced by by subdividing the population into a hierarchy of subschools. He reports running at interactive rates with 32 subschools each containing 33 fish on a 200MHz Pentium-class machine. Cool School was developed as part of the Virtual Whale project mentioned above. Simulation of a Flock of Birds A 1997 class project at Stanford by Chris Quartetti and Eng-Shien Wu, includes a movie file showing flocking and collision avoidance, and C source code. Boids Demos in VRML, Java3D, and C Anthony Steed (of University College London) developed the first two implementations to compare VRML and Java3D, and the third to test the DIVE multi-user VR system. Source is includes for all three. Flock This A commercial plug-in from Northern Lights Productions for the Electric Image animation system, creates herds and flocks of animated characters. new Gnat Cloud and Mega Flies Keith Wiley created these Mac applications to simulate extremely large swarm-like populations, using modifications of the basic boid algorithms. See also his Flock With Obstacles applet. new vbBoid Richard Lowe wrote this boids implementation in Visual Basic and provided the source code at PlanetSourceCodes VB repository. (I have not seen it run but:) It apparently provides for interactive specification of obstacles. new 3D Boids Robert Platt wrote a boids implementation as a Windows application for a Final Year Project in college. The original version used Direct3D and he later rewrote it to use OpenGL. Binaries and source are available for download from his page. new The Birds Olcay Cirit wrote this 2d shooter game based on boids. It runs under Windows 95, 98, and NT and is available for free download. You can shot at the flocking birds, but watch out, because they can shoot back And since they are a flock, they can make coordinated group attacks. new Crowd simulation Bill Powers developed these models of people moving in relation to other people and things as part of a suite of (Windows PC based) demonstrations of his Perceptual Control Theory. Powers and his colleagues in the Control Systems Group seek to model and understanding the purposeful behavior of living organisms. new Creature Behaviour Simulator James Greenbank wrote this ecological simulation of a three species system using individual-based local rules. It is written as a Java application. This page contains links to a paper, the source code and both platform-independent and Windows-specific executables. new CM: Flocking Model a StarLogoT implementation of flocking from Connected Mathematics (Making Sense of Complex Phenomena Through Building Object-Based Parallel Models.) Includes links to a movie of the simulation and a page of background. new flock v1.0 John Kundert-Gibbs wrote this flocking plug-in for Maya in its scripting language MEL . It is available at the HIGHEND3D repository. new Gregs boids Greg Johnson wrote this boids code to use with the Persistence of Vision Raytracer. the page contains links to the code, a movie, and some diagrams of the steering force vectors used in the boids model. new Lexicological note: in addition to common terms like flock . herd . and school . English has a rich history of specific words to describe groups of various animals, sometimes known as collective nouns or venereal terms . These words were used more frequently when hunting wild animals was a major source of food. For an amusing discussion of these words see the book An Exaltation of Larks by James Lipton (Viking Penguin, 1993, ISBN 0140170960). Here are some web pages that provide similar information: Send comments to Craig Reynolds ltcwrred3d gt visitors since June 29, 1995 Last update: September 6, 2001 (fixed the early motion tests link December 6, 2006) (fixed links to Brian J. Morks work July 30, 2007)
No comments:
Post a Comment