现在的位置: 首页 > 综合 > 正文

枚举法(Enumeration)

2019年03月12日 ⁄ 综合 ⁄ 共 2074字 ⁄ 字号 评论关闭

1.算法思想

枚举法就是在解决某一问题时,枚举所有可能情况,而得到最终结果的方法。也叫暴力破解法(Brute Force)。

2.例子

2.1问题描述

4皇后问题。在4×4棋盘上放置4个皇后,使她们不会互相攻击。

2.2算法描述

我们用row[n]=m表示在棋盘的第n行的m列放置皇后。
我们枚举棋盘上摆皇后所有的可能。
验证摆法是否满足条件,使皇后不会互相攻击。

我们表示棋盘的方法保证了棋盘上每一行只会有一个皇后。验证皇后不会互相攻击,只需要验证每一列不会有多于一个皇后,对角线方向不会有多余一个皇后就可以了。

2.3代码

void FillBoard();
bool IsInterAttack();
void OutBoard();

#define ROW 4
int row[ROW+1];

/**//*void InitBoard()
{
    int i;
    for(i=0;i<=ROW;i++)
        row[i]=0;
}
*/


void FillBoard()
...{
    
int k1,k2,k3,k4;
    
for(k1=1;k1<=ROW;k1++)
        
for(k2=1;k2<=ROW;k2++)
            
for(k3=1;k3<=ROW;k3++)
                
for(k4=1;k4<=ROW;k4++)
                
...{
                    row[
1]=k1;
                    row[
2]=k2;
                    row[
3]=k3;
                    row[
4]=k4;
                    
if(!IsInterAttack())
                        OutBoard();
                }

                    
}


//output
void OutBoard()
...{
    
int k,i;
    printf(
"
");
    
for (i=1;i<=ROW;i++)
    
...{
        
for(k=1;k<=ROW;k++)
        
...{
            
if(row[i]==k)
                printf(
"");
            
else
                printf(
"");
        }

        printf(
"
");
    }

    printf(
"
");
}


//check if queens will attach each other
bool IsInterAttack()
...{
    
int i,k;
    
for(i=1;i<=ROW;i++)
    
...{
        
for(k=1;k<=ROW;k++)
        
...{
            
if(k==i) continue;
            
//check column
            if(row[i] == row[k]) return true;
            
//check slash diagonal direction
            if(i+row[i] == row[k] + k) return true;
            
//check back slash diagonal direction
            if(i-row[i] == k-row[k]) return true;
        }

    }

    
return false;
}


void queen_test()
...{
    FillBoard();    
}


int main(int argc, char* argv[])
...{
    queen_test();
    
return 0;
}

2.4运行结果


O * O O
O O O *
* O O O
O O * O


O O * O
* O O O
O O O *
O * O O

3.进一步思考

由于计算机擅长不厌其烦地快速重复某件事,所以这种方法在可能枚举值的数量少的时候很有效。一旦可能枚举值的数量很多,使计算机需要相当长的时间才能枚举所有情况,而这种情况是我们不能忍受的,我们就需要寻找更有效的办法了。

在解决4皇后问题中,我们采用的枚举方式是很笨的。如果棋盘的大小增加,那么循环的嵌套层数就会增加。如果棋盘的行、列数n是个动态变化的值,那么采用嵌套循环的方式枚举就不能解决问题了。

注意到row[1]、row[2]、row[3]、row[4]的可能取值实际是1、2、3、4的排列。推而广之,row[1]、row[2]、row[3]、……、row[n]的可能取值就是1、2、3、……、n的排列。那么我们就可以把我们的算法改进一下了。

【上篇】
【下篇】

抱歉!评论已关闭.