'Algoritmer til løsning af ubegrænsede influensdiagrammer på begrænset plads'
Forfattere
pedersen, Ole ; Ahlmann-Ohlsen, Kristian
Semester
4. semester
Uddannelse
Udgivelsesår
2006
Abstract
Denne afhandling introducerer ubegrænsede influensdiagrammer (UID'er), en udvidelse af influensdiagrammer, hvor beslutninger ikke behøver have en fast indbyrdes rækkefølge. Det gør dem velegnede til problemer, hvor beslutningsrækkefølgen er uklar eller kun delvist bestemt (ordningsasymmetriske beslutningsproblemer). Vi udvikler og afprøver empirisk en algoritme, der balancerer beregningstid og hukommelsesforbrug ved løsning af UID'er. Algoritmen bygger på konditionering (at opdele problemet i mulige tilfælde) og bruger cache (midlertidig lagring) til at styre byttet mellem tid og plads. Vi opstiller øvre grænser for algoritmens tids- og pladskompleksitet i to grænsetilfælde: når der er plads til fuld cache og når der ikke er plads til cache. Uden cache vokser det ekstra pladsforbrug ud over en fast basisallokering lineært med antallet af knuder i UID'et. Endelig gives en formel til at estimere kørselstiden for en given mængde tilgængelig plads.
This thesis introduces Unrestricted Influence Diagrams (UIDs), a generalization of influence diagrams in which decisions do not need to be totally ordered. This makes UIDs suitable for problems where the order of decisions is unknown or only partly specified (order-asymmetric decision problems). We develop and empirically test an algorithm that balances computation time and memory usage when solving UIDs. The algorithm is based on conditioning (splitting the problem into cases) and uses a cache (temporary storage) to trade time for space. We derive upper bounds on the algorithm’s time and space complexity in two extremes: when a full cache is available and when no cache fits. In the no-cache limit, the additional memory beyond a fixed base allocation grows linearly with the number of nodes in the UID. We also provide a formula to estimate running time for a given amount of available memory.
[Dette resumé er genereret ved hjælp af AI]