Algorithmus: Navigation

[InformatikAzubi]

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:

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

 

[ukulele]

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?

 

[ukulele]

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:

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.