Оптимизация aStar в Java

В настоящее время я ищу оптимизацию моего алгоритма aStar, поскольку мой последний прогон занимает примерно одну минуту, чтобы создать один путь. Мне никогда не приходилось оптимизировать, так как я никогда не сталкивался с проблемами производительности, поэтому я не знаю, с чего начать с этого.

http://pastebin.com/MbZtyQFu

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

public class Pathfinding
{
List<Node> closedList = new ArrayList<Node>();
List<Node> openList = new ArrayList<Node>();
int j = 0;

public Node aStar(TiledMap tiles, Node start, Node goal)
{

    Node currentNode = new Node(start.row, start.col, start.gCost, start.fCost, null);
   // closedList.clear();
    //openList.clear();

    while (!reachedGoal(currentNode, goal))
    {
        int row = currentNode.row;
        int col = currentNode.col;

        //right child
        col++;
        addChild(row, col, tiles, currentNode, goal);

        //left child
        col -= 2;
        addChild(row, col, tiles, currentNode, goal);

        //top child
        col++;
        row--;
        addChild(row, col, tiles, currentNode, goal);

        //bottom child
        row += 2;
        addChild(row, col, tiles, currentNode, goal);

        //bottom right
        col++;
        addChild(row, col, tiles, currentNode, goal);

        //bottom left
        col -= 2;
        addChild(row, col, tiles, currentNode, goal);

        //top left
        row -= 2;
        addChild(row, col, tiles, currentNode, goal);

        //top right
        col += 2;
        addChild(row, col, tiles, currentNode, goal);

        //Put currentNode in the closedList
        closedList.add(currentNode);
        //Sort the openList
        Collections.sort(openList);
        //Assign currentNode to the last element in the List
        currentNode = openList.remove(openList.size() - 1);
        //System.out.println("Curr Node Row " +  currentNode.row + ", Curr Node Col " + currentNode.col);
    }
    return currentNode;
}

public boolean reachedGoal(Node currentNode, Node goalNode)
{
    return (currentNode.col == goalNode.col) && (currentNode.row == goalNode.row);
}

public boolean isNodeClosed(double row, double col)
{
    for (int i = 0; i < closedList.size(); ++i)
    {
        if (closedList.get(i).col == col && closedList.get(i).row == row)
        {
            return true;
        }
    }
    return false;
}

public Node getChildFromOpen(double row, double col, List<Node> openList)
{
    for (int i = 0; i < openList.size(); ++i)
    {
        if (openList.get(i).col == col && openList.get(i).row == row)
        {
            return openList.get(i);
        }
    }
    return null;
}

public void addChild(int row, int col, TiledMap tiles, Node currentNode, Node target)
{
    if((row >= 0 && col >= 0) && (row <= 14 && col <= 39))
    {
        if (tiles.isPassable(row, col))
        {
            if (!isNodeClosed(row, col))
            {
                double g = currentNode.gCost + getDistanceFromParent(row, col, currentNode);
                double f = g + getDistance(row, col, target);
                Node child = getChildFromOpen(row, col, openList);

                if (child == null)
                {
                    child = new Node(row, col, g, f, currentNode);
                    openList.add(child);
                }
                else if (child.gCost > g)
                {
                    child.fCost = f;
                    child.gCost = g;
                    child.parentNode = currentNode;
                }
            }
        }
    }
}

public double getDistance(int row, int col, Node goal)
{
    return Math.sqrt((goal.row - row) * (goal.row - row) + (goal.col - col) * (goal.col - col));
}

public double getDistanceFromParent(int row, int col, Node parent)
{
    return Math.sqrt((row - parent.row) * (row - parent.row) + (col - parent.col) * (col - parent.col));
}

Node класс

class Node implements Comparable<Node>
{
    public int row;
    public int col;
    public double gCost;
    public double fCost;
    public Node parentNode = null;

    public Node (int row, int col, double gCost, double fCost, Node parentNode)
    {
        this.row = row;
        this.col = col;
        this.gCost = gCost;
        this.fCost = fCost;
        this.parentNode = parentNode;
    }

    public int compareTo(Node other)
    {
        if(this.fCost < other.fCost)
        {
            return 1;
        }
        else if(this.fCost > other.fCost)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
}
11 голосов | спросил Andrew B 25 J0000006Europe/Moscow 2014, 22:48:01

3 ответа


11

Научите человека рыбе

Если у вас есть программа, которая работает медленнее, чем вы ожидаете, и вы хотите знать, где она медленная, правильным ответом является профайл кода. Возникает вопрос: StackOverflow который описывает ряд инструментов, которые позволят вам запустить код и найти горячие точки.

В качестве альтернативы, профилировщик бедняка должен просто сбрасывать трассировки стека (отправить сигнал через ctrl-break или kill -3) и посмотреть, какой метод вы сейчас находитесь. Если ваша программа работает медленно, в любой момент она, вероятно, находится в медленной части кода. Если вы ломаетесь несколько раз и видите, что вы находитесь в одном и том же месте каждый раз, шансы очень хорошие, что вы смотрите на проблему.

Дайте человеку рыбу

public boolean isNodeClosed(double row, double col)
{
     for (int i = 0; i < closedList.size(); ++i)
     {
         if (closedList.get(i).col == col && closedList.get(i).row == row)
         {
             return true;
         }
     }
     return false;
}

Вероятно, это одна из ваших проблем; подумайте о поведении этого кода на мгновение - чтобы выяснить, закрыт ли узел, вы повторяете список всех узлов, которые вы уже закрыли. По мере продвижения вашего решения этот список становится длиннее и длиннее, что означает выяснение того, продолжает ли узел закрываться.

 public Node getChildFromOpen(double row, double col, List<Node> openList)
 {
    for (int i = 0; i < openList.size(); ++i)
    {
        if (openList.get(i).col == col && openList.get(i).row == row)
        {
            return openList.get(i);
        }
    }
    return null;
}

Такая же проблема здесь, так как больше узлов входит в открытый список, поиск открытого узла занимает больше времени и дольше.

Представьте себе, что вместо этого вы должны отслеживать, что открыто и закрыто по координатам:

public boolean isOpen(int row, int col, boolean[][] open) 
{
    return open[row][col];
}

Теперь ваш поиск идет от O (N), что означает, что требуемое время является функцией количества узлов в вашей задаче, до O (1), что означает, что требуемое время является постоянным.

Конечно, поскольку вы создали класс Node, который имеет свойство row и column, может иметь смысл использовать узлы непосредственно

public boolean isOpen(Node n, boolean [][] open) 
{
    return open[n.row][n.col];
}

Но более продвинутые программисты этого не сделали. Проблема с вашей реализацией List заключается в том, что вычисление, если List содержит определенный узел медленно. Вы выбрали неправильную коллекцию. Set, в частности HashSet предназначен для такого рода вещи.

public boolean isOpen(Node n, Set<Node> open) 
{
    return open.contains(n);
}

Теперь настройки зависят от возможности распознавания, когда два объекта одинаковы. В общем, он делает это, используя Object.hashCode() , чтобы решить, какой« ведро »использовать для отслеживания объекта. Опять же, поиск StackOverflow предоставит предложения о том, как реализовать hashcode. Для сложных объектов вы можете опираться на что-то вроде HashFunction

В этом конкретном случае вам действительно не нужно хэшировать весь узел - вам действительно интересно только, где находится узел. Таким образом, вы можете выделить эти две идеи.

class Location
{
     public int row;
     public int col;

     public int hashCode ()
     {
         return 37 * row + col ;
     }
}

class Node implements Comparable<Node>
{
    public Location location;

    public double gCost;
    public double fCost;
    public Node parentNode = null;
}

public boolean isOpen(Node n, Set<Location> open) {
    return open.contains(n.location);
}

Теперь неплохо позволить значениям хеш-коллекции изменять свои значения хэша «на лету», поэтому мы должны предпринять некоторые шаги, чтобы заблокировать местоположение как тип значения.

class Location
{
     public final int row;
     public final int col;

     public Location(int row, int col)
     {
          this.row = row;
          this.col = col;
     }

     public int hashCode ()
     {
         return 37 * row + col ;
     }
}

Местоположение, возможно, является хорошей абстракцией для вас здесь, так как это значительно упрощает некоторые из ваших «мы еще не сделали»? чеки, потому что вы хотите проверить текущий Node в том же Location в качестве вашей цели. Location.equals() - это прямой способ реализовать эту идею. Еще раз: см. StackOverflow ; вы перебегаете Object.equals (), и поэтому важно, чтобы выверните детали. (Блок Джошуа посвятил глава к этим типам проблем).

class Location
{
     public int row;
     public int col;

     public boolean equals(Object obj)
     {
         if (!obj instanceof Location)
         {
             return false;
         }
         if (obj == that)
         {
             return true;
         }
         Location that = (Location) obj;

         return (this.row == that.row) && (this.col == that.col);
     }

     public int hashCode () {
         return 37 * row + col ;
     }
}

public boolean reachedGoal(Node currentNode, Node goalNode)
{
     return currentNode.location.equals(goalNode.location);
}

Было бы разумно дразнить оценки как еще один класс. Поскольку мы не используем Score в качестве ключа в любом месте, мы можем оставить переменные затрат изменчивыми.

class Score implements Comparable<Score>
{
    public double gCost;
    public double fCost;

    public int compareTo(Score other)
    {
        if(this.fCost < other.fCost)
        {
             return 1;
        }
        else if(this.fCost > other.fCost)
        {
             return -1;
        }
        else
        {
             return 0;
        }
    }
}

class Node implements Comparable<Node>
{
    public Location location;
    public Score score;
    public Node parentNode = null;

    public int compareTo(Score other)
    {
        return score.compareTo(other.score);
    }
}

В этот момент вы даже можете обнаружить, что вам больше не нужен узел; у вас действительно есть разные виды поиска, основанные на Location.

Map<Location,Location> lookupParent = new HashMap();
Map<Location,Score> lookupScore = new HashMap();
Set<Location> openNodes = new HashSet();
Set<Location> closedNodes = new HashSet();
ответил VoiceOfUnreason 26 J0000006Europe/Moscow 2014, 01:34:41
3

Прежде всего, напишите более короткие методы. Это лучше для читателей, «лучше для компилятора (я видел, что второй фактор ускоряется после простого разделения метода на два), и это лучше для вас.

Избегайте ненужного деления на циклы, похоже, что вы работаете с фиксированной сеткой.

Не сортируйте ArrayList, где PriorityQueue выполняет задание.

Попробуйте реализовать LOSCheck без стольких случаев. Это может быть трудно и даже стоить некоторое время, но это может сделать программу более чистой и легкой для оптимизации.

Я боюсь, это не решит вашу проблему, но слишком долго для комментария. Я добавлю некоторую информацию позже. Тем не менее, обзор кода - это то, что нужно этому вопросу, и я предлагаю переместить его туда (и тогда мои промахи будут правы на месте) .

ответил maaartinus 26 J0000006Europe/Moscow 2014, 03:37:23
1

Предлагаю вам посмотреть:

  • используйте профилировщик процессора, чтобы увидеть, где он проводит большую часть времени. Если это большой метод, подумайте об этом, чтобы получить ясность.
  • попробуйте выполнить код в вашем отладчике для простого примера, чтобы увидеть, есть ли очевидная неэффективность. например допустимо ли посещать один и тот же узел более одного раза.
ответил Peter Lawrey 25 J0000006Europe/Moscow 2014, 22:43:00

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132