eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingalgorytm szeregownia i grupowania zadanRe: algorytm szeregownia i grupowania zadan
  • Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!not
    -for-mail
    From: Michoo <m...@v...pl>
    Newsgroups: pl.comp.programming
    Subject: Re: algorytm szeregownia i grupowania zadan
    Date: Wed, 18 Feb 2009 00:52:57 +0100
    Organization: http://onet.pl
    Lines: 33
    Message-ID: <gnfijt$utb$1@news.onet.pl>
    References: <gnfh16$moa$1@inews.gazeta.pl>
    NNTP-Posting-Host: c2-211.icpnet.pl
    Mime-Version: 1.0
    Content-Type: text/plain; charset=ISO-8859-2; format=flowed
    Content-Transfer-Encoding: 8bit
    X-Trace: news.onet.pl 1234914749 31659 62.21.2.211 (17 Feb 2009 23:52:29 GMT)
    X-Complaints-To: a...@o...pl
    NNTP-Posting-Date: Tue, 17 Feb 2009 23:52:29 +0000 (UTC)
    User-Agent: Thunderbird 2.0.0.19 (X11/20090105)
    In-Reply-To: <gnfh16$moa$1@inews.gazeta.pl>
    Xref: news-archive.icm.edu.pl pl.comp.programming:180998
    [ ukryj nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: