topic Re: Calculating shortest distance algorithm in Graphics Programming

Calculating shortest distance algorithm

brophymj — Tue, 27 Oct 2015 10:41:40 GMT

I've created some code that simulates 10 coordinates - four of the coordinates are fixed and all coordinates must lie in the plan (1,1), (10,1), (1,10) & (10.10). The starting position is (1,1). The code below calulcates every possible combination of routes whereby the starting coorddinate is (1,1) and the route must reach every point once and return to (1,1). The code calculates all combinations of routes for a given 10 coordinates correctly so that the shortest route can be established. However, the code does not remove double counting where the routes. Since the start and end point is (1,1) it includes both two of the same routes. Is there a way to remove this?

What I really want to do is to produce points radomly within the boundaries of a circle or diameter D and centre (x,y). I want to produce 1000s of 10 coordinate maps within a specified circle and calculate things like:

The shortest route

Average distance to centre point

Mean distance between each coordinate

etc.

My version of SAS is 9.3 TS Level 1M2

I have SAS/STAT and SAS/BASE

Many thanks

Here is my code below:

data fixed;
input i x y;
datalines;

1 1 1
2 10 10
3 1 10
4 10 1

;

data last;
input i x y;
datalines;

10 1 1
;

data shorter;
input COL1 $200.;
datalines;
run;
/**/
/*%macro simulate;*/
/**/
/*%do k = 1 %to 1;*/

data obs;
   do i= 5 to 10;
      x= round(10* ranuni(0),1);
      y= round(10* ranuni(0),1);
      output;
   end;
run;

data obs;
set fixed obs;
run;

data obs2;
set obs;
coord=catt(x,',',y);
retain start ;
if _n_= 1 then start= coord;
run;

/* flip the column to a row to get the ordered pairs in one record to permute later*/

proc transpose data=obs2 out=coordtrans;
by start;
var coord;
run;

/* you could trop some of the variables n, nfact, j. also the COL1 or start will have your first pair

so you also have it available as an end */

data next(drop = n nfact j);
   set coordtrans;
   array c Col2-col10; /* change the 5 to the number of pairs used*/
   n=dim(c);
   nfact=fact(n);
   do j=1 to nfact;
      call lexperm(j, of c[*]);
      output;
   end;
run;

data next;
set next;
COL11 = COL1;
run;

data test;
set next;

dist1 = 0;

%macro distance;

%do i = 2 %to 11;
%let j = %eval(&i-1);

x1 = input(put(scan(COL&j,1,','),2.),2.);
x2 = input(put(scan(COL&i,1,','),2.),2.);
y1 = input(put(scan(COL&j,2,','),2.),2.);
y2 = input(put(scan(COL&i,2,','),2.),2.);

format dist&i 8.1;

dist&i = sqrt((y2-y1)**2+(x2-x1)**2) + dist&j ;

drop x1 x2 y1 y2 dist&j;

%end;

%mend;

%distance;
run;

proc sort data = test; by dist11; run;

Re: Calculating shortest distance algorithm

LinusH — Tue, 27 Oct 2015 14:07:39 GMT

Sounds like Graph problem.

Search this forum for posts regarding PROC OPTMODEL, SAS/OR and some SAS delivered macros.

Re: Calculating shortest distance algorithm

Rick_SAS — Wed, 28 Oct 2015 13:10:20 GMT

This is called the "Travelling Salesman Problem" or TSP. There have been many SAS posts and papers written about how to solve it in SAS. For a large number of points, you should really use specialized software like SAS/OR or SAS/IML. For your small example, you can use direct enumeration, which you are doing.

This sounds like a school assignment, so rather than completely answering your questions, here are some hints:

1) Yes, the list of all permulations "double counts" the paths, since one route is in the clockwise direction and the other is counter clockwise. To eliminate one route, do not consider permutations for which the second element is greater than the last element. Thus for 4 cities you would consider 1->2->3->4 but not the reverse permutation 1->4->3->2.

2) To generate random points in a circle of radius R centered at (x0, y0)

/* generate points uniformly inside the disk with boundary 
   circle (x-x0)**2 + (y-y0)**2 = R**2
*/
data obs;
x0=1;  y0=2;  R = 2;  /* parameters */
keep i x y;
twopi = 2 * constant("PI");
do i = 5 to 10;
   theta = twopi * rand("uniform");
   u = rand("uniform");
   x = x0 + R*sqrt(u)*cos(theta);
   y = y0 + R*sqrt(u)*sin(theta);
   output;
end;
run;