Страниц: [1]
  Печать  
Автор Тема: Минимальная длина дорог  (Прочитано 5880 раз)
0 Пользователей и 1 Гость смотрят эту тему.
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
: Декабрь 21, 2011, 14:01:03 �

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

Эти пользователи сказали вам СПАСИБО :

Lkob, Smith

За это сообщение 2 пользователи сказали спасибо!
Записан
Lkob
Умник
****
Offline Offline

Сообщений: 625

СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62


Будь проще, и люди к тебе потянутся.

499789811
Просмотр профиля Email
Ответ #1 : Декабрь 21, 2011, 14:08:27 �

Показать скрытый текст
Записан

Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
Les
Гость
Ответ #2 : Декабрь 21, 2011, 14:17:11 �

Показать скрытый текст
надо найти какой нить способ найти минимальную длину не методом перебора
Последнее редактирование: Декабрь 21, 2011, 15:01:26 от Les Записан
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #3 : Декабрь 21, 2011, 14:35:30 �

Ребята, если бы было бы так просто, разве я задал бы эту задачу?
Есть более компактный вариант... Smiley

Эти пользователи сказали вам СПАСИБО :

Les

За это сообщение 1 пользователь сказал спасибо!
Записан
Anatol.
Свой человек
***
Offline Offline

Сообщений: 426

СПАСИБО
-вы поблагодарили: 57
-вас поблагодарили: 96


Мир с ног нАголову


Просмотр профиля
Ответ #4 : Декабрь 21, 2011, 14:55:54 �

Нипанятна  Huh?
Записан

Igni et ferro
Deaduwka
Новенький
*
Offline Offline

Сообщений: 30

СПАСИБО
-вы поблагодарили: 2
-вас поблагодарили: 3


Просмотр профиля Email
Ответ #5 : Декабрь 21, 2011, 15:17:03 �

//текст доступен после регистрации//

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

UPD: там можно проаптималить еще .. если сделать сверху (на рисунке) также как и снизу .. будет приблизительно 2.73
Последнее редактирование: Декабрь 21, 2011, 15:19:39 от Deaduwka Записан
Les
Гость
Ответ #6 : Декабрь 21, 2011, 15:18:48 �

лучьше но я узнал какое минимальное))) и не через интернет) Я МЫЛСЯ И ВДРУГ МЕНЯ ОСЕНИЛО
Записан
Deaduwka
Новенький
*
Offline Offline

Сообщений: 30

СПАСИБО
-вы поблагодарили: 2
-вас поблагодарили: 3


Просмотр профиля Email
Ответ #7 : Декабрь 21, 2011, 16:35:16 �

лучьше но я узнал какое минимальное))) и не через интернет) Я МЫЛСЯ И ВДРУГ МЕНЯ ОСЕНИЛО
Вообще не строить дороги пусть по колдоебинам ездят? типа украина-style? вобщем кидай в спойлер че
Записан
Les
Гость
Ответ #8 : Декабрь 21, 2011, 18:17:01 �

Показать скрытый текст

Эти пользователи сказали вам СПАСИБО :

Anatol.

За это сообщение 1 пользователь сказал спасибо!
Записан
Deaduwka
Новенький
*
Offline Offline

Сообщений: 30

СПАСИБО
-вы поблагодарили: 2
-вас поблагодарили: 3


Просмотр профиля Email
Ответ #9 : Декабрь 21, 2011, 18:50:54 �

Точняк. Можно вывести нехитрую формулу нахождения точки излома, в своем примере я взял просто середину высоты маленького треугольника, но там надо не ее юзать для более точного подсчета, наверное какой-нибудь центр масс ...
Записан
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #10 : Декабрь 21, 2011, 20:29:42 �

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

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

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #11 : Декабрь 21, 2011, 21:45:20 �

Молодцы! Добили!
Нет, это не я придумал это условие, увы Sad - оно бы сделало мне честь, но... Sad
Чтобы долго вас не мурыжить, даю видео, где всё говорит само за себя.
<i style="color:#ff0000;">//текст доступен после <a href="/forum/index.php?action=register">регистрации</a>//</i>
Но математически её решить можно, применяя подход Deaduwka:
Задаться углом Х под которым проводятся эти наклонные и вычислить общую длину как функцию Х.
Ну, а затем найти её максимум Smiley
Последнее редактирование: Декабрь 21, 2011, 22:08:19 от buka Записан
Страниц: [1]
  Печать  
 
Перейти в: