Turbo Pascal kürzeste Route


  • fenchelT
  • 1097 Aufrufe 4 Antworten

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Turbo Pascal kürzeste Route

    halli hallo
    hab mal wieder n neues problem. diesmal sollen wir die krüzeste route zwischen 5 punkten ausrechnen lassen. die punkte werden per zufall gesetzt und der comp soll dann die kürzeste verbindung zwischen ihnen zeichnen.
    die punkte sind ja kein problem, aber die strecke!
    Alles natürlich mit Turbo Pascal! vielen dank!

    hier ist das prog mit den punkten, die kürzeste strecke fehlt aber noch:

    program route;
    uses crt, graph;

    var
    Gd, Gm, i: Integer;
    radius : Integer;
    x, y : array[1..5] of integer;

    procedure orte_erstellen;
    begin setcolor(4);
    for i:=1 to 5 do
    begin
    x:=random(640) +10;
    y[i]:=random(460) +10;
    setfillstyle(1,4);
    FillEllipse(x[i], y[i], 6, 6);
    setcolor(14);
    settextstyle(5,0,1);
    outtextxy(x[i], y[i],chr(64+i));
    end; end;

    {procedure berechnung;}


    begin
    randomize;
    Gd := Detect;
    InitGraph(Gd, Gm, 'c:\bp\bgi');
    if GraphResult <> grOk then
    Halt(1);
    orte_erstellen;
    {berechnung}
    Readln;
    CloseGraph;
    end.

  • Moin,


    Also wenn meine folgende Behauptung stimmt: "Um die kürzeste Strecke zu ermitteln die 5 Punkte miteinander verbinden reicht es immer von aktuellen Punkt zum Punkt in nächster Nähe zu wandern (das gilt aber nur wenn man mit einem Randpunkt anfängt, d.h. dem Punkt der am weitesten oben Links liegt z.B.)" dann kann ich dir helfen. nur bin ich mir nicht sicher ob die stimmt (und ob du den Startpunkt frei wählen darfst).

  • ja du liegst mit deiner vermutung richtig! bitte hilf mir! den startpunkt kann man frei wählen, hauptsache zum schluss hat man die kürzeste strecke, aber mit deiner idee immer den nahegelegensten punkt zu suchen, müsste das eigentlich funkzen, aber wie realisier ich das und lasse die punkt auch verbinden?
    vielen dank für deine hilfe!

    edit: wäre nett, wenn du mein prog als ausgangsvorlage nimmst. vielen dank!

  • Ich bin Krank (koppweh, deswegen will ich nicht vorm Bildschirm sitzen UND denken^^) und dass ich von Graphik keine Ahnung habe, dass habeich ja schon letztes Mal gesagt :)

    Aber:
    1. Du hast die Koordianten der aller Punkte.
    2. Meine o.g. Vermutung stimmt und den Punkt kannst du dir auch aussuchen.

    Also: Um den Abstand zwischen zwei beliebigen, bekannten Punkten zu bestimmen nimmst du eine umgewandelte Formel nach Pythagoras

    Abstand zum Quadrat = (x2-x1)² + (y2-y1)²

    a = Wurzel((x2-x1)²+(y2-y1)²)

    Du schreibst dir also jetzt eine Funktion die alle 5 Punkte durchgeht und den Abstand dieser zum Ursprung berechnet, dann weißt du welcher Punkt dein Startpunkt ist.

    Dann gehst du zu diesem Punkt und suchst dir von da an mit der selben Formel den nächsten und dann eben immer weiter.

    Also erweiter deinen Koordianten Array mal auf

    Punkte ARRAY [1..5] of RECORD
    x: integer;
    y: integer;
    abstand:integer;
    bearbeitet:boolen;
    END;

    Reihenfolge ARRAY [1..5] of integer;

    Du gehst also jedesmal wenn du einen Abstand ermittel willst alle Punkte nicht bearbeiten Punkte bis auf den mit dem du vergleichst durch und ermittelst den Abstand den du unter abstand speicherst. Dannach gehst du nochmals alle nicht bearbeiteten Punkte durch und merkst dir den mit dem kleinsten Abstand, diesen setzt du dann auf bearbeitet, gibts seine Nummer an die aktuelle Reihenfolge und machst dann mit ihm weiter, bis alle 5 durch sind.

    Und dann malst du jeweils Linien mit

    counter=1
    REPEAT
    "male linie von Punkt[reihenfolge.[counter]].x und Punkt[reihenfolge[counter]].y zu Punkt[reihenfolge.[counter+1]].x und Punkt[reihenfolge[counter+1]].y
    inc counter
    until counter=5

    Das kannst du selbst umsetzten, ich werde dazu frühstens am We zeit haben...


    Ansonsten bin ich nicht sicher ob das mit den "immer den aktuell nächsten Punkt" wirklich stimmt...