Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Минимальный разрыв / 5 сообщений из 5, страница 1 из 1
09.11.2008, 18:16
    #35642499
yelzhas
yelzhas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Минимальный разрыв
Даны пункты и соединяющие их пути(a[i,j]=a[j,i]). Даны два пукнта П1 и П2. Необходимо убрать такие дороги чтоб их сумма была наименьшей и нельзя было перейти от П1 до П2. Может эта задача как нибудь по другому называется. Есть ли где нибудь алгоритм?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.11.2008, 18:37
    #35642519
Ренат
Ренат
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Минимальный разрыв
Обычная итерация? Или нет?

a[i,j]= это растояние от пункта i до j? Т.е. задача одномерная?

delphi:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
 var  path: array [ 1 ..n, 1 ..n]  of  real;
...
min:=path[p1,p2];
min_id:= 0 ;
 for  i:= 1   to  n  do 
 if (min>path[p1,i]+path[i,p2])  then 
 begin 
min:=path[p1,i]+path[i,p2];
min_id:=i;
 end ;
 if  min_id= 0   then 
print("кароче прямой дороги ниче нет")
 else 
print("самая быстрая дорого через пункт "+inttostr(min_id));
вместо принтов напиши сам как ты их собиарешься "удалить".... Хоят если ечстно я не очень понял задачу. Можно ее полную формулировку услышать?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.11.2008, 19:38
    #35642569
yelzhas
yelzhas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Минимальный разрыв
Попробую:
Дан граф и два пункта. Необходимо удалить из графа некоторые дороги, так чтобы нельзя было перейти от пункта П1 до П2. К тому же сумма весов удаляемых дорог должна быть минимально возможной.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.11.2008, 19:48
    #35642577
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Минимальный разрыв
Описание этого алгоритма должно быть обязательно упомянтуто где-то в Алгоритмах на графах
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.11.2008, 20:09
    #35642595
yelzhas
yelzhas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Минимальный разрыв
ага спасибо!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Минимальный разрыв / 5 сообщений из 5, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 357ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1344864]:
 0ms
get settings:
 7ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 65ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 49ms
get tp. blocked users:
 1ms
others: 201ms
total:  357ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]