[Izubr]

Наверное все знают задачу про соединение 4 городов расположенных в вершинах квадрата автодорогой наименьшей суммарной длины. А попробуйте найти решение для пяти городов расположенных в вершинах правильного пятиугольника.
И если модифицировать задачу из двумерного пространства в трёхмерное - найти решение для восьми городов расположенных в вершинах куба.

[magystr]

Опять же, хотелось бы уточнить условие.
Как решается задача для четырех точек?
Ответ - просто 3 стороны квадрата?
Если это так, боюсь, что в обоих предложенных задачах решение будет тривиальным...

Или имелось ввиду какое-то другое условие?

[Izubr]

Эээ... Если тебе неизвестна задача про 4 точки, то для тебя в этой теме - три задачи Условие дословно звучит так: "Четыре города расположены в вершинах квадрата со стороной 100 км. Необходимо соединить все 4 города системой автодорог с наименьшей суммарной длиной." Решение "три стороны" конечно же неверно, так как три стороны больше к примеру двух диагоналей.

Это сообщение отредактировал Izubr - 29/11/2009, 01:09

[magystr]

Вот потому и пытаюсь выяснить ПРАВИЛЬНОЕ УСЛОВИЕ,

Насколько я понимаю две диагонали не соединяют ВСЕ ЧЕТЫРЕ города. А только попарно.

Хотелось бы услышать правильную формулировку.

[Izubr]

Как это не соединяет? У тебя что, две диагонали в квадрате не пересекаются?

Это сообщение отредактировал Izubr - 29/11/2009, 11:56

[Сашун]

Эх, молодость, Штейнер, Бонапарт, Торичелли, Ферма...

--------------------

С уважением, А.Малышев

[magystr]

Ну да. Эт я тормознул. Конечно точка пересечения не обязана находиться в каком-то городе.

[Izubr]

Александр Алексеевич, это что, Ваши школьные друзья перечислены? :) Я думал Вы помоложе :)

[Сашун]

Ето просто люди, решавшие задачи такого типа. По памяти, там при числе городов "несколько" есть точные решения, чуть ли не аналитические...

--------------------

С уважением, А.Малышев

[Izubr]

Мне кажется, что для куба задачу они все таки не решали :)