A* complete

Dadung
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Mai 2017 13:08

A* complete

Beitrag von Dadung » 12. Jul 2017 14:16

Hallo,

ich bekomme bei A* zwei timeout Fehler und kann nicht beurteilen, ob ich irgendwo eine Endlosschleife habe (wüsste nicht wieso), oder ob die timeouts zu gering sind. Die Tests scheinen die Trivialfälle, start == Ziel und Graph der Größe 1 zu betrachten.


Mein Code:

Code: Alles auswählen

public void preProcess() throws InvalidInputException
{
    if (getGraph() == null) throw new InvalidInputException("null");
    if (getGraph().getNodeList().size() == 0) throw new InvalidInputException("nodes");
    if (getSourceNode() == null || !getGraph().getNodeList().contains(getSourceNode())) throw new InvalidInputException("source");
    if (getTargetNode() == null || !getGraph().getNodeList().contains(getTargetNode())) throw new InvalidInputException("target");
        
    
    
    setPathFound(false);
    
    PriorityQueue<Node<N, E>> p = new PriorityQueue(getQueueComparator());
    p.offer(getSourceNode());
    setOpenList(p);
    
    setClosedList(new ArrayList<Node<N, E>>());
    
    HashMap<Node<N, E>, Node<N, E>> pre = new HashMap<Node<N, E>, Node<N, E>>();
    pre.put(getSourceNode(), null);
    setPredecessorMap(pre);
    
    HashMap<Node<N, E>, E> dis = new HashMap<Node<N, E>, E>();
    dis.put(getSourceNode(), getComparator().getZero());
    setSourceDistanceMap(dis);
}

Code: Alles auswählen

public void expandNode(Node<N, E> node)
{
    for (Edge<N, E> e : node.getFanOut()) {
        Node<N, E> t = e.getTargetNode();
        
        if (getClosedList().contains(t))
            continue;
        E co = getComparator().sum(getSourceDistanceMap().get(node), e.getData());
        E pre = getSourceDistanceMap().get(t);
        
        if (pre == null || getComparator().greaterEqual(pre, co)) {
            getSourceDistanceMap().put(t, co);
            getPredecessorMap().put(t, node);
            
            if (!getOpenList().contains(t)){
                getOpenList().offer(t);  
            }

        }
    }
}

Code: Alles auswählen

public void doFunctionality()
{
    Node<N, E> c = getCurrentNode();
    if (c == getTargetNode() || c == null) {
        setPathFound(true);
        return;
    }
    getClosedList().add(c);
    expandNode(c);
}

Code: Alles auswählen

public void postProcess()
{
    ArrayList<Node<N, E>> p = new ArrayList<Node<N, E>>();
    setPath(p);
    
    if (!getPredecessorMap().containsKey(getTargetNode())) {
        return;
    }
    for (Node<N, E> c = getTargetNode(); c != null; getPredecessorMap().get(c)) {
        p.add(c);
    }
    reverseCollection(p);
}

Code: Alles auswählen

public boolean checkBreakCondition()
{
    return !isPathFound();
}

Code: Alles auswählen

public void executeVariant()
{
    setCurrentNode(getOpenList().poll());
}
Die Fehler:

Antwort des Servers
Junitreport

Time – 204

Testcount – 22

Failurecount – 2

Ignorerecount – 0

Failurereport

Testheadder – oneElementGraphTest(graph.algorithm.astar.AStarTest)

Message – test timed out after 80 milliseconds

Trace – org.junit.runners.model.TestTimedOutException: test timed out after 80 milliseconds at graph.algorithm.astar.AStar.postProcess(AStar.java:277) at models.graph.algorithm.AbstractAlgorithm.execute(AbstractAlgorithm.java:31) at graph.algorithm.astar.AStarTest.oneElementGraphTest(AStarTest.java:87) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50) at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12) at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47) at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:298) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:292) at java.util.concurrent.FutureTask.run(FutureTask.java:266) at java.lang.Thread.run(Thread.java:748)

Failurereport

Testheadder – dynamicTestSourceIsTarget(graph.algorithm.astar.AStarTest)

Message – test timed out after 80 milliseconds

Trace – org.junit.runners.model.TestTimedOutException: test timed out after 80 milliseconds at java.util.Arrays.copyOf(Arrays.java:3181) at java.util.ArrayList.grow(ArrayList.java:261) at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235) at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227) at java.util.ArrayList.add(ArrayList.java:458) at wrap.substitute.ArrayList.add(ArrayList.java:172) at graph.algorithm.astar.AStar.postProcess(AStar.java:282) at models.graph.algorithm.AbstractAlgorithm.execute(AbstractAlgorithm.java:31) at graph.algorithm.astar.AStarTest.dynamicTestSourceIsTarget(AStarTest.java:556) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:498) at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50) at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12) at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47) at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:298) at org.junit.internal.runners.statements.FailOnTimeout$CallableStatement.call(FailOnTimeout.java:292) at java.util.concurrent.FutureTask.run(FutureTask.java:266) at java.lang.Thread.run(Thread.java:748)

Ich hoffe mir kann hier jemand weiter helfen

Zurück zu „Archiv“