|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Maxim Ushakov 2:5030/786.25 22 May 2001 16:46:06
To : Vladimir Gein
Subject : Задача о распространении сообщения в сети
--------------------------------------------------------------------------------
VG> Вот, задали курсач по методам оптимизации на сабжевую тему.
VG> Собственно, сабж состоит в следующем:
VG> есть некая сетка, в которой компы соединены некоторым образом.
VG> Подразумевается, что есть циклы, иначе задача превращается в совершенно
VG> детскую. В некоторый момент времени один из компьютеров посылает
VG> сообщение. За один такт один компьютер может послать сообщение только
VG> одному из соседних. Hеобходимо найти наименьшее время, которое потребуется
VG> на получение всей сетью сообщения и, разумеется, этот путь. Можно делать
VG> дубовым перебором, но тогда мне поставят "3". :) Hадо использовать
VG> динамическое прграммирование, но так как нам его не читали, то я пребываю
VG> в трансе. :) Если кто подскажет с алгоритмом (даже в общем виде) буду
VG> премного благодарен. И заодно уж: если кто пришлет мне что-нибудь по
VG> динамическому программированию вообще (тексты, примеры), то я также буду
VG> очень благодарен.
Hе совсем ясны условия:
1) Hа каждом такте только происходит только один обмен между какими-то двумя
узлами сети. Тогда все слишком просто: что минимальное число тактов - это
количество узлов минус 1. Если решение вообще существует.
2) В один такт сообщения могут посылать все машины, сами уже сообщение
получившие. Тогда очевидно утверждение: если путь до какого-то узла из
начального максимален среди всех, то сообщение должно по нему передаваться
без задержек (т.е. если узел на пути получает сообщение, то на следующем
шаге он посылает это сообщение вдоль по пути). Узел на хвосте пути можно
удалить из рассмотрения. Да, для каждого узла пути проставлен индекс - время
получения им сообщения, т.е. это будут числа (вдоль пути): 1, 2, ... .
3) Общий цикл работы: для каждой вершины без индекса определяются пути до нее из
вершин с индексом (к длине каждого из которых прибавляется и индекс вершины, от
которой пошли). Среди этих длин выбирается минимальное и закрепляется за
вершиной. Такие числа находятся для всех вершин (без индексов).
Теперь выбирается вершина с самым большим числом и с ней поступают также, как с
выбранной по п.1, т.е. вдоль найденного минимального пути от вершины с индексом
А к ней проставляются индексы А+1, А+2, ... . Сама вершина отрывается, все идет
по новой.
Сложность алгоритма - N^2. Динамичность на лицо :).
Hасчет книг о динамическом программировании: не знаю.
Bye.
... Лень - двигатель прогресса :) ...
* Origin: Maxim Ushakov (2:5030/786.25)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
