This discussion is archived
1 2 Previous Next 19 Replies Latest reply: Oct 9, 2012 2:51 AM by _jum Go to original post RSS
  • 15. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    Jum and Luc

    I may have 10 to 20 points depending on the situation.
    Shall I keep the upper limit of for loop as 10 if number of intermediate points are 10 ??

    thanks
  • 16. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi,
    --------------
    I have tested this different start point, end point, intermediate points
    The distance computation is correct.
    It has to select all three intermediate points (1,2,3) as there is no other way from start point to reach end point.
    But it has selected 1,2
    ----------------------


    DECLARE
    TYPE points IS TABLE OF sdo_geometry;
    ipoints points := points();
    apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.90812, 41.9673885, 0), NULL , NULL);
    epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.900846, 41.967396, 0), NULL, NULL);
    dist NUMBER := 0;
    sumd NUMBER := 9999999;
    route VARCHAR2(200) := '';
    BEGIN
    --initialize
    ipoints.extend(3);
    ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type( -87.905464, 41.967392, 0), NULL, NULL);
    ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type( -87.904189, 41.967377, 0), NULL, NULL);
    ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type( -87.901859, 41.9673795,0), NULL, NULL);
    --brute force
    FOR i IN 1..2 LOOP
    FOR j IN 1..2 LOOP
    --dont use same point twice !
    IF i=j THEN CONTINUE;END IF;
    dist := sdo_geom.sdo_distance(apoint ,ipoints(i),1) +
    sdo_geom.sdo_distance(ipoints(i),ipoints(j),1) +
    sdo_geom.sdo_distance(ipoints(j), epoint,1);
    --get the actual route
    IF sumd>dist THEN
    sumd := dist;
    route := to_char(i)||to_char(j);
    END IF;
    END LOOP;
    END LOOP;
    --length of shortest path
    dbms_output.put_line ('route='||route);
    dbms_output.put_line (sumd);
    END;
    -------------
    route=12
    602.985626658242

    regards
  • 17. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    If you want to find 3 points you have to use 3 FOR LOOPs and to concat 3 indexes for ROUTE:
    SET SERVEROUTPUT ON SIZE 900000;
     
    DECLARE
      TYPE points IS TABLE OF sdo_geometry;
     
      ipoints points :=  points();
      apoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.910994, 41.982889 , 0), NULL , NULL);
      epoint sdo_geometry := sdo_geometry(2001, 8307, sdo_point_type(-87.907813, 41.982816 , 0), NULL, NULL);   
      
      dist   NUMBER := 0;
      sumd   NUMBER := 9999999;
      
      route  VARCHAR2(200) := '';
     
    BEGIN
     
      --initialize
      ipoints.extend(3);
      ipoints(1) := sdo_geometry(2001, 8307,sdo_point_type( -87.905464, 41.967392, 0), NULL, NULL);
      ipoints(2) := sdo_geometry(2001, 8307,sdo_point_type( -87.904189, 41.967377, 0), NULL, NULL);
      ipoints(3) := sdo_geometry(2001, 8307,sdo_point_type( -87.901859, 41.9673795,0), NULL, NULL);
     
      --brute force
      FOR i IN 1..3 LOOP
        FOR j IN 1..3 LOOP
          FOR k IN 1..3 LOOP
              --dont use same point twice !
              IF (i=j OR i=k OR j=k) THEN CONTINUE;END IF;
              dist  := sdo_geom.sdo_distance(apoint    ,ipoints(i),1) +  
                       sdo_geom.sdo_distance(ipoints(i),ipoints(j),1) +
                       sdo_geom.sdo_distance(ipoints(j),    epoint,1);
              --get the actual route
              IF sumd>dist THEN
                sumd  := dist;
                route := to_char(i)||to_char(j)||to_char(k);
              END IF;
          END LOOP;
        END LOOP;
      END LOOP;
     
      --length of shortest path
      dbms_output.put_line ('route='||route);
      dbms_output.put_line (sumd);
    END;
    
    route=123
    3627,935355905372
    The (here very simple) brute force method needs more and more iterations for each intermediate point (n**n), so it can't be used for big numbers of points.
    In this thread there are links and hints for other methods in these cases.
    POINTS ITERATIONS
    ----------------------------
    1            1
    2            4
    3           27
    4          265
    5         3125
    6        46656
    ...
    10 10000000000
    BTW. you should def. use code-tags, to format your code and intend the lines, you see the difference, don't you?
  • 18. Re: shortest distance
    don123 Newbie
    Currently Being Moderated
    hi

    Many thanks..
    I have marked this as answered, however, we need to find alternate solution, i mean same code to solve different intermediate points.

    regards
  • 19. Re: shortest distance
    _jum Journeyer
    Currently Being Moderated
    Many thanks!
    Found another link: Oracle Spatial Network Data Model for Traveling Salesman Problem Analysis. But didn't use Oracle Spatial NetworkData Model nor this API yet.
1 2 Previous Next

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points