搜索算法

求一个搜索算法
在一个 100 * 100 的格子区域内分布着不规则的可建筑的区域，在这个区域上可以修建 2 * 3， 3 * 2， 4 * 5 等不同长宽的矩形建筑，现在要找出一种浪费的空间最少，且能修建更多大面积建筑的方法。修建更多大面积建筑是指在浪费的空间相同的情况下优先修建 4 * 5 而不是 2 * 3.

输入: 一个 100 * 100 大小的 bool 数组，为 true 的区域表示可以修建，为 false 的区域为不可修建。
输出：一个包含修建的建筑列表的数组, 建筑的信息包括建筑的位置，宽和高。

我自己写了个算法，效率太低了，当浪费的空间太大时非常慢，消耗的内存也太大，搜索不出来，看看各位高手有什么好的办法？

附我自己的代码：

------解决方案--------------------

探讨
好吧，我说有效率问题是我臆断了，那你给个用 DLX 算法来解决这个问题的例子，用强有力的实践来证明我说的有效率问题是完全错误的！
你给的链接那个英文的确实没看，看着英文就头晕，帖子里的问题我看了，那是一个全搜索，要找出所有情况。我这里并不需要，只要找到 1 个就可以了。要完全搜索完是我臆断有效率问题的主要原因。

另外，我不是说障碍点多，而是说【算法的障碍】是要搜索点太多了，断句断错了。

------解决方案--------------------
我先说个预处理的思路，如果建筑只包括4*5,2*3,3*2这3个规格，有些情况是根本不可能被覆盖到的，因此可以先将这些小块设为true，
也许会降低一些计算量。

比如(0为空位置)：

0000011100
0000001100
0000000111
0000000000
0000000000

右上的4个0是不可能被覆盖的。

[0,5][1,6]这两个点不可能同时被覆盖
[1,6][2,7]这两个点不可能同时被覆盖

这样的情况下，也许可以舍掉[1,6]这个点
------解决方案--------------------
不知道是否可以先计算出一些可以完美覆盖的矩形的尺寸，比如：

2*3 2*6 2*9 ...... 2*99
3*2 3*4 3*6 ...... 3*100
4*3 4*5 4*6 4*8 4*9 4*10 ...... 4* 100
5*6 5*12 5*18......5*96
..........

然后判断可否将空地划分为若干个这个集合里面的矩形。
------解决方案--------------------
写了一个算纯矩形的,没有考虑相同面积下4*5和2*3的问题（如果考虑的话，效率恐怕会下降到n^3）

不知道有了这些数据,对lz后面的程序能否有些帮助

效率大概为(m+k)*n^2
m为建筑的数量，k为建筑最宽的边+建筑最长的边，n为空地的大小

C# code


        private void button2_Click(object sender, EventArgs e)
        {
            int[][] buildingSize = new int[][] { new int[] { 2, 3 }, new int[] { 3, 2 }, new int[] { 4, 5 } };
            //记录浪费块数的数组
            int[,] pRectangle = searchpRect(buildingSize, 100,100);
        }

        private int[,] searchpRect(int[][] buildingSize, int width,int height)
        {
            //初始化矩阵
            int[,] pReturn = new int[width, height];
            width++;
            height++;

            //初始化矩阵2
            int[,] pRectangle = new int[width, height];
            for (int i = 0; i < width; i++)
                for (int j = 0; j < height; j++)
                    pRectangle[i, j] = i * j;

            //生成可完美覆盖的矩形
            int maxWidth = 0;
            int maxHeight = 0;

            foreach (int[] bsize in buildingSize)
            {
                pRectangle[bsize[0], bsize[1]] = 0;
                maxWidth = Math.Max(bsize[0], maxWidth);
                maxHeight = Math.Max(bsize[1], maxHeight);

                for (int i = bsize[0]; i < width; i++)
                    for (int j = bsize[1]; j < height; j++)
                        if ((pRectangle[i - bsize[0], j] == 0 && pRectangle[bsize[0], j] == 0) || (pRectangle[i, j - bsize[1]] == 0 && pRectangle[i, bsize[1]] == 0))
                            pRectangle[i, j] = 0;
            }

            //生成最少浪费块数
            for (int i = 1; i < width; i++)
                for (int j = 1; j < height; j++)
                    if (pRectangle[i, j] != 0)
                    {
                        pRectangle[i, j] = MinWaste(maxWidth, maxHeight, i, j, pRectangle);
                        pReturn[i - 1, j - 1] = pRectangle[i, j];
                    }

            return pReturn;
        }

        private int MinWaste(int sWidth,int sHeight, int x, int y, int[,] Rectangle)
        {
            int startX = Math.Max(x - sWidth,1);
            int startY = Math.Max(y - sHeight,1);
            int min = x * y;

            for (int i = startX; i < x; i++)
                min = Math.Min(Rectangle[i, y] + Rectangle[x - i, y],min);

            for (int i = startY; i < y; i++)
                min = Math.Min(Rectangle[x, i] + Rectangle[x, y - i], min);

            return min;
        }

相关推荐