Γρήγορος αλγόριθμος για vertex cover

[Lanike71]

Έχω υλοποιήσει ένα άπληστο αλγόριθμο που λύνει το minimum vertex cover με καλά αποτελέσματα. Το πρόβλημα είναι ότι όταν ξεπεράσουμε τους 1000 κόμβους και τις 10.000 περίπου ακμές, ακόμα και ο άπληστος αργεί (πάντα εξαρτάται από το τι βαθμού είναι οι κορυφές, αλλά έδωσα ένα παράδειγμα).

Υπάρχει άλλος γρήγορος αλγόριθμος που να μπορεί να πετύχει καλύτερους χρόνους;

Ο αλγόριθμος που χρησιμοποιώ τώρα είναι αυτός που σε κάθε loop υπολογίζει το βαθμό κάθε κορυφής και επιλέγει την κορυφή με το μεγαλύτερο βαθμό, προσθέτει την κορυφή στο σετ της λύσης και αφαιρεί από το γράφο όλες τις συσχετιζόμενες κορυφές, μέχρι να μην υπάρχει κορυφή στο γράφο.

[k33theod]

Γειά Lanike71

Αν και έχω πολύ μικρή εμπειριά από γράφους, και εφόσον δεν βρεις βιβλιοθήκη έτοιμη που να σε καλύπτει.

Δοκίμασε αυτό

1) Initialize the result as {}
2) Consider a set of all edges in given graph.  Let the set be E.
3) Do following while E is not empty
...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
...b) Remove all edges from E which are either incident on u or v.
4) Return result 

Time Complexity of above algorithm is O(V + E).  Παραδείγματα εδώ https://www.geeksforgeeks.org/vertex-cover-problem-set-1-introduction-approximate-algorithm-2/

Για αυτόν που περιγράφεις προτείνω: στο 1ο loop που θα κάνεις βάλε σε μια δομή όλες τις κορυφές sorted αυτό δεν ιδιαίτερα δύσκολο ή αργό νομίζω. Μετά κάνεις pop από τη δομή στο σετ σου αντί να ξαναψάχνεις πάλι και αφαιρείς τις σχετιζόμενες από τη δομή.

Μήπως αν χρησιμοποιήσεις κάποιον traversal είναι πιο γρήγορο BFS ίδιο complexity O(V + E) https://en.wikipedia.org/wiki/Graph_traversal

Επεξ/σία 26 Ιουνίου 2018 από k33theod

[albNik]

Στις 25/6/2018 στις 7:58 ΠΜ, Lanike71 είπε

Ο αλγόριθμος που χρησιμοποιώ τώρα είναι αυτός που σε κάθε loop υπολογίζει το βαθμό κάθε κορυφής και επιλέγει την κορυφή με το μεγαλύτερο βαθμό, προσθέτει την κορυφή στο σετ της λύσης και αφαιρεί από το γράφο όλες τις συσχετιζόμενες κορυφές, μέχρι να μην υπάρχει κορυφή στο γράφο.

Ο πολυωνυμικός αλγόριθμος σου είναι λάθος αλλιώς θα σου είχαν δώσει το νόμπελ. Mπορεί κατά σύμπτωση να πετυχαίνει το σωστό.

Δεν υπάρχει γρήγορος τρόπος να βρεις ποιος από τους 2^1000 συνδυασμούς είναι ο minimum.

 

Επεξ/σία 26 Ιουνίου 2018 από albNik

[Lanike71]

4 ώρες πριν, albNik είπε

Ο πολυωνυμικός αλγόριθμος σου είναι λάθος αλλιώς θα σου είχαν δώσει το νόμπελ. Mπορεί κατά σύμπτωση να πετυχαίνει το σωστό.

Δεν υπάρχει γρήγορος τρόπος να βρεις ποιος από τους 2^1000 συνδυασμούς είναι ο minimum.

Δεν καταλαβαίνω τι θες να πεις.Τι ακριβώς κάνει λάθος;

Ακόμα και διαισθητικά να το πάρεις, θεωρώ ότι είναι ο απλούστερος αλγόριθμος και είπα ότι πετυχαίνει καλά αποτελέσματα, δεν είπα ότι επιστρέφει το βέλτιστο σετ.

Δες σελ. 152 στο παράδειγμα:

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

[albNik]

3 λεπτά πριν, Lanike71 είπε

Δεν καταλαβαίνω τι θες να πεις.Τι ακριβώς κάνει λάθος;

Ακόμα και διαισθητικά να το πάρεις, θεωρώ ότι είναι ο απλούστερος αλγόριθμος και είπα ότι πετυχαίνει καλά αποτελέσματα, δεν είπα ότι επιστρέφει το βέλτιστο σετ.

Δες σελ. 152 στο παράδειγμα:

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

Ok sorry, εννοούσες προσεγγιστικά 

καλά αποτελέσματα  !=  minimum vertex cover

Mπορώ να σκεφτώ ένα πιο απλό: συγκέντρωσε τις κορυφές ξεκινώντας από αυτές που έχουν μεγαλύτερο βαθμό μέχρι να καλύψουν όλες τις πλευρές.  

 

[Lanike71]

^

Αυτό ακριβώς κάνει ο αλγόριθμος. Ξεκινάει από την κορυφή  V με το μεγαλύτερο βαθμό, την προσθέτει στη λύση, αφαιρεί τις κορυφές είναι προσπίπτουσες (αν θυμάμαι καλά τον όρο, αυτές που ενώνονται με ακμές) με τη V από το γράφο και συνεχίζει ώσπου G = κενό σύνολο.

Δοκίμασα και με άλλο αλγόριθμο, που υπολογίζει το σύνολο των βαθμών των κορυφών που γειτνιάζουν με κάθε κορυφή και επιλέγει το max (με τη λογική ότι αφού το sum είναι πολύ μεγάλο, υπάρχουν πολλές κορυφές που επηρεάζονται από την αφαίρεση της κορυφής αυτής). Αυτό που ισχύει όμως είναι ότι το sum μπορεί να είναι ένα άθροισμα και πολλών κοινών κορυφών, άρα το sum είναι ψιλο fake μετρική...

Συν τοις άλλοις, δεν κέρδισα ούτε σε μικρότερο σετ, αλλά ούτε και σε χρόνο...

 

Επεξ/σία 26 Ιουνίου 2018 από Lanike71

[albNik]

2 λεπτά πριν, Lanike71 είπε

^

Αυτό ακριβώς κάνει ο αλγόριθμος. Ξεκινάει από την κορυφή  V με το μεγαλύτερο βαθμό, την προσθέτει στη λύση, αφαιρεί τις κορυφές είναι προσπίπτουσες (αν θυμάμαι καλά τον όρο, αυτές που ενώνονται με ακμές) με τη V από το γράφο και συνεχίζει ώσπου G = κενό σύνολο.

Δοκίμασα και με άλλο αλγόριθμο, που υπολογίζει το σύνολο των βαθμών των κορυφών που γειτνιάζουν με κάθε κορυφή και επιλέγει το max (με τη λογική ότι αφού το sum είναι πολύ μεγάλο, υπάρχουν πολλές κορυφές που επηρεάζονται από την αφαίρεση της κορυφής αυτής). Αυτό που ισχύει όμως είναι ότι το sum μπορεί να είναι ένα άθροισμα και πολλών κοινών κορυφών, άρα το sum είναι ψιλο fake μετρική...

Ίσως είναι λίγο πιο περίπλοκος ο αλγόριθμος  στο βιβλίο,
Το να ταξινομήσεις τις κορυφές σύμφωνα με το βαθμό και να πάρεις τις N πρώτες μέχρι να καλύψουν το graph πιστεύω είναι αστραπιαίο ακόμα και για εκατομύρια κορυφές, αλλά περιέχει μεγαλύτερο σφάλμα.

[Lanike71]

Τελικά βελτίωσα λίγο τον αλγόριθμο, καθώς ο αλγόριθμος ελέγχει και τη σούμα των βαθμών κορυφών των παιδιών σε περίπτωση ισοβαθμίας 2 κορυφών, αλλά και το κυριότερο, διάλεξα άλλο τρόπο στον επανυπολογισμό σε κάθε loop και αυτό έχει να κάνει  με το χρόνο που χρειάζεται η γλώσσα να δημιουργήσει αντικείμενα, να προσθέσει, διαγράψει κλπ, κάτι που δεν είχα λάβει και τόσο υπ' όψη. Και αυτό έφερε ως και 90% μείωση στο χρόνο.

Επεξ/σία 30 Ιουνίου 2018 από Lanike71

[k33theod]

Δοκίμασε και αυτόν που σου έγραψα αντί να αφαιρείς nodes αφαιρείς σχετιζόμενα edges που είναι το πιο λογικό.

 

[Επισκέπτης]

Τσέκαρε το networkx είναι πολύ καλό, μεταξύ άλλων έχει και vertex cover.

[Lanike71]

6 ώρες πριν, k33theod είπε

Δοκίμασε και αυτόν που σου έγραψα αντί να αφαιρείς nodes αφαιρείς σχετιζόμενα edges που είναι το πιο λογικό.

Θα δοκιμάσω και θα πω. Μία ματιά στα γρήγορα που έριξα, έχω μία απορία :

Με ποιό κριτήριο επιλέγει κάποια ακμή; (αν δε μου διαφεύγει κάτι).

[k33theod]

arbitrary σημαίνει αυθαίρετα, κάνε pop

Επεξ/σία 1 Ιουλίου 2018 από k33theod

[k33theod]

Γράφω λίγο χαζό code μήπως βοήθήσω

G=(v,e) //όπου v vertex όπου e edge
result={}
while(e){//όσο έχει κάτι μέσα
  //βήμα 1
  (u,w) = e.pop()//παίρνεις ένα edge
  result.push(u)
  result.push(w)
  //βήμα2 
  for edge in e{
	if u in edge or w in edge //αν βρεις edge που έχει κορυφή u ή w
	  e.remove(edge)// διέγραψε την 
  }
return result

 

Επεξ/σία 1 Ιουλίου 2018 από k33theod

[Lanike71]

Σε ευχαριστώ για τη βοήθεια, αλλά έχω δοκιμάσει με αυθαίρετη επιλογή κορυφής (τυχαία δηλαδή), που είναι ακριβώς το ίδιο και το αποτέλεσμα ήταν πάντα χειρότερο από τον greedy.

Μάλιστα, είχα δώσει ένα δικαίωμα να τρέξει για λίγο χρόνο παραπάνω, αλλά δεν...Οπότε κατέληξα σε αυτόν που έχω τώρα.

[pmav99]

Στις 30/6/2018 στις 7:26 ΜΜ, Lanike71 είπε

Τελικά βελτίωσα λίγο τον αλγόριθμο, καθώς ο αλγόριθμος ελέγχει και τη σούμα των βαθμών κορυφών των παιδιών σε περίπτωση ισοβαθμίας 2 κορυφών, αλλά και το κυριότερο, διάλεξα άλλο τρόπο στον επανυπολογισμό σε κάθε loop και αυτό έχει να κάνει  με το χρόνο που χρειάζεται η γλώσσα να δημιουργήσει αντικείμενα, να προσθέσει, διαγράψει κλπ, κάτι που δεν είχα λάβει και τόσο υπ' όψη. Και αυτό έφερε ως και 90% μείωση στο χρόνο.

always profile your code!