Category Archives: Theory-O-Matic

Einführung in BPMN

So, nachdem ich nun schon einige Artikel mit Ablaufdiagrammen gepostet habe (so zum Beipiel zur Optionsauswahl, zum allgemeinen Ablauf der KI und zur Kaufentscheidung) wurde ich nun gefragt, wie man diese eigentlich liest. Kurz gestockt, hmm, stimmt, das gehört wohl nicht zum Standardausbildungskanon ^^ Also die genutzte Notation ist die BPMN, also die Business Process Modelling Notation.

In diesem Artikel möchte ich kurz auf diese eingehen und die zentralen (also die von mir genutzten) Symbole erläutern, nach dieser kurzen Einführung sollte das Lesen der von mir geposteten Ablaufdiagramme also kein Problem mehr sein :)

Continue reading

Posted in Theory-O-Matic. Tagged with , .

mehr zum Sekretärinnenproblem

Nachdem das Sekretärinnenproblem in seiner Grundform unseren Anforderungen nicht gerecht wurde, will ich in diesem zweiten Artikel ein paar Erweiterungen aus der Literatur vorstellen. Vier (erste) Kritikpunkte wurden schon erwähnt, mal sehen was die Literatur dazu sagt:

Der Zielfunktionwert ist im Standardproblem entweder 1 (bester Kandidat gewählt) oder 0 (sonst).  Bei uns ist der Zielfunktionswert der Nutzen des angenommenen Kaufangebots (abzüglich der Evaluationskosten). Allgemeine Nutzenfunktionen wurden schon 1973 von Mucci vorgestellt. Diese sind (mit einigen Voraussetzungen, die bei uns gelten) wie die Grundform lösbar [1].

Im Standardproblem kommen die Kandidaten zum Entscheider, der NSC nachher muss den nächsten Händler (wahrscheinlich) aufsuchen. Dadurch entstehen Evaluationskosten (also Wegezeit). Auch Evaluationskosten wurden bereits in der Literatur behandelt, zuerst von Lorenzen in 1978 [4]. Mit allgemeiner Nutzenfunktion (ohne die Möglichkeit, zurück zu gehen und eine abgelehnte Option anzunehmen) lässt sich auch diese Aufgabe (unter gewissen Voraussetzungen) geschlossen lösen [5].

In der Grundform des Sekretärinnenproblems ist eine einmal abgelehnte Option dauerhaft verloren. Dem NSC wird es möglich sein, den Händler eines abgelehnten Angebots noch einmal zu besuchen und das Angebot (so der Händler es noch anbietet) doch noch anzunehmen. Schon 1974 wurde diese Erweiterung von Yang vorgestellt [2], gelöst wird auch diese Form mit dynamischer Programmierung [1].

Auch eine unbekannte Anzahl an Kandidaten wurde in der Literatur schon behandelt [1]. Doch diesen Punkt können wir uns eigentlich schenken – man kann leicht abschätzen, wie viele Händler besuchen ob der Evaluationskosten überhaupt Sinn macht und darüber lässt sich die Anzahl der Kandidaten schon gleich ab Anfang beschränken.

Soo, soweit zu den einzelnen Punkten.. Aber wir brauchen ja alle Punkte zusammen.. Das dann demnächst mit eigenem Hirnschmalz.

[1] P.R. Freeman. (1983). The Secretary Problem and its Extensions: A Review. International Statistical Review, 51 (1983), pp. 189-206.
[2] Smith, M.H. (1975). A secretary problem with uncertain employment. J. Appl. Prob. 12, pp. 620-624.
[3] Mucci, A.G. (1973). Differential equations and optimal choice problems. Ann. Statist. 1, pp. 104-113.
[4] Lorenzen, T. J. (1978). Generalising the secretary problem. Adv. Appl. Prob. 11, pp. 384-396.
[5] Lorenzen, T. J. (1981). Optimal stopping with sampling cost: the secretary problem. Ann. Prob. 9, pp. 167-172.

Posted in Inspiration-O-Matic, Theory-O-Matic. Tagged with , , .

Das Sekretärinnenproblem

Der NSC kann nun nicht nur mit Hilfe der Zeitreihenanalyse ermitteln, welchen Preis er für das angebotene Gut für fair hält,  sondern kann über die Nutzendifferenz von Gut und Geld auch genau den erwarteten Nutzen ermitteln (siehe auch Geld und Nutzen). Doch wie entscheidet er nun, ob er das Kaufangebot annimmt oder in der Hoffnung nach einem besseren Angebot (vorerst) ablehnt und weitersucht? Ein erster Schritt zur Antwort könnte das Sekretärinnenproblem sein, dessen Grundform ich in diesem Artikel vorstellen möchte.

In der Grundform des Sekretärinnenproblems werden nacheinander n Bewerber(innen) vorgestellt und nach der Evaluation des jeweils aktuellen Bewerbers muss sofort entschieden werden, ob die Bewerbung angenommen oder abgelehnt wird. Es darf nur genau eine Bewerbung angenommen werden (also wenn eine Bewerbung angenommen wird, gehen alle vielleicht noch kommenden besseren Bewerber verloren) und eine einmal abgelehnte Bewerber(in) ist dauerhaft verloren. Es gibt nur zwei Ausgänge: Sieg (die beste Bewerbung wurde angenommen, Zielfunktionswert 1) oder Niederlage (die beste Bewerbung wurde nicht angenommen, Zielfunktionswert 0). Die Aufgabe ist es, eine optimale Annehm- / Ablehnstrategie zu finden, also eine Strategie, in der die Chance, die beste Bewerbung anzunehmen, maximal ist. [1]

In dieser einfachen Version gibt es für das Sekretärinnenproblems geschlossene Lösungen [1]. Doch die Situation mit unserem NSC wird von den Annahmen der Grundform nicht abgedeckt, so zum Beispiel:

  • Der Zielfunktionwert entspricht dem Nutzen des angenommenen Kaufangebots (abzüglich der Evaluationskosten) und wird nicht 0, wenn es eine bessere Option gegeben hätte.
  • Die Evaluation einer weiteren Option kostet Zeit (Weg zum nächsten Händler..).
  • Es ist möglich, eine abgelehnte Option noch einmal zu evaluieren, dies verursacht erneut Evaluationskosten (Weg zurück zum Händler) und eventuell ist das Angebot nicht mehr gültig.
  • Die Anzahl der möglichen Kaufangebote ist a priori nicht notwendigerweise bekannt.

[1] P.R. Freeman. 1983. The Secretary Problem and its Extensions: A Review. International Statistical Review, 51 (1983), pp. 189-206.

Posted in Inspiration-O-Matic, Theory-O-Matic. Tagged with , , .

KI und Preisentwicklung

Während die Testumgebung für die erste Version der KI für unsere NSCe noch im Bau ist, kann man ja schon einmal über erste Erweiterungen nachdenken :) Der momentan größte Dorn in meinem Auge ist das fehlende Preisgefühl der NSCe. Momentan ist es so, dass der NPC Dinge kauft (weil sich das als gut erwiesen hat) und zwar unabhängig vom Preis, zu dem das Gut gerade angeboten wird. Das ist für die spätere Integration in ein größeres System mit einem Wirtschaftssystem natürlich fatal. Zum einen ist es geradezu eine Aufforderung zum Exploit an alle Spieler. Zum anderen macht es das Wirtschaftssystem unberechenbar, wenn eine nicht vernachlässigbare Anzahl an Teilnehmernsich eben nicht rational verhält. Das erste neue Ziel ist also die Antizipation des NSCs von Preisentwicklungen.

Als Mittel der Wahl, um Preisentwicklungen mathematisch zu berücksichtigen, ist die Zeitreihenanalyse. Genauer gesagt war mein erster Gedanke ein in den Wirtschaftswissenschaften gängiger Ansatz der Zeitreihenanamyse, das Trend-Saison-Modell. Hier werden Preisdaten über die Zeit erhoben und in Trend-, Saison- und Rauschkomponente unterteilt. Die Trendkomponente beinhaltet die langfristige, nicht periodische Entwicklung des Preises. Die Saisonkomponente enthält saisonal periodisch wiederkehrende Effekte. Die Rauschkomponente enthält nicht erklärbare, unregelmäßige Effekte. Momentan ist nicht absehbar, dass wir überhaupt Saisoneffekte haben werden, also können wir wohl auf die Saisonkomponenete verzichten. Plan?

Posted in Theory-O-Matic. Tagged with , , , .

Wirtschaft und Handel

Ein weiteres mögliches Thema wäre die Entwicklung eines Wirtschaftssystems inklusive Handelssystem, Monitoring und Steuerungsmöglichkeiten. Es soll in unserem Spiel einen geschlossenen Geldkreislauf geben. Geschlossener Geldkreislauf, also geschlossene Volkswirtschaft heißt in unserem Falle auch, dass alle Teilnehmer in Wirtschaftssystem (Spieler und NPCs) einen festen Geldbetrag haben und damit agieren. Während über das Verhalten der Spieler nur Annahmen getroffen werden können und wir dieses Verhalten auch nur indirekt steuern können, sollten sich die teilnehmenden NPCs nach Regeln verhalten, die der Stabilität des Systems zuträglich sind. Als Ziele lassen sich also festhalten:

  1.   langfristig stabiles Preisniveau
    1. gleichbleibende Anfangsbedingungen für neue Spieler
    2. kein “Explodieren” der Geldmenge
    3. keine übermäßige Differenz zwischen armen und reichen Spielern
  2. geringe Konjunkturschwankungen

Die uns zur Verfügung stehenden Steuerungsmöglichkeiten sind:

  • Events zur Erhöhung / Senkung der Geldmenge
  • Verhalten der teilnehmenden NPCs

Continue reading

Posted in Theory-O-Matic. Tagged with .

nun auch mit Ton: der erste Blogartikel ist vertont :)

Yay :) Gestern haben wir den ersten Blogartikel auch zum Anhören (und Anschauen) veröffentlicht :) 30 Minuten Erklärungen meinerseits zum Artikel Verhalten der NSCs sind bei YouTube hochgeladen :) Freu mich über Klicks und Feedback :)

Posted in News-O-Matic, Theory-O-Matic. Tagged with , .

Den (eigenen?) Weg finden

In diesem Artikel möchte ich einen Gedanken zur Wegfindung von NSCs mit euch teilen. Wie kann ein NSC einen Weg finden, ohne dass ein offizieller Pfad existiert? Und ohne dass – noch viel schlimmer – geskriptete Wege hinterlegt werden? Aber gleichzeitig auch ohne dass der NSC allwissend ist, die Wege besser findet als der Spieler und ohne dass er, alles bisher gewesene ignorierend, außerhalb von Städten und offiziellen Wegen rein nach Himmelsrichtungen läuft? Nun habe ich schon mehrfach das Wort offizieller Weg / Pfad genutzt, was ist eigentlich ein Weg?

“Wege entstehen dadurch, dass man sie geht.” (Franz Kafka)

Dieses schöne Zitat von Kafka war sicherlich im übertragenen Sinn gemeint, stimmt aber auch in seiner wörtlichen Bedeutung.

Continue reading

Posted in Theory-O-Matic. Tagged with , , .

Verhalten der NSCs

Ein weiteres mögliches und sehr ergiebiges neues Thema wäre die KI der NSCs. Welche Anforderungen und welche Wünsche werden an eine KI in einem Computerspiel gestellt? Ich weiß vor allem, was ich nicht möchte. Ich möchte keine “dummen Bots”. Ich möchte keine feindlichen NSCs, die nach der Uhr ihre Attacken ausführen, ich möchte keine zivilen NSCs, die zu jeder vollen Stunde ihren üblichen Weg laufen und dabei jedes Mal dieselbe Unterhaltung führen. Mehr noch: Frei nach dem Motto “Lernen ist wie Rudern gegen den Strom. Sobald man aufhört, treibt man zurück” (Benjamin Britten) ist jede KI, die sich dem Verhalten der Spieler nicht anpasst, die nicht dauerhaft von ihrer Umwelt lernt, unbefriedigend. Ich würde also erwarten, dass sich die NSCs dem Umfeld und damit auch meinen Aktionen anpassen. Das Ziel einer KI für feindliche, vor allem aber für verbündete NSCs in einem Spiel, in dem viel Zeit auch außerhalb von Kämpfen verbracht wird, sollte auch die Erhaltung und Erzeugung von Ambiente und Konsistenz beinhalten. Die NSCs sollten Aktionen nicht ausführen, weil wir das so geskriptet haben, sondern weil sie einen Grund dafür haben. Sie sollten kein Brot kaufen, weil ein Skript ihnen sagt, dass sie jeden Tag ein Brot kaufen, sondern weil sie Hunger haben und ein Brot kaufen dann eine gute Idee ist. Wenn die gesellschaftlichen Gepflogenheiten sich durch die Spieler ändern, dann sollten sie es erkennen. Wenn sich Treffpunkte heraus gebildet haben, an denen sich die Spieler vermehrt aufhalten, dann sollten die NSCs sich daran anpassen und zum Beispiel beginnen, dort Ware zu verkaufen oder nach Arbeit zu suchen. Und das alles, ohne! für jede Situation ein eigenes Skript zu schreiben. Leider bestehen die meisten KI Systeme, wie sie in Lehrbüchern stehen, nur aus immer komplexeren Skripten, die immer mehr Daten mit einrechnen. Die KI, wie ich sie mir vorstelle, ist in drei Ebenen unterteilt:

  • Ebenen der KI

    Ebenen der angedachten künstlichen Intelligenz

    Motivationsebene: Mit Hilfe einer Motivationspyramide wird bestimmt, welche Bedürfnisse den NSC motivieren, also welche Ziele angegangen werden. Je nach Archetyp des NSCs kann die Motivationspyramide entsprechend angepasst sein, bzw. die sich dahinter verbergenden konkreteren Ziele können variieren (Anerkennung kann sowohl in handwerklichem Können, in Reichtum oder auch im Krieg gesucht werden). Diese Ziele schränken die Optionen, die der nächsten Ebene gewählt werden können, stark ein. Beispiel für eine in dieser Ebene getroffene Entscheidung: Die Bedürfnisse der Art “Grundbedürfnisse” sind erfüllt, Ziele mit Zweck Bedürfniserfüllung “Sicherheit” werden nun auch verfolgt.

  • Optionsebene: Welche Handlungsoptionen stehen zur Verfügung, wie werden sie bewertet, welche werden ausgeführt? Beispiel für eine in dieser Ebene getroffene Entscheidung: Aus der Motivationsebene kamen hohe Bewertungen für die Bedürfnisse “Grundbedürfnisse” und “Sicherheit”. Es stehen also Optionen wie “Essen / Trinken bei Gastwirt y oder Bauer z besorgen” aber auch “ein Schloss bei Schmied y kaufen und einbauen” oder “eine Waffe bei Schmied x kaufen” zur Verfügung, nicht aber Optionen der Selbstverwirklichung wie “ein Bild malen”. Diese Optionen werden gewertet und eine Entscheidung für eine oder mehrere Optionen werden getroffen.
  • Situationsebene:Die Optionsebene hat eine auszuführende Handlung bestimmt. Die Situationsebene ist die konkreteste Ebene, hier geht es um Fragen wie: Wie verhalte ich mich, wenn ein “befreundeter” NSC oder Spieler vorbeiläuft, wie führe ich die eigentlich Aktion (“Waffe kaufen”) durch, wie biege ich an Kreuzung b ab, wenn mein eigentlicher Weg versperrt ist, wie reagiere ich, wenn mich jemand angreift? Beispiel für eine Entscheidung dieser Ebene: “Gib dem Schmied x Geld für die Waffe”, aber auch Reaktionen auf einen Angriff wie “die Flucht ergreifen” oder “zur Wehr setzen” und damit verbunden das Kampfverhalten (welche Schläge führe ich aus..).

Continue reading

Posted in Theory-O-Matic. Tagged with , , .

Apikaldominanz bei Birke und Ahorn

Ahorn

Ahorn

Soo.. mal ein kleines Update so für zwischendurch :) Wir haben den strahlend blauen Himmel des letzten Wochenendes genutzt, um auf Texturenjagd zu gehen. Und folgende Erkenntnis gehabt: birkentechnisch sind wir hier ganz schwach ausgestattet. Aber wenn es um Ahorne gibt, da haben wir sehr viele, sehr sehr schöne Exemplare direkt ums Eck :) Also stand schnell der Plan: Birke wird hinten an gestellt, in den ersten Demonstrationen der Umweltsimulation werden wir also Ahorne sehen. Das bringt aber leider noch ein bisschen Mehrarbeit mit sich, denn die Stammform des Ahorn unterscheidet sich von dem der Birke.

Das Stichwort, auf das ich hier kurz eingehen wollte, ist Apikaldominanz. Unter Apikaldominanz versteht man die Dominanz eines Sprosses, durchgesetzt durch Unterdrückung des Wachstums der  anderes Sprossen. Dadurch bildet sich ein Hauptstamm aus, von dem alle Äste ausgehen. Bei Birken (und den bisher implementierten Nadelbäumen) ist diese Dominanz wesentlich stärker ausgeprägt als zum Beispiel beim Ahorn, der in den meisten Fällen drei oder mehr ähnlich stark ausgeprägte vertikale Hauptäste hat. Und genau da entsteht der Zusatzaufwand: Eine Wuchsform wie der Ahorn war zwar geplant, ist aber noch nicht umgesetzt. Ein Ahorn mit der Wuchsform einer Birke schaut aber halt nicht aus wie ein Ahorn, sondern wie eine Birke mit den falschen Texturen ;) Also auf ans Werk und eine Wuchsform mit mehreren Hauptsprossen umgesetzt! :)

Posted in Inspiration-O-Matic, Theory-O-Matic. Tagged with , .

Ein etwas anderes Bewertungssystem

Zunächst dachte ich bei repost.it an eine klassisches Sternerating. Nutzer können sich anonym und schnell zwischen meist einem und fünf Sterne entscheiden, um ihr eigenes Feedback direkt an andere Nutzer weiterzugeben. Nachdem Cookie dann aber ein zweidimensionales Bewertungssystem eingeworfen hatte, war ich sofort begeistert von der Idee. Der Ansatz ist simpel. Warum dem Nutzer nur eine Zahl in Form eines Sternes vergeben lassen, wenn man visuell auch in eine andere Richtung gehen kann ohne dabei an eine feste Zahl gebunden zu sein. Das etwas andere Bewertungssystem war geboren!

Das repost.it Bewertungssystem sollte alle Anforderungen eines klassischen (Sterne-)Bewertungssystems erfüllen. Darunter Anonymität, Einfachheit und Sicherheit bei der Bewertung. So entschieden wir uns für ein klassisches Dreieck, welches die Reposts für eine Bewertung in sprichwörtlich alles Richtungen abdeckt. Man sollte nicht nur über “Gut” und “Schlecht” entscheiden können, sondern ob es eventuell einfach zu “Normal” ist und zwar rein visuell ohne eine Note zu vergeben. Auch technisch war ein schneller Weg gefunden dies umzusetzen. Die JQuery Bibliothek lieferte sämtliche Funktionalitäten, die benötigt wurden. Man musste diese lediglich kombinieren. Im Hintergrund nimmt eine Datenbank jedes Rating seperat für jedes Reposting auf, wobei über eine PHP-Funktion die Mehrfacheingabe unterbunden und die X- und Y-Koordinaten weitergegeben wurden.

Lediglich der Platzbedarf des Dreiecks ist höher als bei einer Sternebewertung, auch konnte ich bisher technisch nicht den Knopf zur Bewertung umgehen und die Bewertung direkt auf der Hauptseite war sehr verbuggt… Beides sollte aber sowohl designtechnisch, als auch technisch noch möglich sein. Ihr könnt aber bereits jetzt schon das Bewertungssystem testen, welches bisher als am Interessantesten hervorgehoben wurde. Das freut uns natürlich sehr, weil doch einiges an Arbeit drin steckt und uns euer Feedback besonders wichtig ist – egal über eine Bewertung oder direkt per Mail, etc. :)

Posted in Theory-O-Matic. Tagged with .

Mein NSC versteht mich nicht..

Wäre das nicht imba, wenn dein Lieblings NSC dich nicht nur nett anlächeln könnte oder wortlos mit dir handeln könnte, sondern dich verstehen, dir antworten und sich vielleicht sogar an die Gamersprache gewöhnen könnte? Wenn du einen Söldner NSC ansprichst mit “Hey, LFM Torlahöhle, Interesse?” und der antwortet mit “Alles FFA?” – ich fände es toll :) Und klar, Gamersprache ist in einem RP nicht gewollt, aber auch dort gibt es genug Anwendungsfälle, in denen das nice ist: andere Namen für Orte, sprachliche Umgangsformen..

Aber ist das umsetzbar? Nach den ersten Kapiteln aus “The Handbook of Computational Linguistics and Natural Language Processing” von A. Clark, Ch. Fox, Sh. Lappin (Beute aus meinem letzten Unibib Raid) lautet meine vorläufige Antwort leider “Nein”. Aber so schnell lasse ich mich nicht entmutigen..

Posted in Theory-O-Matic. Tagged with , , .

Fast ein Baum im Baum..

Wie versprochen möchte ich immer mal wieder auf interessante Aspekte in Konzeption und Coding der von mir implementierten Features eingehen. Dabei geht es mir nicht so sehr um eine flächendeckende Beschreibung – ich habe nicht vor, die Doku in den Blog zu verlagern ;) – sondern darum, einzelne, aus meiner Sicht schöne oder interessante Stellen zu erläutern. Beginnen möchte ich dabei mit einer Stelle in der Simulation der Umwelt, genauer mit der Auswertungsreihenfolge der Umweltfaktoren.

Die Menge der durch Photosynthese umgewandelte und damit der Pflanze zur Verfügung stehenden Energie hängt von einer Reihe von abiotischen Faktoren ab, die sich gegenseitig beeinflussen (siehe auch Wikipedia). In der realen Welt sind dies Kohlenstoffdioxid, Licht, Wasser und Temperatur. In einer fiktiven Welt können natürlich beliebige Umweltfaktoren wie Magie, Schall oder eine andere Art Licht hinzukommen. Diese Umweltfaktoren beeinflussen sich gegenseitig und beeinflussen die Effektivität der Photosynthese, ein paar Beispiele aus der realen Welt sind: Die Menge an aufnehmbaren Kohlenstoffdioxid kann gedrosselt werden durch die Wassermenge bzw. die Luftfeuchtigkeit, die Temperatur beeinflusst die Photosyntheserate. Wenn man beliebige Kombinationen von beliebig vielen verschiedenen Umweltfaktoren zulassen möchte, stellen sich vor allem zwei Probleme:
1. In welcher Reihenfolge können die Umweltfaktoren ausgewertet werden? Im obigen Beispiel sollte die Wassermenge berechnet werden, bevor die Kohlenstoffdioxidmenge berechnet wird, da dieses Ergebnis von der aufgenommenen Wassermenge abhängt.
2. Wie bildet man alle möglichen Beeinflussungsarten wie “beeinflusst die Photosyntheserate” oder “setzt eine obere Grenze” ab?

Wir beschäftigen uns zunächst (also in diesem Beitrag) mit der ersten Frage. Da theoretisch beliebige Kombinationen von a priori nicht bekannten Umweltfaktoren möglich sein sollen, kann dem Programm keine vorher festgelegte Reihenfolge vorgegeben werden. Wie soll eine solche Reihenfolge also festgelegt werden? Dazu zunächst ein wenig Graphentheorie [1], wirklich nur ein ganz wenig. Ein gerichteter Graph G = (V, E) besteht aus einer Menge von Knoten V und eine Menge von gerichteten Kanten E, wobei jede Kante definiert ist als ein geordnetes Paar von Knoten. Ein solcher gerichteter Graph ist kreisfrei, falls es keinen Weg gibt, der aus einem Knoten heraus und später wieder in ihn hinein führt. Wenn wir unsere Problemstellung nun übersetzen in die neu gelernten Begriffe, so ist jeder Umweltfaktor ein Knoten und immer, wenn ein Umweltfaktor einen anderen Umweltfaktor beeinflusst, zeichnen wir eine Kante vom Knoten des ersten Umweltfaktors zum Knoten des zweiten Umweltfaktors. Wenn in diesem Graph ein Kreis auftritt heißt das, dass sich die Umweltfaktoren ringförmig beeinflussen, also zum Beispiel wäre “Wassermenge beeinflusst Kohlenstoffdioxidmenge beeinflusst Magie beeinflusst Wassermenge” ein Kreis. Diesen Fall wollen wir ausschließen, da man sich in der Berechnung sonst ewig im Kreis drehen könnte. Wir haben nun also einen kreisfreien, gerichteten Graphen vorliegen. Ein solcher Graph ist topologisch sortiert, wenn man eine Reihenfolge der Knoten gefunden hat, in der für jede Kante der Endknoten weiter hinten in der Reihenfolge liegt als der Anfangsknoten. Wenn man eine solche topologische Sortierung der Umweltfaktoren hat und die Umweltfaktoren in dieser Reihenfolge auswertet, dann beeinflusst jeder Umweltfaktor nur Umweltfaktoren, die später ausgewertet werden -> perfekt :)

Ist man erst einmal zu dieser Erkenntnis gelangt, dann ist der Rest kein Hexenwerk mehr – ein Algorithmus zum topologischen Sortieren von Graphen ist schnell gefunden. Man startet mit einer leeren Liste bereits sortierter Knoten und sucht in jeder Iteration im Graphen nach Knoten ohne eingehende Kanten, nimmt diese ans Ende der Liste bereits sortierter Knoten auf und entfernt den Knoten und alle ausgehenden Kanten aus dem Graphen. Am Ende ist der Graph leer und die Knoten sind topologisch sortiert. In der so ermittelten Reihenfolge werden die Umweltfaktoren dann vom Programm ausgewertet. Das obige Beispiel hat als eine mögliche topologische Sortierung Wasser -> Temperatur -> Luftfeuchtigkeit ->Kohlenstoffdioxid -> Licht.

[1] Algorithmische Graphentheorie, Volker Turau, Oldenbourg Verlag, 3. Auflage, 2009

Posted in Code-O-Matic, Theory-O-Matic. Tagged with , , .