Home | Community | Message Board

Original Seeds Store
This site includes paid links. Please support our sponsors.


Welcome to the Shroomery Message Board! You are experiencing a small sample of what the site has to offer. Please login or register to post messages and view our exclusive members-only content. You'll gain access to additional forums, file attachments, board customizations, encrypted private messages, and much more!

Kraken Kratom Shop: Red Vein Kratom

Jump to first unread post Pages: 1
Offlinekotik
fuckingsuperhero
 User Gallery
Folding@home Statistics
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. :grin:


--------------------
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.


Extras: Filter Print Post Top
Offlinesupra
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)


Extras: Filter Print Post Top
OfflineSeussA
Error: divide byzero


Folding@home Statistics
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.


Extras: Filter Print Post Top
Offlinekotik
fuckingsuperhero
 User Gallery
Folding@home Statistics
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.




:thumbup:  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)


Extras: Filter Print Post Top
OfflineSeussA
Error: divide byzero


Folding@home Statistics
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.


Extras: Filter Print Post Top
Jump to top Pages: 1

Kraken Kratom Shop: Red Vein Kratom


Similar ThreadsPosterViewsRepliesLast post
* Booth's Algorithm for hardware multiplication? Kaleidoscope 1,275 3 03/06/06 04:34 AM
by Seuss
* Court Rules on Bus Searches No bus rides 4 us ... Lana 1,068 1 06/17/02 11:55 AM
by luvdemshrooms
* cool web search NewfoundFreedom 1,547 18 09/20/04 11:14 PM
by ChingChong
* Sound Familiar? funkymonk 507 6 12/22/04 07:33 PM
by Krishna
* Deleting Search History DrinkSolaritea 1,752 4 03/08/02 06:02 PM
by Unknown
* might be getting searched! rain_angel 2,036 19 08/04/02 04:41 AM
by GabbaDj
* Deleting Google Search Entries gregorio 912 10 02/04/06 09:35 PM
by tak
* all my url links are hijacked by a search engine psilocyben 906 5 06/29/05 05:13 PM
by CptnGarden

Extra information
You cannot start new topics / You cannot reply to topics
HTML is disabled / BBCode is enabled
Moderator: trendal, automan, Northerner
639 topic views. 0 members, 1 guests and 3 web crawlers are browsing this forum.
[ Show Images Only | Sort by Score | Print Topic ]
Search this thread:

Copyright 1997-2024 Mind Media. Some rights reserved.

Generated in 0.027 seconds spending 0.007 seconds on 14 queries.