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ć?