Εργασία 2 [2019-20] - Καλύτερες γνωστές λύσεις

[pefraimi]

Στο θέμα αυτό μπρείτε προαιρετικά να ανεβάζετε τις καλύτερες γνωστές λύσεις (μόνο το κόστος των λύσεων) για τα στιγμιότυπα graph_0146_01234.gexf και graph_0500_01234.gexf με k = 13.

Όποια ομάδα υπολογίζει μια λύση είτε για το graph_0146_01234.gexf είτε για το graph_0500_01234.gexf με κόστος καλύτερο από την μέχρι τότε γνωστή (στο forum) λύση, μπορεί να αναρτά εδώ το κόστος της λύσης.

Προσοχή: Ανακοινώνουμε μόνο το κόστος της λύσης, όχι την ίδια τη λύση (όχι ποιους κόμβους περιλαμβάνει).

[pefraimi]

Ως τιμές εκκίνησης δίνονται

για τον γράφο graph_0146_01234.gexf το κόστος 1114, και
για τον γράφο graph_0500_01234.gexf το κόστος 3730.

[chripelt1]

Εμείς βρήκαμε για τον graph_0146_01234 κόστος 856 και για τον graph_0500_01234 κόστος 2485

[pefraimi]

Πολύ καλή προσπάθεια! Είναι καλές τιμές.

Βασιζόμενοι όμως σε παραλλαγή του brute force ή του greedy μπορούν να βελτιωθούν και άλλο. Για να δούμε.

Σημείωση: Προτείνω με την ανακοίνωση στο θέμα αυτό να αναφέρεται και ο αριθμός της ομάδας.

[chripelt1]

Εμείς βρήκαμε για τον graph_0146_01234 κόστος 856 και για τον graph_0500_01234 κόστος 2485

Είμαστε η ομάδα 9.

[Chrisake]

Ομάδα 23:
Βρήκα:

για τον γράφο graph_0146_01234.gexf κόστος 726
για τον γράφο graph_0500_01234.gexf κόστος 2008

[triasamo]

Ομάδα 24:
για τον γράφο graph_0500_01234.gexf κόστος 1980

[Severian]

Ομάδα 17
για τον γράφο graph_0500_01234.gexf κόστος 1871

[Severian]

Ομάδα 17
για τον γράφο graph_0500_01234.gexf κόστος 1871

Ομαδα 17:
για τον γράφο graph_0146_01234.gexf κόστος 726 και εμείς

[chrikara47]

Ομάδα 21:
Για το γράφο graph_0146_01234.gexf κόστος 716.

[Severian]

Ομάδα 17
για τον γράφο graph_0500_01234.gexf κόστος 1871

Ομαδα 17:
για τον γράφο graph_0146_01234.gexf κόστος 726 και εμείς

Ομαδα 17:
για τον γράφο graph_0146_01234.gexf κόστος 677

[Severian]

Ομαδα 17:

Για τον γράφο graph_0500_01234.gexf κόστος: 1816

Για τον γράφο graph_0146_01234.gexf κόστος: 677

[chrikara47]

Ομάδα 21:
Για το γράφο graph_0500_01234.gexf κόστος 1806.

[Severian]

Ομαδα 17:

Για τον γράφο graph_0500_01234.gexf κόστος: 1802

Για τον γράφο graph_0146_01234.gexf κόστος: 677

[tsav]

Ομάδα 29:
Για το γράφο graph_0500_01234.gexf κόστος 1785.