مبحث رنگها مربوط به الگوریتم

[NIIT]

ممنون میشم اگه کسی حلشو بفرسته
بااحترام





فقط اگه میشه سریعتر بفرستین....خیلی ممنون
.....

موضوعات مشابه:

• مقدمه ای بر طراحی و تحلیل الگوریتم ها

[Hossein]

من الان کتاب و جزوه طراحی الگوریتم دستم نیست . اما یادمه جزوه دو سه ترم پیش استاد حسامی فر رو نگاه کنید توش هست .یک سری نمونه سوال هست از ترم های قبل که ایشون همیشه کپی برابر اصل اونها امتحان میگیره فوقش یکی دوتا سوال خلق الساعه مطرح کنه که قبلا نگفته باشه اما 80درصد سوالهای پایان ترم از سالهای گذشته هست.

اینم برای خالی نبودن عریضه ! برنامه کامل رنگ آمیزی گراف در سی ++

منبع هم اینجاست : و توضیحات کاملی داده همراه با عکس و تصویر و ... خلاصه خیلی خیلی کامله .
http://www.dharwadker.org/vertex_coloring/

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

using namespace std;



bool removable(vector<int> neighbor, vector<int> cover);

int max_removable(vector<vector<int> > neighbors, vector<int> cover);

vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover);

vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover, int k);

int cover_size(vector<int> cover);

ifstream infile ("graph.txt");

ofstream outfile ("coloring.txt");



int main()

{

 //Read Graph

 cout<<"Vertex Coloring Algorithm."<<endl;

 int C, N, n, i, j, k, K, p, q, r, s, min, edge, counter=0;

 infile>>N;

 vector< vector<int> > Graph;

 for(i=0; i<N; i++)

 {

  vector<int> row;

  for(j=0; j<N; j++)

  {

   infile>>edge;

   row.push_back(edge);

  }

  Graph.push_back(row);

 }

 //COLORING to INDEPENDENT SET conversion

 cout<<"Graph has N = "<<N<<" vertices."<<endl;

 cout<<"Find a vertex coloring using at most C colors. Enter C = ";

 cin>>C;

  //Complete garph on C verteices

  vector<vector<int> > KC;

  vector<int> row1;

  for(int i=0; i<C; i++) row1.push_back(1);

  for(int i=0; i<C; i++) KC.push_back(row1);

  for(int i=0; i<C; i++) KC[i][i]=0;

  //Cartesian product of Graph and KC

  vector<vector<int> > graph;

  vector<int> rowind;

  for(int i=0; i<C*N; i++) rowind.push_back(0);

  for(int i=0; i<C*N; i++) graph.push_back(rowind);

  for(int i=0; i<C*N; i++)

  for(int j=0; j<C*N; j++)

  {

   int i_G=i/C, i_KC=i%C, j_G=j/C, j_KC=j%C;

   if((i_G==j_G) && (KC[i_KC][j_KC]==1)) graph[i][j]=1;

   if((Graph[i_G][j_G]==1) && (i_KC==j_KC)) graph[i][j]=1;

  }

  //Assign parameters for finding independent sets in the graph

  n=N*C; K=n/C; k=n-K;

 //Find Neighbors

 vector<vector<int> > neighbors;

 for(i=0; i<graph.size(); i++)

 {

  vector<int> neighbor;

  for(j=0; j<graph[i].size(); j++)

  if(graph[i][j]==1) neighbor.push_back(j);

  neighbors.push_back(neighbor);

 }



 //Find Independent Sets

 bool found=false;

 cout<<"Finding Vertex Colorings..."<<endl;

 min=n+1;

 vector<vector<int> > covers;

 vector<int> allcover;

 for(i=0; i<graph.size(); i++)

 allcover.push_back(1);

 for(i=0; i<allcover.size(); i++)

 {

  if(found) break;

  counter++; cout<<counter<<". ";  outfile<<counter<<". ";

  vector<int> cover=allcover;

  cover[i]=0;

  cover=procedure_1(neighbors,cover);

  s=cover_size(cover);

  if(s<min) min=s;

  if(s<=k)

  {

   outfile<<"Vertex Coloring ("<<n-s<<"): ";

   for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<"("<<j/C+1<<","<<j%C+1<<") ";

   outfile<<endl;

   cout<<"Vertex Coloring Size: "<<n-s<<endl;

   covers.push_back(cover);

   found=true;

   break;

  }

  for(j=0; j<n-k; j++)

  cover=procedure_2(neighbors,cover,j);

  s=cover_size(cover);

  if(s<min) min=s;

  outfile<<"Vertex Coloring ("<<n-s<<"): ";

  for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<"("<<j/C+1<<","<<j%C+1<<") ";

  outfile<<endl;

  cout<<"Vertex Coloring Size: "<<n-s<<endl;

  covers.push_back(cover);

  if(s<=k){ found=true; break; }

 }

//Pairwise Intersections

 for(p=0; p<covers.size(); p++)

 {

  if(found) break;

  for(q=p+1; q<covers.size(); q++)

  {

   if(found) break;

   counter++; cout<<counter<<". ";  outfile<<counter<<". ";

   vector<int> cover=allcover;

   for(r=0; r<cover.size(); r++)

   if(covers[p][r]==0 && covers[q][r]==0) cover[r]=0;

   cover=procedure_1(neighbors,cover);

   s=cover_size(cover);

   if(s<min) min=s;

   if(s<=k)

   {

    outfile<<"Vertex Coloring ("<<n-s<<"): ";

    for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<"("<<j/C+1<<","<<j%C+1<<") ";

    outfile<<endl;

    cout<<"Vertex Coloring Size: "<<n-s<<endl;

    found=true;

    break;

   }

   for(j=0; j<k; j++)

   cover=procedure_2(neighbors,cover,j);

   s=cover_size(cover);

   if(s<min) min=s;

   outfile<<"Vertex Coloring ("<<n-s<<"): ";

   for(j=0; j<cover.size(); j++) if(cover[j]==0) outfile<<"("<<j/C+1<<","<<j%C+1<<") ";

   outfile<<endl;

   cout<<"Vertex Coloring Size: "<<n-s<<endl;

   if(s<=k){ found=true; break; }

   }

 }

 if(found) cout<<"Found  complete Vertex Coloring using at most "<<C<<" colors."<<endl;

 else cout<<"Could not find complete Vertex Coloring using at most "<<C<<" colors."<<endl

 <<"Maximum partial Vertex Coloring found for "<<n-min<<" vertices."<<endl;

 cout<<"See coloring.txt for results."<<endl;

 system("PAUSE");

 return 0;

}



bool removable(vector<int> neighbor, vector<int> cover)

{

 bool check=true;

 for(int i=0; i<neighbor.size(); i++)

 if(cover[neighbor[i]]==0)

 {

  check=false;

  break;

 }

 return check;

}



int max_removable(vector<vector<int> > neighbors, vector<int> cover)

{

 int r=-1, max=-1;

 for(int i=0; i<cover.size(); i++)

 {

  if(cover[i]==1 && removable(neighbors[i],cover)==true)

  {

   vector<int> temp_cover=cover;

   temp_cover[i]=0;

   int sum=0;

   for(int j=0; j<temp_cover.size(); j++)

   if(temp_cover[j]==1 && removable(neighbors[j], temp_cover)==true)

   sum++;

   if(sum>max)

   {

    max=sum;

    r=i;

   }

  }

 }

 return r;

}



vector<int> procedure_1(vector<vector<int> > neighbors, vector<int> cover)

{

 vector<int> temp_cover=cover;

 int r=0;

 while(r!=-1)

 {

  r= max_removable(neighbors,temp_cover);

  if(r!=-1) temp_cover[r]=0;

 }

 return temp_cover;

}



vector<int> procedure_2(vector<vector<int> > neighbors, vector<int> cover, int k)

{

 int count=0;

 vector<int> temp_cover=cover;

 int i=0;

 for(int i=0; i<temp_cover.size(); i++)

 {

  if(temp_cover[i]==1)

  {

   int sum=0, index;

   for(int j=0; j<neighbors[i].size(); j++)

   if(temp_cover[neighbors[i][j]]==0) {index=j; sum++;}

   if(sum==1 && cover[neighbors[i][index]]==0)

   {

    temp_cover[neighbors[i][index]]=1;

    temp_cover[i]=0;

    temp_cover=procedure_1(neighbors,temp_cover);

    count++;

   }

   if(count>k) break;

  }

 }

 return temp_cover;

}



int cover_size(vector<int> cover)

{

 int count=0;

 for(int i=0; i<cover.size(); i++)

 if(cover[i]==1) count++;

 return count;

}