1

所以我一直在研究一个问题，基本前提是给定任意大小的网格，我需要计算“旅行”的数量。巡回赛是从左上角开始（我使用点 x=1，y=1 表示）并在左下角结束（x=1 y=max，无论 'y' 的最大值是多少）。除此之外，它还必须沿途每隔一个点接触一次，并且只能访问网格中的任何点一次。

按照我在下面写的方式，它运行时间约为 42-45 秒，但如果可能的话，我想让它在 30 秒或更短的时间内运行。所以，我问你的问题是，我可以改变或去掉什么来让它运行得更快？

我尝试使所有内容都不是静态的并实例化该类（这增加了我的运行时间几秒钟）。

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Date;

public class CodingPuzzle
{
public static List<Point> lAllPoints = new ArrayList<Point>();
public static int iMaxX;
public static int iMaxY;
public static int iCompletePaths = 0;

public static void depthFirstSearch(Point current, Stack<Point> result)
{
    if (result.contains(current))
        return;

    result.push(current);

    if (current.x == 1 && current.y == iMaxY && result.size() == iMaxX*iMaxY)
    {
        // This is a complete path
        iCompletePaths++;
    }
    for (Point p: getPossibleMoves(current))
    {
        depthFirstSearch(p, result);
    }

    // No path was found
    result.pop();
    return;
}

public static List<Point> getPossibleMoves (Point fromPoint)
{
    int iCurrentPointIndex = lAllPoints.indexOf(fromPoint);
    List<Point> lPossibleMoves = new ArrayList<Point>();

    if (fromPoint.x == 1 && fromPoint.y == 1)
    {
        // Top left point
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else if (fromPoint.x == 1 && fromPoint.y == iMaxY)
    {
        // Bottom left point. Should always be the last point. No valid moves.
        // If a path gets here before the end it shouldn't need to continue.
    }

    else if (fromPoint.x == iMaxX && fromPoint.y == 1)
    {
        // Top right point
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
    }

    else if (fromPoint.x == iMaxX && fromPoint.y == iMaxY)
    {
        // Bottom right point
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
    }

    else if (fromPoint.x == 1 && fromPoint.y != iMaxY)
    {
        // Any other point on the left side
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else if (fromPoint.x == iMaxX)
    {
        // Any other point on the right side
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
    }

    else if (fromPoint.y == 1)
    {
        // Any other point on the top
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else if (fromPoint.y == iMaxY && fromPoint.x != 1)
    {
        // Any other point on the bottom
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else
    {
        // Any other point not on an edge.
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    return lPossibleMoves;
}

public static void setUpGrid(int x, int y)
{
    iMaxX = x;
    iMaxY = y;
    for (int i = 1; i <= x; i++)
        for (int j = 1; j <= y; j++)
            lAllPoints.add(new Point(i, j));
}

public static void main(String[] args)
{
    Date start = new Date(System.currentTimeMillis());
    setUpGrid(10, 4);
    Stack<Point> sCurrentPoints = new Stack<Point>();
    depthFirstSearch(lAllPoints.get(0), sCurrentPoints);
    Date end = new Date(System.currentTimeMillis());
    long total = end.getTime() - start.getTime();
    System.out.println(iCompletePaths + " paths found in " + total/1000 + " seconds.");
}
4

3 回答 3

3

我会减少代码为获得计数所做的工作量。

public class CodingPuzzle2 {
    private final int width;
    private final int height;

    public CodingPuzzle2(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public int countPaths(int x, int y) {
        boolean[][] visited = new boolean[width][height];
        int[] count = {0};
        countPaths(x, y, visited, 1,  count);
        return count[0];
    }

    private void countPaths(int x, int y, boolean[][] visited, int depth, int[] count) {
        if (x < 0 || x >= width || y < 0 || y >= height || visited[x][y])
            return;
        visited[x][y] = true;
        try {
            if (x == 0 && y == height - 1) {
                if (depth == width * height)
                    count[0]++;
                return;
            }
            countPaths(x, y + 1, visited, depth+1, count);
            countPaths(x + 1, y, visited, depth+1, count);
            countPaths(x - 1, y, visited, depth+1, count);
            countPaths(x, y - 1, visited, depth+1, count);
        } finally {
            visited[x][y] = false;
        }
    }

    public static void main(String... args) {
        long start = System.nanoTime();
        CodingPuzzle2 cp = new CodingPuzzle2(10,4);
        int count = cp.countPaths(0, 0);
        long time = System.nanoTime() - start;
        System.out.printf("%,d paths found in %.3f seconds.%n", count, time / 1e9);
    }
}

印刷

2,329 paths found in 1.758 seconds.
于 2012-04-16T17:01:03.277 回答
0

我要做的第一件事是分析您的代码（正如彼得在对您的问题的评论中所说的那样）。如果不知道您将时间花在哪里，很难“让事情变得更快”。但是您的算法可能效率低下。对于分析，您可以使用 Oracle JVM 附带的 jvisualvm。

您可能想研究解决图的哈密顿路径的算法，这实际上就是您正在做的事情。有比蛮力更有效的解决方案。

于 2012-04-16T16:43:56.233 回答
0

别人怎么说。它将帮助您成为更好的程序员。

除此之外，这是您正在寻找的快速胜利 - 从Deque切换Stack到ArrayDeque 。这个单一的改变使它在我的机器上快了 44%。Java 7 -server

于 2012-04-16T16:50:47.323 回答