Есть 4 города расположенные в вершинах квадрата.
Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
Можно создавать перекрёстки.
А есть алгоритмическое решение такой задачи?
Если есть, то какое?
Диагонали не подходят!
Есть только одна комбонация:
+ . . . . . +
.\ . . . . /
. \ . . . /
. .\_____/
. ./ . . \
. / . . . \
./ . . . . \
+ . . . . . +
Если принять сторону квадрата за 1, то общая длина равна 2.73 (Доказано) (диагональ 2.82)
Осталось доказать:
Является эта конфигурация минимальной?
17.02.03 13:13: Перенесено из 'Алгоритмы'
Неожиданно обнаружив приписку "модератор" после ника
и новую кнопочку "Редактировать", спешу поюзать обновку
Все "Интересные задачи" надо складывать в этот форум.
Обратно, в этом форуме все посты — "Интересные задачи".
Поэтому пожалуйста, выбирайте тему поста так, чтобы
было хоть какое-то указание на то, о чём там идёт речь.
Для данной задачи это могло бы быть, например, "Кратчайшая сеть дорог".
Pushkin.
