topic Re: Simulating all the possible routes starting on one position and returning to that position in Graphics Programming

Simulating all the possible routes starting on one position and returning to that position

Hugo123 — Thu, 20 Aug 2015 20:02:41 GMT

I am trying to simulate combinations based on 5 coordinates (datset below):

data coord;

input x 1. y 1.;

datalines;

run;

Every combination must begin with (1,1) and end with (1,1) i.e.

(1,1) -> (3,2)-> (5,5)-> (9,1)-> (1,4)-> (1,1)

and all combinations must be unique and finally that there can't be the above route and

(1,1) ->(1,4)-> (9,1)-> (5,5)-> (3,2)-> (1,1)

as both routes are the same but in opposite directions.

Is there a way to do this in sas?

Re: Simulating all the possible routes starting on one position and returning to that position

FatCaptain — Wed, 09 Sep 2015 15:38:29 GMT

The code below should do what you require.

Just a few notes.

1) I've stuck the x and the y coordinate together as it's easier to deal with them in this way.

2) I've hard coded the 1,1 coordinate as it does not change. This can however be incorporated into the data if you require.

3) The data set outds2 also contains a list of the routes you require and outds3 contains the reverse of these routes.

/*Set up the initial table*/
data coord;
input xy 8.;
datalines;
32
55
91
14
run;

/*Find all unique routes*/
proc sql noprint ;
create table outds as
select 11 as c1,
       a.xy as c2,
       b.xy as c3,
       c.xy as c4,
       d.xy as c5,
       11 as c6
from coord as a,
   coord as b,
   coord as c,
   coord as d
where a.xy ne b.xy and a.xy ne c.xy and a.xy ne d.xy and b.xy ne c.xy and b.xy ne d.xy and c.xy ne d.xy ;

select count(*) into :nobserv from outds ;

quit ;

/*Find the routes which are the reverse of already known routes*/
data outds2 (drop=c2_2 c3_2 c4_2 c5_2);
do i = 1 to &nobserv-1 ;
   do j = i+1 to &nobserv ;
       set outds point=i ;
           set outds (rename=(c2=c2_2 c3=c3_2 c4=c4_2 c5=c5_2)) point=j ;
               if c2=c5_2 and c3=c4_2 and c4=c3_2 and c5=c2_2 then output ;
   end ;
end ;
stop ;
run ;

/*Remove the reverse routes from the main data set*/
proc sql ;
create table outds3 as
select *
from   outds
except all
select *
from   outds2 ;
quit ;

Re: Simulating all the possible routes starting on one position and returning to that position

MikeZdeb — Fri, 11 Sep 2015 13:08:28 GMT

Hi, here's another approach that uses LEXPERM to generate the permutations of nodes (same answer as the other posted solution with some paths shown in the reverse order) ...

* generate permutations of four nodes;
data perm;
array x(4) $2 ('32' '14' '55' '91');
do j=1 to fact(4);
rc=lexperm(j, of x(*));
output;
end;
keep x:;
run;

* identify duplicates (left-2-right = right-2-left, output only one of the pair);

data check;

retain x0 x5 '11';
set perm nobs=howmany;
s1 = catt(of x1-x4);
do j=_n_ to howmany;
set perm point=j;
s2 = catt(of x4-x1);
if s1 eq s2 then leave;
end;
if s1 eq s2 then output;
keep x:;
run;

data set CHECK ...

Obs x0 x1 x2 x3 x4 x5

1 11 91 55 32 14 11
2 11 55 91 32 14 11
3 11 91 32 55 14 11
4 11 32 91 55 14 11
5 11 55 32 91 14 11
6 11 32 55 91 14 11
7 11 91 55 14 32 11
8 11 55 91 14 32 11
9 11 91 14 55 32 11
10 11 55 14 91 32 11
11 11 91 32 14 55 11
12 11 91 14 32 55 11

Re: Simulating all the possible routes starting on one position and returning to that position

Rick_SAS — Mon, 14 Sep 2015 18:39:06 GMT

This is an enumeration of the possible paths in the Traveling Salesman problem. As the number of points grows, brute-force enumeration becomes prohibitive, but you can use various optimization schemes to obtain optimal or nearly optimal paths.

Do an internet search for +SAS "Traveling salesman" to see many solutions in SAS for the TSP.