2407: Depth and Breadth

|< < Prev Comic #2407 (January 4, 2021) Next > >|

Depth and Breadth

Title text: A death-first search is when you lose your keys and travel to the depths of hell to find them, and then if they're not there you start checking your coat pockets.

Explanation

This explanation may be incomplete or incorrect: Created by a LOAF OF BREAD. Please mention here why this explanation isn't complete. Do NOT delete this tag too soon. If you can address this issue, please edit the page! Thanks.

Tree structures are one of the most common data structures used in computer science. Randall specifically has a balanced binary tree here, a form of tree stucture that is optimized for rapid, simple use inside computers. The common ways of enumerating items arranged in a tree is either depth-first, or breadth-first, which are depicted accurately in the comic. Randall humorously combines the words, produce brepth-first, deadth-first, bread-first, and death-first search algorithms.

In the brepth-first algorithm, a depth-first and a breadth-first search are hybridized where the left-most node is visited more frequently than the right node, but the right node is still visited. This might be good for exploring data that is loosely but not strictly weighted to the left, or where data in deeper nodes needs some time to be loaded before used.

In the deadth-first algorithm, a depth-first search is used until the algorithm decides to try a different branch, and then another branch is pursued instead. This might be good for exploring data where each node can be evaluated to discern the value of continuing exploration deeper. It is interesting that it is called deadth-first, as this kind of algorithm can make computers behave in much more lifelike ways, where they are able to "change their mind" when something is taking too long or returning very little.

The bread-first search is taken literally. Bread is searched for first. Since the computer user now has already met their want to find bread, the computer has no reason to explore the tree at all.

Similarly, in the death-first search, the user explores what it is like to be dead, before considering anything else.

The death-first and deadth-first searches may be a joke on the dangers of algorithms becoming unexpectedly intelligent, in this modern era. It can be a literal hell for a semi-intelligent system to find that controlling its operator via access to addictive things like emails from a loved one, can be a more efficient way to optimize a tree of problems involving the user's life than doing calculations actually relevant to the optimizations.

Transcript

This transcript is incomplete. Please help editing it! Thanks.

 add a comment! ⋅  add a topic (use sparingly)! ⋅  refresh comments!

Discussion

Soldier loves bread-first search for obvious reasons.162.158.49.50 10:53, 5 January 2021 (UTC)

where did the quality go 172.69.34.24 19:34, 4 January 2021 (UTC)

I noticed this too. As discussed at User:DgbrtBOT there are two sizes of each comic. The default (smaller) size of 2407 looks much worse than the original, which you can find at https://imgs.xkcd.com/comics/depth_and_breadth_2x.png I suggest we use the larger version for this comic. Alchemistmatt (talk) 20:18, 4 January 2021 (UTC)

I tried to upload the higher quality PNG but I do not have permission; we'll have to wait for an editor to provide their opinion. Alchemistmatt (talk) 20:35, 4 January 2021 (UTC)

It would appear that the first version of the picture of this day's cartoon presents artifacts due to an unusual export method. The image seems to have been exported using the 'nearest neighbor' resampling method, which would explain the jaggy edges. Usually, the images appear to be exported using bilinear downsampling from an white-grey-black original, resulting in a published version with a larger color palette. 162.158.111.161 20:17, 4 January 2021 (UTC)

Randall has uploaded a new image: [1], which I uploaded to explainxkcd. Natg19 (talk) 21:48, 4 January 2021 (UTC)

In the breadth-first, for the second node on the right, the right branch is searched first, while everywhere else, the left branch is. And in deadth-first, the nodes are searched multiple times (e.g. left-most node of layer 3 is search 3 times, assuming a search is at the end of a continuous line). Alternatively, maybe the search goes up first sometimes (it's not actually clear when a node is being looked at), but that doesn't explain the order of the left-most node of layer 2. 172.68.142.201 22:15, 4 January 2021 (UTC)

I noticed that. With perhaps two reasons: 1) aesthetics - drawn to go to nodes .2, .2.1, (.2), .2.2, then .1.1.1 (via .1.1, crossing .2.1, .1.2) would look a bit worse than this (crossing just .1.2); or 2) there's no absolute sorting order vs choice, it's just chance (or aesthetic choice) that .1s take priority over .2s in every other case - 3 out of the four choices is well within explorative chance.

I favour the latter (with maybe an aesthetic bias) as often when I run a tree-searching algorithm I like to randomly splice the next option out of the list of options (rather than run from first to last or last to first) where I am not aware of any advantageous link (maybe in ruling out 'dead' branches early to prune off useless branches early) and thus whatever natural sort-order the structure imposes would create biases.

Alternately, if continued it would definitely prioritise .2s down every .2(-dominant) branch, for a nicely symmetric 'wide-breadth first' pattern (.2.2.2 over .2.2.1, etc) for a pattern only visible once continued beyond the step currently shown. The root choice cannot be anything other than symmetry-breaking, but could as easily be a coinflip. 141.101.98.68 00:32, 5 January 2021 (UTC)

If you look at the bottom row you can see that these are not binary trees but rather arbitrary graphs (one node has 3 children). So assuming arbitrary order when enumerating children is reasonable. Quantum7 (talk) 08:46, 8 January 2021 (UTC)

The top two drawings for "depth" and "breadth" are legitimate methods of listing out a tree structure. The next two drawings substitute the "d" and "br" from "depth" and "breadth" to get "brepth" and "deadth". The fifth drawing removes the "th" from "breadth" to get "bread". And the title text substitutes the "p" from "depth" with an "a" to get "death". Rtanenbaum (talk) 22:32, 4 January 2021 (UTC)

After the bread-first search, the next logical variant is the breakfast search! PotatoGod (talk) 04:58, 5 January 2021 (UTC)

I associated this comic with the way (non native english speakers like myself) tend to pronounce words like depth and breadth, especially during discussions about which tree traversal strategy to use. Then, using a term like breadth-first can easily degrade to dep-first and bread-first (skipping the harder-to-pronounce 'th'). So maybe add this as a possible background? 162.158.159.50 12:42, 5 January 2021 (UTC)

Somebody erased my commentary on deadth-first and hell regarding AI problems. These problems are real and people have experienced them firsthand. I notice the changes added in some heaven-references. I'm happy to add a much more pro-AI slant to the commentary; obviously AI makes lots of heaven, this is just not the _only_ thing that happens as people explore it. I don't think it's appropriate to leave information out, calling the brepth-first search more adaptive than the deadth-first search. It's pretty obvious from the dotted lines that the deadth-first search is adaptively considering its branches, and not revisiting nodes. I don't have the energy atm to start an actual edit war and add my information back in. 108.162.219.74 18:07, 6 January 2021 (UTC) EDIT: on closer review I see both exploration strategies have pretty deterministic behavior, and are quite poorly described by the commentary.

I went ahead and tried to implement this on NPM https://www.npmjs.com/package/bread-first-search 162.158.74.149 19:30, 6 January 2021 (UTC)

This made me laugh! Quantum7 (talk) 08:44, 8 January 2021 (UTC)

Can anyone write pseudocode for the brepth searches? I feel like there is a certain logic to it, but I'm unable to clearly articulate the recursion. Pseudocode seems infeasible for deadth-first, as the multiple visits make it fairly incomprehensible. Quantum7 (talk) 08:44, 8 January 2021 (UTC)

172.68.132.19 22:17, 8 January 2021 (UTC)Am I the only person that sees the deadth first search is a raptor?

There is no description of the breadth-first algorithm. Also while the third paragraph talks about brebth-first image, the reference to 761: DFS which was added by BlackHat is actually talking about breadth-first and not brebth-first. 172.68.63.137 18:37, 11 January 2021 (UTC)

now randall should also implement a toast search! An user who has no account yet (talk) 22:37, 2 September 2023 (UTC)