Greedy Best First Search Algorithm
Greedy Best First Search Algorithm, how to compute the length of its traverse?
I have this problem that I am working on that has to do with the greedy best first search algorithm. However I am bit stuck on computing the length of the traverse when it comes to points (x, y). For example lets say I have these points: (0, 1), (0, 2), (1, 2), (1, 3). So what I did is draw out a diagram on the x, y plane.
Now knowing the GBF algorithm, it goes to check the closet node and so in this case the transverse would look like so: (0, 1)->(0, 2)->(1, 2)->(1, 3). So now in order to compute the length of the points connections done by the GBF, do I need to basically add up the path, which in this case would be three or compute the distance between the points? Right now I am trying to grasp this problem before I go ahead and try to implement it. Any clarifications would be helpful.
I have this problem that I am working on that has to do with the greedy best first search algorithm. However I am bit stuck on computing the length of the traverse when it comes to points (x, y). For example lets say I have these points: (0, 1), (0, 2), (1, 2), (1, 3). So what I did is draw out a diagram on the x, y plane.
Now knowing the GBF algorithm, it goes to check the closet node and so in this case the transverse would look like so: (0, 1)->(0, 2)->(1, 2)->(1, 3). So now in order to compute the length of the points connections done by the GBF, do I need to basically add up the path, which in this case would be three or compute the distance between the points? Right now I am trying to grasp this problem before I go ahead and try to implement it. Any clarifications would be helpful.
typical implementations would populate another data structure with three pieces of data: point 1, point 2, and the "cost" (here you seem to want the linear distance as the cost and yes, you will need to compute that for your version).
then you can use that list by sorting on the cost field, and choosing the cheapest points off the top of that via the algorithm from there. If I recall you add the cheapest, then look at the next to see if those points are already covered by what you have so far, if not add, if so, skip, ... until path is complete.
then you can use that list by sorting on the cost field, and choosing the cheapest points off the top of that via the algorithm from there. If I recall you add the cheapest, then look at the next to see if those points are already covered by what you have so far, if not add, if so, skip, ... until path is complete.
Last edited on
Ooohhhhh I get it now. So basically I compute the distance between each points(so like the distance between (0,1) and (0,2) etc.), which will give me the value that will decide on which way the greedy algorithm will head to and add them if not already added. But I have another dumb question, do I also compute the distance between (0,1) and (1,2)?, since based on the value of that distance, then it will check which one has the largest value between the value of (0,1)&(0,2) or (0,1)&(1,2) and then head down that path.
It depends on your problem statement. A "fully connected" graph needs the point pairs and costs for every combination of points. Other graphs do not have connections between all points, for example a guy trying to find his cheapest way home using available plane tickets from city to city (maybe you just can't fly from atlanta to mexico city today).
your cost function also depends; in the traveller scenario you want the least expensive tickets while in your scenario maybe you want to cover the most distance each hop. It depends on what you are doing.
I am not an expert on graph stuff... I did this once in excel (its a one line formula, lol) and again later because I thought I had a better method (Run the standard greedy from each vertex instead of just one, and use the cheapest of those) which is an expensive way to get a slightly better (but not optimal) result.
your cost function also depends; in the traveller scenario you want the least expensive tickets while in your scenario maybe you want to cover the most distance each hop. It depends on what you are doing.
I am not an expert on graph stuff... I did this once in excel (its a one line formula, lol) and again later because I thought I had a better method (Run the standard greedy from each vertex instead of just one, and use the cheapest of those) which is an expensive way to get a slightly better (but not optimal) result.
Last edited on
Oh ok, Its based of the TSP so I will follow that method. Thank you for your help!
Topic archived. No new replies allowed.