Der schnellste Weg von Punkt i zu Initialpunkt P

Du hast eine Idee für ein Projekt?
Antworten
BennyS
User
Beiträge: 19
Registriert: Montag 28. November 2016, 13:36

Hallihallo!
Ich habe eine kleine Denkaufgabe. Leider bin ich noch zu keinem zufriedenstellenden Entschluss gekommen. Das hat zuerst auch gar nicht mal so viel mit Python zutun, eher mit der Logik dahinter. Vielleicht erschließt sich daraus dann auch eine python routine.
Also das Problem ist folgendes:
Ich habe eine Punktewolke (im einfachen Beispiel kann das auch erstmal eine 2-D Wolke sein). Daraus bestimme ich einen Initialpunkt. Von allen anderen Punkten aus, soll nun der schnellste Weg vom ausgewählten Punkt zum Initialpunkt P gefunden werden (über andere Punkte wiederrum). Im besten Fall soll darin noch eine Routine enthalten sein, die den geringsten Abstand berücksichtigt. Da alles auf den Initialpunkt bezogen wird, sollte die Punktverlinkung natürlich im besten Fall auch in Richtung des Initialpunktes ablaufen.

Ein kleines Beispiel habe ich hier http://fs5.directupload.net/images/170215/b835zixm.jpg.

Hat jemand hierfür zufällig einen Geistesblitz und kann mir helfen?


Wäre super dankbar!

Grüße
Benjamin
BlackJack

@BennyS: Mir ist noch nicht so ganz klar wie die Verbindungen zwischen den Knoten aussehen‽ Ansonsten würde ich mal „single-source shortest paths“ in den Raum werfen.
BennyS
User
Beiträge: 19
Registriert: Montag 28. November 2016, 13:36

Diese Verbindungen sollen nur "bildlicher" Natur sein.

Am liebsten hätte ich am Ende noch ein zusätzliches Textfile, dass Informationen zu den Pfaden enthält. Z.B:
Initialpunkt = Punkt 5

Punkt 17 - Punkt 11,
Punkt 11 - Punkt 2,
Punkt 2 - Punkt 5.

Das Stichwort "Single-source shortest paths" gefällt mir schon mal ganz gut, muss mich da jetzt nur noch reinfuchsen :shock:
BlackJack

Nachtrag: Bevor man anfängt Standardalgorithmen selbst zu implementieren, das NetworkX-Package anschauen. :-)
BennyS
User
Beiträge: 19
Registriert: Montag 28. November 2016, 13:36

Irgendwie blicke ich noch nicht ganz durch.
Ich habe bereits ein paar dijkstra Algorithmen auf Github o.Ä. gefunden und versucht zu implementieren. Dennoch verstehe ich noch nicht ganz wie ich meine Datenreihen da einlesen kann.
Bei Networkx ist es ähnlich. Ich kann Nodes hinzufügen, aber woher weiß Networkx deren Koordinaten? Und was hat es mit der Gewichtung auf sich, falls ich die Punkte selbst nicht gewichten möchte?


Vielen dank schon mal
BlackJack

@BennyS: Was meinst Du mit Koordinaten? NetworkX arbeitet auf Graphen. Das man die in der Ebene zeichnen kann, und dabei dann jeder Knoten eine Koordinate braucht, hat nichts Graphen an sich zu tun. Die kennen nur Knoten und Kanten und gegebeennfalls Gewichtung.

Wenn einen eine spezielle Gewichtung nicht interessiert, der Algorithmus aber eine benötigt, gewichtet man in der Regel einfach alle Elemente gleich. Meistens mit 1.

Aber sehr wahrscheinlich brauchst Du ja doch eine Gewichtung, also Beispielsweise bei jeder Kante den Abstand zwischen den Punkten für die die beiden Knoten der Kante stehen. Denn sonst wäre ja jeder Punkt gleich weit von jedem anderen entfernt. Falls ich die Fragestellung richtig verstanden habe.
BennyS
User
Beiträge: 19
Registriert: Montag 28. November 2016, 13:36

Danke Blackjack schon mal für deine Mühe mit mir.

Ich glaube ich versuche nochmal das Problem darzustellen:
Ich habe folgende Punkte
# x y z
1 1 1 1
2 1 3 5
3 4 1 2
4 3 2 7
5 2 5 3
6 8 2 4
...

Im eigentlichen Fall kann dies auch eine n-dimensionale Punkte Wolke sein.
Ich definiere nun Punkt 3 als Startpunkt.

Was ich nun gerne hätte, wäre folgender Output: Die Pfade von jedem Punkt zum Punkt 3 über den kürzesten Weg. (kürzeste Distanz zwischen den Punkten, die angegebenen Pfaden müssen nicht stimmen, dienen nur als Beispiel)
Also z.b.
6 - 5 - 3
5 - 3
4 - 3
3
2 - 5 - 3
1 - 2 - 4 - 3

Ein Begriff der mir häufig über den Weg läuft ist der Dijkstra Algorithmus.
BennyS
User
Beiträge: 19
Registriert: Montag 28. November 2016, 13:36

Ich kann leider den Beitrag nicht mehr editieren, deswegen ein "Antwortpost"
Ich bin jetzt soweit, dass ich von meiner Punktewolke ausgehend, die Abstände zwischen jedem Punktepaar mit Scikitlearn berechne, daraus erhalte ich dann eine Matrix die die Punktabstände enthält. Diese wiederrum kann ich diesem Algorithmus hier weitergeben: http://www.geeksforgeeks.org/printing-p ... algorithm/
BlackJack

@BennyS: Ich hatte die Abstände selbst berechnet, und dafür für den Dijkstra NetworkX verwendet. :-) Deine Beispieldaten sind langweilig, nur Pfade mit maximal zwei Punkten. :P

Code: Alles auswählen

{Point(1, 1, 1, 1): [Point(3, 4, 1, 2), Point(1, 1, 1, 1)],
 Point(2, 1, 3, 5): [Point(3, 4, 1, 2), Point(2, 1, 3, 5)],
 Point(3, 4, 1, 2): [Point(3, 4, 1, 2)],
 Point(4, 3, 2, 7): [Point(3, 4, 1, 2), Point(4, 3, 2, 7)],
 Point(5, 2, 5, 3): [Point(3, 4, 1, 2), Point(5, 2, 5, 3)],
 Point(6, 8, 2, 4): [Point(3, 4, 1, 2), Point(6, 8, 2, 4)]}
BennyS
User
Beiträge: 19
Registriert: Montag 28. November 2016, 13:36

Was sagen diese Punkte nun aus?

Mein bisheriger Code sieht wie folgt aus:

Code: Alles auswählen

import numpy as np
from pylab import *
from sklearn.metrics.pairwise import euclidean_distances
from collections import defaultdict

np.set_printoptions(threshold=np.nan)

pathOut=open("Path.txt","w+") 
pathInfo=[]

#Class to represent a graph
class Graph:
 
    # A utility function to find the vertex with minimum dist value, from
    # the set of vertices still in queue
    def minDistance(self,dist,queue):
        # Initialize min value and min_index as -1
        minimum = float("Inf")
        min_index = -1
        #from the dist array,pick one which has min value and is till in queue
        for i in range(len(dist)):
            if dist[i] < minimum and i in queue:
                minimum = dist[i]
                min_index = i
        return min_index
 
 
    # Function to print shortest path from source to j
    # using parent array
    def printPath(self, parent, j):
        if parent[j] == -1 : #Base Case : If j is source
            print j,
            return
        self.printPath(parent , parent[j])
        print j,
         
 
    # A utility function to print the constructed distance
    # array
    def printSolution(self, dist, parent,src):
        #src = 0
        self.pathInfo=[]
        print("Vertex \t\tDistance from Source\t\t\t\tPath")
        for i in range(1, len(dist)):
            print("\n%d --> %d \t\t%d \t\t\t\t\t" % (src, i, dist[i])),
            self.printPath(parent,i)
 
 
    '''Function that implements Dijkstra's single source shortest path
    algorithm for a graph represented using adjacency matrix
    representation'''
    def dijkstra(self, graph, src):
 
        row = len(graph)
        col = len(graph[0])
 
        # The output array. dist[i] will hold the shortest distance from src to i
        # Initialize all distances as INFINITE 
        dist = [float("Inf")] * row
 
        #Parent array to store shortest path tree
        parent = [-1] * row
 
        # Distance of source vertex from itself is always 0
        dist[src] = 0
     
        # Add all vertices in queue
        queue = []
        for i in range(row):
            queue.append(i)
             
        #Find shortest path for all vertices
        while queue:
 
            # Pick the minimum dist vertex from the set of vertices
            # still in queue
            u = self.minDistance(dist,queue)    
 
            # remove min element    
            queue.remove(u)
 
            # Update dist value and parent index of the adjacent vertices of
            # the picked vertex. Consider only those vertices which are still in
            # queue
            for i in range(col):
                '''Update dist[i] only if it is in queue, there is
                an edge from u to i, and total weight of path from
                src to i through u is smaller than current value of
                dist[i]'''
                if graph[u][i] and i in queue:
                    if dist[u] + graph[u][i] < dist[i]:
                        dist[i] = dist[u] + graph[u][i]
                        parent[i] = u
 
 
        # print the constructed distance array
        self.printSolution(dist,parent,src)

        
test=np.loadtxt("Dataset.txt",skiprows=0)
testdata=test[:,1::]



distances=euclidean_distances(testdata, testdata)

for ijk in range(len(distances)):
    for ijk2 in range(len(distances)):
        if distances[ijk,ijk2]>=(0.8*distances.mean()):
            distances[ijk,ijk2]=0
    
g= Graph()

#Print the solution
g.dijkstra(distances,0)

pathOut.close()

#This code is contributed by Neelam Yadav

Irgendwie schaffe ich es nicht, die "Path" spalte auch in einer Textfile zu speichern. (Die zugrunde liegenden Datensätze Dataset.txt )

Irgendwie müsste man doch in der def printSolution auch noch ein "write" einbauen können, damit Python mir die Pfade in ein Textfile schreibt (mit dazugehörigen Infos). Aber das klappt bei mir leider nicht, ich vermute aufgrund des verkapselten printPath befehls. Kannst du mir da vielleicht noch helfen?
Zuletzt geändert von Anonymous am Donnerstag 16. Februar 2017, 14:23, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
BlackJack

@BennyS: Das ist eine Abbildung von Zielpunkt auf den Pfad von Punkt 3 zu diesem Punkt. Die müsste man für Deine Zwecke dann also noch umkehren.

Deine Graph-Klasse ist keine Klasse. Bitte nicht einfach Funktionen ohne Grund in eine Klasse stecken, wir sind hier ja nicht bei Java. ;-)
BlackJack

Das hier war der Code den ich verwendet hatte:

Code: Alles auswählen

#!/usr/bin/env python
from __future__ import absolute_import, division, print_function
from itertools import combinations
from math import sqrt
from pprint import pprint

import networkx as nx

SOURCE = '''\
# x y z
1 1 1 1
2 1 3 5
3 4 1 2
4 3 2 7
5 2 5 3
6 8 2 4
'''.splitlines()


class Point(object):

    def __init__(self, id_, x, y, z):
        self.id = id_
        self.x = x
        self.y = y
        self.z = z

    def __repr__(self):
        return (
            '{0.__class__.__name__}({0.id!r}, {0.x!r}, {0.y!r}, {0.z!r})'
                .format(self)
        )

    def distance(self, other):
        return sqrt(
            (self.x - other.x)**2
            + (self.y - other.y)**2
            + (self.z - other.z)**2
        )

    @classmethod
    def from_line(cls, line):
        return cls(*map(int, line.split()))


def main():
    lines = iter(SOURCE)
    next(lines)  # Skip header
    points = map(Point.from_line, lines)
    graph = nx.Graph()
    graph.add_weighted_edges_from(
        (a, b, a.distance(b)) for a, b in combinations(points, 2)
    )
    paths = nx.single_source_dijkstra_path(graph, points[2])
    pprint(paths)


if __name__ == '__main__':
    main()
Antworten