test
test
test
posted by s at
5:11 PM
|
0 comment(s)
Sunday, November 09, 2008
Saturday, September 13, 2008
Sunday, February 19, 2006
Friday, February 17, 2006
Tuesday, February 14, 2006
posted by s at
2:21 PM
|
0 comment(s)
Wednesday, February 08, 2006
Thursday, October 13, 2005
hmmm
Finding Dense Subgraph In Systems Of Geometric Constraints
ΜΑΡΚΟΥΖΗΣ ΔΗΜΗΤΡΗΣ
Α.Μ. 59
Introduction & Motivation
Geometric Constraint Problem (GCP)
Πεπερασμένο σύνολο από γεωμετρικά αντικείμενα (σημεία, ευθείες, επίπεδα)
Πεπερασμένο σύνολο περιορισμών μεταξύ των γεωμετρικών αντικειμένων (καθετότητα, απόσταση, κ.α.)
Λύση του GCP είναι τοποθέτηση των γεωμετρικών αντικειμένων με τέτοιο τρόπο ώστε να ικανοποιούνται οι περιορισμοί.
Introduction & Motivation
Γενικά η επίλυση ενός GCP ανάγεται στην επίλυση μη γραμμικών πραγματικών συστημάτων
Τα γεωμετρικά αντικείμενα αντιστοιχούν στις μεταβλητές και οι περιορισμοί μεταξύ αυτών στις εξισώσεις
Introduction & Motivation
Το κόστος της λύσης ενός GCP εξαρτάται από το μέγεθος του μεγαλύτερου υποσυστήματος που επιλύεται με τη βοήθεια μιας αλγεβρικής μεθόδου. Μάλιστα η χρονική πολυπλοκότητα της λύσης αυτής είναι τουλάχιστον εκθετική στο μέγεθος ενός τέτοιου υποσυστήματος
Introduction & Motivation
Decomposition-Recombination (DR) plan
Αποσυνθέτουμε το σύστημα περιορισμών σε μικρότερα υποσυστήματα, οι λύσεις των οποίων επανασυνθέτονται απλοποιώντας το αρχικό σύστημα στο οποίο εφαρμόστηκε το DR plan
Τα υποσυστήματα αυτά πρέπει να είναι rigid (discretely solvable), δηλαδή να έχουν πραγματικές διακριτές λύσεις
Introduction & Motivation
Μέτρο απόδοσης DR plan:
Μέγεθος υποσυστημάτων κατά τη διάρκεια της αποσύνθεσης
Optimal DR plan
Αυτό που ελαχιστοποιεί το μέγεθος του μεγαλύτερου τέτοιου υποσυστήματος
Introduction & Motivation
Για την επίλυση του DR problem κατασκευάζουμε έναν γράφο
Το DR plan είναι μια ακολουθία εφαρμογών παραγωγής γράφων, όπου το αριστερό μέρος είναι ο γράφος που πρόκειται να αντικατασταθεί και το δεξί μέρος είναι ο νέος γράφος που θα τον αντικαταστήσει
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Ένα GCP C μπορεί να αναπαρασταθεί με έναν geometric constraint graph G = (V,E,w)
V: κόμβοι αντιστοιχούν στα γεωμετρικά αντικείμενα του C
Ε: ακμές αντιστοιχούν στους γεωμετρικούς περιορισμούς του C
w(v): βαθμοί ελευθερίας του κόμβου v
w(e): βαθμοί ελευθερίας της ακμής e
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Ένας υπογράφος που ικανοποιεί τη συνθήκη
ονομάζεται dense και η συνάρτηση d(A) ονομάζεται density
To D είναι σταθερά και είναι ίσο
3 για 2d
6 για 3d
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
minimal dense Subgraph:
Αυτός που δεν περιέχει άλλο dense υπογράφο
Είναι directly solvable
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Plan for decomposing and recombining G
a = {1,2,3,4} b={5,6,7,8} c={9,10,11,12} d={13,14,15,16} e={17,18,19,20}
Υπολογισμός των επιμέρους λύσεων και επανασύνθεση τους σε ένα νέο γράφο με κόμβους τους a,b,c,d,e
I={a,b,c} ,II= {d,e}
Επανασύνθεση των I και II σε ένα νέο γράφο
…
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Ένα DR plan ενός geometric constraint graph είναι μια ακολουθία από γράφους Gi που έχουν τις ακόλουθες ιδιότητες
G1 = G
Decomposition: Για κάθε i υπάρχει ένας minimal υπογράφος
Recombination: O γράφος Gi+1 είναι μια παραλλαγή του Gi, που προκύπτει αντικαθιστώντας τον Si με τον Ti(Si) προκαλώντας τη μετατροπή Ti(Gi)=Gi+1.Η μετατροπή Τi ορίζεται για όλους τους υπογράφους του Gi και ονομάζεται simplifier.
Sn = Gn
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
DR plan
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Οι simplifiers Ti πρέπει να ικανοποιούν τις παρακάτω ιδιότητες
Εάν ο Α είναι υπογράφος του Β τότε και Τi(A) είναι υπογράφος του Ti(B)
είναι το ίδιο με
είναι το ίδιο με
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Οι επόμενες 4 ιδιότητες ονομάζονται validity
Κάθε constraint graph Gi μπορεί να γραφεί ως όπου Si είναι discretely solvable και Si και Ri δεν έχουν κοινές ακμές
Για κάθε o Τi(A) είναι ισομορφικός με τον Α
Η αρχική απεικόνιση T0 είναι μια αναγνωριστική απεικόνιση πάνω στα υποσύνολα του G1
Όλοι οι πρόγονοι του Si π.χ. είναι discretely solvable
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
To DR plan Q του G ονομάζεται solvability preserving εάν για κάθε i και για όλους τους υπογράφους ο Α είναι discretely solvable και οποτεδήποτε ή τότε ο αντίστοιχος απλοποιημένος υπογράφος είναι Ti(A) είναι discretely solvable και το αντίστροφο
To DR plan Q του G ονομάζεται strictly solvability preserving εάν για κάθε i και για όλους τους υπογράφους ο Α είναι discretely solvable και o υπογράφος Ti(A) θα είναι discretely solvable και το αντίστροφο
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Το DR plan Q του G ονομάζεται complete εάν για όλα τα i και για όλους τους discretely solvable υπογράφους Β των υπογράφων Si που επιλέγονται από το Q ισχύει ότι
Β = Τi-1Ti-2…Tj(Sj) για j
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Optιmal DR plan
είναι ίσο με
προσθέτουμε το D για κάθε μια από τις εικόνες του Sj που υπάρχουν στο Α μαζί με το βάρος των κόμβων του Α που δεν ανήκουν σε μια τέτοια εικόνα
Size of DR plan: το μέγιστο από τα μεγέθη των αντίστοιχων discretely solvable υπογράφων Si
Optimal size G: το ελάχιστο όλων των DR plans του G
Optimal DR plan: αυτό που έχει το ίδιο μέγεθος με το βέλτιστο μέγεθος του G
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Ένας DR planner ονομάζεται general εάν τερματίζει με ένα DR plan όταν δέχεται ως είσοδο ένα discretely solvable σύστημα
Ένας DR planner έχει την Church – Rosser ιδιότητα σε κάθε βήμα, εάν τερματίζει με ένα DR plan ανεξάρτητα ποιος discretely solvable υπογράφος Si θα επιλεγεί στο io βήμα
USING GRAPH TRANSFORMATIONS FOR FINDING DR PLANS
Ένας DR planner X λέμε ότι adapts to underconstraint constraint graphs εάν κάθε DR plan που παράγεται από το Χ τερματίζει με ένα γράφο Gn που αποτελείται από ένα σύνολο W = {A1,…,Ak} discretely solvable υπογράφων έτσι ώστε το W να είναι maximal δηλαδή καμία ένωση των υποσυνόλων του W δε δίνει discretely solvable υπογράφο.
A new DR planner:
Frontier Algorithm
Αυτός ο DR planner χρησιμοποιεί τον «Algorithm Dense» για να βρει τους minimal dense υπογράφους, σύμφωνα με τον οποίο απομονώνεται αρχικά ένας dense υπογράφος και στη συνέχεια βρίσκουμε μέσα σε αυτόν έναν minimal
A new DR planner:
Frontier Algorithm
Algorithm Dense
H density ορίζεται ως εξής
Σκοπός μας είναι να μεγιστοποιήσουμε την παραπάνω ποσότητα ή διαφορετικά να ελαχιστοποιήσουμε την
A new DR planner:
Frontier Algorithm
Algorithm Dense
Κατασκευάζουμε ένα bipartite directed network G*=(Μ,Ν,s,t,E*,w) που σχετίζεται με το γράφο G=(V,E,w)
Οι κόμβοι N είναι οι κόμβοι V
Οι κόμβοι Μ είναι οι ακμές E
s : source
t : sink
E* = {(e,u),(e,v) | e={u,v} E}
c(s,e) = w(e)
c(u,t) = w(u)
H χωρητικότητα (e,u) είναι άπειρη
A new DR planner:
Frontier Algorithm
Algorithm Dense
A new DR planner:
Frontier Algorithm
Algorithm Dense
Ξεκινάμε με ένα άδειο υπογράφο G’ του G και προσθέτουμε σε αυτόν ένα κόμβο τη φορά
Για κάθε κόμβο u που προστίθεται κατανέμουμε το βάρος w(e) των ακμών που προσπίπτουν σε αυτόν και είναι γειτονικές του G’ σε ένα ή και στα 2 άκρα τους με τέτοιο τρόπο ώστε αυτό να μην υπερβαίνει το βάρος των κόμβων
Εάν μπορέσουμε να κατανείμουμε το βάρος των ακμών του, ο G’ δεν είναι dense.Διαφορετικά είναι και μάλιστα ο τελευταίος κόμβος που προστίθεται ανήκει σε όλους στους dense υπογράφους του G’
A new DR planner:
Frontier Algorithm
Algorithm Dense
Κατανομή μιας ακμής e του G αντιστοιχεί στην εισαγωγή μιας ροής στο γράφο ίση με τη χωρητικότητα της ακμής (s,e) του G*.
Αυτό μπορεί να επιτευχθεί είτε άμεσα μέσω ενός μονοπατιού της μορφής (s,e,u,t) είτε με ανακατανομή του βάρους της ακμής
A new DR planner:
Frontier Algorithm
Algorithm Dense
A new DR planner:
Frontier Algorithm
Ο υπογράφος Si που παράγεται από τους εσωτερικούς του κόμβους (internal vertices) αντικαθιστάται από έναν κόμβο (core vertex) ci.
Οι συνοριακοί κόμβοι (frontier vertices), οι ακμές που ενώνουν αυτούς και τα βάρη τους παραμένουν αμετάβλητα
Ο core vertex συνδέεται με κάθε με κάθε frontier vertex u του Si με μια ακμή το βάρος της οποίας είναι ίσο με το άθροισμα των βαρών των αρχικών ακμών που ενώνουν τους internal vertices
Το βάρος του core vertex επιλέγεται έτσι ώστε η density του Ti(Si) να είναι ίση με -D
A new DR planner:
Frontier Algorithm
ci
w(ci) = 5
A new DR planner:
Frontier Algorithm
O DR planner FA μπορεί να ορισθεί περιγράφοντας τις simplifiers transformations Ti.
Έστω Si o minimal dense Subgraph του Gi,
SI o υπογράφος που παράγεται από τους εσωτερικούς κόμβους του Si
FI o υπογράφος που παράγεται από τους frontier vertices του Si
Α οποιοσδήποτε υπογράφος του Gι
τότε
A new DR planner:
Frontier Algorithm
Εάν τότε Τi(A) = A
Εάν τότε Τi(A) = (VTA,ETA)
VTA είναι η ένωση όλων των κόμβων του Α – SI με τους κόμβους του FI και τον core vertex ci.
ETA είναι η ένωση όλων των ακμών του Α με τις ακμές του SI που έχουν μόνο το ένα άκρο τους στο SI (combines edges)
A new DR planner:
Frontier Algorithm
Performance Analysis of FA
O FA είναι ένας valid DR planner που έχει την Church-Rosser ιδιότητα. Επίσης, βρίσκει DR plans για maximal discretely solvable υπογράφους underconstrained γράφων
Ο FA είναι complete
A new DR planner:
Frontier Algorithm
Performance Analysis of FA
O FA είναι solvability preserving, αλλά όχι strictly solvability preserving
EXAMPLE
w(u) = 2
w(e) = 1
D = 3
EXAMPLE
Click to add title
posted by s at
10:13 AM
|
2 comment(s)