|
kotik
fuckingsuperhero


Registered: 06/29/04
Posts: 3,531
Last seen: 4 years, 24 days
|
anyone familiar with BFS/DFS/A* Search Algorithms?
#7498741 - 10/08/07 06:08 PM (16 years, 3 months ago) |
|
|
I have been working on a program lately, and tackling more than a few concepts that I haven't used before. There are some talented coders on here, so I figured I would give it a shot.
There are around 1000 lines total, but this could be any number at all. Essentially, the XML file is formatted into what I guess would be a double-linked list, or better yet a graph, since there can be multiple children in each node.
I was trying to figure out a path finding solution, for the shortest possible route between two specific nodes. I managed to do this with a basic BFS algorithm, and instead of an A* method, I just keep track of the solution as it is created, step by step.
I'm not really having problems - as I successfully managed to get this to work consistently, but it is still very new to me, and i could use some suggestions.
-------------------- No statements made in any post or message by myself should be construed to mean that I am now, or have ever been, participating in or considering participation in any activities in violation of any local, state, or federal laws. All posts are works of fiction.
|
supra
computerEnthusiast
Registered: 10/26/03
Posts: 6,446
Loc: TEXAS
Last seen: 12 years, 9 months
|
Re: anyone familiar with BFS/DFS/A* Search Algorithms? [Re: kotik]
#7499766 - 10/08/07 10:21 PM (16 years, 3 months ago) |
|
|
what language are you coding in? PROLOG? I wrote an A* search for city traveling as the first assignment for my AI class last year, but i guess im not understanding the problem well enough to help you?
the way mine worked was i had a vector that i wrote my own bubblesort for, and pushed back the distance traveled+distance to next town, then sort, then travel to the town that makes the shortest total distance. It worked well, except their was one situation where it would get stuck going back and forth between the same towns, but I had to hard code that transition in...
hope some of that may help...
as far as the breadth first or depth first, you should see how many daughters each level has, if each node has many daughters, then do breadth first, if it has fewer daughters and isn't too deep of a list do depth first. These are the kind of situations that prolog would help solve for you, showing the best search method for your specific problem.
peace
Edited by supra (10/08/07 10:23 PM)
|
Seuss
Error: divide byzero



Registered: 04/27/01
Posts: 23,480
Loc: Caribbean
Last seen: 2 months, 20 days
|
Re: anyone familiar with BFS/DFS/A* Search Algorithms? [Re: kotik]
#7500500 - 10/09/07 05:25 AM (16 years, 3 months ago) |
|
|
> I managed to do this with a basic BFS algorithm, and instead of an A* method, I just keep track of the solution as it is created, step by step.
I've used the exact same solution in the past for finding a path, though you still have to keep track of what nodes you have visited. The path found might not be the shortest path, however. Do a search for "all pairs shortest path" and you will find tons of info.
-------------------- Just another spore in the wind.
|
kotik
fuckingsuperhero


Registered: 06/29/04
Posts: 3,531
Last seen: 4 years, 24 days
|
Re: anyone familiar with BFS/DFS/A* Search Algorithms? [Re: Seuss]
#7500518 - 10/09/07 05:35 AM (16 years, 3 months ago) |
|
|
Quote:
Seuss said: Do a search for "all pairs shortest path" and you will find tons of info.
thanks. the solution I've managed to work out seems to pick the shortest path everytime. I am still testing it, but it seems to be holding up well. I'll post a code snippet once it's cleaner.
the thing is, im still trying to grasp the concept, so even if it IS working.. im not sure how! heh...
Quote:
supra said: what language are you coding in?
ActionScript.
-------------------- No statements made in any post or message by myself should be construed to mean that I am now, or have ever been, participating in or considering participation in any activities in violation of any local, state, or federal laws. All posts are works of fiction.
Edited by kotik (10/09/07 05:36 AM)
|
Seuss
Error: divide byzero



Registered: 04/27/01
Posts: 23,480
Loc: Caribbean
Last seen: 2 months, 20 days
|
Re: anyone familiar with BFS/DFS/A* Search Algorithms? [Re: kotik]
#7502301 - 10/09/07 05:30 PM (16 years, 3 months ago) |
|
|
> the solution I've managed to work out seems to pick the shortest path everytime.
If you are using something like Dijkstra's (sp?) algorithm (assuming I am remembering correctly... it has been a long time since my data structures classes), then you will still be getting a shortest path. Keep the number of nodes small as the complexity of the problem can easily become O(N^4) depending upon the code.
-------------------- Just another spore in the wind.
|
|