Springen naar inhoud

Een boolean decision diagram oplossen


  • Log in om te kunnen reageren

#1

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 02 januari 2011 - 01:52

Stel, gegeven een BDD

Zou je een algoritme kunnen bedenken, die gegeven de graaf van de BDD, om aan een bepaalde uitkomst te komen x1, x2 en x3 kiest. Dit is vrij triviaal. Maar nog beter: zou je gegeven verschillende BDD's, een algoritme of een sterke heuristiek kunnen vinden die de x1, x2 en x3 zo kiest dat iedere BDD een respectievelijk gegeven uitkomst uitkomt?
Geplaatste afbeelding
Zoiets zou bijzonder interessante toepassingen hebben. Dus beste mensen, als we iets vinden is dit een grote doorbraak op wiskundig gebied. Ik kan niets vinden in de literatuur dat er zelfs vaagweg iets mee te maken heeft, dus voor zo ver ik gevonden heb, is het nog niet onderzocht.

Zie dit als een experiment van mijnentwege op dit forum. ;) Ik werk regelmatig dergelijke ideeŽn uit, soms komen ze uit, meestal niet. Het hoeft ook niet meteen helemaal opgelost te zijn. Interessante visies, ideeŽn, links of verbanden met andere theorieŽn zijn allemaal bijzonder welkom. Ik vraag me af of we op dit forum met de kritische massa zitten om samen antwoorden op dergelijke problemen te vinden.

Dus: shoot!

"Differential, people"
-Gregory House-
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 02 januari 2011 - 12:43

Zou je een algoritme kunnen bedenken, die gegeven de graaf van de BDD, om aan een bepaalde uitkomst te komen x1, x2 en x3 kiest. Dit is vrij triviaal.

Volgens mij is het ook vrij eenvoudig om alle mogelijke inputs te vinden (gewoon door de boom omhoog). Je kan dan volgens mij twee dingen doen: of je doet dit met alle BDD's en kijkt dan welke set inputs voor alle BDD's goed is, of je probeert net zolang mogelijke inputs voor de boom die je bekeken hebt bij alle andere BDD's totdat je er een vindt die bij allemaal voldoet. Maar dit lijkt me allemaal enorm simpel dus ik zal wel een of andere nuance gemist hebben bij het probleem...

#3

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 02 januari 2011 - 13:12

Volgens mij is het ook vrij eenvoudig om alle mogelijke inputs te vinden (gewoon door de boom omhoog). Je kan dan volgens mij twee dingen doen: of je doet dit met alle BDD's en kijkt dan welke set inputs voor alle BDD's goed is, of je probeert net zolang mogelijke inputs voor de boom die je bekeken hebt bij alle andere BDD's totdat je er een vindt die bij allemaal voldoet. Maar dit lijkt me allemaal enorm simpel dus ik zal wel een of andere nuance gemist hebben bij het probleem...

Ja, brute forcen is uiteraard een mogelijkheid. Maar die zijn van 0(2^n). Dus als de BDD x1 ... x32 onbekenden heeft, loopt de complexiteit te snel op. De BDD-representatie is echter lineair t.o.v. het aantal onbekenden (dus O(n)), wat mij doet vermoeden dat er ook algoritmes zijn, of sterke heuristieken op de brute-force bestaan die ook in polynomiale tijd draaien.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures