Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-23755
Titel: Efficient algorithms for constraint propagation and for processing tree descriptions
Verfasser: Thiel, Sven
Sprache: Englisch
Erscheinungsjahr: 2004
SWD-Schlagwörter: CSP
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: This thesis consists of two parts. In the first part we present propagation algorithms, which to solve a CSP is based on interleaving constraint progagation and search. The task of a propagation alogrithm is to prune portions of the search space which do not contain a solution so that the search does not have to explore them. We present propagation alogrithms for the following constraints: Sortedness, Alldiff, WeightedPartialAlldiff and NonOverlapping (of two convex polygons). The second part deals with a tree processing problem, which is represented as a dominance graph. The task is to assemble a collection of tree fragments into a tree T such that the ancestor relation of T satisfies some given constraints. We discuss efficient algorithms for deciding whether a dominance graph D has a solved form and for enumerating all (minimal) solved forms of D.
Diese Arbeit besteht aus zwei Teilen. Im ersten Teil behandeln wir Propagierungsalgorithmen zum Lösen von Constraint-Problemen. Ein Lösungsansatz basiert darauf, Constraint-Propagierung und Suche abzuwechseln. Durch die Propagierung werden Teile des Suchraums eliminiert, die keine Lösung enthalten. Dadurch verringert sich der Raum, der von der Suche exploriert werden muss, und die Lösung(en)werden oftmals schneller gefunden als durch Suche alleine. Wir beschreiben Propagierungsalgorithmen für folgende Constraints: Sortedness, Alldiff, WeightedPartial Alldiff und NonOverlapping. Der zweite Teil behandelt ein Baumverarbeitungsproblem, das durch einen Dominanzgraphen beschrieben wird. Das Problem besteht darin, Baumfragmente so zu einem Baum zusammen zu setzen, dass bestimmte Anforderungen an die Vorfahr-Relation des Baumes erfüllt sind. Wir entwickeln einen Linearzeit Lösbarkeitstest und effiziente Algorithmen zum Aufzählen aller (minimalen) gelösten Formen eines Dominanzgraphen.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-3226
hdl:20.500.11880/23811
http://dx.doi.org/10.22028/D291-23755
Erstgutachter: Kurt Mehlhorn
Tag der mündlichen Prüfung: 17-Mai-2004
SciDok-Publikation: 15-Jul-2004
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - Sonstige Einrichtungen
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
ThielSven_ProfDrKurtMehlhorn.pdf3,06 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.