Witam,
Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
koncowego. Musze okreslic kolejnosc wykonywania zadan i je pogrupowac.
Kryterium grupowania, to mozliwosc wykonania kliku zadan w jednej chwili
(grupa sklada sie z zadan, ktore moga byc wykonywane w danej chwili).
Zakladam, ze ilosc maszyn jest nieograniczona. Oczywiscie zadania sa od
siebie zalezne, ale dla kazdego mamy tylko informacje o jego najblizszych
zaleznosciach, tj. wiemy tylko, jakie zadania ma sie wykonac krok wczesniej,
zeby to moglo sie rozpoczac (tzn. taka informacja jest zawarta w samej
definicji zadania). Koncowym wynikiem ma byc lista grup zadan (oczywiscie
musze miec informacje co w tej grupie sie znajduje) uporzadkowana wg.
kolejnosci wykonywania.
Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
optymalny dla takiego problemu.
Z gory dzieki za pomoc

do góry

qweer pisze:
> Witam,
> Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
> Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
> koncowego. Musze okreslic kolejnosc wykonywania zadan i je pogrupowac.
> Kryterium grupowania, to mozliwosc wykonania kliku zadan w jednej chwili
> (grupa sklada sie z zadan, ktore moga byc wykonywane w danej chwili).
> Zakladam, ze ilosc maszyn jest nieograniczona. Oczywiscie zadania sa od
> siebie zalezne, ale dla kazdego mamy tylko informacje o jego najblizszych
> zaleznosciach, tj. wiemy tylko, jakie zadania ma sie wykonac krok wczesniej,
> zeby to moglo sie rozpoczac (tzn. taka informacja jest zawarta w samej
> definicji zadania). Koncowym wynikiem ma byc lista grup zadan (oczywiscie
> musze miec informacje co w tej grupie sie znajduje) uporzadkowana wg.
> kolejnosci wykonywania.
> Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
> optymalny dla takiego problemu.

Najprostsze, choć może lekko nieoptymalne pamięciowo(przyjmuję założenie
o jednostkowym rozmiarze zadania): Robisz graf skierowany w którym w
węzłach masz licznik - na ile zadań dane zadanie czeka bezpośrednio oraz
listę zadań które czekają na nie (odwrotnie niż w danych wejściowych).
Przeglądasz dane 1 raz i do listy wrzucasz wszystkie zadania z
licznikiem=0 - to jest 1 grupa. ->Dopóki są jakieś zadania na tej
liście. Wypisz grupę, odejmij 1 od liczników każdego zadania na które
wskazują te z listy dodając do drugiej listy te którym licznik się
wyzerował. Wywal pierwszą listę. Aktualną listą jest 2 lista. Powtórz
->. Jeżeli w grafie zostały zadania z niezerowym licznikiem to znaczy,
że był cykl.


--
Pozdrawiam
Michoo

do góry

On Wed, 18 Feb 2009 00:25:26 +0100, "qweer" <cisrudlow[wytni]@o2.pl>
wrote:

>Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
>optymalny dla takiego problemu.


Nie ma algorytmu "najbardziej optymalnego"

A.L.

do góry

On Wed, 18 Feb 2009 00:25:26 +0100, "qweer" <cisrudlow[wytni]@o2.pl>
wrote:

>Witam,
>Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
>Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
>koncowego.

No i co ten graf nam mowi?...

A.L.

do góry

On 18 Lut, 00:25, "qweer" <cisrudlow[wytni]@o2.pl> wrote:

> Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
> optymalny dla takiego problemu.

Jak A.L. powiedział, nie ma najbardziej optymalnego algorytmu. Wg
jakiego
kryterium masz ułożyć te zadania?

Pozdrawiam,
Wit Jakuczun [ http://wlogsolutions.pl ]

do góry

qweer pisze:
> Witam,
> Mam dosc proste zadanie do zrealizowania. Jaki algorytm mi polecicie?
> Mam graf zadan(niepodzielnych) bez okreslonego zadania poczatkowego i
> koncowego. Musze okreslic kolejnosc wykonywania zadan i je pogrupowac.
> Kryterium grupowania, to mozliwosc wykonania kliku zadan w jednej chwili
> (grupa sklada sie z zadan, ktore moga byc wykonywane w danej chwili).
> Zakladam, ze ilosc maszyn jest nieograniczona. Oczywiscie zadania sa od
> siebie zalezne, ale dla kazdego mamy tylko informacje o jego najblizszych
> zaleznosciach, tj. wiemy tylko, jakie zadania ma sie wykonac krok wczesniej,
> zeby to moglo sie rozpoczac (tzn. taka informacja jest zawarta w samej
> definicji zadania). Koncowym wynikiem ma byc lista grup zadan (oczywiscie
> musze miec informacje co w tej grupie sie znajduje) uporzadkowana wg.
> kolejnosci wykonywania.
> Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
> optymalny dla takiego problemu.
> Z gory dzieki za pomoc

Polecam książkę pt. "Badania operacyjne dla informatyków", niestety
autora czy wydawnictwa nie pomnę, ale tam są całe stada algorytmów
szeregowania zadań opisane.

Adam Kłobukowski

do góry

On Tue, 17 Feb 2009 23:12:49 -0800 (PST), Wit Jakuczun
<w...@g...com> wrote:

>On 18 Lut, 00:25, "qweer" <cisrudlow[wytni]@o2.pl> wrote:
>
>> Prosze o rade, jaki moge wykorzystac algorytm, ktory bedzie najbardziej
>> optymalny dla takiego problemu.
>
>Jak A.L. powiedział, nie ma najbardziej optymalnego algorytmu. Wg
>jakiego
>kryterium masz ułożyć te zadania?

Ja powiedzialem dwie rzeczy:

1. Jak ktos mowi "najbardziej oprtymalny" to ma klopoty z jezykiem
polskim,,
2. Algorytmy szeregowania zadan sa NP-complete, wiec trudno mowic o
"optymalnym" algorytmie

A.L.

do góry

On Wed, 18 Feb 2009 10:15:31 +0100, Adam K?obukowski
<a...@k...pl> wrote:

>
>Polecam książkę pt. "Badania operacyjne dla informatyków", niestety
>autora czy wydawnictwa nie pomnę, ale tam są całe stada algorytmów
>szeregowania zadań opisane.
>
>Adam Kłobukowski

Blazewicz, Cellary, Slowinski, Weglarz, "Badania operacyjne dla
informatykow", WNT, 1983

G. Coffman, "Teoria szeregowania zadan", WNT, 1980.

Z nowszych:

Smutnicki, "Algorytmy szeregowania" Akademicka Oficyna Wydawnicza
EXIT, 2002

Grabowski, Nowicki, Smutnicki, "Metoda blokowa w zagadnieniach
szeregowanai zadan". EXIT, 2003

A.L.

do góry

On Wed, 18 Feb 2009 07:00:05 -0600, A.L. <a...@z...com> wrote:

>2. Algorytmy szeregowania zadan sa NP-complete, wiec trudno mowic o
>"optymalnym" algorytmie

Powinno byc

Problemy szeregowania sa NP-complete...

A.L.

do góry

> Najprostsze, choć może lekko nieoptymalne pamięciowo(przyjmuję założenie
> o jednostkowym rozmiarze zadania): Robisz graf skierowany w którym w
> węzłach masz licznik - na ile zadań dane zadanie czeka bezpośrednio oraz
> listę zadań które czekają na nie (odwrotnie niż w danych wejściowych).
> Przeglądasz dane 1 raz i do listy wrzucasz wszystkie zadania z
> licznikiem=0 - to jest 1 grupa. ->Dopóki są jakieś zadania na tej
> liście. Wypisz grupę, odejmij 1 od liczników każdego zadania na które
> wskazują te z listy dodając do drugiej listy te którym licznik się
> wyzerował. Wywal pierwszą listę. Aktualną listą jest 2 lista. Powtórz
> ->. Jeżeli w grafie zostały zadania z niezerowym licznikiem to znaczy,
> że był cykl.

Tak, tak, ale nie mam tutaj ograniczen czasowych. Jest tylko ograniczenie
zaleznosci kolejnosciowych. Jezeli byloby tak, to bym mogl tutaj wykorzystac
lekko zmodyfikowany algorytm wyznaczania sceizki krytycznej (juz nie pamietam
kogo to byl wynalazek)


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry