Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Июнь 2012   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 10656
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 4318
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2487
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная

Номер выпуска:284
Дата выхода:02.06.2012, 02:00
Администратор рассылки:Асмик Гаряка (Академик)
Подписчиков / экспертов:36 / 41
Вопросов / ответов:1 / 1

Консультация # 186244: Здравствуйте! У меня возникли сложности с таким вопросом: нужно только по типу:

Консультация # 186244:

Здравствуйте! У меня возникли сложности с таким вопросом:


нужно только по типу:


вот такое решение не надо:
http://rfpro.ru/question/183210

Дата отправки: 30.05.2012, 00:26
Вопрос задал: Иван Васильевич Митяев (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Советник):

Здравствуйте, Иван Васильевич Митяев!

Положим B8* = 0, B1 = B2 = B3 = B4 = B5 = B6 = B7 = B9 = B10 = ∞. Метка вершины 8 постоянна.

1. Смежными с вершиной 8 являются вершины 5, 7 и 10. Пересчитаем метки этих вершин:
B5 = min{B2+c25, B4+c45, B7+c75, B8+c85} = min{∞+7, ∞+4, ∞+2, 0+3} = min{∞, ∞, ∞, 3} = 3
B7 = min{B4+c47, B5+c57, B6+c67, B8+c87, B9+c97, B10+c10,7} = min{∞+9, ∞+2, ∞+3, 0+7, ∞+8, ∞+4} = min{∞, ∞, ∞, 7, ∞, ∞} = 7< br>B10 = min{B7+c7,10, B8+c8,10, B9+c9,10} = min{∞+4, 0+5, ∞+2} = min{∞, 5, ∞} = 5
min{B5, B7, B10} = min{3, 7, 5} = 3
Вершина 5 получает постоянную метку:
B5* = 3, B7 = 7, B8* = 0, B10 = 5, B1 = B2 = B3 = B4 = B6 = B9 = ∞

2. Смежными с вершиной 5 являются вершины 2, 4, 7 и 8. Метка вершины 8 постоянна, пересчитаем метки вершин 2, 4 и 7:
B2 = min{B1+c12, B4+c42, B5+c52} = min{∞+1, ∞+6, 3+7} = min{∞, ∞, 10} = 10
B4 = min{B1+c14< /sub>, B2+c24, B3+c34, B5+c54, B6+c64, B7+c74} = min{∞+5, ∞+6, ∞+8, 3+4, ∞+5, 7+9} = min{∞, ∞, ∞, 7, ∞, 16} = 7
B7 = min{B4+c47, B5+c57, B6+c67, B8+c87, B9+c97, B10+c10,7} = min{∞+9, 3+2, ∞+3, 0+7, ∞+8, 5+4} = min{∞, 5, ∞, 7, ∞, 9} = 5
min{B2, B4, B7} = min{10, 7, 5} = 5
Вершина 7 получает постоянную метку:
B2 = 10, B4 = 7, B5* = 3, B7* = 5, B8* = 0, B10 = 5, B1 = B3 = B6 = B9 = ∞< br>
3. Смежными с вершиной 7 являются вершины 4, 5, 6, 8, 9 и 10. Метки вершин 5 и 8 постоянны, пересчитаем метки вершин 4, 6, 9 и 10:
B4 = min{B1+c14, B2+c24, B3+c34, B5+c54, B6+c64, B7+c74} = min{∞+5, 10+6, ∞+8, 3+4, ∞+5, 5+9} = min{∞, 16, ∞, 7, ∞, 14} = 7
B6 = min{B3+c36, B4+c46, B7+c76, B9+c96} = min{∞+4, 7+5, 5+3, ∞+6} = min{∞, 12, 8, ∞} = 8
B9 = min{B6+c69, B7+c79, B10+c10,9} = min{∞+6, 5+8, 5+2} = min{∞, 13, 7} = 7
B10 = min{B7+ c7,10, B8+c8,10, B9+c9,10} = min{5+4, 0+5, 5+2} = min{9, 5, 7} = 5
min{B< sub>4, B6, B9, B10} = min{7, 8, 7, 5} = 5
Вершина 10 получает постоянную метку:
B2 = 10, B4 = 7, B5* = 3, B6 = 8, B7* = 5, B8* = 0, B9 = 7, B10* = 5, B1 = B3 = ∞

4. Смежными с вершиной 10 являются вершины 7, 8 и 9. Метки вершин 7 и 8 постоянны, пересчитаем метку вершины 9:
B9 = min{B6+c69, B7+c79, B10+c10,9} = min{8+6, 5+8, 5+2} = min{14, 13, 7} = 7
Вершина 9 получает постоянную метку:
B2 = 10, B4 = 7, B5* = 3, B6 = 8, B7* = 5, B 8* = 0, B9* = 7, B10* = 5, B1 = B3 = ∞

5. Смежными с вершиной 9 являются вершины 6, 7 и 10. Метки вершин 7 и 10 постоянны, пересчитаем метку вершины 6:
B6 = min{B3+c36, B4+c46, B7+c76, B9+c96} = min{∞+4, 7+5, 5+3, 7+6} = min{∞, 12, 8, 13} = 8
Вершина 6 получает постоянную метку:
B2 = 10, B4 = 7, B5* = 3, B6* = 8, B7* = 5, B8* = 0, B9* = 7, B10* = 5, B1 = B3 = ∞

6. Смежными с вершиной 6 являются вершины < b>3, 4, 7 и 9. Метки вершин 7 и 9 постоянны, пересчитаем метки вершин 3 и 4:
B3 = min{B1+c13, B4+c43, B6+c63} = min{∞+3, 7+8, 8+4} = min{∞, 15, 12} = 12
B4 = min{B1+c14, B2+c24, B3+c34, B5+c54, B6+c64, B7+c74} = min{∞+5, 10+6, ∞+8, 3+4, 8+5, 5+9} = min{∞, 16, ∞, 7, 13, 14} = 7
min{B3, B4} = min{12, 7} = 7
Вершина 4 получает постоянную метку:
B2 = 10, B3 = 12, B4* = 7, B5* = 3, B6* = 8, B7* = 5, B8* = 0, B9* = 7, B10* = 5, B1 = ∞

7. Смежными с вершиной 4 являются вершины 1, 2, 3, 5, 6 и 7. Метки вершин 5, 6 и 7 постоянны, пересчитаем метки вершин 1, 2 и 3:
B1 = min{B2+c21, B3+c31, B4+c41} = min{10+1, 12+3, 7+5} = min{11, 15, 12} = 11
B2 = min{B1+c12, B4+c42, B5+c52} = min{∞+1, 7+6, 3+7} = min{∞, 13, 10} = 10
B3 = min{B1+c13, B4+c43, B6+c63} = min{∞+3, 7+8, 8+4} = min{∞, 15, 12} = 12
min{B1, B2, B3} = min{11, 10, 12} = 10
Вершина 2 получает постоянную метку:
B1 = 11, B2* = 10, B3 = 12, B4* = 7, B5* = 3< /b>, B6* = 8, B7* = 5, B8* = 0, B9* = 7, B10* = 5

8. Смежными с вершиной 2 являются вершины 1, 4 и 5. Метка вершины 2 постоянна, пересчитаем метки вершин 1 и 3:
B1 = min{B2+c21, B3+c31, B4+c41} = min{10+1, 12+3, 7+5} = min{11, 15, 12} = 11
B3 = min{B1+c13, B4+c43, B6+c63} = min{11+3, 7+8, 8+4} = min{14, 15, 12} = 12
min{B1, B3} = min{11, 12} = 11
Вершина 1 получает постоянную метку:
B1* = 11, B2* = 10, B3 = 12, B4* = 7, B5* = 3, B6* = 8, B7* = 5, B8* = 0, B9* = 7, B10* = 5

9. Смежными с вершиной 1 являются вершины 2, 3 и 4. Метки вершин 2 и 4 постоянна, пересчитаем метку вершины 3:
B3 = min{B1+c13, B4+c43, B6+c63} = min{11+3, 7+8, 8+4} = min{14, 15, 12} = 12
Вершина 3 получает постоянную метку:
B1* = 11, B2* = 10, B3* = 12, B4* = 7, B5* = 3, B6* = 8, B7* = 5, B8* = 0, B9* = 7, B10* = 5

Вершин, не имеющ их постоянной метки нет, следовательно, алгоритм завершён. Кратчайший путь от вершины 8 до вершины 3 равен c85 + c57 + c76 + c63 = 3 + 2 + 3 + 5 = 12 = B3

Консультировал: Коцюрбенко Алексей aka Жерар (Советник)
Дата отправки: 30.05.2012, 07:19

5
Спасибо!
-----
Дата оценки: 31.05.2012, 19:23
Рейтинг ответа:

НЕ одобряю +1 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012
В избранное