Max Home IndustryНекоторые из наших новостей заслуживают второго шанса. Вот один из мая 2020 года, который соответствует нашим критериям «Слишком хорошо». На самом деле это не новость, но я думаю, что это весело и заслуживает более широкой известности. Это проблема робота-панды, также известная как проблема обрезки бамбукового сада (BGT).
Что в нем особенного, так это то, что его легко сформулировать и понять, и он очень доступен, независимо от того, являетесь ли вы любителем или серьезным ученым-компьютерщиком.
Проблема, как указано в недавней статье, заключается в следующем:
«Вы только что купили дом на берегу озера. Бамбуковый сад растет за пределами дома и закрывает прекрасный вид на озеро. Чтобы решить эту проблему, вы также купили робота-панды-садовника, который раз в день может мгновенно обрезать один бамбук. . Вы уже измерили скорость роста каждого бамбука в саду, и теперь вам нужно запрограммировать садовника подходящим графиком стрижки бамбука, чтобы вид был как можно более четким ».
Что ж, вашей первой мыслью может быть бесполезная роботизированная панда, которая может срезать только один бамбук в день — это, конечно, был первый комментарий Гарри Фэйрхеда, но тогда он наш парень в области Интернета вещей, оборудования и робототехники! Попробуйте объяснить практическому человеку, что чистые алгоритмы заслуживают изучения.
Формально ли это звучит более впечатляюще?
В саду находится n бамбуков b1, …, bn, где известная суточная скорость роста бамбука hi> 0, при h1≥ … ≥hnand ∑ hi = 1. Первоначально высота каждого бамбука равна 0, и в конце каждого дня робот-садовник может обрезать не более одного бамбука, чтобы мгновенно сбросить его высоту до нуля. Высота бамбука bi в конце дня d≥1 и до того, как садовник решит, какой бамбук обрезать, равна (d − d ′) hi, где d ′