wtorek, 26 października 2010

Shortest Path Search - geometrical approach

I was thinking about slightly more heuristic approximation of shortest path choice instead of numerical representation of our path choices.
Dijkstry's algorithm (among others) provides formal solution to the problem, but is it representative for actual choices of agents in the network (us) ? I don't think so.

I'm not saying I've found anything extraordinary, but I wanted to investigate if following hypothesis is true:
Shortest path from A to B is the path of which sum of areas (integral) between direct line from A to B is smallest.
In fig.1 shortest path from A to B is via [X1,X2,X3] because the distance (sum of areas ~ integral) between direct line from A to B and the path [A,X1,X2,X3,B] is smallest. (there's no direct link from A to B!)


It seemed reasonable - I think my brain works more that way, than numerically optimizing. 
So there are some effects in matlab:
  1. I've generated random network of 100 nodes
  2. I've drawn direct line AB from A to B
  3. I've calculated areas between AB and links
  4. I've chosen the smallest sum of areas for the path
Those are the results:
Green lines are network links.
Red line is actual shortest path search result,
blue line is my "smallest-area" result.
They are overlapped for most of the path (i.e. only red line is vissible)

Results are similar, but not exactly the same. The problem of this approach is now rather obvious:
Contr-example:
Path from A to B:
shortest path is via node C - path [ACB], but the smallest area is  obtained for path [ADCB]. So the hypothesis is failed.

I'll try to think about the modifications so that the initial assumptions are held and results are correct....

Brak komentarzy:

Prześlij komentarz