New Topic/Question
Reply
As in the title, what are the concrete applications of APSP problem. On the internet i have found only network routing, distributed computing and bioinformatics but it's a bit vague. Could anyone describe any 2 applications.
2 Replies - 925 Views - Last Post: 06 February 2012 - 11:09 AM
Topic Sponsor:
MultiQuoteReplies To: Real life applications of All-Pairs Shortest Path problem
#2
lordofduct
- I'm a cheeseburger
-
Reputation: 1250
- Posts: 3,421
- Joined: 24-September 10
Re: Real life applications of All-Pairs Shortest Path problem
Posted 06 February 2012 - 09:46 AM
What do you consider a "real world" application?
I could think of many scenarios in 'my' fields of interest, but I don't know if you'd classify them as 'real world'.
For instance path-finding in game AI may use a network node map of all-pairs paths for finding its way around a map from any given point in a node map to any given target. I have pre-determined path cost map that has been pre-calculated denoting how expensive between EVERY possible pair of nodes in the map (the all-pairs)... my AI object, say a hunter drone in an FPS, has multiple targets of interest: any opponent (broken into priorities for weak and integral to opposing team), attribute modifiers (health packs, ammo, etc), defensive points (guarding flag, protecting home base), and any other game specific goals. Now in code we generate a reduction map for all of these possible attributes in the existing pre-computed node map. We then select the best path over all, which appears to human players as the computer "making a choice". We may stir in some blind spots (redact parts of map so computer doesn't appear to be all knowing), and adverse choice modifiers that reflect most recent activity (if recently shot at, flag a 'fear' attribute of AI object, this creates a modifier that heightens chance to flee towards protected areas/team mates, or even perform random 'irrational' choices like including 'shoot team-mate' to the possible choice in node paths).
In networking you may see this as a network node map of a closed system. We need to choose efficient paths for data to travel from point A to point B, but data can and will appear at any given moment from any given node and need to travel to any other node. An analysis of the entire system can create a cost efficiency analysis in your network to show where weak or latent spots in your network may exist... data traveling from F to X has no efficient paths and takes 5 times as long as any other point to point, this is a place in our network where we may want to consider modification.
Is this homework? I hope it's not, and instead you're just using this as a starting point to learn more. Then again, go ahead, use my answers... I'd love to see if my casual pulling information out of my ass actually succeeds... are you willing to take that chance?
I could think of many scenarios in 'my' fields of interest, but I don't know if you'd classify them as 'real world'.
For instance path-finding in game AI may use a network node map of all-pairs paths for finding its way around a map from any given point in a node map to any given target. I have pre-determined path cost map that has been pre-calculated denoting how expensive between EVERY possible pair of nodes in the map (the all-pairs)... my AI object, say a hunter drone in an FPS, has multiple targets of interest: any opponent (broken into priorities for weak and integral to opposing team), attribute modifiers (health packs, ammo, etc), defensive points (guarding flag, protecting home base), and any other game specific goals. Now in code we generate a reduction map for all of these possible attributes in the existing pre-computed node map. We then select the best path over all, which appears to human players as the computer "making a choice". We may stir in some blind spots (redact parts of map so computer doesn't appear to be all knowing), and adverse choice modifiers that reflect most recent activity (if recently shot at, flag a 'fear' attribute of AI object, this creates a modifier that heightens chance to flee towards protected areas/team mates, or even perform random 'irrational' choices like including 'shoot team-mate' to the possible choice in node paths).
In networking you may see this as a network node map of a closed system. We need to choose efficient paths for data to travel from point A to point B, but data can and will appear at any given moment from any given node and need to travel to any other node. An analysis of the entire system can create a cost efficiency analysis in your network to show where weak or latent spots in your network may exist... data traveling from F to X has no efficient paths and takes 5 times as long as any other point to point, this is a place in our network where we may want to consider modification.
Is this homework? I hope it's not, and instead you're just using this as a starting point to learn more. Then again, go ahead, use my answers... I'd love to see if my casual pulling information out of my ass actually succeeds... are you willing to take that chance?
This post has been edited by lordofduct: 06 February 2012 - 09:51 AM
Was This Post Helpful?
0
Page 1 of 1
|
|
| 