About path finding(in Graphs)..

This is a discussion on About path finding(in Graphs).. within the General Discussions forums, part of the Community Boards category; Originally Posted by manasij7479 :Too much Calculation: Though this can become ineffective if I try to manage subnets recursively.... I ...

  1. #16
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,538
    Quote Originally Posted by manasij7479 View Post
    :Too much Calculation:
    Though this can become ineffective if I try to manage subnets recursively....
    I would think crunching numbers are faster than memory accesses. Anyway, don't throw the idea out the window before you actually see how it performs in real code.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  2. #17
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Elysia View Post
    I would think crunching numbers are faster than memory accesses. Anyway, don't throw the idea out the window before you actually see how it performs in real code.
    Yes.. coupled with any algorithm, this gives a good advantage when I just want a good path..not analyze all the other possible ways to find the minimum 'tentative distance'...(And the first will typically be the one following the 'closest to straight' path )
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  3. #18
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    I don't see much application for A* here, but if you're interested, take a look at A* search algorithm - Wikipedia, the free encyclopedia, particularly the Weighted A* section. That allows you to pick a heuristic that sometimes overestimates by a bit, resulting in faster but non-optimal paths. This shouldn't be a problem though, since you only need good enough. Your problem will be with devising a reasonable heuristic.

    The IP address "distance" will not work as a heuristic for A*. For A* to be optimal, the heuristic must never overestimate the cost from any node to the goal. For spatial stuff, straight line is great, since it's the shortest possible distance between any two nodes. To do that, we require some sort of Cartesian coordinates for every node in the graph. We're looking the path with the shortest time, and there is no correlation between IP addresses and the latency between them. You would need something that guessed the fastest possible travel time between any node and the goal. That would have to account for the number of hops along the way, but the individual nodes don't know how far they are from the goal, so devising a valid heuristic is not really possible. We can't even make a reasonable guess as to how fast we can get from a node to the goal.

    A little bit of Googling for "a algorithm for fastest times" (Google discards the *) turned up this paper, which might be a useful, if a little bit dry, read. It works with A*, so might have some useful heuristics to investigate.

    EDIT: I judged that paper by the title and scanning the abstract, no idea how good it really is.
    Last edited by anduril462; 11-09-2011 at 03:56 PM.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding the path of a file
    By caduardo21 in forum C Programming
    Replies: 8
    Last Post: 08-09-2005, 11:00 AM
  2. Finding the path to your executable
    By jmd15 in forum Windows Programming
    Replies: 3
    Last Post: 07-19-2005, 09:32 AM
  3. path finding
    By X PaYnE X in forum Game Programming
    Replies: 27
    Last Post: 05-30-2005, 01:38 AM
  4. Finding current path
    By eam in forum Windows Programming
    Replies: 9
    Last Post: 12-19-2003, 09:15 PM
  5. Finding the path of an .exe file
    By Gonzo in forum C Programming
    Replies: 1
    Last Post: 09-15-2003, 05:19 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21