[lol_nope]

Programirki, poszukuje algorytmu minimalizacji drzewa ANDow i ORow tak, zeby bylo jaknajmniej operacji. Dobrze byloby, gdyby dalo sie wziac pod uwage, ze AND jest o okolo 10% kosztowniejszy od ORa.
Drzewo nie ma ograniczen, jezeli chodzi o ilosc zagniezdzen.
Ktos, cos?
#programowanie #algorytmy #java

[cjkas]

findbugs w trybie eksperymentalnym bodajże podawał jak uprościć kod itp. ale głowy nie dam bo już dawno tego nie używałem

[ania-nowak1231]

@lol_nope: https://pl.wikipedia.org/wiki/Metoda_Karnaugh lub wolfram: http://www.wolframalpha.com/input/?i=((A%20OR%20B)%20AND%20(NOT%20B%20AND%20C)%20OR%20C)&t=crmtb01&f=rc

[leoha]

@lol_nope: To jest problem NP-trudny, wiec dla większej (>4) ilości zmiennych zostaje tylko jakaś heurystyka. Może https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer ?

[lol_nope]

@cjkas: @ania-nowak1231: @leoha:
To nie do końca tak. Nie upraszczam swojego kodu, tylko wejście od usera, więc findbugs, mapy karnaugh i wolfram odpadają (chyba, że będę wysyłać żądania do API wolframa przy każdym żądaniu od usera :D).
Wejście nie będzie też kompletną funkcją boolowską - będą tam tylko operacje AND i OR.
Nie musi być to postać minimalna, heurystyka w zupełności wystarczy - czas, który stracę na zmniejszaniu drzewka

[leoha]

@lol_nope: Ależ ja cie doskonale zrozumiałem i wciąż uważam, że każda z metod jest dobra (metoda Karnaugh, metoda Quine'a-McCluskeya, metoda iteracyjnego konsensusu, metoda Espresso).
A jak chcesz cos bardzo prostego to po prostu szukaj zależności, które zmniejszają ilość operacji OR/AND np:

a OR (a AND b) <=> a
a OR 0 <=> a
a AND 0 <=> 0
(a OR b) AND (a OR C) <=> a OR (b AND c)