Когда-то давно слышал такую задачу: кто-то оказался в лесу без каких-либо навигационных приборов и ему нужно выйти из лесу. По какой траектории ему нужно двигаться, чтобы гарантировано выйти из лесу и еще и чтобы это было оптимальная траектория. Что-то такое кажется... точно не помню.
Кто знает эту задачу подскажите как она точно формулируется и каково ее строгое математическое решение, плиз!
Здравствуйте, Максим Рогожин, Вы писали:
МР>Привет всем!
МР>Когда-то давно слышал такую задачу: кто-то оказался в лесу без каких-либо навигационных приборов и ему нужно выйти из лесу. По какой траектории ему нужно двигаться, чтобы гарантировано выйти из лесу и еще и чтобы это было оптимальная траектория. Что-то такое кажется... точно не помню.
МР>Кто знает эту задачу подскажите как она точно формулируется и каково ее строгое математическое решение, плиз!
Скорее всего это задача "В тёмном лесу"
Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
Решение пока не привожу. Может, кто то хочет подумать. Так как задача известная, то решение можно и нагуглить
B>Скорее всего это задача "В тёмном лесу"
B>Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
Нет, это другая задача. Ни каких расстояний не задано. Форма леса не задана.
Здравствуйте, Максим Рогожин, Вы писали:
B>>Скорее всего это задача "В тёмном лесу"
B>>Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
МР>Нет, это другая задача. Ни каких расстояний не задано. Форма леса не задана.
Здравствуйте, Максим Рогожин, Вы писали:
B>>Скорее всего это задача "В тёмном лесу"
B>>Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
МР>Нет, это другая задача. Ни каких расстояний не задано. Форма леса не задана.
Решение не будет отличаться. Форма леса "не важна" и в задаче "В темном лесу".
А в каком то виде расстояние задать придется, так как формулировка задачи в виде "надо гарантированно выйти и по оптимальной траектории" подразумевает,
что оптимальность получаемых решений будет определяться по расстоянию, которое придется пройти в худших случаях или как среднее по всем возможным случаям.
Если бы лес было разрешено раздувать до бесконечности, то выйти было бы вообще нельзя.
Здравствуйте, Максим Рогожин, Вы писали:
B>>Скорее всего это задача "В тёмном лесу"
B>>Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
МР>Нет, это другая задача. Ни каких расстояний не задано. Форма леса не задана.
Выбираем любое n
(1). n шагов строго вперёд, потом поворот налево на 90гр
(2). n шагов строго вперёд, потом поворот налево на 90гр
(3). Увеличиваем n в два раза и goto (1)
Здравствуйте, baily, Вы писали:
B>Решение не будет отличаться. Форма леса "не важна" и в задаче "В темном лесу".
Будет.
B>А в каком то виде расстояние задать придется, так как формулировка задачи в виде "надо гарантированно выйти и по оптимальной траектории" подразумевает, B>что оптимальность получаемых решений будет определяться по расстоянию
Нет, не подразумевает. Не помню, что именно имелось ввиду под оптимальностью, может быть что нельзя возвращаться в ту точку где мы уже были, может еще что-то, но не обязательно расстояние.
Здравствуйте, kov_serg, Вы писали:
_>Выбираем любое n _>(1). n шагов строго вперёд, потом поворот налево на 90гр _>(2). n шагов строго вперёд, потом поворот налево на 90гр _>(3). Увеличиваем n в два раза и goto (1)
) А это самая оптимальная траектория? Доказать надо, что траектории лучше нету)
Здравствуйте, Максим Рогожин, Вы писали:
МР>) А это самая оптимальная траектория? Доказать надо, что траектории лучше нету)
Очевидно, что если мы про "в тёмном лесу", то, сначала, надо отойти на 1 км по прямой.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
B>Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
B>Решение пока не привожу. Может, кто то хочет подумать. Так как задача известная, то решение можно и нагуглить
Отойти на километр по прямой и пройти по окружности с центром в точке начального нахождения?
Здравствуйте, SomeOne_TT, Вы писали:
SO_>Здравствуйте, baily, Вы писали:
B>>Мальчик заблудился в лесу. Ровно в 1 км от него проходит дорога. Неизвестно только направление на неё. Как следует идти мальчику, чтобы выйти на дорогу по наикратчайшей траектории? Лес настолько густой, что дорогу мальчик увидит, только выйдя на неё.
B>>Решение пока не привожу. Может, кто то хочет подумать. Так как задача известная, то решение можно и нагуглить
SO_>Отойти на километр по прямой и пройти по окружности с центром в точке начального нахождения?
Где взять циркуль, ночью в тёмном лесу, и чем вы собираетесь отмерять 1 км?
E>Очевидно, что если мы про "в тёмном лесу", то, сначала, надо отойти на 1 км по прямой.
А мы не про "в темном лесу", а про первоначальную задачу) (Сформулирована в первом сообщении, хотя и расплывчато)
kov_serg написал траекторию по которой мы гарантировано выйдем из лесу. Я просто хотел найти источник этой задачи и посмотреть на строгое доказательство и уточнить, что имелось ввиду под оптимальностью.
Здравствуйте, Максим Рогожин, Вы писали:
МР>А мы не про "в темном лесу", а про первоначальную задачу) (Сформулирована в первом сообщении, хотя и расплывчато)
В исходной задаче не ясно, что такое "оптимально", и что такое "выйти из лесу", поэтому в её рамках что либо доказать невозможно...
МР>kov_serg написал траекторию по которой мы гарантировано выйдем из лесу. Я просто хотел найти источник этой задачи и посмотреть на строгое доказательство и уточнить, что имелось ввиду под оптимальностью...
Собственно понятно, что хороший кандидат для траектории — логарифмическая спираль, потому, что она сохраняет угол к направлению на старт.
Так что гуглим и на первой странице видим...
Оно?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>В исходной задаче не ясно, что такое "оптимально", и что такое "выйти из лесу", поэтому в её рамках что либо доказать невозможно...
А я вот и хочу найти точную формулировку и посмотреть доказательство. В этом и суть моего первого поста.
E>Собственно понятно, что хороший кандидат для траектории — логарифмическая спираль, потому, что она сохраняет угол к направлению на старт.
А что нам дает сохранение угла? Тут принципиально не сохранение угла, а расширяющийся круговой обход вокруг центра. Можно кругами ходить и круг за кругом увеличивать радиус круга.
E>Так что гуглим и на первой странице видим... E>Оно?
В том то и дело, что не оно. Задачу которую я описал в первом сообщении можно нагуглить. Мне интересен первоисточник и имеется ли у нее доказанное решение.
Здравствуйте, Максим Рогожин, Вы писали:
МР>А я вот и хочу найти точную формулировку и посмотреть доказательство. В этом и суть моего первого поста.
Это я понимаю, я не понимаю твоего вопроса про то, точно ли предложенная "прямоугольная спираль" оптимальна
МР>А что нам дает сохранение угла? Тут принципиально не сохранение угла, а расширяющийся круговой обход вокруг центра. Можно кругами ходить и круг за кругом увеличивать радиус круга.
Ну лог. спираль, делает это в некотором смысле оптимально.
E>>Так что гуглим и на первой странице видим... E>>Оно?
МР>В том то и дело, что не оно. Задачу которую я описал в первом сообщении можно нагуглить. Мне интересен первоисточник и имеется ли у нее доказанное решение.
А это не твоя задача, которую ты забыл/потерял, разве?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
SO_>>Отойти на километр по прямой и пройти по окружности с центром в точке начального нахождения? _>Где взять циркуль, ночью в тёмном лесу, и чем вы собираетесь отмерять 1 км?
ясно же что у мальчика есть смартфон с GPSом
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Erop, Вы писали:
E>Это я понимаю, я не понимаю твоего вопроса про то, точно ли предложенная "прямоугольная спираль" оптимальна
Ну я имел ввиду, что по такой траектории мы действительно выйдем, но меня интересует точная формулировка и доказательство)
E>А это не твоя задача, которую ты забыл/потерял, разве?
Я бегло просмотрел ту статью, которую ты прислал — там рассматриваются три случая:
1. полоса ширины l
2. круг диаметра d
3. полуплоскость и задано расстояние до края
Здравствуйте, Максим Рогожин, Вы писали:
E>>А это не твоя задача, которую ты забыл/потерял, разве?
МР>Я бегло просмотрел ту статью, которую ты прислал — там рассматриваются три случая: МР>1. полоса ширины l МР>2. круг диаметра d МР>3. полуплоскость и задано расстояние до края
МР>и где здесь моя задача?)
Ну так тебе виднее, что ты читал.
IMHO, довольно толковый разбор вариантов. Ты что-то другое искал?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Ну так тебе виднее, что ты читал. E>IMHO, довольно толковый разбор вариантов. Ты что-то другое искал?
Егор, вы видимо, не обратили внимание на мое второе сообщение — я там уточнил задачу. А именно: форма леса может быть любой, никакие расстояния не заданы, лес ограничен.
Здравствуйте, Erop, Вы писали:
E>Собственно понятно, что хороший кандидат для траектории — логарифмическая спираль, потому, что она сохраняет угол к направлению на старт.
Логарифмическая спираль — плохой кандидат, потому что мальчика на старте затошнит
Перекуём баги на фичи!
