Hallo zusammen,
Ich stehe vor folgendem Problem:
Ich habe eine 2D-Matrix gegeben ((0, 0) - (10,10)) und einen Punkt auf der Matrix (5,5).
Außerdem habe ich verschiedene Linien in dieser Matrix definiert (z.B. Linie [(0,3) - (0,7)] und Linie [(2,4) - (7,4)].
Nun besteht meine Aufgabe darin, die Linie zu finden, deren Start- oder Endwert meinem Punkt (5,5) am nächsten ist (wenn es zwei gleich-weit entfernte Linien gäbe, dürfte ich frei entscheiden).
Anschließend wird mein Punkt(5,5) zu dem Endpunkt der gerade ermittelten Linie und das Spiel geht von vorne los.
Damit soll ich die Liste mit den Linien "sortieren", sodass der kürzeste Weg beschritten wird, wenn ich die Linien nacheinander "ablaufen" solle.
Ich habe keinen Ansatz gefunden...
Über Anregungen wäre ich sehr dankbar
VG
elchico
Punkt auf Ebene der geg Punkt auf Ebene am nähstem
@elchico: Wenn man den insgesamt kürzesten Weg sucht kann man IMHO nicht ”greedy” vorgehen weil es sein könnte das man an einer Stelle einen längeren Schritt wählen muss als den lokal kürzesten um den global kürzesten zu bekommen. Beispiel:
`S` ist der Startpunkt. Da wäre der linke Punkt von `a` am nächsten. Wenn man `a` abgelaufen ist wäre der linke Punkt von `c` am nächsten. Von dessen anderen Ende müsste man dann weit zurückgegen zum rechten Punkt von `b`. Kürzer wäre aber wenn man von `a` erst zum weiter entfernten linken Punkt von `b` springt und vom anderen Ende von `b` dann zum linken Punkt von `c`.
Code: Alles auswählen
+--b--+
S +-a-+
+---------------------------c-----------------------------------+
stimmt, soweit hatte ich nicht gedacht.
OK, dann suche ich den absolut kürzesten Weg (also in deinem Beispiel erst a, dann b, dann c)
Hast du auch Ideen zur Umsetzung ?
Wie gesagt, ich komme schon gar nicht dazu, "a" zu finden ... geschweige denn, wie ich den absolut kürzesten Weg finden soll.
OK, dann suche ich den absolut kürzesten Weg (also in deinem Beispiel erst a, dann b, dann c)
Hast du auch Ideen zur Umsetzung ?
Wie gesagt, ich komme schon gar nicht dazu, "a" zu finden ... geschweige denn, wie ich den absolut kürzesten Weg finden soll.
@elchico: Das lässt sich leicht zu einem Graphenproblem umformulieren. Der Startpunkt und die Liniendendpunkte sind Knoten. Jeder Knoten ist mit jedem anderen Knoten durch eine Kante verbunden. Das Kantengewicht ist die Entfernung zwischen den Punkten die durch die jeweiligen Knoten repräsentiert werden. Jetzt suchen wir den Weg mit dem geringsten Gewicht vom Startpunkt der a) jeden Knoten besucht, b) dabei keine Kante mehr als einmal verwendet, und c) jede Kante die für eine Linie steht beinhaltet. a) und b) sind die üblichen Bedigungen, das heisst man muss eigentlich nur einen Standardalgorithmus adaptieren, so dass auch c) erfüllt ist.
@/me: Wobei ich da jetzt auf Anhieb keine Idee hätte wie man `networkx` die Bedingung c) beibringt, ausser das man wirklich alle Pfade erzeugt und aus denen dann den kürzesten herausfiltert der diese Bedinung erfüllt. Wenn man den Algorithmus selber implementiert, könnte man gezielt bei jedem zweiten Schritt die einzige obligatorische Kante wählen die durch eine Linie in der Aufgabenstellung vorgegeben ist. Zumindest ”algorithmisch” sollte das effizienter sein.
hi
danke zusammen ich schau mir mal networkx an, habe von nem kumpel jetzt auch was von quadtrees gehört...
danke zusammen ich schau mir mal networkx an, habe von nem kumpel jetzt auch was von quadtrees gehört...
Nahezu ungetestet und extrem unterdokumentiert:
Code: Alles auswählen
#!/usr/bin/env python
from collections import namedtuple
from math import sqrt
def is_odd(number):
return bool(number & 1)
class Point(namedtuple('_Point', 'x y')):
def __repr__(self):
return '{0.__class__.__name__}({0.x!r}, {0.y!r})'.format(self)
def distance(self, other):
return sqrt((self.x - other.x)**2 + (self.y - other.y)**2)
Line = namedtuple('Line', 'point_a point_b')
class Node(object):
def __init__(self, point, line=None):
self.point = point
self.line = line
self.line_edge = None
self.free_edges = dict()
def __len__(self):
return len(self.free_edges)
def __iter__(self):
return self.free_edges.iteritems()
def connect_to(self, other):
if self is not other:
distance = self.point.distance(other.point)
if self.line is other.line:
self.line_edge = (other, distance)
else:
self.free_edges[other] = distance
def connect_to_many(self, others):
for other in others:
self.connect_to(other)
class ShortestPathFinder(object):
def __init__(self, graph):
self.graph = graph
self.current_node = None
self.visited = None
self.path = None
self.weight = None
self.result = None
self.min_weight = None
def __call__(self, start_point):
self.current_node = Node(start_point)
self.current_node.connect_to_many(self.graph)
self.visited = set()
self.path = list()
self.weight = 0
self.result = None
self.min_weight = float('inf')
self._find_path()
return self.result
def _find_path(self):
if (
len(self.path) == len(self.graph)
and self.weight < self.min_weight
):
self.min_weight = self.weight
self.result = list(self.path)
else:
if is_odd(len(self.path)):
edges = [self.current_node.line_edge]
else:
edges = self.current_node
for target_node, weight in edges:
if target_node not in self.visited:
self.weight += weight
if self.weight < self.min_weight:
self.current_node = target_node
self.visited.add(target_node)
self.path.append(target_node)
self._find_path()
self.visited.remove(target_node)
self.path.pop()
self.weight -= weight
class Graph(object):
def __init__(self):
self.nodes = list()
def __len__(self):
return len(self.nodes)
def __iter__(self):
return iter(self.nodes)
def _connect_nodes(self):
for node_a in self:
node_a.connect_to_many(self)
def add_node(self, node):
self.nodes.append(node)
def iter_shortest_path(self, start_point):
return (n.point for n in ShortestPathFinder(self)(start_point))
@classmethod
def from_lines(cls, lines):
result = cls()
for line in lines:
for point in line:
result.add_node(Node(point, line))
result._connect_nodes()
return result
def iter_shortest_path(lines, start_point):
return Graph.from_lines(lines).iter_shortest_path(start_point)
def main():
point = Point(5, 5)
lines = [
Line(Point(*a), Point(*b))
for a, b in [((0, 3), (0, 7)), ((2, 4), (7, 4))]
]
print list(iter_shortest_path(lines, point))
if __name__ == '__main__':
main()