Color Graphing-AI

[theoamd]

Ψάχνω source code το οποίο να επιλύει το πρόβλημα Color Graphing μέσω κάποιας μορφής του Hill Climbing(πχ τη stochastic) για να τρέξω κάποια .dat αρχεία που έχω.

Προσπάθησα να το φτιάξω και μόνος μου, αλλά αντιμετωπίζω ορισμένα προβλήματα κι έχω φάει γερό λαγκάρισμα

Γνωρίζει κανείς που μπορώ να το βρω; (προτιμάται η C++ -εκεί το πάλεψα- προκειμένου να δω πιθανά λάθη μου)

[nucleus]

Πως μοντελοποίησες τις κορυφές του γράφου? Με struct?

[theoamd]

Απλή ανάθεση δεδομένων από το αρχείο σε μεταβλητές. Σκέψου ότι καθένα από τα αντίστοιχα αρχεία που επεξεργάζεται το πρόγραμμα έχουν την παρακάτω μορφή:

<n number of colors> <color1> <color2> .... <color n>

<number of nodes>

<number of edges>

//node connections

<node1> <node35>

<node2> <node73>

.

.

.

.

.

.

.

<node n-4> <node n>

αυτό ήταν ένα τυχαίο παράδειγμα αρχείου

[nucleus]

Χωρίς να τις "ομαδοποιείς" σε μια δομή δεδομένων?

struct edge {

int from_koryfh_id; //από που ξεκινάει το edge

int to_koryfh_id; //που τελειώνει

}

struct κορυφη {

int id_koryfhs; //χαρακτηρίζει μοναδικά κάθε κορυφή

char *color; //το χρώμα της

edge akmes[]; //πίνακας που κρατά τις ακμές

}

Δυστυχώς στην υλοποίηση του αλγόριθμου δεν μπορώ να σε βοηθήσω

[zaxos]

Επίσης σκέψου να προτιμήσεις αναπαράσταση του γράφου με Adjacency List για να είναι πιο αποδοτική η διάσχιση του γράφου, ειδικά αν υπάρχουν μεγάλου μεγέθους input.

π.χ. (από δικιά μου υλοποιήση σε ένα project)

/* * * * * Graph Representation Related * * * * */

struct node
{
int vertex; // vertex id
int w; // weight of root -> vertex
struct node *next;
};

typedef struct node* nodeptr;

// getnode(): creates new node
nodeptr getnode()
{
nodeptr n;
n = (nodeptr) malloc(sizeof(struct node));
n->next=NULL;
return n;
}

// graph_init(): initializes graph
void graph_init(nodeptr graph[],int V)
{
int i;

for (i=0; i<V; i++)
graph[i]=NULL;
}

[theoamd]

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

Όποιος έχει την καλοσύνη και το χρόνο ας ρίξει μια ματιά στα παρακάτω(σλουρπ σλουρπ ) μπας και βγάλουμε καμιά άκρη.

Μορφή αλγορίθμου

Hill-climbing with stochastic choices and restarts (αναρρίχηση λόφων με στοχαστικές επιλογές και επανεκκινήσεις)

Ο αλγόριθμος αυτός είναι μια παραλλαγή του hill-climbing που στο graph coloring πρόβλημα κάνει τα εξής:

Ο χρήστης δίνει ως παράμετρο δύο όρια. Το όριο επαναλήψεων και όριο επανεκκινήσεων

Ο αλγόριθμος ξεκινάει με μια τυχαία ανάθεση χρωμάτων σε κόμβους

Σε κάθε επανάληψη επιλέγει τυχαία έναν κόμβο ανάμεσα στους κόμβους που συμμετέχουν σε τουλάχιστον μια σύγκρουση

Για τον κόμβο που επέλεξε βρίσκει το χρώμα που αν του ανατεθεί έχει ως αποτέλεσμα την μέγιστη μείωση του πλήθους των συγκρούσεων

Αν φτάσει στο όριο επαναλήψεων χωρίς να έχει βρει λύση κάνει επανεκκίνηση

Αν φτάσει στο όριο επανεκκινήσεων χωρίς να έχει βρει λύση σταματάει

Μορφή αρχείου προς είσοδο:

5 0 1 2 3 4

87

406

0 19 <>

0 13 <>

0 3 <>

0 78 <>

0 65 <>

0 82 <>

1 31 <>

1 54 <>

1 73 <>

1 45 <>

1 6 <>

1 3 <>

1 33 <>

1 71 <>

1 28 <>

1 22 <>

1 42 <>

1 41 <>

1 80 <>

1 52 <>

1 18 <>

1 38 <>

1 85 <>

1 15 <>

1 55 <>

1 86 <>

1 32 <>

1 57 <>

1 75 <>

1 66 <>

1 34 <>

1 53 <>

1 82 <>

1 78 <>

1 10 <>

1 65 <>

1 79 <>

2 21 <>

2 22 <>

2 71 <>

2 57 <>

2 86 <>

2 82 <>

2 32 <>

3 11 <>

3 86 <>

3 18 <>

3 73 <>

3 31 <>

3 54 <>

3 45 <>

3 33 <>

3 20 <>

3 17 <>

3 58 <>

3 48 <>

3 13 <>

3 19 <>

3 82 <>

3 78 <>

3 65 <>

4 30 <>

4 33 <>

4 82 <>

4 77 <>

5 46 <>

5 82 <>

6 34 <>

6 18 <>

6 86 <>

6 32 <>

6 33 <>

6 82 <>

6 57 <>

7 70 <>

7 48 <>

7 82 <>

8 10 <>

8 75 <>

8 13 <>

8 39 <>

8 82 <>

8 56 <>

9 41 <>

9 82 <>

10 39 <>

10 13 <>

10 66 <>

10 82 <>

10 75 <>

11 73 <>

11 31 <>

11 45 <>

11 33 <>

11 13 <>

11 20 <>

11 19 <>

11 67 <>

11 35 <>

11 51 <>

11 82 <>

12 42 <>

12 26 <>

12 84 <>

12 59 <>

12 18 <>

13 73 <>

13 31 <>

13 45 <>

13 33 <>

13 20 <>

13 48 <>

13 39 <>

13 75 <>

13 19 <>

13 82 <>

13 78 <>

13 65 <>

14 60 <>

14 48 <>

14 82 <>

15 66 <>

15 76 <>

15 62 <>

15 21 <>

15 41 <>

15 75 <>

15 65 <>

15 82 <>

16 36 <>

16 83 <>

16 18 <>

16 86 <>

16 57 <>

16 44 <>

16 72 <>

16 49 <>

16 82 <>

17 70 <>

17 58 <>

17 82 <>

17 48 <>

18 50 <>

18 22 <>

18 71 <>

18 54 <>

18 41 <>

18 80 <>

18 52 <>

18 42 <>

18 26 <>

18 84 <>

18 59 <>

18 31 <>

18 73 <>

18 34 <>

18 65 <>

18 70 <>

18 45 <>

18 33 <>

18 36 <>

18 83 <>

18 86 <>

18 57 <>

18 44 <>

18 72 <>

18 49 <>

18 67 <>

18 68 <>

18 51 <>

18 48 <>

18 82 <>

19 73 <>

19 31 <>

19 45 <>

19 33 <>

19 86 <>

19 58 <>

19 70 <>

19 20 <>

19 48 <>

19 82 <>

19 78 <>

19 65 <>

20 73 <>

20 31 <>

20 45 <>

20 33 <>

20 65 <>

20 82 <>

20 78 <>

21 76 <>

21 62 <>

21 41 <>

21 82 <>

22 42 <>

22 34 <>

22 86 <>

22 28 <>

22 66 <>

22 71 <>

22 82 <>

22 32 <>

23 66 <>

23 65 <>

23 79 <>

23 82 <>

24 82 <>

25 82 <>

26 42 <>

26 84 <>

26 59 <>

27 50 <>

27 68 <>

27 67 <>

27 82 <>

28 34 <>

28 86 <>

28 32 <>

28 71 <>

28 82 <>

28 66 <>

29 38 <>

29 82 <>

30 33 <>

30 66 <>

30 43 <>

30 75 <>

30 82 <>

31 65 <>

31 86 <>

31 69 <>

31 45 <>

31 73 <>

31 54 <>

31 33 <>

31 82 <>

32 66 <>

32 57 <>

32 71 <>

32 86 <>

32 82 <>

33 86 <>

33 34 <>

33 70 <>

33 57 <>

33 65 <>

33 69 <>

33 45 <>

33 73 <>

33 54 <>

33 82 <>

34 86 <>

34 57 <>

34 85 <>

34 65 <>

34 71 <>

34 55 <>

34 75 <>

34 66 <>

34 53 <>

34 82 <>

35 51 <>

35 82 <>

36 83 <>

36 86 <>

36 57 <>

36 44 <>

36 72 <>

36 49 <>

36 82 <>

37 82 <>

38 65 <>

38 82 <>

39 75 <>

39 82 <>

39 56 <>

40 82 <>

41 42 <>

41 65 <>

41 86 <>

41 80 <>

41 52 <>

41 76 <>

41 62 <>

41 66 <>

41 82 <>

42 71 <>

42 80 <>

42 52 <>

42 65 <>

42 86 <>

42 82 <>

42 84 <>

42 59 <>

43 75 <>

43 82 <>

44 83 <>

44 86 <>

44 57 <>

44 72 <>

44 49 <>

44 82 <>

45 65 <>

45 86 <>

45 70 <>

45 69 <>

45 73 <>

45 54 <>

45 82 <>

46 82 <>

47 82 <>

48 60 <>

48 65 <>

48 70 <>

48 58 <>

48 78 <>

48 67 <>

48 68 <>

48 51 <>

48 82 <>

49 83 <>

49 86 <>

49 57 <>

49 72 <>

49 82 <>

50 84 <>

50 59 <>

50 68 <>

50 67 <>

50 82 <>

51 67 <>

51 68 <>

51 82 <>

52 65 <>

52 86 <>

52 82 <>

52 80 <>

53 75 <>

53 66 <>

53 82 <>

54 65 <>

54 86 <>

54 69 <>

54 73 <>

54 82 <>

55 82 <>

56 82 <>

57 70 <>

57 68 <>

57 71 <>

57 83 <>

57 72 <>

57 86 <>

57 82 <>

58 70 <>

58 82 <>

59 84 <>

60 82 <>

61 82 <>

62 76 <>

62 82 <>

63 82 <>

64 82 <>

65 73 <>

65 80 <>

65 86 <>

65 85 <>

65 66 <>

65 75 <>

65 82 <>

65 79 <>

65 78 <>

66 86 <>

66 71 <>

66 75 <>

66 79 <>

66 82 <>

67 68 <>

67 82 <>

68 70 <>

68 82 <>

69 73 <>

69 82 <>

70 82 <>

71 86 <>

71 82 <>

72 83 <>

72 86 <>

72 82 <>

73 86 <>

73 82 <>

74 82 <>

75 79 <>

75 82 <>

76 82 <>

77 82 <>

78 82 <>

79 82 <>

80 86 <>

80 82 <>

81 82 <>

82 83 <>

82 85 <>

82 86 <>

83 86 <>

Ο κώδικας που έχω κάνει:

#include <iostream>
#include <string>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cstdio>



using namespace std;



class method3{

private:
string file_name;
string line;
ifstream inFile;

int colors;
int nodes;
int edges;

int iterations;
int restarts;
int collisions;




public:
//------------------------------------------------------------------------
void openfile()
{
cout<<"Input file name: ";
cin>>file_name;
ifstream inFile((file_name+".txt").c_str());
if (inFile.is_open())
{
cout <<"File "<<file_name+".txt"<<" succefully opened "<<endl;

//diavasma dedomenwn apo to arxeio

//ari9mos xrwmatwn
getline(inFile,line);
colors=atoi(line.c_str());
cout<<"Number of colors: "<<colors<<endl;

//ari9mos komvwn
getline(inFile,line);
nodes=atoi(line.c_str());
cout<<"Number of nodes: "<<nodes<<endl;

//ari9mos akmwn
getline(inFile,line);
edges=atoi(line.c_str());
cout<<"Number of edges: "<<edges<<endl;

//ana9esi akmwn sto data[edges][2]
int data[edges][2];
int a,b;

for (int i=0; i < edges; i++)
{
int j=0;
inFile >> a >> b ;
data[i][j] = a;
data[i][j+1]=b;
cout << data[i][j] <<" "<<data[i][j+1]<< endl;
getline(inFile,line);
}
//--telos ana9esis akmwn

int moves=0;
do{

do{
cout<<"Iteration limit: ";
cin>>iterations;
cout<<"Restarts limit: ";
cin>>restarts;
}while(iterations<=0 || restarts<=0);


//ana9esi tuxaiwn xrwmatwn stous komvous-----
int random_colors[nodes];

for (int j=0;j<=nodes;j++){
random_colors[j] =rand() % colors;
cout << "node " << j << " is colored: "<<random_colors[j] << endl;
}
//---------------------------------------------------
int collisions1;
int cc[5];

//for start
for (int t=0;t<colors;t++) { //5 xrwmata
for(int i=0;i<nodes;i++) //87 komvoi
{
int j=0;
if(random_colors[data[i][j]]=random_colors[data[i][j+1]]) //an uparxei sugkrousi diale3e ena komvo sti tuxi
{

int x=rand()%2; //epilogi tuxaiou komvou
int random_node=data[i][x]; //ana9esi tou se metavliti
moves++; //emfanisi tuxaiou komvou

random_colors[random_node]=t; //ana9esi prwtou xrwmatos ston tuxaio komvo pou epilex9ike
++collisions1;
}//end if
}

cc[t]=collisions1;
} //end for

//=============upologismos xrwmatos elaxistwn sugkrousewn
int mincolor[colors];
int min=cc[0];
int y;
for(int i=0;i<colors;i++)
{ if(cc[i]<min)
{min=cc[i];y=mincolor[cc[i]];}
}

//emfanisi apotelesmatwn
cout<<min<<endl;
cout<<y<<endl;
cout<<moves<<endl;

collisions=0;
}while(collisions!=0);
//==telos upologismou elaxistwn sugkrousewn kai xrwmatos

} //end if
else{cout<< "Couldn't open the suggested file "<<endl;exit(0);}


}

//------------------------------------------------------------------------

};



int main() {
int choice;

cout<<"Choose one of the specified algorithms below:\n";
cout<<"1.Greedy Hill-Climbing with sideways moves\n";
cout<<"2.Greedy Hill-Climbing with sideways moves and restarts\n";
cout<<"3.Greedy Hill-Climbing with stochastic choices and restarts\n";

cin>>choice;
if(choice==3)
{
method3 a;
a.openfile();

}



system("PAUSE");
}

#include <cstdlib>

*δεν μπορώ να κατανοήσω στο μυαλό μου την αναγκαιότητα χρήσης struct για το συγκεκριμένο πρόβλημα

**χρησιμοποίησα ένα χύμα-function γιατί ήταν ο μόνος τρόπος να παίξει

***και MATLAB αν παίζει τίποτα, δεν μας χαλάει, το θέμα είναι να δούμε μια πρότυπη μορφή κώδικα, γιατί νομίζω το λάθος μου είναι λογικό