eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingalgorytm szeregownia i grupowania zadanRe: algorytm szeregownia i grupowania zadan
  • Path: news-archive.icm.edu.pl!newsfeed.gazeta.pl!newsfeed.pionier.net.pl!pwr.wroc.pl!
    news.wcss.wroc.pl!not-for-mail
    From: Mirek <p...@d...zind.ikem.pwr.wroc.pl>
    Newsgroups: pl.comp.programming
    Subject: Re: algorytm szeregownia i grupowania zadan
    Date: Wed, 18 Feb 2009 20:05:02 +0000 (UTC)
    Organization: WUT
    Lines: 51
    Message-ID: <gnhple$5ff$1@z-news.wcss.wroc.pl>
    References: <gnfh16$moa$1@inews.gazeta.pl>
    <2...@p...null.onet.pl.invalid>
    NNTP-Posting-Host: infrared.zind.ikem.pwr.wroc.pl
    X-Trace: z-news.wcss.wroc.pl 1234987502 5615 156.17.14.223 (18 Feb 2009 20:05:02 GMT)
    X-Complaints-To: a...@n...pwr.wroc.pl
    NNTP-Posting-Date: Wed, 18 Feb 2009 20:05:02 +0000 (UTC)
    User-Agent: tin/1.9.3-20080506 ("Dalintober") (UNIX) (Linux/2.6.26-1-686 (i686))
    Xref: news-archive.icm.edu.pl pl.comp.programming:181072
    [ ukryj nagłówki ]

    On śro, 18 lut 2009 17:11:19 in article
    news:<20090218171119.432b4f13.wojciech_mula@poczta.n
    ull.onet.pl.invalid>
    Wojciech Muła wrote:
    > "qweer" <cisrudlow[wytni]@o2.pl> wrote:
    >
    >> 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.
    >
    > Do pogrupowania zadań niezależnych: sortowanie topologiczne.
    (a)---------------- (b)====================

    ad a) trochę dziwne sformułowanie, raczej chodzi chyba tutaj o
    częściowy porządek czyli zbiór typu poset.

    ad b) też myślałem nad taką odpowiedzią, bo OP pisał

    # Troche malo zrozumiale sie wyrazilem. Chodzilo mi o to, ze
    # mamy sami wyznaczyc element (elemety, jezeli to jest grupa)
    # poczatowy. Zakladam, ze graf nie jest cykliczny.

    Czyli nie chodzi o TS (czyli zanurzenie posetu w porządek
    liniowy), a jemu potrzebny jest raczej podział posetu na
    warstwy: "Zakladam, ze ilosc maszyn jest nieograniczona".
    "Elementy początkowe" to nie problem, po prostu podzbiór zadań
    bez wcześniejszych zależności.

    Dalej jednak brak kryterium optymalności wymaganej prze OPa -
    nie zostało ono przecież sformułowane. Więc problem nie jest
    jednoznaczny. Popatrzmy na taki poset (relacje następtswa z
    góry na dół):

    a x
    /\ |
    | c |
    b | |
    | d |
    \/ y
    f

    - warstwa 1 to {a,x}, a co z warstwą drugą? Mamy możliwości {b}
    {c}, {y}, {b,y}, {c,y} oraz {b,c,y}. Którą wybrać?

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: