1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen
  2. Willkommen im Forum für alle Datenbanken! Registriere Dich kostenlos und diskutiere über DBs wie Mysql, Oracle, Sql-Server, Postgres, Access uvm
    Information ausblenden

Algorithmus: Navigation

Dieses Thema im Forum "Microsoft SQL Server" wurde erstellt von InformatikAzubi, 27 November 2011.

  1. InformatikAzubi

    InformatikAzubi Neuer Benutzer

    huhu Zusammen,

    ich hab in der Schule die Aufgabe bekommen ein Navi zu basteln. Die Daten für die einzelnen Strecken habe ich in einer Datenbank abgelegt. Eine UDF soll die einzelnen Strecken, die zum Ziel führen, ausgeben. Ich muss ja alle möglichen Streckenkombinationen berechnen. Und mein Problem ist das Durchlaufen aller möglichen Fahrrouten. Wie durchlaufe ich alle möglichen Routen?

    Ich möchte nicht, dass ihr mir den Quellcode schreibt. Vielleicht wisst ihr eine Lösung wie ich zum Ziel komme.

    Hier inforamtionen zu meiner Grundidee:

    Also meine Streckeninformationen stehen in einer Tabelle namens "Strecken". Diese ist folgendermaßen aufgebaut:
    Strecken_ID INT --um jede Strecke eindeutig zu identifizieren
    Strecken_Start_ID INT --ID der Startstadt
    Strecken_Ziel_ID INT --ID der Zielstadt
    Strecken_Distanz INT --Länge der Strecke in Km
    Strecken_Typ INT -- 0 = Autobahn, 1 = Feldwege
    Strecken_Geschwindigkeit INT --Geschwindigkeit, die man auf der Strecke fahren darf

    Meine angefangede UDF sieht folgendermaßen aus:
    Code:
    CREATE PROCEDURE [dbo].[GET_WAY](
      @StartID          INT,
      @ZielID          INT,
      @WegArt          INT
    )
     
    returns @RET TABLE(
        TourID              INT,
        StartID              INT,
        ZielID              INT,
        Distanz              INT,
        Geschwindigkeit  INT)
    /*
    @description Berechnet die gewünschte Route
     
    param    @StartID      ID des Startknoten
    param    @ZielID      ID des Zielknoten
    param    @WegArt      0 = schnellste Route, 1 = kürzeste Route
     
    Information zur TourID: Diese ID kann mehreren Strecken zugeordnet werden. Alle Strecken, die die selbe TourID haben, führen zum gewünschten Ziel.
     
    sample exec GET_WAY 1,2,0
     
    created 26.11.2011 Mein_Name (zensiert)
    */
    AS
    BEGIN
     
    --In diesen 2 ZwischenVariablen werden ID, der Orte gesperichert, wo ich schonmal war, damit ich nicht im Kreis fahre
      DECLARE @ZwischenStartID INT,
              @ZwischenZielID INT,
              @TourID
     
      --ermitteln des Start- und Ziel-Orts
      SET @ZwischenStartID = @STARTID
      SET @ZwischenZielID = @ZIELID
      SET @TOURID = 1
     
    --*******************************************************************************
    --Hier muss die Tabelle @RET mit allen möglichen Streckenkombinationen,
    --die zum Ziel führen gefüllt werden. Das schaffe ich aber nicht
    --*******************************************************************************
     
    --Auswertung der Schnellsten oder der kürzesten Route
    Declare    DECLARE @BEST_TOUR_ID INT
     
    IF ( @WegArt = 0 )--0 = schnellste Route, 1 = kürzeste Route
      BEGIN
          SET @BEST_TOUR_ID = (SELECT tourid,
                                      MIN(SUM(Geschwindigkeit))
                              FROM  @RET
                              GROUP  BY TourId)
      END
    ELSE
      SET @BEST_TOUR_ID = (SELECT tourid,
                                  MIN(SUM(Distanz))
                          FROM  @RET
                          GROUP  BY TourId)
                   
    --Alle zu langen Strecken werden gelöscht, so dass nur 1 Tour ausgegeben wird
    DELETE FROM @RET where TourId <> @BEST_TOUR_ID
      RETURN
    END
    
    Vielen Dank im voraus

    InformatikAzubi
     
  2. ukulele

    ukulele Datenbank-Guru

    Hört sich für mich sehr komplex an ohne das ich mich da jetzt komplett einlesen kann. Soll das wirklich in SQL berechnet werden? Ich wüsste nicht wie ich alle möglichen Kombinationen in SQL ermitteln sollte.

    Und was ich auch nicht verstehe: Was genau ist die Strecken Start ID und die Strecken End ID, eine Kreuzung? Oder warum steht die Information in den Daten der Strecken Tabelle, gibt es nur Städte als Start- und Endpunkte?
     
  3. ukulele

    ukulele Datenbank-Guru

    Eventuell legt man per Abfrage das Kreuzprodukt aus der Tabelle Strecken mit sich selbst zugrunde und fügt solange die Tabelle erneut hinzu, bis Start und Ziel ermittelt wurden. Ungefähr so:
    Code:
    SELECT    s1.Strecken_ID,
    --        [...]
            sn.Strecken_ID
    FROM    Strecken s1,
    --      [...]
            Strecken sn
    WHERE    s1.Strecken_Start_ID = @StartID
    AND        sn.Strecken_Ziel_ID = @ZielID
    AND        s1.Strecken_Ziel_ID -- [...]
    --      [...]
            = sn.Strecken_Start_ID
    Natürlich muss man schauen:
    - ...ob es eine Strecke gibt die direkt zum Ziel führt (Das wäre die einfachste Lösung)
    - ...wieviele Strecken notwendig sind, um zum Ziel zu kommen. Reichen 2 nicht aus, muss eine weitere Tabelle hinzu gefügt werden s2,s3, etc.
    - ...ob nicht vieleicht durch hinzufügen einer weiteren Strecke der Weg kürzer / schneller wird. Man muss also über die notwendige Anzahl von Strecken hinaus noch etwas weiter rechnen.

    PS: So eine Aufgabe steht und fällt mit Testdaten, da sollte man sich auf jedenfall viel Mühe geben.
     

Diese Seite empfehlen