Breadth first search Puns

I was doing more leetcode when I realized I was rusty on BFS, so I set out to implement it in Racket. Here is my implementation. It takes an adjacency list (a list where each element is a list of the connected nodes for that node index) and the start/source node as input and returns the predecessor array. The queue is something I implemented based on Okasaki's Purely Functional Data Structures (minus the laziness, I'm still figuring out laziness in Racket by reading through code in the pfds collection).

(define (breadth-first-search g s)
  (let* ([n (length g)]
         [gvec (list->vector g)]
         [color (make-vector n 0)]
         [d (make-vector n -1)]
         [p (make-vector n -1)]
         [q (make-queue)])
    (vector-set! color s 1)
    (vector-set! d s 0)
    (queue-push q s)
    (do ([u (queue-head q) (queue-head q)])
        ((queue-empty? q)
         p)
      (for-each (lambda (v)
                  (when (zero? (vector-ref color v))
                    (vector-set! color v 1)
                    (vector-set! d v (add1 (vector-ref d u)))
                    (vector-set! p v u)
                    (queue-push q v)))
                (vector-ref gvec u))
      (queue-pop q)
      (vector-set! color u 2))))

This code works, but it feels very imperative to me. This is partly because of the vectors that I used since I wanted O(1) access to vector elements. The do also feels weird, though I have don't know of a better way to iterate when the iteration is not over a sequence. Is there a way to convert something like a queue into a sequence? It feels like that might be connected to laziness. Lastly, I mentioned the pfds collection above, is there something that prevents me from using typed Racket in a normal Racket program, i.e. are types an all-or-none proposition?

My data structures teacher is having us do a project where a knight is randomly generated on a chess board and has to find the shortest path to a space the user chooses. He has mentioned that we should be using Breadth First Search recursion but hasn't explained what it is or how to implement. Would love some help and suggestions.

Hi,

I have started implementing the Nqueens problem using BFS but my code below is only allowing me to find solutions upto N=16 which takes almost 8 hours. After that, my computer rans our of memory and kills the script. How can I improve this? I want to at least solve it for N=20 in a decent time. Also, it has to be by using BFS because it's an assignment :) Just a tip to the right direction would help a lot. Thank you!

from collections import deque

def valid(state, new_queen):
    for col, row in enumerate(state):
          if abs(row - new_queen) == abs(col - len(state)) or\
          new_queen in state:
              return False        
    return True

size = 8
queue = deque((queen_pos,) for queen_pos in range(size))
while queue:
    board_state = queue.popleft()
    if len(board_state) == size:
        print('solution:', board_state)
        continue
    for queen_pos in range(size):
        if not valid(board_state, queen_pos):
            continue
        next_state = board_state + (queen_pos,)
        queue.append(next_state)

The blog post in question

I’m relatively new to procedural generation. Currently, all I have created are some voronoi cells in Python. I’ve spent the past couple days going over the posts and concepts from this blog (among many others). I understand most of the general concepts, but some things just don’t make sense to me no matter how much research I do. How do I actually apply noise to voronoi cells? What’s the point of line rasterization? How does using BFS factor into all of this?

I realize what I’m asking for is rather broad, but I’d appreciate answers to any one of these questions.

Hello!

I'm working through learntla.com, and whilst running the tower of hanoi example, I came across a non-minimal trace that has 9 states instead of 8:

State 2 is

<<2, 3>>, <<1>>, <<>>

and state 3 is

<<2, 3>>, <<>>, <<1>>

But going from state 1 to state 3 directly is allowed by the spec.

This behaviour is reproducible (happened twice over 10 runs of the same spec, the other runs have a minimal trace.

Model checking result window indicates "TLC mode: Breadth-first search".

What am I missing? Is TLC really performing a BFS? Is it just reporting whatever result from the first solver thread to complete?

Many thanks

Hey fellow comscis,

for an AI-course I just started to recap searching-strategies. While doing so, I stumbled upon this weird problem, that seems clear to everyone but me. Maybe someone can point out, where I am wrong:

Depth-First-Search does not have the Completness-property. Completness meaning in practical terms, being able to find all possible solutions that can be found. The reason for this is that DFS can get "lost", when the currently selected path is infinite.

Now, Breadth-First-Search should have the Completness-property, because it will not get lost in an path of infinite length, but (and this is where I am not able to follow anymore) what about a node that has an infinite number of child-nodes? Imagine the starting node having infinite children and all solutions are in depth 2. BFS will never find any solution, because it is stuck searching depth 1.

What am I missing?

https://reddit.com/link/9ydxkf/video/1bnzdbnl58z11/player

Under the condition that at each step, the order that the vertices are visited, and the source node are arbitrary, and the graph is undirected and connected? I would think this would trivially be true, except for the fact that it is not true for Depth first search, as any spanning tree that isn't a path, cannot be produced by depth first search.

Clarification: In these circumstances if vertex has 3 edges, bfs can produce 3 distinct trees from that single starting vertex. So there are more than n distinct bfs trees for a given graph (when a node has multiple edges you can pick the edge that bfs will visit first).

Edit: If you believe this is not the case, please provide a counter example of a minimum spanning tree that can not be produced by BFS.

Hi r/gamedev,

I've been working on new interactive version of my Amit's Thoughts on Pathfinding pages. It's too big to tackle all at once (rough plan), so I've been working on parts of it at a time in 1-2 month chunks.

Introduction to A* is my new version of this page.

The TL;DR is that of graph search algorithms, Breadth First Search is the simple one to start with and the easiest to understand. When you add early exit, weighted edges, and heuristic guidance, you get A*. But each of these additions are simple to understand on their own, and sometimes you'll want to use a type of graph search other than A*.

Things I wanted to do differently:

• I made all the diagrams are interactive (of course)
• I mentioned non-grids a little more (still not enough)
• I used contour lines to compare the algorithms (not sure if this will make sense—feedback please)
• I showed working Python code for each of the algorithms (I have mixed feelings about this, as I think the longevity of my site is in part related to being about algorithms and not about code)
• I added an implementation page that includes the helper functions and classes needed for the search algorithms, both Python and C++ versions
• I gave some guidance on which of these graph search algorithms to use

I have a long way to go to update all of my pathfinding pages, so I'm publishing the pages as I go instead of waiting until the end. I'd love to get feedback on the new version, especially for the contour line visualization and the inclusion of source code. Thanks!

So I was reading about breadth first search and stumble accros this line: It computes the distance (smallest number of edges) from s to each reachable vertex.

What does this suppose to mean? If s is root node and lets say a, b and c are children of g, then shouldnt the distance to all reachable vertex be same. Because in BFS there are no weighted graphs.

Sorry for asking this dumb question and thank you for your help

Full paragraph: Given a graph G D .V;E/ and a distinguished source vertex s, breadth-first search systematically explores the edges of G to “discover” every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a “breadth-first tree” with root s that contains all reachable vertices. For any vertex  reachable from s, the simple path in the breadth-first tree from s to  corresponds to a “shortest path” from s to  in G, that is, a path containing the smallest number of edges. The algorithm works on both directed and undirected graphs.

"Come to the good side!" -Gabby Pascuzzi

Wow. Just wow. Another fantastic episode in a fantastic season. David vs. Goliath is well on its way to becoming the best season of all time. Don't @ me. But is it the best gameplay of all time? Let's take a look...

Who Played Well:

I'll start off by giving props to the Davids as a whole. Davie, Nick, Christian, Carl, and Gabby all worked together to form an excellent plan that successfully took down Dan. It was a team effort and they all did a great job. Christian is also in the best position movie forward as he has an Idol. The down-side is all of the Davids know about said Idol, but at least he has one.

Nick picked the right time to play his Vote Steal. He had no way of knowing if Alec, Kara, and Alison were going to vote with them and I would bet Alec and Kara only switched their votes once Nick played the steal. Definitely the right call.

Finally, we have Carl who played the most important role in taking down Dan. I have to admit, I did not expect Carl to play the Idol Nullifier correctly, but he did it. He had the finishing blow to Dan's game. It was the perfect use of the Nullifier and looks great in front of the jury.

Who Sucked:

Let me start off by saying they Goliaths weren't wrong in their idea. Mike, Alec, Alison, Kara, Dan, and Angelina were all right in going after Christian. They have to get the Davids out of this game if they want to win. Goliath-strong is the right move, but they screwed up by not making the Davids comfortable. They know there are advantages and Idols in this game. If they had lured the Davids into a false sense of security, maybe none of the them would have played anything and Christian would have gone home. Having a powwow on the beach where everyone could see them was a bad call and drove the Davids to their awesome move. Right idea, wrong execution on the Goliaths part.

Kara was dead-dog-wrong for wanting to get rid of Dan here. She should realize that she has no chance of winning against the Davids, but she might stand a chance against someone like Dan. She was fortunate to have Alec and Alison change their minds, but all of this makes her look bad in front of the Davids and Dan.

Alec may have won Immunity, but I think he had a net bad night, along with Kara and Alison. They basically gave the Davids false hope before going back to Goliath-strong. That won't win them any favor with the Davids. Now, they did switch their votes (besides Alis

One of our interview questions is a graph traversal problem where I've had a couple of people do what I'm calling "Layer at a time" breadth first search, which is basically:

def layer_at_a_time_bfs(root):
    visited = set()
    visited.add(root)
    queue = [root]

    while queue:
        next_layer = []
        for node in queue:
            for related in node.relateds:
                if related not in visited:
                    visited.add(related)
                    doStuff(related)
                    next_layer.append(related)
        queue = next_layer

i.e. process an entire layer, assign it to the queue, then iterate.

I hadn't seen this definition of BFS before, is this taught at some specific college or in some book?