Это не совсем новость, но я думаю, что это весело и заслуживает того, чтобы быть более известным. Это проблема робота-панды, иначе известная как проблема обрезки бамбукового сада (BGT). Что в нем особенного, так это то, что его легко сформулировать и понять, и он очень доступен, независимо от того, являетесь ли вы любителем или серьезным компьютерным ученым.
Проблема, как говорится в недавней статье, заключается в следующем:
-Вы только что купили дом у озера. Бамбуковый сад растет за пределами дома и мешает прекрасному виду на озеро. Чтобы решить эту проблему, вы также купили робота-садовника панды, который один раз в день может мгновенно обрезать один бамбук. Вы уже измерили скорость роста каждого бамбука в саду, и теперь вам предстоит запрограммировать садовника с подходящим графиком обрезки бамбука, чтобы сохранить вид как можно более четким"
Ну, ваша первая мысль могла бы быть какой бесполезной роботизированной пандой, чтобы иметь возможность резать только один бамбук в день - это, конечно, был первый комментарий Гарри Фэрхеда, но тогда он наш IoT, аппаратный и робототехнический парень! Попробуйте объяснить практичному человеку, что чистые алгоритмы стоит изучать.
Звучит ли это более впечатляюще, выраженное формально?
В саду есть n бамбуков b1,..., БН, где бамбук
bi имеет известную суточную скорость роста hi>0, при h1≥...≥hn
и ∑ hi = 1. Первоначально высота каждого бамбука равна 0, и в конце каждого дня робот-садовник может обрезать не более одного бамбука, чтобы мгновенно сбросить его высоту до нуля. Высота бамбука bi в конце дня d≥1 и до того, как садовник решит, какой бамбук обрезать, равна (d−d')hi, где d '< d-последний день, предшествующий d, в который был обрезан bi (если bi никогда не обрезался до дня d, то d'= 0).
Задача состоит в том, чтобы построить алгоритм резки, который держит самый высокий бамбук как можно короче.Эта высота называется период изготовления. Обратите внимание, что общая скорость роста сада равна 1, и это означает, что макеспан должен быть по крайней мере 1 - Можете ли вы это доказать? Более того, есть простые случаи, когда он может быть сколь угодно близок к 2-му-какие случаи?
- После этих предварительных наблюдений мы можем начать изобретать алгоритмы для получения оптимальных макспанов. Вот тут-то все и становится интересным:
- Два натуральных стратегии сокращения-Max и уменьшить-быстрый(х).
- Уменьшить-максимум отделкой высокого бамбука в день, в то время как снижение-быстрый(х) отделка быстрорастущий бамбук из
- что выше, чем X. Известно, что сокращения-Max и уменьшить-быстрый(х) достигает в период изготовления в o(logn) и 4 для лучший выбор х= 2, соответственно.
- Далее в статье доказываются некоторые новые верхние границы для обоих алгоритмов-прочитайте их, чтобы узнать. Затем он переходит к рассмотрению временных и пространственных требований алгоритмов.
- Это действительно хорошая проблема информатики, которая интересна сама по себе и является отличным примером для внедрения CS-мышления. Возможно, он даже скрывает идею игры в своей работе-злые панды? Дайте мне знать, если вы его напишете.
- Если вы хотите увидеть интерактивную симуляцию, то посетите: обрезка бамбукового сада