Скачать или смотреть Bill Gates, Pancakes & Heuristics

Efficient algorithms for placing pancakes into an ordered stack are related to the maths problem of "prefix reversals". The video visualises the problem in both ways.

AI research uses the task because it's simple and the number of possible flips in each state keeps going up as you add more pancakes. Also, the gap heuristic is rather good.

The maths paper that Bill Gates wrote as a college student was on estimating the number of necessary flips. Maybe he could have gone on to a big future as a researcher...

0:00 Intro
0:11 Example with 3 pancakes & simple rules
0:28 Manhattan distance and "admissibility"
0:53 State space for 3 pancakes & the gap heuristic
1:19 Bill Gates' 1978 paper & the state space for 4 pancakes
1:47 The pancake problem as a benchmark

There's a Wikipedia page that focuses on the mathematics of the problem, and the lower bound for the number of flips needed for different sized stacks.
https://en.wikipedia.org/wiki/Pancake...

You can guarantee a solution in 2n-3 steps by repeatedly using one flip to take the largest pancake not yet sorted to the top, and then taking it down to its final position with one more flip. Gates found a better bound , and it stood for 30 years until it was improved... by researchers using a technique reliant on computers.

=====

Soundtrack: And They Lived Happily Ever After - Instrumental Version
Song by Ziv Grinberg
under license from artlist.io
https://artlist.io/song/63861/and-the...

Bill Gates photos:
https://commons.wikimedia.org/wiki/Fi...
Creative Commons 2.0

https://commons.wikimedia.org/wiki/Fi...
Albuquerque, New Mexico police department, Public domain, via Wikimedia Commons

Valenzano & Yang paper:
https://www.aaai.org/ocs/index.php/SO...

Wikipedia on Manhattan distance:
https://en.wikipedia.org/wiki/Taxicab...
https://commons.wikimedia.org/wiki/Fi...
Creative Commons Attribution-Share Alike 3.0 Unported

Outro background, and sound effects, from storyblocks.org

Reference on Manhattan design:
https://www.charlespetzold.com/etc/Av...

► Support the chanel
Like: Give a 👍 to this video (thanks!)
Subscribe: https://www.youtube.com/c/abitofintel...