Форум умных людей

Задачи и головоломки => Математические задачи => Тема начата: buka от Декабрь 21, 2011, 14:01:03


Название: Минимальная длина дорог
Отправлено: buka от Декабрь 21, 2011, 14:01:03
Допустим, у нас есть 4 города, расположенных в углах некоторого квадрата.
Необходимо их соединить между собой так, чтобы из одного (любого) города можно было попасть в любой другой.
При этом, поскольку строить дороги накладно, надо найти такое соединение, чтобы суммарные затраты на стр-во этого соединения были минимальны.

Название: Re: Минимальная длина дорог
Отправлено: Lkob от Декабрь 21, 2011, 14:08:27
Показать скрытый текст

Название: Re: Минимальная длина дорог
Отправлено: Les от Декабрь 21, 2011, 14:17:11
Показать скрытый текст
надо найти какой нить способ найти минимальную длину не методом перебора

Название: Re: Минимальная длина дорог
Отправлено: buka от Декабрь 21, 2011, 14:35:30
Ребята, если бы было бы так просто, разве я задал бы эту задачу?
Есть более компактный вариант... :)

Название: Re: Минимальная длина дорог
Отправлено: Anatol. от Декабрь 21, 2011, 14:55:54
Нипанятна  ???

Название: Re: Минимальная длина дорог
Отправлено: Deaduwka от Декабрь 21, 2011, 15:17:03
http://img.maryno.net/images/3c157faf2f6edf788c82f4ce4843d273/7e40a3c3d4033a192b17f4c8d621f0e0.png

Это решение не оптимально, я думаю. Но оно лучше двух диагоналей.

UPD: там можно проаптималить еще .. если сделать сверху (на рисунке) также как и снизу .. будет приблизительно 2.73

Название: Re: Минимальная длина дорог
Отправлено: Les от Декабрь 21, 2011, 15:18:48
лучьше но я узнал какое минимальное))) и не через интернет) Я МЫЛСЯ И ВДРУГ МЕНЯ ОСЕНИЛО

Название: Re: Минимальная длина дорог
Отправлено: Deaduwka от Декабрь 21, 2011, 16:35:16
Цитата: Les от Декабрь 21, 2011, 15:18:48
лучьше но я узнал какое минимальное))) и не через интернет) Я МЫЛСЯ И ВДРУГ МЕНЯ ОСЕНИЛО
Вообще не строить дороги пусть по колдоебинам ездят? типа украина-style? вобщем кидай в спойлер че

Название: Re: Минимальная длина дорог
Отправлено: Les от Декабрь 21, 2011, 18:17:01
Показать скрытый текст

Название: Re: Минимальная длина дорог
Отправлено: Deaduwka от Декабрь 21, 2011, 18:50:54
Точняк. Можно вывести нехитрую формулу нахождения точки излома, в своем примере я взял просто середину высоты маленького треугольника, но там надо не ее юзать для более точного подсчета, наверное какой-нибудь центр масс ...

Название: Re: Минимальная длина дорог
Отправлено: Smith от Декабрь 21, 2011, 20:29:42
Цитата: buka от Декабрь 21, 2011, 14:01:03
Допустим, у нас есть 4 города, расположенных в углах некоторого квадрата.
Необходимо их соединить между собой так, чтобы из одного (любого) города можно было попасть в любой другой.
При этом, поскольку строить дороги накладно, надо найти такое соединение, чтобы суммарные затраты на стр-во этого соединения были минимальны.

привет, buka,  сам придумал условие?  :good2:
оки, уточните, плз, например, есть ли ограничения по минимальному расстоянию между пунктами, или из А в С можно попасть просто через Б и тогда (условно) отсутствует необходимость строения некоторых дорог (А-С) априори, а, соответственно, и задача воспринимается иначе... проще говоря, условие - полное?   ???

Название: Re: Минимальная длина дорог
Отправлено: buka от Декабрь 21, 2011, 21:45:20
Молодцы! Добили!
Нет, это не я придумал это условие, увы :( - оно бы сделало мне честь, но... :(
Чтобы долго вас не мурыжить, даю видео, где всё говорит само за себя.
http://www.youtube.com/watch?v=dAyDi1aa40E
Но математически её решить можно, применяя подход Deaduwka:
Задаться углом Х под которым проводятся эти наклонные и вычислить общую длину как функцию Х.
Ну, а затем найти её максимум :)