probleme beim Programmierung einem Routenplaner mit A Stern algorithmus

[Prince Nour]

Routenplaner

Wie kommt man möglichst schnell von A nach B?

Kürzeste Verbindung von A nach B?

ich habe versucht mit a*stern Algorithmus es irgendwie zu Implementieren ,aber leider hat's bei mir nicht geklappt,um besser zu verstehen,was ich meinte,sie können unter dieser seite schauen,da gibt's ausführliche Informationen.

http://de.wikipedia.org/wiki/A*-Algorithmus

.
und das gleiche wollte ich erreichen mit beispiel was da steht.
vielen dank im vouraus.

 

[Djinndrache]

Ich habe vor kurzem für ein kleines Team-Projekt eine Wegsuche benötigt und wir haben den Dijkstra-Algorithmus verwendet.

Vielleicht hilft es dir ja, zumindest als Denkanstoß:

public class Dijkstra {

	public static void computePaths(Vertex source, ArrayList<String> ziel) {
		source.minDistance = 0.;
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		vertexQueue.add(source);
		while (!vertexQueue.isEmpty()) {
			Vertex u = vertexQueue.poll();

			// Visit each edge exiting u
			for (Edge e : u.adjacencies) {
				Vertex v = e.target;
				double weight = e.weight;
				double distanceThroughU = u.minDistance + weight;
				if (distanceThroughU < v.minDistance) {
					vertexQueue.remove(v);
					v.minDistance = distanceThroughU;
					v.previous = u;
					vertexQueue.add(v);
				}
			}
			if (ziel.contains(u.name)) {
				vertexQueue.clear();
				break;
			}
		}
	}

	public static ArrayList<String> getShortestPathTo(Vertex target) {
		ArrayList<String> path = new ArrayList<String>();
		for (Vertex vertex = target; vertex != null; vertex = vertex.previous) {
			path.add(vertex.toString());
		}
		Collections.reverse(path);
		return path;
	}

	public ArrayList<String> getDirection(ArrayList<Vertex> vertices, ArrayList<String> ziel, String start) {
		int i = -1;
		for (Vertex v : vertices) {
			if (v.name.equals(start)) {
				i = vertices.indexOf(v);
			}
		}
		computePaths(vertices.get(i), ziel);
		double dist = 10000;
		Vertex ausgabe = null;
		for (String z : ziel) {
			for (Vertex v : vertices) {
				if (v.name.equals(z) && v.minDistance < dist) {
					dist = v.minDistance;
					ausgabe = v;
				}
			}
		}
		ArrayList<String> path = getShortestPathTo(ausgabe);
		for (Vertex v : vertices) {
			v.previous = null;
			v.minDistance = 10000;
		}
		return path;
	}
}

Ein Vertex ist dabei im Prinzip immer ein Weg und ein Edge ist eine Art "Knotenpunkt", von dem sich wieder weitere Wege auf tun, ungefähr wie folgt:

class Vertex implements Comparable<Vertex> {
	public final String name;
	public ArrayList<Edge> adjacencies;
	public double minDistance = Double.POSITIVE_INFINITY;
	public Vertex previous;
	public int wert;

	public Vertex(String argName) {
		name = argName;
	}

	public String toString() {
		return name;
	}

	public int compareTo(Vertex other) {
		return Double.compare(minDistance, other.minDistance);
	}
}

class Edge {
	public final Vertex target;
	public final double weight;

	public Edge(Vertex argTarget, double argWeight) {
		target = argTarget;
		weight = argWeight;
	}
}

Kann nicht für Fehlerfreiheit garantieren, aber es funktioniert soweit einwandfrei bei uns.

Edit: Credits natürlich insbesondere auch an mein Team bei diesem (ex)Projekt.

 

[Helgon]

Ein Vertex ist dabei im Prinzip immer ein Weg und ein Edge ist eine Art "Knotenpunkt", von dem sich wieder weitere Wege auf tun, ungefähr wie folgt:

Mal vom Code abgesehen, müsste es nicht andersrum sein? Ein Vertex ist der Punkt und die Edge die Verbindung (Kante/Linie die zwischen zwei Vertexes(ist das der Plural? ) entsteht?)

 

[Djinndrache]

Mal vom Code abgesehen, müsste es nicht andersrum sein? Ein Vertex ist der Punkt und die Edge die Verbindung (Kante/Linie die zwischen zwei Vertexes(ist das der Plural? ) entsteht?)

Ja, das stimmt, danke für die Klarstellung. Der Vertex (Plural ist übrigens Vertices, ähnlich wie Index->Indices) ist natürlich der Punkt und der Edge eine Verbindung zwischen zwei Vertices. Ist schon ein Weilchen her...
Aber ist ja auch im Code so, ein Vertex hat eine Menge von Edges als adjacencies. Ich hatte nur in der Erklärung die Begriffe durcheinander geworfen

 

[Prince Nour]

viel dank jungs