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

  • 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:

    KVC_01

    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.:

    KVC_02

    KVC_02.jpg

    Hier sollen z.B. alle 4 'Einsen' auf der linken Seite zu einem 4-er Päckchen gebildet werden und die dritte 'Eins' in oberen Reihe soll mit der zweiten 'Eins' in dieser Reihe zu einem 2-er Päckchen gebildet werden.

    Wäre ganz oben rechts noch eine 'Eins', so sollten aber 2x 4-er Päckchen gebildet werden.

    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:

    KVC_2E_Code

    Kurze Erläuterung:

    $Av ist die Tabelle als Array (ohne die Bezeichnungen wie x1, x1̅ usw.)

    $TermAv benutze ich um die Gleichung aus zu geben. Die Abfrage "if $TermAv <> "A"&$TermChar &" = " Then" dient dazu um zu gucken ob ich schon ein Teil der Gleichung habe, falls ja, soll er diese mit " ∨ " erweitern, bevor die Gleichung um die Eingänge erweitert wird.

    $ComboA1_4/2 hab ich hier als Hilfsvariable benutzt, weil ich keine weiteren 2-er bzw. 1-er Päckchen bilden muss, das funktioniert aber auch nur bei der Tabelle mit 2 Eingängen.

    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:

    KVC_03

    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-marburg.de/~thormae/lectu…de/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:

    Spoiler anzeigen

    KVC_04.jpg

    Ich prüfe von oben links nach rechts, Reihe für Reihe, dann von oben links nach unten Spalte für Spalte.

    Erste Feld = 1

    Dann prüfe ich dieses Feld nach rechts auf vielfaches von 2 = wahr

    Dann prüfe ich diese beiden Felder nach unten auf vielfaches von 2 = wahr

    Weitere vielfache von 2 nach rechts und unten = falsch

    Erstes 4er Päckchen fertig.

    Dann mache ich das selbe mit der zweiten 'Eins' von oben links?! Selbe Spiel, er bildet wieder ein 4er Päckchen, allerdings kann ich hier doch schon nur nach rechts/unten prüfen, sonst würde er das erste 4er Päckchen ja nochmal bilden. So und nun würde ich aber nochmal die dritte 'Eins' prüfen und das würde ein 2er Päckchen nach unten ergeben, welches ich aber nicht mehr haben will, weil alle 'Einsen' in diesem Päckchen bereits verbraucht sind. Da fällt mir gerade auf, wahrscheinlich kann ich das irgendwie mit Hilfsvariablen lösen, dass wenn alle 'Einsen' eines Päckchen verbraucht sind, die nicht nochmal verwendet werden müssen.

    Und nach links/hoch muss ich auch gar nicht überprüfen, wenn ich von oben links anfange... Okay, vielleicht hatte ich vorher irgendwo einen Denkfehler, ich werde das jedenfalls so nochmal probieren, ob das klappt und melde mich dann wieder.

    Übrigens JS kann ich leider nicht, dachte zwar würde daraus trotzdem wenigstens den Sinn verstehen, hab ich aber leider nicht :D

    @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

    Einmal editiert, zuletzt von MrShady187 (10. Mai 2018 um 17:19)

  • 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.

    Spoiler anzeigen

    EDIT:

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

    Spoiler anzeigen

    KVC_06.jpg

    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.

    Einmal editiert, zuletzt von MrShady187 (21. Mai 2018 um 21:08)

  • 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.

    Spoiler anzeigen

    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:

    Spoiler anzeigen

    So würde das auch noch nicht richtig funktionieren, da er einen Term mehrmals hinzufügen würde, aber das eigentliche Problem scheint hier zu sein, dass ich in "If Av($iI, $jJ) = 1 Then" nicht die $iI und $jJ Variablen packen kann, weil das schon in der Funktion selbst Variablen sind? Oder woran genau liegt das und wie kann ich das umgehen?

    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.

    Einmal editiert, zuletzt von MrShady187 (24. Mai 2018 um 18:03)