Thread: Does anyone feel like programming?

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    15

    Does anyone feel like programming?

    I've been doing an extensive math assignment but i'm no where near complete. There's a question where we need to develop an algorithm (which isn't even for marks), the analysis and discussion of it are only relevant and worth marks. It's backtracking to find an optimal solution. I'm also under the assumption that this isn't too difficult, or else I wouldn't be asking, i'm just realling pressed for time. Thanks if anybody knows how to write it, or has
    already done somehting like this.

    problem:
    A undirected graph with non-negatively weighted edges. Solve the shortest path from a starting node, to a finishing node. Use backtracking to solve the shortest path (and arrive at an optimal solution).

    Code:
                                                                        1                           (stating node = 0, ending = 5)
                                                                     /  |  \
                                                                    /   |   \                                                               
                                                                    0---2---3
                                                                    |   \   /  
                                                                    4     5
    
    Note: any numbers can be used on the above graph, but one example is as good as the next.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Don't know your class, but I'd be willing to bet up to a quarter that the reason the algorithm isn't worth any marks is because it's printed in your textbook in a shaded box labeled algorithm 18.4 or the like.

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    111
    Can you use a common algorythm for this ? i suggest you use DSS or Dijkstra's algorithm.
    Last edited by jabka; 06-18-2008 at 01:59 PM.
    why Gaos didn't had a wife ?
    http://bsh83.blogspot.com

  4. #4
    Registered User
    Join Date
    Jun 2008
    Posts
    15
    Ya that could work, i'll probably have to tone it down a bit because it's overly complicated and large. Thanks

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    111
    You can optimise this algorythems ?

    please exaplain how .
    why Gaos didn't had a wife ?
    http://bsh83.blogspot.com

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    This is a simple least cost algorithm like A* (A star). You may want to google A* and see if you can use it. From what it sounds like this is exactly what you need.

  7. #7
    ---
    Join Date
    May 2004
    Posts
    1,379
    It's a matter of checking how many paths current node has and check to see which path is the shortest distance to the end node, go back, take that path, check the paths on the new node and so on..

  8. #8
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Well, it is fairly simple. You have no choice but to search all possible paths. Now you have some choices how to search. But there is no optimization there, since your choice effectiveness would depend on the graph.

    Now, to find the optimal algorithm you have to first declare what you consider the "cost" of the algorithm. Since it is a math project and not a computer science project you would assume that the cost is only moving from one node to the other. Not memory used, instructions used and whatever else.

    In this case again you can't have an optimal solution than searching the whole graph. What you can do though is ASSUME that the graph is completely random.
    Thus, every graph of N nodes has the same possibility to exist. Then find what is the most possible biggest route. Lets say it is N/2. Your algorithm would check first paths with length N/2. And you could claim you have the optimal solution. If I was a math professor that is what I would take as optimal, since no other optimization can be made.

    Of course it is complicated to find possibilities for N nodes

    For 3 nodes for example:
    --3 connections
    1: 100%
    --2 connections
    1: 50%
    2: 50%
    --Overall
    possible max length == 1 75%
    possible max length == 2 25%
    you choose 1 (which is useless of course, but just an example)
    Last edited by C_ntua; 06-18-2008 at 07:14 PM.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It's not true that you have to search all possible paths.
    If you have found a solution with a total cost of n and all other partial paths have a cost greater than n, then you can stop immediately.
    The "non-negatively weighted edges" part allows you to make that optimisation.

    You can't really take advantage of the A* algorithm here because that involves having an estimate of the cost remaining to reach the goal, as well as the total cost travelled along the edges so far. There probably isn't any good way to estimate the remaining cost.
    However you can implement a greedy algorithm that tries the shortest-path-so-far first, which is like A* but where the estimated remaining cost is always zero.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. When you don't feel like reading\programming..
    By Brain Cell in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 03-03-2005, 06:32 PM
  2. Feel Like An Idiot
    By golfinguy4 in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 07-04-2003, 12:45 PM
  3. Feel Guilty..
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 01-22-2003, 03:00 PM
  4. feel free to laugh at my code!
    By JimJamJovi in forum C Programming
    Replies: 4
    Last Post: 01-11-2002, 04:40 AM