Breadth First Search and the Pig Thief

Breadth First Search is a search algorithm that explores different options in the order in which they are encountered. As such, the algorithm explores the nodes along the frontier of the currently unexplored states, exploring all nodes/states at distance N before proceeding into those at distance N+1. For example, on a graph the algorithm first explores all neighboring nodes to a current node before exploring neighbors-of-neighbors.

"Sir! Farmer Bob has reported that his prize pig has been stolen!" cried the deputy as soon as Sheriff Gallard arrived. Sheriff Gallard sighed. This was not the way that she was hoping to spend the morning. She had a full quadruple-large, double-bold coffee from Zed's coffee shop, and she had been hoping to finish at least a few sips before the first emergency.

"Are you sure that it is not a dragon attack?" the sheriff asked. Dragons were not her responsibility, so it was better to rule them out at the beginning. No use in walking all the way out to Bob's Farm if it was an obvious dragon attack.

"No sir. Farmer Bob saw human footprints leading away from the barn." answered the deputy.

"Alright. Let's see what we have got." replied the sheriff.

Twenty minutes later, Sheriff Gallard arrived at Bob's farm. The barn door stood open and there were two sets of tracks outside, one human and one pig. It was an obvious pig theft. The best option now was to search for the pig and hope they could catch the thief quickly. So much for enjoying her morning coffee.

Unfortunately, the tracks disappeared shortly before the first fork in the path. Sheriff Gallard pulled out her pad of paper, and she wrote the word "Farm" at the top. Then she walked to the first intersection. She looked down both paths, and had a brief internal debate. Which direction did the thief go? Both paths looked equally likely.

"Let's start this way." she finally declared, pointing to the left path.

As she spoke, she crossed off the word "farm" and wrote "Farm-Left-Path" and "Farm-Right-Path" under it. The deputy and farmer looked on with curiosity.

After 100 meters, the three of them reached another fork in the road. There was a sign saying: "Fulton Crossing." There was no sign of the pig or the thief. Sheriff Gallard, pulled out her note pad again. She crossed off the phrase "Farm-Left-Path" and wrote down "Fulton-Crossing-Left-Path" and "Fulton-Crossing-Right-Path" at the bottom of the list. Her list now had three uncrossed items: "Farm-Right-Path", "Fulton-Crossing-Left-Path", and "Fulton-Crossing-Right-Path".

"Let's go back." she declared.

The deputy and farmer were surprised.

"But, my pig." protested the farmer.

"Don't worry. We will find your pig." the sheriff assured him. "But, now we need to try the Farm-Right-Path."

So the three of them backtracked to the first split in the path and tried the other option. Once again, they soon reached another split. Sheriff Gallard crossed "Farm-Right-Path" off her list and wrote the two newly found options under it. Then, she insisted on going back to Fulton's crossing and trying the left path from there. Although they were starting to get frustrated, neither of her companions objected.

Unfortunately, they still did not find the pig. After taking the left path out of Fulton's crossing, they came to yet another split. Sheriff Gallard again updated her list and insisted on going back to the Fulton's Crossing Right Path.

"But, why?" asked the farmer.

"Because it is at the top of my list." answered the sheriff. She was beginning to feel the lack of coffee acutely. Usually, she would be on her third cup by this time in the morning.

"But, we are already here. Why do we keep backtracking?" pressed the farmer. The deputy nodded in agreement, but was wise enough not to say anything.

"Because we are doing a breadth first search." answered the sheriff. The baffled looks of her two companions told her that they did not at all follow what she was saying.

"A breadth first search expands out the search along the frontier of what has already been explored. You basically, start by exploring all paths of length 1. Then you explore all paths of length 2. And, so forth. You keep a queue of all the places you have not explored yet and take the first one off the queue." explained the sheriff. "I am using this list as my queue. This list has all the options that we have not tried yet. We always explore whatever option is at the top of the list. And, Fulton's Crossing Right Path is the next place to explore."

"But why?" asked the farmer again.

The sheriff glanced quickly at the farmer. There was no tactful way to put this.

"Because, you have the world's laziest pigs." she answered.

"What?" asked Farmer Bob.

"What does that have to do with finding the thief?" asked the deputy.

"You see… his pigs walk incredibly slowly. Really, it is almost unbelievable. Have you ever seen an animal move as slowly? Sometimes I have a hard time believing that they are moving at all. They are like giant pig-turtles." The sheriff paused for a moment as she thought about the pigs. Quickly she snapped out of it. "Anyway, the thief cannot move that fast. I am using breadth first search to cover the shortest paths first. In this particular instance, I think it will lead us to the pig-napper quickly."

Both the farmer and the deputy stared at her in shock. However, neither could argue with the logic.

So, the three of them continued using this approach to search for the thief. Each time they reached a new branch in the road, the sheriff would update her list with the new options. Then she would pick the top item off the list and they would investigate that path. The result was a thorough, organized search.

They caught up with the thief a few list entries and about an hour later. The pig thief had made it down exactly 3 forks in the road during the 5 hour escape attempt. When they found him, he was pulling on the pig's collar and screaming at it to move. The pig was ignoring him and eating some grass. Occasionally, it would even snort disdainfully in response. But, mostly, it just refused to move.

Sheriff Gallard smiled. Her intuition about the first split had been wrong. The thief had taken the right path out of the farm. If she had kept following a single path deep into the search, she would not have caught up with the thief. She would have probably ended up in Old Stanton before turning back. Breadth first search had worked again.

------------------------------

Side note: Unlike the sheriff, computers do not need to physically backtrack during a search. Thus they do not have the same overhead as we saw in the search for the pig thief. Instead computers can often keep a reference to the next state and jump directly to exploring that state. As an example, consider searching for useful information off a particular webpage. Breadth first search is the equivalent of opening the page's links in new tabs and then exploring those tabs one by one (possibly opening even more tabs).