#graph-algorithm
Вопрос:
Я получил этот вопрос во время теста по набору персонала несколько дней назад. Я в принципе ничего не мог сделать —
Нам дается дерево(дерево-это связный граф, где каждая пара узлов имеет один простой путь между ними) с n узлами(также длиной ребра между узлами) и начальным узлом, где у нас есть ловец обезьян с постоянной скоростью 1 единица/сек. Обезьяны очень проворны со сколь угодно большой скоростью(бесконечная скорость) и пытаются избежать ловца. Они знают о положении друг друга и стараются максимально увеличить общее время, необходимое ловцу, чтобы поймать их. Катчер пытается свести это время к минимуму. Если в какой-то момент времени обезьяна и ловец находятся в одном и том же положении, обезьяна поймана, сколько бы их ни было. Мы должны найти время, необходимое ловцу, чтобы поймать их всех.
Правка — Нам также дается количество и начальные узлы всех обезьян.
Из комментария Серхио — я забыл уточнить, что обезьяны знают позицию ловца и друг друга, а ловец всегда знает позиции всех обезьян.
Пожалуйста, помогите
Комментарии:
1. Я думаю, что проблема недостаточно конкретизирована. Если обезьяны могут перемещаться как вверх, так и вниз по дереву, знают о положении ловца и разумно пытаются уклониться от него (двигаясь с бесконечной скоростью), то в лучшем случае потребуется неопределенное количество времени, чтобы поймать их всех. В худшем случае ловец никогда не сможет поймать их всех.
2. Привет, Серджио. На каком основании вы это говорите? график представляет собой дерево, поэтому обезьяна не сможет убежать, если ловец решит отправиться за ней, даже если у них бесконечная скорость, им придется пересечь ловушку и быть пойманными. Это мое понимание, пожалуйста, поправьте меня, если я ошибаюсь.
3. Представьте себе дерево с тремя ветвями, A, B и C (для простоты основные ветви прямые, дополнительных ветвей нет). Ловец спускается вниз и ловит всех обезьян в нем. Затем он возвращается к корню и опускается вниз B. Тем временем все обезьяны в C перемещаются в A, поэтому, когда ловец опустится на C, он не найдет никаких обезьян. Он может повторить попытку A, но что, если все обезьяны сейчас находятся в B (перемещены, пока ловец был в C)? Теперь это вопрос случая, и шансы ловца становятся все хуже по мере того, как на дереве появляется все больше ветвей.
4. Я не понимаю, как это может быть делом случая после того, как он вернется в root? Возможно, я плохо объяснил вопрос, но когда ловец возвращается к корню, он может нацелиться на любую ветвь, какую захочет, у ловца также есть полная информация о том, где находятся обезьяны, так как он может их видеть. Допустим, он выбирает одну обезьяну для поимки за раз, тогда я не думаю, что существует какой-либо сценарий, при котором эта конкретная обезьяна может избежать поимки(поскольку это дерево, поэтому не может быть циклов). Он может поймать их всех одного за другим вот так.
5. Я думаю, что вы можете значительно прояснить вопрос, предоставив по крайней мере один или два примера ввода и вывода алгоритма..