Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ѕример («адача о кратчайшем пути)




–ассмотрим задачу о кратчайшем пути в графе с неотрицательными весами дуг (рис.1). ¬етвление в этой задаче - это выбор очередной дуги. ¬ качестве нижней оценки примем суммарную длину частичного пути до некоторой вершины. Ќа рис.2. приведены шаги ветвлени€ в предположении, что ветвление производитс€ дл€ вершины из активного множества с наименьшей нижней оценкой. Ўаги ветвлени€ можно выразить схемой:

1.

2.

3.

на шаге 3 получен первый УрекордФ Ёто позвол€ет исключить из активного множества вершину

4. на этом шаге из активного множества исключаютс€ вершины и

5. ѕоскольку в активном множестве нет вершин, процесс закончен.

–ис.1. «адача о кратчайшем пути.

 

–ис.2. ƒерево поиска, полученное при условии, что ветвление производитс€ в вершине наименьшей нижней границы. - УрекордФ.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 668 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќадо любить жизнь больше, чем смысл жизни. © ‘едор ƒостоевский
==> читать все изречени€...

1261 - | 1025 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.011 с.