algorithm - 仿真和 Ad-Hoc 优化算法

Question

在 N 乘 M 的矩形区域中有镜子正方形(1 <= N，M <= 1,000)。在每个方格中，有双两个对角之间的一面镜子。这两个可能配置由 / 表示(镜像连接左下角到右上角)和\(一个连接左上角和右下角的镜像)。

考虑向这个正方形发射光束。您可以沿网格的某列或某行垂直或水平发射光束。这会导致光束根据排列反射特定顺序的镜子。当一束光打到一面镜子上时，由于镜子都是对角线的，被反射的垂直光束将开始向水平方向行进，反之亦然。

能反射光束的最多有多少面镜子如果光可以无限期地反射，答案是-1。因此，给定网格的排列，问题是计算这个最大数

例如:具有如下配置的 3 x 3 网格:

/\\
\\\
/\/

将有一个输出:

3

约束:网格最大可达 1000 x 1000 大

将光束照射到中间的柱子上，您会得到 3。

我的解决方案:

从每个可能的位置(所有外边缘位置)发射光束。模拟这些光束并在光束退出时完成计数。如果光束再次击中同一位置，则输出 -1。我的解决方案只适用于小案例，但不适用于网格超过 100 x 100 的大案例，它需要很长时间才能完成。

我想把它减少到O( 200 万)。

能否请您推荐一些算法来提供帮助？

Answer 1

这听起来是个有趣的问题。 @Xavier Holt 的评论可能非常重要:“光束永远不会无限期地反射”。每个旨在跟踪访问过的字段(即检查某个字段是否被访问过两次)的数据结构都可能 - 在最坏的情况下 - 显着减慢整个过程。

根据 mcdowella 的建议，基于图形的方法在这里可能是可行的。但是由于光束如何穿过镜子网格的规则非常简单(并且，如上所述，循环检测等不是必需的)，可以将其归结为穿过二维阵列。当前状态由当前位置 (x,y) 和当前方向 (dy,dy) 表示，根据遇到的每种镜像类型进行更新。

我刚刚实现了这个(用 Java)。 computeResults 方法计算 5 元素 int[] 数组的列表，其中

• result[0] = 输入 x 坐标
• result[1] = 输入 y 坐标
• result[2] = 进入 x 方向
• result[3] = 输入 y 方向
• result[4] = 离开镜像字段前的步数

“核心逻辑”在simulate 方法中。

某些部分(尤其是将字段和解决方案路径渲染到框架中的部分)相当快且非常脏，但也许有人会发现它很有趣。无论如何，它在一台非常旧的 PC 上可以在几秒钟内计算出 2000x2000 网格的解决方案。

import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class MirrorTracer
{
    public static void main(String[] args)
    {
        //basicTest();
        largerTest();
    }

    private static void basicTest()
    {
        String input =
            "SBB" +
            "BBB" +
            "SBS";
        int sizeX = 3;
        int sizeY = 3;
        int array[][] = createArray(input, sizeX, sizeY);

//        int n = simulate(array, 2, 0, 0, 1);
//        System.out.println(n);

        List<int[]> results = computeResults(array, sizeX, sizeY);
        printResults(array, sizeX, sizeY, results);
    }

    private static void largerTest()
    {
        int sizeX = 60;
        int sizeY = 60;
        int array[][] = createRandomArray(sizeX, sizeY, new Random(0));

        List<int[]> results = computeResults(array, sizeX, sizeY);
        printResults(array, sizeX, sizeY, results);

        showResult(array, sizeX, sizeY, findBestResult(results));
    }



    private static List<int[]> computeResults(int array[][], int sizeX, int sizeY)
    {
        List<int[]> results = new ArrayList<int[]>();
        for (int x=1; x<sizeX+1; x++)
        {
            results.add(compute(array, x, 0, 0, 1));
            //results.add(compute(array, x, sizeY+1, 0, -1));
        }
        for (int y=1; y<sizeY+1; y++)
        {
            results.add(compute(array, 0, y, 1, 0));
            //results.add(compute(array, sizeX+1, y, -1, 0));
        }
        return results;
    }

    private static int[] compute(int array[][], int x, int y, int dx, int dy)
    {
        int nx = x + dx;
        int ny = y + dy;
        int n = simulate(array, x, y, dx, dy);
        return new int[]{ nx-1, ny-1, dx, dy, n };
    }

    private static int simulate(int array[][], int x, int y, int dx, int dy)
    {
        int steps = 0;
        while (true)
        {
            int nx = x + dx;
            int ny = y + dy;
            if (isOnBorder(array, nx, ny))
            {
                break;
            }
            //System.out.println("Move from "+x+" "+y+" in "+dx+" "+dy+" to "+nx+" "+ny);
            int ndx = dy;
            int ndy = dx;
            if (array[nx][ny] == '/')
            {
                ndx = -dy;
                ndy = -dx;
            }
            x = nx;
            y = ny;
            dx = ndx;
            dy = ndy;
            steps++;
        }
        return steps;
    }

    private static boolean isOnBorder(int array[][], int x, int y)
    {
        return 
            x == 0 || x == array.length - 1 ||
            y == 0 || y == array[x].length - 1;
    }







    private static int[][] createArray(String input, int sizeX, int sizeY)
    {
        int array[][] = new int[sizeX+2][sizeY+2];
        for (int y=1; y<sizeY+1; y++)
        {
            for (int x=1; x<sizeX+1; x++)
            {
                char c = input.charAt((x-1) + (y-1) * sizeX);
                array[x][y] = c == 'S' ? '/' : '\\';
            }
        }
        return array;
    }

    private static int[][] createRandomArray(
        int sizeX, int sizeY, Random random)
    {
        int array[][] = new int[sizeX+2][sizeY+2];
        for (int y=1; y<sizeY+1; y++)
        {
            for (int x=1; x<sizeX+1; x++)
            {
                boolean b = random.nextBoolean();
                array[x][y] = b ? '/' : '\\';
            }
        }
        return array;
    }


    private static void printResults(
        int array[][], int sizeX, int sizeY, List<int[]> results)
    {
        print(array, sizeX, sizeY);
        for (int result[] : results)
        {
            printResult(result);
        }

        int bestResult[] = findBestResult(results);
        System.out.println("Longest sequence:");
        printResult(bestResult);
    }

    private static void print(int array[][], int sizeX, int sizeY)
    {
        for (int y=1; y<sizeY+1; y++)
        {
            for (int x=1; x<sizeX+1; x++)
            {
                System.out.print((char)array[x][y]);
            }
            System.out.println();
        }
    }

    private static int[] findBestResult(List<int[]> results)
    {
        int maxLength = -1;
        int maxLengthResult[] = null;
        for (int result[] : results)
        {
            if (result[4] > maxLength)
            {
                maxLength = result[4];
                maxLengthResult = result;
            }
        }
        return maxLengthResult;

    }

    private static void printResult(int result[])
    {
        int x = result[0];
        int y = result[1];
        int dx = result[2];
        int dy = result[3];
        int n = result[4];
        System.out.println("Entering at "+x+" "+y+" in direction "+dx+" "+dy+" does "+n+" steps");
    }





    private static void showResult(
        final int array[][], final int sizeX, final int sizeY, 
        final int bestResult[])
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI(array, sizeX, sizeY, bestResult);
            }
        });
    }

    private static void createAndShowGUI(
        final int array[][], final int sizeX, final int sizeY, 
        final int bestResult[])
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        JPanel resultPanel = new JPanel()
        {
            protected void paintComponent(Graphics g) 
            {
                super.paintComponent(g);

                int cellSizeX = getWidth() / (sizeX+2);
                int cellSizeY = getHeight() / (sizeY+2);

                g.setColor(Color.BLACK);
                for (int y=1; y<sizeY+1; y++)
                {
                    for (int x=1; x<sizeX+1; x++)
                    {
                        int x0 = x * cellSizeX;
                        int y0 = y * cellSizeY;
                        int x1 = x0 + cellSizeX;
                        int y1 = y0 + cellSizeY;
                        if (array[x][y] == '/')
                        {
                            g.drawLine(x0+2, y1-2, x1-2, y0+2);
                        }
                        else
                        {
                            g.drawLine(x0+2, y0+2, x1-2, y1-2);
                        }
                    }
                }
                g.setColor(Color.RED);
                int dx = bestResult[2];
                int dy = bestResult[3];
                int x = bestResult[0]-dx+1;
                int y = bestResult[1]-dy+1;
                paintSimulation(g, array, x, y, dx, dy, cellSizeX, cellSizeY);
            }

            private int paintSimulation(
                Graphics g, int array[][], int x, int y, 
                int dx, int dy, int cellSizeX, int cellSizeY)
            {
                int steps = 0;
                while (true)
                {
                    int nx = x + dx;
                    int ny = y + dy;

                    int x0 = x * cellSizeX + cellSizeX / 2;
                    int y0 = y * cellSizeY + cellSizeY / 2;
                    int x1 = nx * cellSizeX + cellSizeX / 2;
                    int y1 = ny * cellSizeY + cellSizeY / 2;
                    g.drawLine(x0, y0, x1, y1);

                    if (isOnBorder(array, nx, ny))
                    {
                        break;
                    }

                    int ndx = dy;
                    int ndy = dx;
                    if (array[nx][ny] == '/')
                    {
                        ndx = -dy;
                        ndy = -dx;
                    }
                    x = nx;
                    y = ny;
                    dx = ndx;
                    dy = ndy;
                    steps++;
                }
                return steps;
            }

        };

        f.getContentPane().add(resultPanel);
        f.setSize(800,800);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }


}