Здравствуйте, Calc, Вы писали:

C>Есть 4 города расположенные в вершинах квадрата.
C>Нади их соединить дорогами, так чтоб сумарная длина дорог была минимальной.
C>Можно создавать перекрёстки.

C>А есть алгоритмическое решение такой задачи?

C>Если есть, то какое?

C>Диагонали не подходят!

C>Есть только одна комбонация:
C>+ . . . . . +
C>.\ . . . . /
C>. \ . . . /
C>. .\_____/
C>. ./ . . \
C>. / . . . \
C>./ . . . . \
C>+ . . . . . +

Так вот, это типичная задача, которая в общем случае, или если быть точным на я зыке теории алгоритмов, называется Геометрическое дерево Штейнера. Полиномиального алгоритма для ее решения не существет, если есть желание могу доказать. А это частный случай этой задачи. Так вот углы между ребрами, которые получиились в следствии выставления допю точек(лежат внутри квадрата), должны составлять угол в 120 градусов.