Forum

[Exceptionfault]

Die Frage "Wer kennt wen über wen?" ist nüchtern betrachtet, nichts anderes als ein extrem einfacher Pathfinding Algorithmus. Das schöne daran ist, dass übliche Parameter wie "Wegekosten" o.ä. wegfallen und nur die Anzahl der Knoten bis zum Ziel entscheidend für die kürzeste Strecke sind. Daher eignet sich hier das rekursive SQL ("connect by") von Oracle sehr gut.

Rein aus Interesse habe ich mich mal an den wohl bekanntesten Pathfinding Algorithmus (A*) gemacht und in PL/SQL umgesetzt:

Als Grundlage dient mir ein Koordinatensystem mit fixen Orten, dargestellt durch folgende Tabelle und INSERTS

Code:

0 1 2 3 4 5 6 7 8 9101112 0A B 1 H 2 C 3 D 4 F I 5E 6 G 7 K 8 J N 9 M 10 L 11 O 12 CREATE TABLE places ( placeid NUMBER(10,0) CONSTRAINT NN_places_id NOT NULL, name VARCHAR2(30) CONSTRAINT NN_places_name NOT NULL, posx NUMBER(10,0) CONSTRAINT NN_places_posx NOT NULL, posy NUMBER(10,0) CONSTRAINT NN_places_posy NOT NULL ); ALTER TABLE places ADD CONSTRAINT PK_places PRIMARY KEY ( placeid ) USING INDEX; INSERT INTO places VALUES( 1, 'A', 0, 0 ); INSERT INTO places VALUES( 2, 'B', 4, 0 ); INSERT INTO places VALUES( 3, 'C', 6, 2 ); INSERT INTO places VALUES( 4, 'D', 2, 3 ); INSERT INTO places VALUES( 5, 'E', 0, 5 ); INSERT INTO places VALUES( 6, 'F', 5, 4 ); INSERT INTO places VALUES( 7, 'G', 7, 6 ); INSERT INTO places VALUES( 8, 'H', 9, 1 ); INSERT INTO places VALUES( 9, 'I', 11, 4 ); INSERT INTO places VALUES( 10, 'J', 9, 8 ); INSERT INTO places VALUES( 11, 'K', 3, 7 ); INSERT INTO places VALUES( 12, 'L', 5, 10 ); INSERT INTO places VALUES( 13, 'M', 1, 9 ); INSERT INTO places VALUES( 14, 'N', 12, 8 ); INSERT INTO places VALUES( 15, 'O', 7, 11 );

Die einzelnen Orte sind untereinander mit Strassen verbunden. Als zusätzliche Information werden die Wegekosten abgelegt. In meinem Fall wurden sie einfach über die Länge der Strecke berechnet. Ich gehe also davon aus, dass ich auf allen Strecken gleich schnell voran komme, keine Steigungen o.ä. vorhanden sind etc..

Code:

CREATE TABLE roads ( sourceid NUMBER(10,0) CONSTRAINT NN_roads_source NOT NULL, targetid NUMBER(10,0) CONSTRAINT NN_roads_target NOT NULL, cost NUMBER(5,0) CONSTRAINT NN_roads_cost NOT NULL ); ALTER TABLE roads ADD CONSTRAINT PK_roads PRIMARY KEY ( sourceid, targetid ) USING INDEX; CREATE UNIQUE INDEX idx_roads_inv ON roads ( targetid, sourceid ); INSERT INTO roads VALUES ( 1, 4, 10 ); INSERT INTO roads VALUES ( 9, 14, 15 ); INSERT INTO roads VALUES ( 10, 14, 10 ); INSERT INTO roads VALUES ( 14, 15, 25 ); INSERT INTO roads VALUES ( 12, 15, 5 ); INSERT INTO roads VALUES ( 13, 12, 15 ); INSERT INTO roads VALUES ( 13, 5, 15 ); INSERT INTO roads VALUES ( 5, 4, 7 ); INSERT INTO roads VALUES ( 8, 9, 12 ); INSERT INTO roads VALUES ( 8, 3, 10 ); INSERT INTO roads VALUES ( 3, 4, 15 ); INSERT INTO roads VALUES ( 3, 2, 7 ); INSERT INTO roads VALUES ( 1, 2, 15 ); INSERT INTO roads VALUES ( 7, 10, 7 ); INSERT INTO roads VALUES ( 6, 7, 7 ); INSERT INTO roads VALUES ( 7, 11, 15 ); INSERT INTO roads VALUES ( 11, 5, 13 ); INSERT INTO roads VALUES ( 8, 7, 23 );

Daraus ergibt sich dann folgende Karte:
(siehe Anhang...)


Der Algorithmus selbst benötigt 2 temporäre Tabellen zur Berechnung:

Code:
CREATE GLOBAL TEMPORARY TABLE freelist ( placeid NUMBER(10,0), parentid NUMBER(10,0), abscost NUMBER(10,0), calccost NUMBER(10,0), CONSTRAINT PK_FREELIST PRIMARY KEY ( placeid ) USING INDEX ); CREATE GLOBAL TEMPORARY TABLE locklist ( placeid NUMBER(10,0), parentid NUMBER(10,0), abscost NUMBER(10,0), calccost NUMBER(10,0), CONSTRAINT PK_LOCKLIST PRIMARY KEY ( placeid ) USING INDEX );

Die Funktionsweise des A* Algorithmus möchte ich hier nicht erläutern, das würde den Rahmen sprengen, darum hier einfach der Sourcecode meines Packages:

sql Code:

CREATE OR REPLACE FUNCTION CALCCOSTS( sourceid        IN places.placeid%TYPE,                                       targetid        IN places.placeid%TYPE )                                       RETURN             NUMBER IS     s       places%ROWTYPE;     t       places%ROWTYPE;     calc    NUMBER; BEGIN     SELECT  *     INTO    s     FROM    places     WHERE   placeid = sourceid;         SELECT  *     INTO    t     FROM    places     WHERE   placeid = targetid;         calc := 5 * ROUND( SQRT( (t.POSX - s.POSX)*(t.POSX - s.POSX) + (t.POSY - s.POSY)*(t.POSY - s.POSY) ) );     DBMS_OUTPUT.put_line( '=> Calculation distance between ' || TO_CHAR( sourceid ) || ' and ' || to_char( targetid ) || ' => ' || to_char( calc ) );     RETURN  calc; END;                         /   SHO ERRORS   CREATE OR REPLACE PACKAGE A_STAR IS       PROCEDURE SEARCH(   sourceid    IN places.placeid%TYPE,                         targetid    IN places.placeid%TYPE );     END; /   SHOW ERRORS     CREATE OR REPLACE PACKAGE BODY A_STAR IS       targetnode      places.placeid%TYPE;       ------------------------------------------------------------------------------------------------     PROCEDURE INIT_SEARCH     IS     BEGIN         DELETE FROM LOCKLIST;         DELETE FROM FREELIST;         targetnode := NULL;     END;         ------------------------------------------------------------------------------------------------     PROCEDURE ADD_TO_LOCKLIST( n_placeid  IN places.placeid%TYPE,                                n_parentid IN places.placeid%TYPE,                                n_abscost  IN NUMBER,                                n_calccost IN NUMBER,                                n_rowt     OUT locklist%ROWTYPE )     IS     BEGIN         DBMS_OUTPUT.put_line( '=> Adding node to locklist: ' || TO_CHAR( n_placeid ));         INSERT INTO LOCKLIST VALUES( n_placeid, n_parentid, n_abscost, n_calccost )         RETURNING placeid, parentid, abscost, calccost INTO n_rowt;         DELETE FROM FREELIST WHERE placeid = n_placeid;     END;           ------------------------------------------------------------------------------------------------     PROCEDURE STEP_FORWARD( rowt OUT locklist%ROWTYPE )     IS     BEGIN         SELECT  *         INTO    rowt         FROM    FREELIST         WHERE   ABSCOST + CALCCOST = ( SELECT MIN( ABSCOST + CALCCOST ) FROM FREELIST )         AND     ROWNUM  = 1;           END;         ------------------------------------------------------------------------------------------------     PROCEDURE MERGE_FREELIST( source    IN locklist%ROWTYPE )     IS     BEGIN         MERGE INTO FREELIST f         USING   (                     -- finde alle orte, die mit der source verbunden sind und noch nicht in der                     -- lockliste drin stehen                     SELECT  sourceid AS PLACEID,                             cost                           FROM    roads                     WHERE   targetid = source.placeid                     AND     sourceid NOT IN ( SELECT PLACEID FROM locklist )                     UNION                     SELECT  targetid AS PLACEID,                             cost                     FROM    roads                     WHERE   sourceid = source.placeid                     AND     targetid NOT IN ( SELECT PLACEID FROM locklist )         ) r         ON (             f.PLACEID = r.PLACEID           )         WHEN MATCHED THEN             UPDATE SET      f.PARENTID = source.placeid,                             f.ABSCOST  = source.abscost + r.cost                    WHERE    f.ABSCOST  > source.abscost + r.cost                                 WHEN NOT MATCHED             THEN INSERT VALUES ( r.PLACEID, source.PLACEID, source.abscost + r.cost, CALCCOSTS( r.placeid, targetnode ));         END;             ------------------------------------------------------------------------------------------------     PROCEDURE SEARCH(   sourceid        IN places.placeid%TYPE,                         targetid        IN places.placeid%TYPE )     IS         rowt locklist%rowtype;         i   PLS_INTEGER := 1;     BEGIN         INIT_SEARCH;                 targetnode := targetid;         ADD_TO_LOCKLIST( sourceid, sourceid, 0, 0, rowt );                 WHILE rowt.placeid <> targetid LOOP             MERGE_FREELIST( rowt );                     STEP_FORWARD( rowt );             ADD_TO_LOCKLIST( rowt.placeid, rowt.parentid, rowt.abscost, rowt.calccost,  rowt );             i := i+1;             IF i >= 1000 THEN                 RETURN;             END IF;         END LOOP;             END;           END; /   SHOW ERRORS

Der Aufruf erfolgt dann einfach mit

Code:
set serveroutput on exec A_STAR.SEARCH( 9, 1 );

Wobei die beiden Parameter die ID`s des Startknoten und des Zielknoten angeben.

Wer sich detailiert damit auseinadersetzen will, kann mal hier ( http://www.gamasutra.com/features/20...pinter_pfv.htm ) etwas tiefer nachlesen. Meine Implementation ist dagegen recht rudimentär.