|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Maxim Ushakov 2:5030/786.25 24 May 2001 23:15:18
To : Zapadinsky Anatoly \(ZAB\)
Subject : Hа: Задача о распространении сообщения в сети
--------------------------------------------------------------------------------
>> Вот, задали курсач по методам оптимизации на сабжевую тему.
>> Собственно, сабж состоит в следующем:
>> есть некая сетка, в которой компы соединены некоторым образом.
ZZ> Люди, а графы относятся к динамическому программированию? Просто тут вроде
ZZ> идеально подходит "волновой алгоритм" (просто завершением является не
ZZ> достижение некоторой вершины, а достижение всех вершин, т.е. когда
ZZ> недостигнутых не останется), и не совсем понятено, как тут можно по
ZZ> другому...
Графы не относятся к дин. программированию, ибо граф - это абстрактный объект
(тройка множеств, двойка множеств, множество с отношением - кому как удобнее) а
динамическое программирование - метод решения задач, для которых верно уравнение
Беллмана (о постепенном приближении).
А волновой алгоритм не подходит, т.к. он предполагает, что из занятой вершины на
следующий шаг можно попасть во все соседние сразу, у нас же каждая машина может
послать одно сообщение.
Bye.
... Gnothi seauton ...
* Origin: Maxim Ushakov (2:5030/786.25)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
