Write a recursive function to determine all possible paths between a number of addresses


hi,

 

i have matrix holds time data takes travel between different addresses (zipcodes actually).

 

i want determine possible unique routes (each route should travel each zipcode), can determine routes take least amount of time. thought easiest solution use recursive function , determine unique routes mimicing tree structure arrays.

 

however actionscript/flex knowledge not sufficient enough write i'm afraid.

 

my begin scenario looks this:

 

var timematrix:array = {      "3014cd" : {           "1011ab" : 50,           "9714am" : 30,           "2727"   : 20 }      "1011ab" : {           "3014cd" : 30,           "9714am" : 40,           "2727"   : 10,      "9714am" : {           "3014cd" : 55,           "1011ab" : 20,           "2727"   : 30 }      "2727" : {           "3014cd" : 78,           "1011ab" : 30,           "9714am" : 25 } };  var zipcodes:array; zipcodes.push("3014cd"); zipcodes.push("1011ab"); zipcodes.push("9714am"); zipcodes.push("2727");  

 

thanks in advance

  1.     var allroutes:xml =
  2.     <routes>
  3.         <zip n="3014cd" t="0">
  4.             <zip n="1011ab" t="50"/>
  5.             <zip n="9714am" t="55"/>
  6.             <zip n="2727" t="78"/>
  7.         </zip>
  8.             <zip n="1011ab" t="0">
  9.             <zip n="3014cd" t="50"/>
  10.             <zip n="9714am" t="20"/>
  11.             <zip n="2727" t="10"/>
  12.         </zip>
  13.             <zip n="9714am" t="0">
  14.             <zip n="3014cd" t="55"/>
  15.             <zip n="1011ab" t="20"/>
  16.             <zip n="2727" t="25"/>
  17.         </zip>
  18.         <zip n="2727" t="0">
  19.             <zip n="3014cd" t="78"/>
  20.             <zip n="1011ab" t="10"/>
  21.             <zip n="9714am" t="25"/>
  22.         </zip>
  23.     </routes>;
  24.     var hash:array = [];
  25.     function shortestcircut(routes:xml, startpoint:string, endpoint:string):int
  26.     {
  27.         if (!routes.*.length()) return int.max_value - int(routes.@t);
  28.         trace(startpoint, " => ", endpoint);
  29.         trace("---------------------------");
  30.         trace(routes.toxmlstring());
  31.         trace("---------------------------");
  32.         var startzip:xml = routes.*.(@n == startpoint)[0];
  33.         var endzip:xml = routes.*.(@n == endpoint)[0];
  34.         var ptime:int = routes.hasownproperty("@t") ? int(routes.@t) : 0;
  35.         var time:int = int(startzip.*.(@n == endpoint).@t) + ptime;
  36.         if (time == ptime) return int.max_value - ptime;
  37.         trace("ptime:", ptime, "time:", time);
  38.         var available:xmllist = startzip.*.(int(@t) < time);
  39.         var availablezips:array = [];
  40.         available.(availablezips.push(string(@n)));
  41.         var totalavailables:xmllist =
  42.         routes.*.((valueof() !== startzip &&
  43.         availablezips.indexof(string(@n)) > -1) ?
  44.         true : !hash.push(string(@n)));
  45.         var unavailable:xmllist = routes..*.(int(@t) >= time);
  46.         while (unavailable.length())
  47.         {
  48.             delete unavailable[0];
  49.         }
  50.         delete routes.*.(@n == endpoint)[0];
  51.         if (!routes.*.length()) time;
  52.         var lookup:xml;
  53.         var addedtime:int;
  54.         for each (var n:string in availablezips)
  55.         {
  56.             lookup = totalavailables.(@n == n)[0];
  57.             addedtime = ptime + int(available.(@n == n)[0].@t);
  58.             unavailable =
  59.                 routes.*.(@n == n && (@t = int(@t) +
  60.                 addedtime)).*.(int(@t) + addedtime >= time);
  61.             while (unavailable.length())
  62.             {
  63.                 delete unavailable[0];
  64.             }
  65.         }
  66.         unavailable = routes.*.(hassimplecontent());
  67.         while (unavailable.length())
  68.         {
  69.             delete unavailable[0];
  70.         }
  71.         totalavailables = routes.*.(valueof() !== startzip);
  72.         delete routes.*.(valueof() === startzip)[0];
  73.         if (!routes.*.length()) time;
  74.         while (routes.*.length())
  75.         {
  76.             routes.@t = routes.*[0].@t;
  77.             addedtime = shortestcircut(routes.copy(), routes.*[0].@n, endpoint);
  78.             trace(time, "- adding -", routes.*[0].@t, "- next approach -", addedtime);
  79.             if (addedtime < time) time = addedtime;
  80.             delete routes.*[0];
  81.         }
  82.         trace("<--------------------------->");
  83.         return time;
  84.     }
  85.     trace(shortestcircut(allroutes.copy(), "2727", "3014cd"));


More discussions in Flex (Read Only)


adobe

Comments

Popular posts from this blog

Flip address is out of range arduino uno r3

Arduino Uno not uploading

Indesign and MathType fonts