Kürzester Pfad: Code so eine gute Idee?

[-horn-]

moien,

ich wollte gerne den kürzesten weg von einem bestimmten startpunkt über alle wegpunkt berechnen, wobei es keinen festen zielpunkt gibt.
ich habe mich da am Dijkstra-Algorithmus orientiert, soweit ich den verstanden habe .

ich denke mir also, dass ich vom startpunkt zum nächstliegendstem punkt gehe, den abspeicher und von der "noch-zu-gehen" liste streiche und dann von dem abgespeichertem punkt zu ihm am nächsten liegenden punkt gehe.
ziel soll es sein die gesamtstrecke am geringsten zu halten.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package shortestway;

import static java.lang.Math.*;
import java.util.*;


/**
 *
 * @author Andreas
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        // wegpunkte
        // wegpunkte als einfache 2d koordinaten
        // original wegpunkte 0,1,2,3,4,5 test
        double[] xOriginal = {7,4,3,5,3,5};
        double[] yOriginal = {4,5,7,5,1,5};
        
        // startpunkt
        double xStart = 3;
        double yStart = 3;
        
        
        // list, damit gezielt geloecht und index angepasst werden kann
        LinkedList x = new LinkedList();
        LinkedList y = new LinkedList();
        LinkedList position = new LinkedList();
        LinkedList route = new LinkedList();
        
        // ueberfuehren der original koordinaten in listen wg veraenderbarkeit
        // position wird gespeichert, um route ueber wegpunkte abspeicherbar
        for(int i=0; i<xOriginal.length; i++){
            x.add(xOriginal[i]);
            y.add(yOriginal[i]);
            position.add(i);
        }
        //System.out.println(position.get(4));
        //System.out.println(position.size());
        
        
        // berechnung startpunkt zu erstem wegpunkt
        double distanceTMP;
        int indexTMP = 0;
        
        distanceTMP = Math.sqrt(Math.pow((Double) x.get(0) - xStart,2) + Math.pow((Double) y.get(0) - yStart,2));
        //System.out.println("distanceTMP0 = " + distanceTMP + " indexTMP0 = " + indexTMP);
        
        for(int i=1; i<x.size(); i++){
            //System.out.println(Math.sqrt(Math.pow((Double) x.get(i) - xStart,2) + Math.pow((Double) y.get(i) - yStart,2)));
            
            if(distanceTMP > Math.sqrt(Math.pow((Double) x.get(i) - xStart,2) + Math.pow((Double) y.get(i) - yStart,2))){
                distanceTMP = Math.sqrt(Math.pow((Double) x.get(i) - xStart,2) + Math.pow((Double) y.get(i) - yStart,2));
                indexTMP = i;
            }
        }
        System.out.println("distanceTMP1 = " + distanceTMP + " indexTMP1 = " + indexTMP);
        
        route.add(position.get(indexTMP));
        
        
        // nun von letzter stelle der schon in der routenliste gespeicherten koordinaten zu den noch in den koordinatenliste befindlichen stellen
        for(int j=0; j<xOriginal.length-1; j++){
            
        // position mit der kuerzesten strecke vom start aus koordinatenliste entfernen
        x.remove(indexTMP);
        y.remove(indexTMP);
        position.remove(indexTMP);
        
        // neustart der variablen
        distanceTMP = 0;
        indexTMP = 0;
        
        distanceTMP = Math.sqrt(Math.pow((Double) x.get(0) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(0) - yOriginal[(Integer) route.get(route.size()-1)],2));
        //System.out.println("distanceTMP0 = " + distanceTMP + " indexTMP0 = " + indexTMP);
        
        for(int i=1; i<x.size(); i++){
            //System.out.println(Math.sqrt(Math.pow((Double) x.get(i) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(i) - yOriginal[(Integer) route.get(route.size()-1)],2)));
            if(distanceTMP > Math.sqrt(Math.pow((Double) x.get(i) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(i) - yOriginal[(Integer) route.get(route.size()-1)],2))){
                distanceTMP = Math.sqrt(Math.pow((Double) x.get(i) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(i) - yOriginal[(Integer) route.get(route.size()-1)],2));
                indexTMP = i;
            }
            
        }
        System.out.println("distanceTMP1 = " + distanceTMP + " indexTMP1 = " + indexTMP);
        route.add(position.get(indexTMP));
        }
        
        // nur noch ausgabe der routenpunkte
        System.out.print("route = ");
        for(int i=0; i<route.size(); i++){
            System.out.print(route.get(i) + ";");
        }        
        System.out.println();
    }

}

allerdings kann ich schon jetzt sagen, dass es mindestens eine ausnahme geben wird. wenn es vom startpunk, oder jedem anderen zwischenstartpunkt, mindestens zwei nacharpunkte mit gleichem abstand gibt, dann entscheidet der programm noch nicht, welcher nun den kürzesten weg verursacht. es wird der erste zu berechnende punkt genommen, und danach wird weiter berechnet. es muss also nicht der kürzeste weg herauskommen.

das programm kann aber mit punkten gleicher koordinaten umgehen. da spielt dann die reihenfolge keine rolle, da die gesamtdistanz nicht beeinflusst wird.


so, was haltet ihr von dem ansatz? und gleich vorweg. ich bin kein informatiker, ich kenne keine noch so grossen leute und deren algorythmen. auf Dijkstra bin ich auch erst nachdem mein satz fertig war gestossen .

grüße, Andreas

 

[Spacerat]

dann entscheidet der programm noch nicht, welcher nun den kürzesten weg verursacht

Wie wäre es denn damit, unter Ausschluss des aktuellen Punktes, jeweils eine Wegstrecke der nächsten beiden Punkte zu berechnen? Denn eines dürfte Klar sein. Die beiden Punkte mit dem selben Abstand zum Aktuellem müssen verbunden werden. Der nächste Punkt dahinter entscheidet, bei welchem Punkt es vom Aktuellem nicht weitergeht. Wenn das nicht einleuchtet kann ich es ja mal illustrieren.

mfg Spacerat

 

[-horn-]

dann entscheidet der programm noch nicht, welcher nun den kürzesten weg verursacht

Wie wäre es denn damit, unter Ausschluss des aktuellen Punktes, jeweils eine Wegstrecke der nächsten beiden Punkte zu berechnen? Denn eines dürfte Klar sein. Die beiden Punkte mit dem selben Abstand zum Aktuellem müssen verbunden werden. Der nächste Punkt dahinter entscheidet, bei welchem Punkt es vom Aktuellem nicht weitergeht. Wenn das nicht einleuchtet kann ich es ja mal illustrieren.

mfg Spacerat

moien,

an so eine weiche dachte ich auch, nur wird das 100prozentig auf rekursion hinauslaufen, was ich nich absolut nicht kann, denn wenn ich nun nicht eine so einer stelle habe sondern nachher noch mal so einen oder mehrere fälle wird das dann schwierig. zumindest weiss ich nicht, wie man das programmiert bekommt

grüße, Andreas

 

[Leroy42]

denn wenn ich nun nicht eine so einer stelle habe sondern nachher noch mal so einen oder mehrere fälle wird das dann schwierig. zumindest weiss ich nicht, wie man das programmiert bekommt

Kein Wunder!

Das Problem ist nun mal np-vollständig

 

[Spacerat]

Mal 'ne Frage... Weist du was Vektoren, insbesondere Distanz-Vektoren, sind? Ich meine nicht diese Java-Klasse!

Mir kommt da nämlich so 'ne Idee... Ich hau' mir mal eben die Nacht um die Ohren...

mfg Spacerat

 

[Marco13]

Unabhänig vom eigentlichen Problem ... zum Programm an sich.... kurz zusammengefasst: :autsch: Alles in der main! Ein paar Klassen,

class Node
{
    private int x;
    private int y;
    private boolean visited;
    ...
    public float distanceTo(Node other) { ... }
    public List<Node> getNeighbors() {....}
}

und vielleicht noch

class Edge
{
    private Node n0;
    private Node n1;

    public float getLength() { ... }
}

würden nicht schaden ... dann würden solche :autsch:-Blöcke wie

for(int i=1; i<x.size(); i++){
            //System.out.println(Math.sqrt(Math.pow((Double) x.get(i) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(i) - yOriginal[(Integer) route.get(route.size()-1)],2)));
            if(distanceTMP > Math.sqrt(Math.pow((Double) x.get(i) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(i) - yOriginal[(Integer) route.get(route.size()-1)],2))){
                distanceTMP = Math.sqrt(Math.pow((Double) x.get(i) - xOriginal[(Integer) route.get(route.size()-1)],2) + Math.pow((Double) y.get(i) - yOriginal[(Integer) route.get(route.size()-1)],2));
                indexTMP = i;
            }
           
        }

zu sowas wie

Node current = ...
Node closest = null;
float minDistance = Float.MAX_VALUE;
for (Node other : current.getNeighbors())
{
    float distance = current.distanceTo(other);
    if (distance < minDistance)
    {
        minDistance = distance;
        closest = other;
    }
}

(wie du das Programm mit dem bisherigen .... """Konzept""" weiterführen wolltest, ist mir schleierhaft...)

 

[Spacerat]

@Marco13: so etwas villeicht?

import java.awt.Dimension;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Insets;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.HashMap;

public final class ShortRound
extends Frame
{
  private static final long serialVersionUID = -2996657567359909821L;
  private final ArrayList<Line> lines = new ArrayList<Line>();

  private ShortRound()
  {
  }

  public static void main(String[] args)
  {
    final ShortRound sr = new ShortRound();
    int n;
    ArrayList<Point2D.Float> points = new ArrayList<Point2D.Float>();
    for(n = 0; n < 100; n++) {
      points.add(new Point2D.Float((float) Math.random() * 634, (float) Math.random() * 448));
    }
    HashMap<Point2D.Float, ArrayList<Line>> linemap = new HashMap<Point2D.Float, ArrayList<Line>>();
    ArrayList<Point2D.Float> pointmap = new ArrayList<Point2D.Float>(0);
    ArrayList<Line> al;
    Line la, lb = null;
    float miles = 0;
    Point2D.Float pa, pb;
    while(!points.isEmpty()) {
      pa = (lb != null)? lb.b : points.get(0);
      points.remove(pa);
      lb = null;
      if(!points.isEmpty()) {
        for(n = 0; n < points.size(); n++) {
          pb = points.get(n);
          la = new Line(pa, pb);
          if(lb == null) {
            lb = la;
          } else {
            switch(lb.compareTo(la)) {
            case 1:
              lb = la;
              break;
            case 0:
              if(!linemap.containsKey(pa)) {
                al = new ArrayList<Line>(0);
                linemap.put(pa, al);
              } else {
                al = linemap.get(pa);
                al.clear();
              }
              al.add(la);
              al.add(lb);
              lb = new Line(la.b, lb.b);
              pointmap.add(pa);
            }
          }
        }
        sr.lines.add(lb);
        miles += lb.length();
      }
    }
    sr.setTitle("Kürzester Weg: " + miles + " km");
    Dimension size = new Dimension(640, 480);
    sr.setPreferredSize(size);
    sr.setMaximumSize(size);
    sr.setMinimumSize(size);
    sr.setSize(size);
    sr.setResizable(false);
    sr.addWindowListener(new WindowAdapter()
    {
      public void windowClosing(WindowEvent e)
      {
        sr.dispose();
        System.exit(0);
      }
    });
    sr.pack();
    sr.setVisible(true);
  }

  public void paint(Graphics g)
  {
    Insets i = getInsets();
    int n, x1, y1, x2, y2;
    Line l;
    for(n = 0; n < lines.size(); n++) {
      l = lines.get(n);
      x1 = (int) l.a.x + i.left;
      x2 = (int) l.b.x + i.left;
      y1 = (int) l.a.y + i.top;
      y2 = (int) l.b.y + i.top;
      g.drawLine(x1, y1, x2, y2);
      g.fillOval(x1 - 2, y1 - 2, 4, 4);
      g.fillOval(x2 - 2, y2 - 2, 4, 4);
    }
  }

  private static final class Line
  implements Comparable<Line>
  {
    private final Point2D.Float a, b;

    private Line(Point2D.Float a, Point2D.Float b)
    {
      if(a == null || b == null) throw new NullPointerException();
      this.a = a;
      this.b = b;
    }

    private float length()
    {
      return (float) a.distance(b);
    }

    public int compareTo(Line o)
    {
      return (length() < o.length())? -1 : ((length() > o.length())? 1 : 0);
    }

    public boolean equals(Object obj)
    {
      if(this == obj) return true;
      try {
        Line l = (Line) obj;
        return compareTo(l) == 0;
      } catch(ClassCastException e) {
        return false;
      }
    }
  }
}

Das stellt das Ganze auch visuell dar - sorry wegen der Verwendung des AWT... . Obwohl es noch aussieht wie der Fluchtweg eines Vollpfostens, will sagen, das ist definitiv NICHT der kürzeste Weg. Ausserdem ist der Zufall des Problems, das Zwei Strecken vom selben Punkt ausgehend die gleiche Länge haben, noch nicht eingetreten. Aber zumindest ist es schon mal recht übersichtlich. Was solls... noch mal 'n paar Gedanken machen... Möglicherweise doch erst alle Wegstrecken sammeln und dann auswerten.

mfg Spacerat

 

[Marco13]

Jein ... jedes Mal eine neue Line erstellen ist vielleicht auch ungünstig. Es gibt schon Graphen-Implementierungen, die die nötigen Methoden anbieten, aber grundsätzlich gibt es eine Operation, die bei praktisch allen Wegeproblemen die kritischste ist: Iteriere über alle Kanten, die von einem Knoten ausgehen. Je nachdem wie .. generisch man seine Klassen machen will, und wie dynamisch der darunterliegende Graph ist (bezüglich der Knotenpositionen, aber besonders auch bezüglich der Konnektivität), gibt es da verschiedene Möglichkeiten dafür.