Editing Talk:2407: Depth and Breadth

<!--Please sign your posts with ~~~~ and don't delete this text. New comments should be added at the bottom.-->
Soldier loves bread-first search for obvious reasons.[[Special:Contributions/162.158.49.50|162.158.49.50]] 10:53, 5 January 2021 (UTC)

where did the quality go [[Special:Contributions/172.69.34.24|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 [https://xkcd.com/2407/ 2407] looks much worse than the original, which you can find at [https://imgs.xkcd.com/comics/depth_and_breadth_2x.png https://imgs.xkcd.com/comics/depth_and_breadth_2x.png] I suggest we use the larger version for this comic. [[User:Alchemistmatt|Alchemistmatt]] ([[User talk:Alchemistmatt|talk]]) 20:18, 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.
[[Special:Contributions/162.158.111.161|162.158.111.161]] 20:17, 4 January 2021 (UTC)
: Randall has uploaded a new image: [https://imgs.xkcd.com/comics/depth_and_breadth.png], which I uploaded to explainxkcd. [[User:Natg19|Natg19]] ([[User talk: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. [[Special:Contributions/172.68.142.201|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. [[Special:Contributions/141.101.98.68|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. [[User:Quantum7|Quantum7]] ([[User talk: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". [[User:Rtanenbaum|Rtanenbaum]] ([[User talk:Rtanenbaum|talk]]) 22:32, 4 January 2021 (UTC)

After the bread-first search, the next logical variant is the breakfast search! [[User:PotatoGod|PotatoGod]] ([[User talk: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?  [[Special:Contributions/162.158.159.50|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. [[Special:Contributions/108.162.219.74|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 [[Special:Contributions/162.158.74.149|162.158.74.149]] 19:30, 6 January 2021 (UTC)
: This made me laugh! [[User:Quantum7|Quantum7]] ([[User talk: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. [[User:Quantum7|Quantum7]] ([[User talk:Quantum7|talk]]) 08:44, 8 January 2021 (UTC)

[[Special:Contributions/172.68.132.19|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 [[User:BlackHat|BlackHat]] is actually talking about breadth-first and not brebth-first. [[Special:Contributions/172.68.63.137|172.68.63.137]] 18:37, 11 January 2021 (UTC)

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