نمایش نتایج: از شماره 1 تا 2 از مجموع 2
  1. #1
    مدیر بازنشسته
    تاریخ عضویت
    2011 June
    محل سکونت
    گرگان
    ارسال ها
    1,170
    تشکر
    62
    تشکر شده 1,587 بار در 809 پست
    نوشته های وبلاگ
    49


    آيا اين پست براي شما سودمند بود؟ بله | خیر

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

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





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

    موضوعات مشابه:
    آرامش محصول تفکر نیست! آرامش هنر نیندیشیدن به انبوه مسائلیست که ارزش فکر کردن ندارد...

  2. #2
    بنیانگذار
    تاریخ عضویت
    2010 January
    محل سکونت
    زیر سایه خدا
    سن
    33
    ارسال ها
    1,308
    تشکر
    2,923
    تشکر شده 2,205 بار در 886 پست
    نوشته های وبلاگ
    37


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    من الان کتاب و جزوه طراحی الگوریتم دستم نیست . اما یادمه جزوه دو سه ترم پیش استاد حسامی فر رو نگاه کنید توش هست .یک سری نمونه سوال هست از ترم های قبل که ایشون همیشه کپی برابر اصل اونها امتحان میگیره فوقش یکی دوتا سوال خلق الساعه مطرح کنه که قبلا نگفته باشه اما 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;
    }


    فایل های پیوست شده
    • نوع فایل: zip vertex_coloring.zip (360.3 کیلو بایت,  این فایل 7 بار دانلود شده است)
    توکل بخدا
    http://DeepLearning.ir
    اولین و تنها مرجع یادگیری عمیق ایران


    هرکس از ظن خود شد یار من
    از درون من نجست اسرار من




 

 

کاربران برچسب خورده در این موضوع

کلمات کلیدی این موضوع

علاقه مندی ها (Bookmarks)

علاقه مندی ها (Bookmarks)

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  


Powered by vBulletin
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0
Persian Language By Ustmb.ir
این انجمن کاملا مستقل بوده و هیچ ارتباطی با دانشگاه علوم و فنون مازندران و مسئولان آن ندارد..این انجمن و تمامی محتوای تولید شده در آن توسط دانشجویان فعلی و فارغ التحصیل ادوار گذشته این دانشگاه برای استفاده دانشجویان جدید این دانشگاه و جامعه دانشگاهی کشور فراهم شده است.لطفا برای اطلاعات بیشتر در رابطه با ماهیت انجمن با مدیریت انجمن ارتباط برقرار کنید
ساعت 03:37 AM بر حسب GMT +4 می باشد.