Schaltungen mittels KV-Tabelle automatisch lösen (Benötige Hilfe)

Statement zur DSGVO im Forum

Alles zur DSGVO und zur Umsetzung im Forum hier: Statement zur DSGVO (letztes Update: 30.05.2018)
  • Hi, ich versuche ein Programm zu erstellen, dass KV-Tabellen automatisch befüllt und mir die möglichst kürzeste Kombination aus Gattern wiedergibt.

    Kurz zur Erklärung wie das geht, ich hab z.B. eine Tabelle mit 2 Eingängen:

    Bei A1 gib ich die Zahlen selbst ein und das Programm überführt sie rechts in die Tabelle, dann überprüft er, ob vertikal oder horizontal mehrere 'Einsen' liegen.

    Es können immer nur 2-er, 4-er, 8-er oder eben 1-er Päckchen gebildet werden. Es können z.B. 4 'Einsen' untereinander oder nebeneinander ein 4-er Päckchen ergeben oder auch 2 neben- und untereinander.

    Das geht auch über den Rand hinaus, so können z.B. 4 'Einsen' in den äußersten 4 Ecken, ein 4-er Päckchen ergeben.

    Das ist bei dem Bsp. mit 2 Eingängen noch nicht relevant aber bei 3 oder 4 Eingängen.

    Man kann auch 'Einsen' die man für ein Päckchen schon verbraucht hat, auch nochmal benutzen um ein weiteres Päckchen zu bilden, allerdings nur, wenn es auch Sinn macht.

    Als Bsp.:

    Weiterhin besteht die Möglichkeit, dass ein Ausgang nicht relevant ist und mit 'x' belegt wird. Das 'x' kann auch dazu genutzt werden ein Päckchen mit 'Einsen' zu bilden, soll aber nur in Betracht gezogen werden, wenn es dabei hilft, ein Päckchen zu bilden.

    Am Ende müssen alle 'Einsen' in der Tabelle verbraucht sein und dann sieht man sich die Päckchen an. Für die Bildung der Gleichung muss man sich jetzt das Päckchen ansehen, in welchen Eingängen es sich befindet.

    Befindet sich ein Päckchen z.B. in x1, aber nicht in x1¯, so ist x1 die Gleichung. Befindet sich das Päckchen in beiden Eingängen (x1 und x1¯), so ist weder x1, noch x1¯ Teil der Gleichung.

    An dem Bsp. KVC_02 wäre die Gleichung A1 = x1 ∨ (x2 ∧ x3). Beim 4-er Päckchen wird x2 und x2¯ eingeschlossen, sowie x3 und x3¯, deswegen werden die beiden Eingänge ausgeschlossen und es bleibt x1 als Gleichung über, weil x1¯ nicht eingeschlossen ist. Beim 2-er Päckchen ist x1 und x1¯ eingeschlossen, aber x2¯ und x3¯ nicht, deswegen bleibt x2 ∧(und) x3 über.

    Ich hoffe ich hab nichts vergessen und es halbwegs vernünftig erklärt.


    So nun hab ich das mit 2 Eingängen hin bekommen, der Code dazu:

    Allerdings bin ich maßlos überfordert, das für eine Tabelle mit 3 oder 4 Eingängen zu erstellen und ich glaube auch auf diese Art und Weise würde da an die eine Million Zeilen Code entstehen und meine eigentliche Frage ist, hat jemand eine Idee, wie ich das anders abfragen kann bzw. gibt es irgendwelche Funktionen in AutoIT mit denen ich sowas viel einfacher machen kann?

    Ich bin leider noch kein Profi in AutoIT.

    Das Hauptproblem was ich sehe, ist, dass ich manche 'Einsen' manchmal, doppelt verwenden muss, aber manchmal eben nicht.

    Das selbe auch mit dem 'x', welches ich ja nur verwenden möchte, wenn es mir dabei hilft, mit anderen 'Einsen' ein Päckchen zu bilden.

    Hier nochmal ein Screen, wie die Tabelle mit 4 Eingängen bei mir aussieht:

    Ich hoffe wirklich jemand kann mir hierbei irgendwie helfen und ich bin für jede Idee dankbar.


    Mit freundlichem Gruß

    Eugen

  • Ich denke, mit dem probieren aller Möglichkeiten hast du den falschen Ansatz gewählt.

    Meine erste Idee wäre, die Daten in ein Array zu schreiben. Dann ein zweites Array anzulegen in dem gespeichert wird, ob das Feld schon verwendet wurde. Wenn nicht arbeitest du das Feld ab (Funktionsaufruf). Beim abarbeiten gehst du die gesamte Von-Neumann-Nachbarschaft des Feldes durch und fügst alle (1er/dontcare) Felder zu einer Liste (und markierst sie als abgearbeitet). Am Ende analysiserst du die hinzugefügten Felder, indem du die Vielfachen von 2 ausprobierst. Das machst du sowohl in der Breite, als auch in der Höhe. Wenn du dabei immer die größten Felder nimmst kannst du sie verknüpfen.


    Wie genau die Umsetzung aussehen könnte müsste ich mir dann aber genauer überlegen :)


    Nebenbei: Ich hab grad diese Seite gefunden. Der Quellcode ist in JavaScript, also, falls du inspiration suchst: http://www.mathematik.uni-marb…res/ti1/code/karnaughmap/


    MfG Kanashius.

  • Ohne dich von deinem Vorhaben abbringen zu wollen... KV-Diagramme sind zwar eine sehr anschauliche Darstellung von Minimierung und bei weniger als etwa 5 Eingangsvariablen auch noch von Hand annehmbar schnell... Aber sie sind mit Sicherheit nicht das Optimum, wenn du Computerunterstützung hast. Wenn du schon selber eine Minimierungssoftware basteln willst, solltest du vielleicht eher auf Quine-McCluskey setzen. Ich hab's zwar selber noch nie programmiert, aber das sollte sich wesentlich strukturierter schreiben lassen als KV-Diagramme. Und ich meine, mich an die Aussage in "Digitaltechnik" erinnern zu können, dass QM sowieso ein computeroptimierter (für Computer optimiert) Algorithmus ist.


    EDIT

    Wenn es denn unbedingt KVDs sein müssen... Dann kann man dein konkretes Problem ja darauf reduzieren, dass zwei 2D-Arrays miteinander verglichen werden müssen. Wie komme ich darauf? Naja, die simpleste Herangehensweise wäre, alle möglichen Päckchen für ein Diagramm der Größe XxX statisch zu speichern und dann diese Liste mit dem Eingangsdiagramm zu vergleichen. Damit das etwas performanter geht, könnte man das 2D-Array durch eine Bitfolge ersetzen und einfach nur ein BitAND durchführen. Sollte gehen.

  • Hey, erstmal vielen Dank für die Antworten..


    @Kanashius

    Okay also, ich glaube den Ansatz hatte ich auch schon, aber genau da hab ich ja das Problem, dass ich nicht weiß, wann ich eine 'Eins/dontcare' nochmal verwenden muss oder nicht.

    Ich versuchs mal an nem Bsp:

    @chesstiger

    Mit deiner Antwort bin ich leider überfordert haha

    Also ich weiß, was du meinst mit dem Abgleich von dem Array der Tabelle mit einem vordefiniertem Array mit den möglichen Päckchen, allerdings wüsste ich nicht genau, wie ich diese Abfrage realisieren sollte, weil ich eben theoretisch viele Päckchen haben kann, die auch ineinander greifen.. Ich werde versuchen, das irgendwie zu testen und melde mich dann.

    BitAND kenne ich leider auch noch nicht, aber ich lese mich schlau.


    EDIT:

    Achja und ja es muss KV sein, ich mache gerade ein Techniker Studium und habe mir das als Abschlussarbeit ausgesucht, hab mir das Anfangs aber doch etwas leichter vorgestellt hehe

  • So sorry, konnte mich die letzten Tage nicht motivieren weiter zu machen hehe

    Also ich hab jetzt folgendes geschrieben, ist glaub ich zwar etwas besser als das was ich bei 2 Eingängen gemacht habe, aber ich glaube wirklich kurz wird das mit der Methode auch nicht. Könnt ihr mir vielleicht sagen, ob ich auf dem richtigen Weg bin? Das ist jetzt nur die Abfrage für alle Möglichkeiten bei der ersten 'Eins' oben links, aber die nächsten Abfragen werden auf jeden Fall kürzer, da es weniger Möglichkeiten gibt.

    EDIT:

    Und da bin ich schon beim nächsten Problem...


    Theoretisch macht er ja alles richtig, aber die (x2 ∧ x3) ist hier überflüssig, da ich mit dem danach folgenden Term (x1 ̅ ∧ x3) alle 'Einsen' auch verbrauchen würde..

    Ich könnte in diesem speziellen Fall die Reihenfolge der Abfrage ändern, aber ich vermute spätestens bei 4 Eingängen wird das nicht mehr reichen.

    Vorschläge? Ich hätte jetzt spontan die Idee, dass er erst die Abfragen machen soll, wo mehr 'Einsen' unverbraucht sind, aber wie ich das umsetze weiß ich auch noch nicht.

  • EDIT 2:

    Die Nachricht war zu lang für den vorherigen Post..

    Also ich hab das jetzt für 3 Eingänge gelöst, indem ich erst eine Abfrage auf mindestens 2 unverbrauchte 'Einsen' mache und danach auf mindestens eine.

    Schön ist es nicht, aber es funktioniert.

    Ich wäre trotzdem sehr dankbar für weitere Vorschläge, wie ich das mit 4 Eingängen komfortabler lösen könnte :D

    Hier der Code dazu, habe diesen nochmal etwas verändert.


    EDIT 3:

    Achja, nach langem hin und her überlegen und rum probieren, glaube ich gibt es keine bessere Möglichkeit :D

    Die Abfragen einfacher zu realisieren würde noch gehen, aber ich glaube, die Ausgabe der unterschiedlichen Gleichungen kann ich nicht vereinfachen..

    Meine letzte Idee ist leider schon an der Funktion gescheitert, hier mal der Code dazu:

    Dann hab ich noch eine weitere Frage, ich würde gerne die einzelnen Päckchen in der Tabelle umkreisen, da hab ich leider gar keine Idee, für die GUI benutze ich den Koda von SciTE und da sind die Möglichkeiten begrenzt.

    Und es wäre gut, wenn ich die einzelnen Päckchen nochmal irgendwie hervorheben kann, wenn ich einen Term anklicke oder die Maus darüber fahre. Gibt es dafür auch noch eine Lösung? :D


    ich hoffe ihr habt noch ein paar Tipps und Ideen für mich, danke im Voraus.