【习题·搜索】Square Destroyer(启发式搜索IDA*)

2023-10-13 13:08

本文主要是介绍【习题·搜索】Square Destroyer(启发式搜索IDA*),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

下图左侧显示了一个用2 *(3 * 4)(= 24)火柴棍制成的完整3 * 3网格。所有火柴的长度都是一个。您可以在网格中找到许多不同大小的正方形。正方形的大小是其边长。在左图所示的网格中,有9个尺寸为1的正方形,4个尺寸为2的正方形和1个正方形的尺寸为3的正方形。

整个网格的每个火柴杆都标有唯一编号,该编号从左到右,从上到下分配,如左图所示。如果你从整个网格中取出一些火柴棍,那么网格中的一些正方形将被破坏,这导致一个不完整的3 3网格。右图示出了在移除编号为12,17和23的三个火柴棍后的不完整的3 3网格。这种移除破坏了5个尺寸为1的正方形,3个尺寸为2的正方形和1个正方形的尺寸为3的正方形。因此,不完整的网格不具有大小为3的正方形,但仍然具有4个尺寸为1的正方形和1个正方形的尺寸2。

在这里插入图片描述

作为输入,您将获得一个(完整或不完整)n n网格,其网格不超过2n(n + 1)个自然数5 <= n。您的任务是计算取出的最小火柴棍数量, 以销毁输入n n网格中存在的所有正方形。

题解

由于 n ≤ 5 n\ \leq \ 5 n  5,因此答案一定不会很大可以使用迭代加深来解决。

其次,我们可以设计一个估价函数:由于每一份正方形都要被破坏,因此我们可以枚举每一个正方形,暴力破坏四条边并记为一次操作;估价值为操作的次数。这种暴力的拆法显然小于或等于实际值。

然后就用IDA*搞就好了,在搜索的时候每一次找到每个完整的正方形枚举正方形的每一条边并破坏;能枚举小的就尽量枚举小的,因为可以降低复杂度;而且每一层只需要枚举一个正方形即可,因为只要枚举到一个完整的正方形一定要去掉,所以枚举的状态一定合法。

代码如下:


#include <bits/stdc++.h>using namespace std;int n,m,deep;struct node 
{bool no[100];
};inline int del(int n)
{return n*2+1;
}bool check(node now,int i,int len)
{for (int j=i;j<=i+len-1 && j<=m;++j)if (now.no[j]) return 1;for (int j=i+n,cnt=0;++cnt<=len && j<=m;j+=del(n))if (now.no[j]) return 1;for (int j=i+n+len,cnt=0;++cnt<=len && j<=m;j+=del(n))if (now.no[j]) return 1;for (int j=i+len*del(n);j<=i+len*del(n)+len-1 && j<=m;++j)if (now.no[j]) return 1;return 0;
}int func(node now)
{int sum=0;for (int len=1;len<=n;++len){for (int k=1,tot=0;k<=m && ++tot<=n-len+1;k+=del(n))for (int i=k,S=0;++S<=n-len+1 && i<=m;++i){if (check(now,i,len)) continue;sum ++;for (int j=i;j<=i+len-1 && j<=m;++j) now.no[j]=1;for (int j=i+n,cnt=0;++cnt<=len && j<=m;j+=del(n)) now.no[j]=1;for (int j=i+n+len,cnt=0;++cnt<=len && j<=m;j+=del(n)) now.no[j]=1;for (int j=i+len*del(n);j<=i+len*del(n)+len-1 && j<=m;++j) now.no[j]=1;}}return sum;
}bool dfs(node now,int x)
{if (x==deep){if (func(now)==0) {cout<<deep<<endl;return 1;}return 0;}if (x+func(now)>deep) return 0;for (int len=1;len<=n;++len){for (int k=1,tot=0;k<=m && ++tot<=n-len+1;k+=del(n))for (int i=k,S=0;++S<=n-len+1 && i<=m;++i){if (check(now,i,len)) continue;for (int j=i;j<=i+len-1 && j<=m;++j){now.no[j]=1;if (dfs(now,x+1)) return 1;now.no[j]=0;}for (int j=i+n,cnt=0;++cnt<=len && j<=m;j+=del(n)){now.no[j]=1;if (dfs(now,x+1)) return 1;now.no[j]=0;}for (int j=i+n+len,cnt=0;++cnt<=len && j<=m;j+=del(n)){now.no[j]=1;if (dfs(now,x+1)) return 1;now.no[j]=0;}for (int j=i+len*del(n);j<=i+len*del(n)+len-1 && j<=m;++j){now.no[j]=1;if (dfs(now,x+1)) return 1;now.no[j]=0;}return 0;}}return 0;
}void work(void)
{int k;cin>>n>>k;node st;m=2*n*(n+1);for (int i=1;i<=m;++i) st.no[i]=0;for (int i=1;i<=k;++i) {int k;cin>>k;st.no[k]=1;}for (deep=0;;++deep) if (dfs(st,0)) return; 
}int main(void)
{freopen("1.in","r",stdin);freopen("1.out","w",stdout);int T;cin>>T;while (T --) work();return 0;
}

这篇关于【习题·搜索】Square Destroyer(启发式搜索IDA*)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/203431

相关文章

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

HDU 1560 IDA*

给出n个串,求最短公共串(不要求连续) h ,最少还需要多长来匹配所有。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;imp

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

第六章习题11.输出以下图形

🌏个人博客:尹蓝锐的博客 希望文章能够给到初学的你一些启发~ 如果觉得文章对你有帮助的话,点赞 + 关注+ 收藏支持一下笔者吧~ 1、题目要求: 输出以下图形