Паук сплел паутину, которая состоит из оси абсцисс, оси ординат, а так же следующих кривых: y=x, y=-x, x^2+y^2=1, x^2+y^2=9, x^2+y^2=16. За день во все узлы попались мухи. Паук сидит в точке (0;0) и собирается съесть всех мух. Какое минимальное расстояние пройдет паук, пока не закончит есть ?

задан 3 Фев '18 7:43

изменен 5 Фев '18 20:07

@Dante101: рассмотрим такую задачу. В узлах целочисленной решётки (в конечном числе) находятся мухи. Паук сидит в (0,0). Как ему быстрее всего их съесть? Известно, что эта задача относится к классу задач максимальной переборной сложности (NP-полной, "по-научному"). То есть хороших алгоритмов перебора не известно. Здесь рассматривается конкретная конфигурация похожего типа, с виду достаточно сложная. Сходу я не сумел придумать даже гипотетически оптимальный обход. Уже после его предъявления можно как-то доказывать, что он оптимален. Может, кто-то сумеет догадаться (любопытно узнать решение)?

(5 Фев '18 23:18) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×396
×212
×57

задан
3 Фев '18 7:43

показан
598 раз

обновлен
5 Фев '18 23:18

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru