馬が碁盤を踏む貪欲なアルゴリズム

【問題の説明】馬の遍歴問題.8×8方格の碁盤では、任意の指定方格から、馬のために碁盤の各格を歩き回り、一度しか通らない経路を探します.【初歩設計】まずこれは探索問題であり、深さ優先探索を用いて解く.アルゴリズムは以下の通りである:1、初期位置座標x,yを入力する;2、ステップc:c>64が1つの解を出力すると、前のステップc-(x,y)←c計算(x,y)に戻るの8つの方位のサブノードを選択し、その実行可能なサブノードを選択してすべての実行可能なサブノードをループし、ステップc++繰り返し2は明らかに(2)再帰的に呼び出されるプロセスであり、大体以下の通りである.
 

void dfs(int x,int y,int count)
{
    int i,tx,ty;
if(count>N*N)
    {
        output_solution();//     
    return;
    }
    for(I=0;i<8;++i)
    {
        tx=hn[i].x;//hn[]         
    ty=hn[i].y;
        s[tx][ty]=count;
    dfs(tx,ty,count+1);//    
        s[tx][ty]=0;
    }
}

 
これは完全に実行可能で、それはすべての解を入力しますが、馬は8を遍歴します.×8時解は非常に多く,天文数字で形容しても過言ではないが,これでは解の過程が非常に遅く,1つの解を出すのも非常に遅い.
どのようにして急速に部分解を得ることができますか?
【欲張りアルゴリズム】
実は馬が碁盤を踏む問題はとっくに提起されていて、1823年にJ.C.Warnsdorffは有名なアルゴリズムを提出しました.各ノードがその子ノードを選択する際には、「出口」の最小値を優先して探索するが、「出口」は、これらの子ノードのうち実行可能な子ノードの個数、すなわち「孫」のノードが少ないほど優先的にジャンプすることを意味し、なぜこのように選択するのかは、出口の多い子ノードを優先的に選択する場合に、局所的に最適な方法である.出口の少ない子結点はますます多くなります「死」の接点が現れる可能性が高い(その名の通り出口がなくスキップもしていないノード)では、次の検索は純粋に無駄であり、無駄な時間を浪費し、逆に毎回出口の少ないノードジャンプを優先的に選択すると、出口の少ないノードがますます少なくなり、成功する機会が大きくなります.このアルゴリズムは欲張りアルゴリズムと呼ばれ、貪欲アルゴリズムや啓発とも呼ばれます解の過程全体の局所を最適に調整するアルゴリズムを示し,最適解または部分解を求めるのにのみ適用され,最適解を求めることはできない.このような調整方法は貪欲戦略と呼ばれ、どのような問題についてどのような貪欲戦略が必要かは不確定であり、具体的な問題は具体的に分析されている.実験は馬遍歴問題が上の貪欲な策略を運用した後に解の速度が非常に明らかに向上したことを証明することができて、もし1つの解を求めるならば甚だしきに至っては遡及しなくて完成することができて、このアルゴリズムが提出した時世界にはまだコンピュータがなくて、この方法は完全に手作業で解を求めることができて、その効率は想像することができます.
前のアルゴリズムの基礎の上で、いくつかのプログラムを追加して実現します.
関数1:ノード出口の計算
 

int ways_out(int x,int y)
{
    int i,count=0,tx,ty;
    if(x<0||y<0||x>=N||y>=N||s[x][y]>0)
    return -1;//-1              
    for(i=0;i<8;++i)
    {
        tx=x+dx[i];
        ty=y+dy[i];
        if(tx<0||ty<0||tx>=N||ty>=N)
            continue;
        if(s[tx][ty]==0)
            ++count;
    }
    return count;
}

 
関数2:ノード出口でソート
 

void sortnode(h_node *hn,int n)//       ，          8
{
    int i,j,t;
    h_node temp;
    for(i=0;i<n;++i)
    {
        for(t=i,j=i+1;j<n;++j)
            if(hn[j].waysout<hn[t].waysout)
            t=j;
        if(t>i)
        {
            temp=hn[i];
            hn[i]=hn[t];
            hn[t]=temp;
        }
    }
}

 
関数3:変更後の検索関数
 

void dfs(int x,int y,int count)
{
    int i,tx,ty;
    h_node hn[8];
    if(count>N*N)
    {
        output_solution();
        return;
    }
    for(i=0;i<8;++i)//       
    {
        hn[i].x=tx=x+dx[i];
        hn[i].y=ty=y+dy[i];
        hn[i].waysout=ways_out(tx,ty);
    }
    sortnode(hn,8);
    for(i=0;hn[i].waysout<0;++i);//       
    for(;i<8;++i)
    {
        tx=hn[i].x;
        ty=hn[i].y;
        s[tx][ty]=count;
        dfs(tx,ty,count+1);
        s[tx][ty]=0;
    }
}

 
関数4:主調関数
 

void main()
{
    int i,j,x,y;
    for(i=0;i<N;++i)//   
        for(j=0;j<N;++j)
            s[i][j]=0;
    printf("Horse jump while N=%d
Input the position to start:",N);
    scanf("%d%d",&x,&y);//      
    while(x<0||y<0||x>=N||y>=N)
    {
    printf("Error! x,y should be in 0~%d",N-1);
    scanf("%d%d",&x,&y);
    }
    s[x][y]=1;
    dfs(x,y,2);//    
}