"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.

w.

do góry

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

do góry

On Wed, 18 Feb 2009 20:05:02 +0000 (UTC), Mirek
<p...@d...zind.ikem.pwr.wroc.pl> wrote:

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


W zaleznosci od tego jak Oryginalny Pytacz sformulowal BY problem.
Poneiwaz problemu nei sformulowal, kazda (czytaj: jakakolwiek)
odpowiedz jest dobra

A.L.

do góry

> Jeżeli masz określone różne długości zadań to zamieniasz listę na listę
> posortowaną wg długości (set) i zawsze zdejmujesz (wszystkie)
> najkrótsze, uaktualniasz wskazywane przez nie, jeżeli wyjdzie jakieś 0
> to dorzucasz do seta. Pracujesz póki set jest niepusty. A kolejny zestaw
> się pojawia zawsze gdy jakieś zadanie z seta wywaliłeś.

Ok. dzieki. Z pospiechu nie przeczytalem dokladnie odpowiedzi, za co przepraszam.

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

do góry

> Jak na moj rozum to on niespecjalnei wie co chce rozwiazac...

Czlowieku, czy Ty sie czyjesz, jakos niedowartosciowany? Nie masz nic
ciekawego i kontruktywnego do powiedzenia, to sie nie odzywaj. Zachowanie
godne 15-to latka. Mysle, ze dokaldnie opisalem, jakie sa zalozenia. Zajecia u
Pana Weglarza itd., a szczegolnie egzaminy, po tylu latach juz wyrzucilem z
pamieci.
Pytam sie o najprostszy, mozliwy przypadek i wskazanie odpowiednich,
istniejacych algorytmow. Gdybym mial czas i, az tak duze checi, to z wielka
przyjemnoscia przegladnalbym wszystkie wymienione ksiazki.
..Wiec koles wyluzuje, bo nie jestem Twoim znajomym, zebys prowadzil ze mna
rozmowe na tym poziomie.


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

do góry

> >"Naj..." tutaj oznacza, ze algorytm jest najbardziej skuteczny (lub
> >najskuteczniejszy) w rozwiazaniu okreslonego problemu.
>
> I to właśnie oznacza "optymalny".


Tutaj sie zgodze, poprawnym jest wywalenie tego "naj". Algorytm moze byc
optymalny w kontekscie jednego problemu, ale w kontekscie innego juz nie. O to
mi wlasnie chodzilo :).

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

do góry

On Wed, 18 Feb 2009 22:48:52 +0000 (UTC), " qweer"
<c...@g...pl> wrote:

>> Jak na moj rozum to on niespecjalnei wie co chce rozwiazac...
>
>Czlowieku, czy Ty sie czyjesz, jakos niedowartosciowany? Nie masz nic
>ciekawego i kontruktywnego do powiedzenia, to sie nie odzywaj. Zachowanie
>godne 15-to latka. Mysle, ze dokaldnie opisalem, jakie sa zalozenia. Zajecia u
>Pana Weglarza itd., a szczegolnie egzaminy, po tylu latach juz wyrzucilem z
>pamieci.

Wlasnie widac. I tego skutki widac tez.

>Pytam sie o najprostszy, mozliwy przypadek i wskazanie odpowiednich,
>istniejacych algorytmow. Gdybym mial czas i, az tak duze checi, to z wielka
>przyjemnoscia przegladnalbym wszystkie wymienione ksiazki.
>..Wiec koles wyluzuje, bo nie jestem Twoim znajomym, zebys prowadzil ze mna
>rozmowe na tym poziomie.

Niestety, zadnych zalozen nie opisales, uskuteczniles tylko machanei
rekami. A matematyka to nei machanie rekami. Aby problem sie dalo
rozwiazac, tzreba go najpierw sformulowac. Twoje "sformulowanie" to
belkot w czystej postaci

A.L.

do góry

On Wed, 18 Feb 2009 22:56:06 +0000 (UTC), " qweer"
<c...@g...pl> wrote:

>
>> >"Naj..." tutaj oznacza, ze algorytm jest najbardziej skuteczny (lub
>> >najskuteczniejszy) w rozwiazaniu okreslonego problemu.
>>
>> I to właśnie oznacza "optymalny".
>
>
>Tutaj sie zgodze, poprawnym jest wywalenie tego "naj". Algorytm moze byc
>optymalny w kontekscie jednego problemu, ale w kontekscie innego juz nie. O to
>mi wlasnie chodzilo :).

Ale zeby mowic o "optymalnosci", tzreba jeszcze powiedziec OPTYMALNOSC
W SENSIE CZEGO. Nie ma "optymalnowci tak w ogole"

A.L.

do góry

On 18 Lut, 23:48, " qweer" <c...@g...pl> wrote:
> > Jak na moj rozum to on niespecjalnei wie co chce rozwiazac...
>
> Czlowieku, czy Ty sie czyjesz, jakos niedowartosciowany? Nie masz nic
> ciekawego i kontruktywnego do powiedzenia, to sie nie odzywaj. Zachowanie
Twój problem polega na tym, że WYDAJE Ci się, że dobrze zadałeś
pytanie. A.L. widząc, że Twoje pytanie jest mętne, spróbował Ci
pomóc w sfomułowaniu go w sposób na tyle sfomalizowany aby
można było udzielić sensownej odpowiedzi.

> godne 15-to latka. Mysle, ze dokaldnie opisalem, jakie sa zalozenia. Zajecia u
> Pana Weglarza itd., a szczegolnie egzaminy, po tylu latach juz wyrzucilem z
> pamieci.
> Pytam sie o najprostszy, mozliwy przypadek i wskazanie odpowiednich,
> istniejacych algorytmow. Gdybym mial czas i, az tak duze checi, to z wielka
> przyjemnoscia przegladnalbym wszystkie wymienione ksiazki.
Czyli zostałeś błędnie wyznaczony do rozwiązania tego problemu.
Problem szeregowania zadań wymaga przeglądnięcia wielu książek
i zachowania w pamięci wykładów z czasów studiów.

Pozdrawiam,
Wit

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.

Jezeli dobrze rozumiem, to rozwiazanie wymaga dosc duzej liczby iteracji
(pewnie da sie wykonac w sposobie mojego myslenia, jakas optymalizacje ;) ).
Problem jest taki, ze wszelkie powiazania pomiedzy obiektami mam na oddzielnej
liscie (jest to niezalezne ode mnie). Ja pomyslem, chyba troszeczke inaczej
(?). Posortowac zadania listowo (po prostu zmieniajac ich kolejnosc na liscie,
wg. ustalonych warunkow, co tez nie jest zbyt optymalne, ale przynajmniej
proste ;) ), co uda sie zrobic w jednym przejsciu przez liste. W 2-gim
przejsciu sprawdzic czy zadanie zalezy od bezposrednio go poprzedzajacego,
jezeli nie, to jest to ta sama grupa. Pewnie nie jest to optymalne dla tego
problemu (nie wiem, czy ma wieksza zlozonosc, zaproponowana przez Ciebie), ale
jak dla mnie proste. Dziekuje za pomoc.

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

do góry