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
- var allroutes:xml =
- <routes>
- <zip n="3014cd" t="0">
- <zip n="1011ab" t="50"/>
- <zip n="9714am" t="55"/>
- <zip n="2727" t="78"/>
- </zip>
- <zip n="1011ab" t="0">
- <zip n="3014cd" t="50"/>
- <zip n="9714am" t="20"/>
- <zip n="2727" t="10"/>
- </zip>
- <zip n="9714am" t="0">
- <zip n="3014cd" t="55"/>
- <zip n="1011ab" t="20"/>
- <zip n="2727" t="25"/>
- </zip>
- <zip n="2727" t="0">
- <zip n="3014cd" t="78"/>
- <zip n="1011ab" t="10"/>
- <zip n="9714am" t="25"/>
- </zip>
- </routes>;
- var hash:array = [];
- function shortestcircut(routes:xml, startpoint:string, endpoint:string):int
- {
- if (!routes.*.length()) return int.max_value - int(routes.@t);
- trace(startpoint, " => ", endpoint);
- trace("---------------------------");
- trace(routes.toxmlstring());
- trace("---------------------------");
- var startzip:xml = routes.*.(@n == startpoint)[0];
- var endzip:xml = routes.*.(@n == endpoint)[0];
- var ptime:int = routes.hasownproperty("@t") ? int(routes.@t) : 0;
- var time:int = int(startzip.*.(@n == endpoint).@t) + ptime;
- if (time == ptime) return int.max_value - ptime;
- trace("ptime:", ptime, "time:", time);
- var available:xmllist = startzip.*.(int(@t) < time);
- var availablezips:array = [];
- available.(availablezips.push(string(@n)));
- var totalavailables:xmllist =
- routes.*.((valueof() !== startzip &&
- availablezips.indexof(string(@n)) > -1) ?
- true : !hash.push(string(@n)));
- var unavailable:xmllist = routes..*.(int(@t) >= time);
- while (unavailable.length())
- {
- delete unavailable[0];
- }
- delete routes.*.(@n == endpoint)[0];
- if (!routes.*.length()) time;
- var lookup:xml;
- var addedtime:int;
- for each (var n:string in availablezips)
- {
- lookup = totalavailables.(@n == n)[0];
- addedtime = ptime + int(available.(@n == n)[0].@t);
- unavailable =
- routes.*.(@n == n && (@t = int(@t) +
- addedtime)).*.(int(@t) + addedtime >= time);
- while (unavailable.length())
- {
- delete unavailable[0];
- }
- }
- unavailable = routes.*.(hassimplecontent());
- while (unavailable.length())
- {
- delete unavailable[0];
- }
- totalavailables = routes.*.(valueof() !== startzip);
- delete routes.*.(valueof() === startzip)[0];
- if (!routes.*.length()) time;
- while (routes.*.length())
- {
- routes.@t = routes.*[0].@t;
- addedtime = shortestcircut(routes.copy(), routes.*[0].@n, endpoint);
- trace(time, "- adding -", routes.*[0].@t, "- next approach -", addedtime);
- if (addedtime < time) time = addedtime;
- delete routes.*[0];
- }
- trace("<--------------------------->");
- return time;
- }
- trace(shortestcircut(allroutes.copy(), "2727", "3014cd"));
More discussions in Flex (Read Only)
adobe
Comments
Post a Comment