还剩12页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
作者声明此题所附程序,深搜是正确的,会输出所有解简单推理程序有误《猜图游戏》解题报告Bysx349【摘要】核心算法思想深搜/数学推理主要数据结构其他辅助知识时间复杂度(深搜,显然在强剪枝下常数极小)/(推理,常数也很小)空间复杂度(常数极小)【题目大意】给定一系列规则和一系列数据,根据规则通过简单推理还原图像(“简单推理”的定义为,仅考虑某一行(列)的信息以及该行(列)中已知的方块的颜色,推理出该行(列)中更多方块的颜色)【算法分析】尽管一开始就看到了简单推理这句话,但是一开始并没有想到有效利用这一条件的方法,于是先考虑到用深搜的做法,配合强剪枝来解决显然,深搜也有好几种做法,可以先搜索行,也可以先搜索列(以搜索行为例)假设我们搜索到第I行对每一列维护一个表,搜索到第I行的第J个格子,将这一个各自的状态加入这个表,并且对这个列的表与这个列的状态进行比对这是一个很普遍的剪枝,显然,这个剪枝的关键在于如何维护这个表因为这个表中有三种状态填0(代表白格),填1(代表黑格),以及填-1(代表未确定)在一开始考虑的时候,我先把所有已经确定的行和列都填好,因此就必须把-1和0区别开来,但是为了接替方便,最后还是将这些已经确定的行作为搜索时的小剪枝,而避免了-1和0的区分,因此,表的状态就只要用一个布尔数组来判断一下就行了但是布尔数组每次的判断还是要的复杂度,在深搜的过程中如果每一步都判断,那么就必然会超时因此需要有更好的方法维护这个表显然,每一列所要求的数字排列是有序的,那么,对于每一列我们都可以用两个数字M,N来表示当前该列的状态,即已经判断了该列的前M个数,并且第M+1个数已经检查了N格(显然N是小于第M+1个数的)如果当前我们判断这一格是白格,那么判断之前的状态中N是否等于第M+1个数,如果等于,则M加上1,N归零,否则如果小于,则显然不可行,回溯;如果当前我们判断这一个是黑格,那么判断之前的状态中N+1是否超过第M+1个数,如果超过,那么不可行,如果不超过,那么N加上1;当判断完整张表之后,相当于在整张表之下全部添加一列白格,在对每一列进行判断这样每次的判断复杂度就只有了那么如何来搜索某一行的状态呢?我们用J,K两个数来表示我们搜...。