0. 摘要

本次作业，要求完成一个word search的程序，具体要求是：输入：一个包含20-60个单词的文件，各单词不大于20个字母，无空格。

输出：一个猜词游戏的字母矩阵，满足如下条件：

1. 每个单词在矩阵中出现，且只出现1次

2. 上下、下上、左右、右左及对角线共8个方向，每个方向均不少于2个单词排布。

3. 矩阵长宽可以不同

4. 不存在无效行或列

5. （进阶要求）矩阵为正方形

6. (进阶要求）矩阵四角有单词覆盖

对于这个题目的实现，在可解的基础上，最重要的是以一种相对高效的方式给出结果。为此，老师讲解了“简单粗暴”法、我也参与到同学们的讨论中。我认为，首先选择一个合适的骨架，在此基础上进行拓展是一个优秀的方法，在实现过程中，骨架的恰当选择和随机化算法的应用都将用来提高效率。

1. 程序框架

这样一个程序，我首先想到类似枚举的算法显然是不行的，为此我们必须找到某些优化条件，在大量的重试中，这会显现出很大的价值。通过观察成品word search的例子，我发现很多长单词都被放置在竖直方向。也许，先选出这样一个竖直的单词作为基础，是一个不错的切入点。为此，在第一阶段，我写了复杂而精准的评估函数。此函数将为每个骨架评估一个值，值越大，越理想，此后的工作就是循环调用产生函数，优先以优选的骨架为基础进行填充，直到得出结果。这里面，“骨架”定义为一个竖直放置的单词（主骨）加上其上搭出的一个方向的其他单词（次骨）。其具体实现，请看下一章详细说明。以下，简要介绍程序框架：

模式匹配函数，若给定的字符串与模式串不能匹配，返回-1。这里面模式串为“不完整的字符串”,如模式串”bei*ang*ni***sity”匹配于”beihanguniversity”。

int compare (string pattern,string ith)

绘图函数，负责将抽象表示的骨架映射到二维数组中，便于后面的函数调用来寻找出骨架的全部模式串string pattern[].参数中 num 表示骨架中主骨在str中的序号。skl[i][0]表示与主骨第i下标字母连接的次骨单词序号。skl[i][1]表示这个次骨与主骨公共字母在次骨串的下标。

void plot_skl_mtrcs(int num, int skl[60][2])

给定一个骨架，找出其全部模式串string pattern[]，用于后期评估骨架的可拓展性。

void find_all_prtn(int num, int skl[60][2])

骨架评估函数，调用上述程序，给定一个骨架，返回一个评估值。该值的大小能够评估选定骨架的理想程度，使得程序能够以较好的切入点进行尝试。

int esimate(int num, int skl[60][2])

作图函数，用于输出结果

void plot()

初始的读取

void init()

骨架选取与迭代

void set_skeleton()

然而，当这些过程完成后，我们还是发现矩阵的大小不够理想。这已经不可以在评估上解决了，因为我们遇到了一个瓶颈，对优化的考虑过于复杂但是在实现中逻辑及其复杂，实现难度很大，而即使不怎么进行骨架的选取，我们发现对于结果的影响也微乎其微。为此，我们进入第二阶段，淡化前期评估的复杂逻辑，转向随机化和大量枚举。第二阶段，我负责的评估部分400行代码大量精简（精简了也没有太大改变，计算机速度快），转而写出一个验证的程序，此程序不断调用前面写出的代码得到一个矩阵，指导矩阵符合要求停止。第二阶段，前面的代码被包装成头文件，验证部分调用之。最终效果姑且令人满意。

我也请教过鲁海浩和肖俊鹏一组，他们告诉我即使全部随机化，也比认真的优化差不到哪里，最多只会多一行一列矩阵而已。这与我的认识完全一致。这个程序启发我，在情况量大、难以入手的程序面前，其实最好的办法就是随机化。

2. 具体代码解释

因为最开始想得不对，我的核心工作在后面都精简了，而个人认为这个评估写的还是比较好，所以这一部分，我将主要解释自己之前写的部分的思路，之前的代码虽然与最终版本不用，但是更加清晰独立能说明功能。至于控制以及修改后的部分，请参阅我的队友熊英夫的博客 http://www.cnblogs.com/yuzuka

难度和复杂度较大的是void find_all_prtn(int num, int skl[60][2]) 和int esimate(int num, int skl[60][2])两个函数，前者找到四个方向的全部模式串，后者进行评估：

void find_all_prtn(int num, int skl[60][2])

首先调用plot_skl_mtrcs(num, skl)将骨架映射至二维数组skl_mtrcs，然后分别在4个方向上定义[beginY][beginX]和[endX][endY]两个点向中间夹逼，直到遇到彼此或者遇到字母。begin,end之间的部分用空格替换‘\0’得到当前位置的一个模式串。

针对不同情况，begin，end两点的横纵坐标的变化规律不同。代码如下：

1 /*  2  * 找出四个方向全部模式串，写入string pattern[]，pattern[i][0] = '\0'表示后面没有了。  3  * 四个方向为水平左到右，竖直上到下，还有左上到右下，和右上到左下。  4  */  5 void find_all_prtn(int num, int skl[60][2])  6 {  7     int i_ptn = 0, i, j, k;  8     int beginX, beginY, endX, endY;  9     char c; 10     plot_skl_mtrcs(num, skl); 11     //horizontal 12     for (i = 0; i < 100; ++i){ 13         endX = 99; 14         endY = 0; 15         while (beginX <= endX){ 16             if (skl_mtrcs[beginX][i] == '\0'){ 17                 beginX++; 18             } 19             if (skl_mtrcs[endX][i] == '\0'){ 20                 endX--; 21             } 22             if (skl_mtrcs[beginX][i] != '\0' && skl_mtrcs[endX][i] != '\0'){ 23                 break; 24             } 25         } 26         if (skl_mtrcs[i][beginX] != '\0'){ 27             for (j = 0; j <= endX - beginX; j++){ 28                 c = skl_mtrcs[beginX + j][i]; 29                 if (c = '\0'){ 30                     c = ' '; 31                 } 32                 pattern[i_ptn][j] = c; 33             } 34             pattern[i_ptn++][j] = '\0'; 35         } 36     } 37     //vertical 38     for (i = 0; i < 99; ++i){ 39         beginY = 0; 40         endY = 00; 41         while (beginY <= endY){ 42             if (skl_mtrcs[i][beginY] == '\0'){ 43                 beginY++; 44             } 45             if (skl_mtrcs[i][endY] == '\0'){ 46                 endY--; 47             } 48             if (skl_mtrcs[i][beginY] != '\0' && skl_mtrcs[i][endY] != '\0'){ 49                 break; 50             } 51         } 52         if (skl_mtrcs[beginY][i] != '\0'){ 53             for (j = 0; j <= endY - beginY; j++){ 54                 c = skl_mtrcs[beginY + j][i]; 55                 if (c = '\0'){ 56                     c = ' '; 57                 } 58                 pattern[i_ptn][j] = c; 59             } 60             pattern[i_ptn++][j] = '\0'; 61         } 62     } 63     //左上到右下 64     //stage 1 65     for (i = 99; i >= 0; --i){ 66         beginX = i; 67         beginY = 0; 68         endX = i; 69         endY = 99; 70         while (beginX <= endX && beginY <= endY){ 71             if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY < endY){ 72                 beginX++; 73                 beginY++; 74             } 75             if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY > endY){ 76                 endX--; 77                 endY--; 78             } 79             if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){ 80                 break; 81             } 82         } 83         if (skl_mtrcs[beginY][beginX] != '\0'){ 84             j = 0; 85             while (beginX <= endX && beginY <= endY){ 86                 c = skl_mtrcs[beginY][beginX]; 87                 if (c = '\0'){ 88                     c = ' '; 89                 } 90                 pattern[i_ptn][j] = c; 91                 j++; 92                 beginX++; 93                 beginY++; 94             } 95             pattern[i_ptn++][j] = '\0'; 96         } 97     } 98     //stage 2 99     for (i = 1; i <= 99; ++i){100         beginX = 0;101         beginY = i;102         endX = 99 - i;103         endY = 99;104         while (beginX <= endX && beginY <= endY){105             if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY < endY){106                 beginX++;107                 beginY++;108             }109             if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY > beginY){110                 endX--;111                 endY--;112             }113             if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){114                 break;115             }116         }117         if (skl_mtrcs[beginY][beginX] != '\0'){118             j = 0;119             while (beginX <= endX && beginY <= endY){120                 c = skl_mtrcs[beginY][beginX];121                 if (c = '\0'){122                     c = ' ';123                 }124                 pattern[i_ptn][j] = c;125                 j++;126                 beginX++;127                 beginY++;128             }129             pattern[i_ptn++][j] = '\0';130         }131     }132     //右上到左下133     //stage 1134     for (i = 0; i <= 99; ++i){135         beginX = i;136         beginY = 0;137         endX = 0;138         endY = i;139         while (beginX <= endX && beginY >= endY){140             if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY > endY){141                 beginX--;142                 beginY++;143             }144             if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY < endY){145                 endX++;146                 endY--;147             }148             if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){149                 break;150             }151         }152         if (skl_mtrcs[beginY][beginX] != '\0'){153             j = 0;154             while (beginX >= endX && beginY <= endY){155                 c = skl_mtrcs[beginY][beginX];156                 if (c = '\0'){157                     c = ' ';158                 }159                 pattern[i_ptn][j] = c;160                 j++;161                 beginX--;162                 beginY++;163             }164             pattern[i_ptn++][j] = '\0';165         }166     }167     //stage 2168     for (i = 98; i >= 0; --i){169         beginX = 99;170         beginY = 99 - i;171         endX = i;172         endY = 99;173         while (beginX <= endX && beginY >= endY){174             if (skl_mtrcs[beginY][beginX] == '\0' && beginX < endX && beginY > endY){175                 beginX--;176                 beginY++;177             }178             if (skl_mtrcs[endY][endX] == '\0' && endX > beginX && endY < endY){179                 endX++;180                 endY--;181             }182             if (skl_mtrcs[beginX][beginY] != '\0' && skl_mtrcs[endX][endY] != '\0'){183                 break;184             }185         }186         if (skl_mtrcs[beginY][beginX] != '\0'){187             j = 0;188             while (beginX >= endX && beginY <= endY){189                 c = skl_mtrcs[beginY][beginX];190                 if (c = '\0'){191                     c = ' ';192                 }193                 pattern[i_ptn][j] = c;194                 j++;195                 beginX--;196                 beginY++;197             }198             pattern[i_ptn++][j] = '\0';199         }200     }201     pattern[i_ptn][0] = '\0';202 }

int esimate(int num, int skl[60][2])

此函数从三个方面评估一个骨架：

est_amnt值：该骨架直接解决了多少单词的连接问题。我认为一个好的骨架，其主骨应当有较好的长度，并又较多经常出现的单词。比如单词see中出现2次最常见字母e，一定比ant这样的词更易拼接，当然这是长度一定的情况下。因此，est_amnt值越高，能够体现主骨架长度和可拓展性优秀，这样的骨架被选出，剩下没解决的问题就会少。

est_extnd值：表示整个骨架（次骨架展开出去的部分）的可拓展性如何。这个值越高，这个骨架为基础产生的矩阵就越小，满足条件的概率就越高。est_extnd的值，由骨架外的单词中能够与pattern[]模式串匹配的个数决定。能够匹配的越多，可拓展性就越好。

ext_shp:最后一个方面是骨架形状是否理想。如果一个骨架在某个方向分布十分不均匀，则结果很可能难以满足没有无效行无效列并且四角均有单词的要求。这里面，我们定义重心这个概念。重心定位于竖直放置的主骨之上，次骨左右分配的不均衡量累加到est_shp这个值中。est_shp是个小于零的值，其绝对值越大，表示形状越不理想。

此外，我定义ESTIMATE_WEIGHT_AMNT，ESTIMATE_WEIGHT_EXTND，STIMATE_WEIGHT_SHP_H，ESTIMATE_WEIGHT_SHP_V4个宏定义。他们是上述三个方面的加权值。这么做的原因是便于后期调试过程中便捷的修改其比重，以此调整评估函数各个考虑方面的权重，达到一个合适的比例，使得函数返回的值能有较好的评估性能。

这部分代码为：

/* * 评估函数。返回值越大越好，正负都有可能。 * num主骨架序号，skl[][0]次骨架序号，skl[][1]次骨架与主骨架连接的字母在次骨架串中的下标。 */ int esimate(int num, int skl[60][2]) {    string s;    string skl_main = strs[num]; // 主骨架    int i, j, k;    int est_rslt, est_amnt = 0, est_extnd = 0, est_shp_h = 0, est_shp_v; // 各个小方面的评估值    char c;    //主骨架连接出的次骨架的个数    if(ESTIMATE_WEIGHT_AMNT != 0)    {        for(i = 0; i < skl_main.length(); ++i)        {            if(skl[i][0] != -1)                est_amnt++;        }    }    //骨架可拓展性    int flag;    if(ESTIMATE_WEIGHT_EXTND != 0)    {        find_all_prtn(num, skl);        for(i = 0; pattern[i][0] != '\0'; i++) // every pattern        {            for(j = 0; j < n; j++) // every pattern with every word            {                                //omit main skeleton                if(j == num)                    continue;                //omit deputy skeletons                flag = 0;                for(k = 0; k < skl_main.length(); ++k)                {                    if(j == skl[k][0])                    {                        flag = 1;                        break;                    }                }                if(flag)                    continue;                //compare                if(compare(pattern[i], strs[j]) != -1 && compare(pattern[i],strrev( &(strs[j][0]) )) != -1)                {                    est_extnd++;                    break;                }            }        }    }    //骨架形状 est_shp < 0,绝对值越小越好    //考虑水平方向失衡程度    if(ESTIMATE_WEIGHT_SHP_H != 0)    {        int unbalance_h, p, l;        for(i = 0; i <= est_amnt; ++i)        {            s = strs[ skl[i][0] ];            l = s.length();            for(int mid = l / 2, j = 0; mid - j >=0; ++j)            {                if(s[mid - j] == skl_main[i])                {                    p = mid - j;                    break;                }                    else if(s[mid + j] == skl_main[i])                                      {                    p = mid + j;                    break;                }            }            unbalance_h = 2 * p - l + 1;            if(unbalance_h < 0)                unbalance_h *= -1;            est_shp_h -= unbalance_h;                    }        est_shp_h /= est_amnt;    }    return ESTIMATE_WEIGHT_AMNT * est_amnt             + ESTIMATE_WEIGHT_EXTND * est_extnd             + ESTIMATE_WEIGHT_SHP_H * est_shp_h            + ESTIMATE_WEIGHT_SHP_V * est_shp_v;}

此处附上辅助函数plot_skl_mtrcs.

1 char pattern[240][60]; //storage tmp matrics for finding patterns 2 char skl_mtrcs[100][100]; 3 /* 4  * 把骨架画出来，供分析所有模式串使用 5  * skl[i][j], j = 0 表示次骨架单词的序号，j = 1表示副骨架这个单词的第几个字母与主骨架结合。所有序号以0开始。 6  */ 7 void plot_skl_mtrcs(int num, int skl[60][2]) 8 { 9     int Lm, L, p, mid, i, j;10     int X, Y;11     char c;12     string s;13     //plot main skeleton14     s = strs[num];15     Lm = s.length();16     for(int mid = Lm / 2, k = 0; mid - k >=0; ++k)17     {18         skl_mtrcs[50][50 - k] = s[mid - k];19         skl_mtrcs[50][50 + k] = s[mid + k]; // 主骨架偶数个元素，最后一个该是 /0  再验证20     }21     //plot each word on main skeleton22     for (i = 0; i < strs[num].length(); ++i){23         if (skl[i][0] == -1){24             continue;25         }26         L = strs[skl[i][0]].length();27         p = skl[i][1];28         for (j = 0; j < L; j++){29             c = strs[skl[i][0]][j];30             X = 50 - p + j;31             Y = 50 - (Lm / 2 - i) - (p - j);32             skl_mtrcs[X][Y] = c;33         }34     }35 }

View Code

第二阶段，使用下面代码循环调用前述修改的函数并且验证：

1 int main() 2 { 3     FILE * fout = fopen(output,"w"); 4     int i,j; 5     char *a; 6     bool visited[60]; 7     string ss1,ss2,ss3; 8     srand(time(0)); 9     int minx=0,miny=0,maxx=1000,maxy=1000,sum,maxsum;10     a = (char *)malloc(sizeof(char)*1000000);11     for (int times=0;times<100;times++)12     {13         deal(a,&minx,&miny,&maxx,&maxy,&sum,ss1,ss2,ss3);14     }15     for (i=minx;i<=maxx;i++)16     {17 18         for (j=miny;j<=maxy;j++)19         {20             if (a[i*1000+j]!=' ')21             {22                 fprintf(fout,"%c ",a[i*1000+j]);23             }24             else {fprintf(fout," ");}25         }26         fprintf(fout,"\n");27 28     }29     cout<
     
      <
      
       <
       
        <
        
         <
         
          <

3. 结果与说明

未填充空白的运行结果是：（其实是正方形）

虽然已经写得头痛..程序还是不完美，在四角均有单词这个问题上还不能完全满足要求。

	Personal Software Process Stages	时间百分比(%)	实际花费的时间 (分钟)	原来估计的时间 (分钟)
Planning	计划
· Estimate	· 估计这个任务需要多少时间，把工作细化并大致排序	5	30	30
Development	开发
· Analysis	· 需求分析 (包括学习新技术)	15	90	90
· Design Spec	· 生成设计文档	0
· Design Review	· 设计复审 (和同事审核设计文档)
· Coding Standard	· 代码规范 (制定合适的规范)	5	30	30
· Design	· 具体设计	15	90	90
· Coding	· 具体编码	30	大于一天	180
· Code Review	· 代码复审	5	30	30
· Test	· 测试（自我测试，修改代码，提交修改）	15	90	90
Reporting	总结报告
· Test Report	· 测试报告	5	30	30
· Size Measurement	· 计算工作量	1	6	6
· Postmortem & Improvement Plan	· 事后总结, 并提出改进	4	25	25
Total	总计	100%	总用时	一周啊