Binärer Suchbaum für künstliche Intelligenz



  • Ich möchte mich mit künstlicher Intelligenz beschäftigen und frage mich welche Bibliothek dafür am besten geeignet ist, um einen binären Suchbaum zu erstellen, boost BGL sieht mir ein wenig zu Groß aus,für das was ich vor habe. Welche Lib würdet ihr Empfehlen für einen einfachen Einstieg in das Thema KI? Ich habe mir gedachte, dass ich erst einmal mit Tic Tac Toe anfange, hier gibt es wenig Möglichkeiten an Zügen. Die KI soll dann alle möglichen Züge ausprobieren und in einen Suchbaum speichern, welche Strategien am Erfolgversprechendsten sind.


  • Mod

    Standardbibliothek? Was willst du denn für eine spezielle Datenstruktur für deine TicTacToe-KI, die nicht std::map oder std::unordered_map ist?



  • SeppJ schrieb:

    Standardbibliothek? Was willst du denn für eine spezielle Datenstruktur für deine TicTacToe-KI, die nicht std::map oder std::unordered_map ist?

    Ich brauche eine Baumstruktur und diese ist mit der STL nicht zu verwirklichen, soweit ich weiß?


  • Mod

    0FAD schrieb:

    SeppJ schrieb:

    Standardbibliothek? Was willst du denn für eine spezielle Datenstruktur für deine TicTacToe-KI, die nicht std::map oder std::unordered_map ist?

    Ich brauche eine Baumstruktur und diese ist mit der STL nicht zu verwirklichen, soweit ich weiß?

    Was machst du dann mit dem Baum? Packst Dinge rein, damit man sie schnell anhand eines Schlüssels finden kann? So wie bei einer std::map? Was denkst du denn, wie die std::map wohl funktioniert? Und selbst wenn die std::map nicht mittels eines Baumes implementiert sein sollte (die std::unordered map bietet beispielsweise eine sehr ähnliche Funktionalität, funktioniert intern aber komplett anders), dann ist es doch immer noch die Funktionalität "Dinge reinpacken und anhand eines Schlüssels schnell finden", die du eigentlich haben möchtest. Es ist doch egal, wie das intern umgesetzt wird. Daher ist std::unordered_map hier auch eine erwähnenswerte (höchstwahrscheinlich sogar bessere!) Alternative.


  • Mod

    Es ist doch egal, wie das intern umgesetzt wird.

    Nein, man möchte natürlich auch Performance. Zum Glück sucht die QoI gänger Implementierungen ihresgleichen, und selbst der Standard gibt Laufzeit-Komplexitäten vor.


  • Mod

    Arcoth schrieb:

    Es ist doch egal, wie das intern umgesetzt wird.

    Nein, man möchte natürlich auch Performance. Zum Glück sucht die QoI gänger Implementierungen ihresgleichen, und selbst der Standard gibt Laufzeit-Komplexitäten vor.

    Daher erwähnte ich ausdrücklich "Schnell" als eine der Anforderungen. Wenn diese Anforderung erfüllt ist (in der Regel in der Form einer garantierten Komplexität, die ich erreichen möchte), dann kann es mir danach recht egal sein, was intern passiert.


  • Mod

    SeppJ schrieb:

    Arcoth schrieb:

    Es ist doch egal, wie das intern umgesetzt wird.

    Nein, man möchte natürlich auch Performance. Zum Glück sucht die QoI gänger Implementierungen ihresgleichen, und selbst der Standard gibt Laufzeit-Komplexitäten vor.

    Daher erwähnte ich ausdrücklich "Schnell" als eine der Anforderungen. Wenn diese Anforderung erfüllt ist (in der Regel in der Form einer garantierten Komplexität, die ich erreichen möchte), dann kann es mir danach recht egal sein, was intern passiert.

    Ups, hab ich überlesen, sorry.



  • hast du mal daran gedacht, dir diesen Baum einfach schnell selbst zu Programmieren oder deine Ergebnisse mittels bubblesort in ein Array zu schieben?



  • HansKlaus schrieb:

    hast du mal daran gedacht, dir diesen Baum einfach schnell selbst zu Programmieren oder deine Ergebnisse mittels bubblesort in ein Array zu schieben?

    Wo soll das Problem mit std::set, std::map und std::sort sein?
    Aber vielleicht soll TE erstmal anfangen zu programmieren, sich schon vorher auf irgendwelche fixe Ideen von wegen "brauche Baum weil wegen irgendwo Verzweigung oder sowas" festzulegen macht nicht viel Sinn.



  • gibt es so nicht, map ist doch normalerweise ein suchbaum.

    Aber die ganze Sache einfach in ein Array einzusortieren dürfte trotzdem schneller sein, wobei ich bisher nur sehr grundlegende Kenntnisse von ki habe und die Anforderungen nicht so kenne.


  • Mod

    HansKlaus schrieb:

    Aber die ganze Sache einfach in ein Array einzusortieren dürfte trotzdem schneller sein, wobei ich bisher nur sehr grundlegende Kenntnisse von ki habe und die Anforderungen nicht so kenne.

    Funktioniert aber nicht so gut mit dem nachträglichen Einfügen, was hier wohl gefragt ist. Außerdem wurde unordered_map bereits genannt. Im Gegenzug gehört jeder geteert und gefedert, der ernsthaft Bubblesort für irgendetwas vorschlägt.



  • was hast du gegen bubblesort? 😁
    Also mein kenntnisstand ist, dass bubblesort bei unsortierten datenbeständen sehr, Sehr langsam ist, bzw ein o(n^2) aufweist, bei vorsortierten oder gar leeren Beständen aber sehr effektiv arbeitet, dann ja nur wenig getauscht werden muss, bzw. das datum direkt an die richtige stelle geschrieben wird.

    Bei einer liste spart man sich sogar noch das verschieben.


Log in to reply