Ява - * алгоритм поиска


У меня возникли проблемы с домашним заданием реализации* алгоритм поиска в Java, я дал график, происхождения и назначения, я должен был выполнить определенные задачи в домашке так что код может быть немного странно(например, каждый раз, когда я добавляю в openlist я должен позвонить в protected boolean addItem(Object item) метод).

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

Ниже Решение решает задачу поиска пути в как 30-х годов, но мне нужно примерно 2 секунды. весь график имеет узлы 103892(перекресток) и 193736 ребер(дорог).

Когда я запускаю профайлер в NetBeans IDE, он говорит, что я провел много времени вызова HashMap.put функции, и само время(а это в основном время, проведенное в plan функция кроме все время, проведенное в других функциях, вызванных этой функцией).

Моя эвристика время нахождения в пути в эвклидово расстояние между узлом и назначения с максимальной скоростью можно.

Код:

package student;

import cz.cvut.atg.zui.astar.AbstractOpenList;
import cz.cvut.atg.zui.astar.PlannerInterface;
import cz.cvut.atg.zui.astar.RoadGraph;
import eu.superhub.wp5.planner.planningstructure.GraphEdge;
import eu.superhub.wp5.planner.planningstructure.GraphNode;
import eu.superhub.wp5.planner.planningstructure.PermittedMode;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;

import java.util.List;

public class Planner implements PlannerInterface {

    private OpenList openList;

    @Override
    public List<GraphEdge> plan(RoadGraph graph, GraphNode origin, GraphNode destination) {
        if (origin == destination) {
            return null;
        }
        Collection<GraphNode> allNodes = graph.getAllNodes();
        int nodeSize = allNodes.size();
        openList = new OpenList(nodeSize);
        Collection<GraphEdge> allEdges = graph.getAllEdges();
        int edgeSize = allEdges.size();
        double topSpeed = 0;
        for (GraphEdge edge : allEdges) {
            if (edge.getPermittedModes().contains(PermittedMode.CAR)) {
                if (edge.getAllowedMaxSpeedInKmph() > topSpeed) {
                    topSpeed = edge.getAllowedMaxSpeedInKmph();
                }
            }
        }
        System.out.println("n"+nodeSize+"e"+edgeSize);
        openList.initilizeHeuristics(allNodes, destination, topSpeed);

        List<Long> closedSet = new ArrayList(nodeSize);

        HashMap<GraphNode, GraphEdge> cameFrom = new HashMap(edgeSize);

        HashMap<Long, Double> gScore = new HashMap(nodeSize);//default value infinity  
        for (GraphNode node : allNodes) {
            gScore.put(node.getId(), Double.MAX_VALUE);
        }
        gScore.put(origin.getId(), 0.0);

        HashMap<Long, Double> fScore = new HashMap(nodeSize);//default value infinity
        openList.fScore = fScore;
        fScore.put(origin.getId(), openList.getInitilizedHeuristics(origin));
        openList.addToQueue(origin.getId());
        while (!openList.isEmpty()) {
            GraphNode current = openList.getLowestPriceNode(graph);
            if (current == destination) {
                return reconstructPath(graph, cameFrom, current);
            }

            openList.removeHead();
            closedSet.add(current.getId());

            List<GraphEdge> outcomingEdges = graph.getNodeOutcomingEdges(current.getId());

            if (outcomingEdges != null) {
                for (GraphEdge edge : outcomingEdges) {
                    if (edge.getPermittedModes().contains(PermittedMode.CAR)) {
                        Long neighbourId = edge.getToNodeId();
                        GraphNode node = graph.getNodeByNodeId(neighbourId);
                        if (closedSet.contains(neighbourId)) {
                            continue;
                        }

                        double tentative_gScore = gScore.get(current.getId()) + edge.getLengthInMetres() / edge.getAllowedMaxSpeedInKmph();
                        if (!openList.contains(neighbourId)) {
                            fScore.put(neighbourId, Double.MAX_VALUE);
                            openList.addToQueue(neighbourId);
                        }
                        if (tentative_gScore >= gScore.get(neighbourId)) {
                            continue;
                        }
                        cameFrom.put(node, edge);
                        gScore.put(neighbourId, tentative_gScore);
                        fScore.put(neighbourId, gScore.get(neighbourId) + openList.getInitilizedHeuristics(node));
                        openList.ReSort(neighbourId);
                    }
                }
            }
        }
        return null;
    }

private List<GraphEdge> reconstructPath(RoadGraph graph, HashMap<GraphNode, GraphEdge> cameFrom, GraphNode current) {
        List<GraphEdge> total_path = new LinkedList();
        total_path.add(cameFrom.get(current));
        while (cameFrom.containsKey(current)) {
            current = graph.getNodeByNodeId(cameFrom.get(current).getFromNodeId());
            total_path.add(cameFrom.get(current));
        }
        Collections.reverse(total_path);
        total_path.remove(0);
        return total_path;
    }
}

-

package student;

import cz.cvut.atg.zui.astar.*;
import eu.superhub.wp5.planner.planningstructure.GraphNode;
import java.util.Collection;
import java.util.Comp

arator;
    import java.util.HashMap;
    import java.util.PriorityQueue;

    public class OpenList extends AbstractOpenList {

        private final HashMap<GraphNode, Double> heuristics;
        private final Comparator<Long> comparator;
        private final PriorityQueue<Long> queue;
        public HashMap<Long, Double> fScore;

        public OpenList(int size) {
            heuristics = new HashMap(size);
            comparator = new MyComparator();
            queue = new PriorityQueue<>(10000, comparator);
        }

        @Override
        protected boolean addItem(Object item) {
            return true;
        }

        protected boolean addToQueue(long nodeidToInsert) {
            queue.add(nodeidToInsert);
            return add(nodeidToInsert);
        }

        protected boolean isEmpty() {
            return queue.isEmpty();
        }

        private double getHeuristic(GraphNode node, GraphNode destination, double topSpeed) {//convert to meters
            double x0 = node.getLatitude();
            double y0 = node.getLongitude();
            double x1 = destination.getLatitude();
            double y1 = destination.getLongitude();
            double R = 6378137;
            double dLat = x1 * Math.PI / 180 - x0 * Math.PI / 180;
            double dLon = y1 * Math.PI / 180 - y0 * Math.PI / 180;
            double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(x0 * Math.PI / 180) * Math.cos(x1 * Math.PI / 180) * Math.sin(dLon / 2) * Math.sin(dLon / 2);
            double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
            return R * c / topSpeed;
        }

        protected GraphNode getLowestPriceNode(RoadGraph graph) {
            return graph.getNodeByNodeId(queue.peek());
        }

        void remove(long nodeid) {
            queue.remove(nodeid);
        }

        boolean contains(long nodeid) {
            return queue.contains(nodeid);
        }

        void initilizeHeuristics(Collection<GraphNode> nodes, GraphNode destination, double topSpeed) {
            for (GraphNode node : nodes) {
                heuristics.put(node, getHeuristic(node, destination, topSpeed));
            }
        }

        double getInitilizedHeuristics(GraphNode node) {
            return heuristics.get(node);
        }

        void ReSort(long nodeid) {
            queue.remove(nodeid);
            queue.add(nodeid);
        }

        void removeHead() {
            queue.remove();
        }

        private class MyComparator implements Comparator<Long> {

            @Override
            public int compare(Long id1, Long id2) {
                if (fScore.get(id1) <= fScore.get(id2)) {
                    return -1;
                } else {
                    return 1;
                }
            }
        }
    }

Поэтому любые идеи о том, как сделать это быстрее? зы: я может поставить весь проект для тех, кто хочет отладить и т. д.



Комментарии