|
Ako sam ja dobro shvatio problem, trebalo bi ga formulirati tako da se nekim od pretrazivanja moze naci raspored obavljanja zadataka za dva radnika za koji je ukupno vrijeme trajanja posla minimalno. Pod tom pretpostavkom dalje rjesavam zadatak :)
Promatramo tijek izvodjenja posla u odredjenim vremenskim trenucima.
U trenutku kada oba radnika rade neki zadatak nista ne mozemo promijeniti (recimo da je u zadatku implicitno napisano da ako pocnemo obavljati neki zadatak onda taj zadatak trebamo obaviti do kraja prije nego pocnemo obavljati sljedeci - nema ostavljanja zadataka i ponovnog vracanja na njih), pa taj trenutak nije relevantan za problem trazenja (isto kako u zadatku s misionarima i kanibalima nismo gledali trenutak kada camac putuje preko rijeke).
Ostaju nam trenuci kada barem jedan od radnika ne radi nista. Koji podaci su relevanti za problem u tom trenutku? Svakako trebamo znati [b]koji su zadaci vec obavljeni[/b]. Osim toga, da bi znali koji je slijedeci relevanti trenutak moramo znati [b]koji zadatak radi drugi radnik[/b] i [b]koliko mu vremena treba da obavi taj zadatak[/b].
Dakle, stanje mozemo reprezentirati kao uredjenu petorku [tex](S, x_1, t_1, x_2, t_2)[/tex] gdje su [tex]S \subseteq \lbrace 1, \ldots, 9\rbrace[/tex] skup do sad obavljenih zadataka, [tex]x_1, x_2[/tex] trenutni zadaci koje obavljaju prvi, odnosno drugi radnik (ako [tex]i[/tex]-ti radnik ne radi niti jedan zadatak stavimo [tex]x_i = 0[/tex]), [tex]t_1, t_2[/tex] vremena preostala radnicima za obaviti odredjeni zadatak. Pri tome je barem jedan od [tex]x_1, x_2[/tex] jednak [tex]0[/tex].
Pocetno stanje je [tex](\emptyset, 0, 0, 0, 0)[/tex] (nista nije napravljeno, niti jedan radnik nista ne radi) a ciljno stanje [tex](\lbrace 1, \ldots, 9 \rbrace, 0, 0,0 ,0)[/tex] (sve je napravljeno, radnici mogu na pauzu :) ).
Jos treba defnirati prijelaze medju stanjima.
Pretpostavimo da smo u stanju [tex](S, x_1, t_1, x_2, t_2)[/tex].
Znamo da je barem jedan od [tex]x_i = 0[/tex]. Pretpostavimo da je to [tex]x_1[/tex], ako nije, onda je sigurno [tex]x_2 = 0[/tex] pa slucaj ide analogno, samo sa zamjenjenim ulogama radnika 1 i 2 (i ne treba paziti da su oba jednaka [tex]0[/tex]).
Sada treba dodijeliti sljedeci zadatak prvom radniku. Za svaki zadatak [tex]\hat{x}[/tex] koji jos nije obavljen i kojeg trenutno ne radi drugi radnik te ciji su prethodnici vec napravljeni ([tex]\hat{x} \in \lbrace 1, \ldots, 9 \rbrace \setminus (S \cup \lbrace x_2 \rbrace), P(\hat{x}) \subseteq S[/tex]) dobivamo novo stanje koje odgovara dodjeljivanju zadatka [tex]\hat{x}[/tex] prvom radniku.
Neka je [tex]\hat{t}[/tex] duljina trajanja zadatka [tex]\hat{x}[/tex].
Imamo sljedece mogucnosti:
1. [tex]\hat{t} > t_2[/tex] (ukljucuje i slucaj [tex]x_2 = 0, t_2 = 0[/tex])
U tom slucaju prvo zavrsava drugi radnik pa je sljedece stanje:
[dtex](S \cup \lbrace x_2 \rbrace, \hat{x}, \hat{t} - t_2, 0, 0)[/dtex]
a cijena prijelaza u to stanje je [tex]t_2[/tex].
Ako je [tex]x_2 = 0[/tex] sve ostaje isto, ali ne dodamo [tex]x_2[/tex] u [tex]S[/tex].
2. [tex] \hat{t} < t_2[/tex]
Prvo zavrsava prvi radnik. Sljedece stanje je:
[dtex](S \cup \lbrace \hat{x} \rbrace, 0, 0, x_2, t_2 - \hat{t})[/dtex]
a cijena prijelaza je [tex]\hat{t}[/tex].
3. [tex] \hat{t} = t_2[/tex]
Oba zavrsavaju u isto vrijeme. Sljedece stanje je:
[dtex](S \cup \lbrace \hat{x}, x_2 \rbrace, 0, 0, 0, 0)[/dtex]
cijena prijelaza [tex]t_2 = \hat{t}[/tex].
Jos ostaje mogucnost da 1. radnik nista ne radi nego prvo priceka drugog radnika, pa kao moguce sljedece stanje treba uzeti i [tex](S \cup {x_2}, 0, 0, 0, 0)[/tex] s cijenom prijelaza [tex]t_2[/tex].
Ako sam ja dobro shvatio problem, trebalo bi ga formulirati tako da se nekim od pretrazivanja moze naci raspored obavljanja zadataka za dva radnika za koji je ukupno vrijeme trajanja posla minimalno. Pod tom pretpostavkom dalje rjesavam zadatak 
Promatramo tijek izvodjenja posla u odredjenim vremenskim trenucima.
U trenutku kada oba radnika rade neki zadatak nista ne mozemo promijeniti (recimo da je u zadatku implicitno napisano da ako pocnemo obavljati neki zadatak onda taj zadatak trebamo obaviti do kraja prije nego pocnemo obavljati sljedeci - nema ostavljanja zadataka i ponovnog vracanja na njih), pa taj trenutak nije relevantan za problem trazenja (isto kako u zadatku s misionarima i kanibalima nismo gledali trenutak kada camac putuje preko rijeke).
Ostaju nam trenuci kada barem jedan od radnika ne radi nista. Koji podaci su relevanti za problem u tom trenutku? Svakako trebamo znati koji su zadaci vec obavljeni. Osim toga, da bi znali koji je slijedeci relevanti trenutak moramo znati koji zadatak radi drugi radnik i koliko mu vremena treba da obavi taj zadatak.
Dakle, stanje mozemo reprezentirati kao uredjenu petorku [tex](S, x_1, t_1, x_2, t_2)[/tex] gdje su [tex]S \subseteq \lbrace 1, \ldots, 9\rbrace[/tex] skup do sad obavljenih zadataka, [tex]x_1, x_2[/tex] trenutni zadaci koje obavljaju prvi, odnosno drugi radnik (ako [tex]i[/tex]-ti radnik ne radi niti jedan zadatak stavimo [tex]x_i = 0[/tex]), [tex]t_1, t_2[/tex] vremena preostala radnicima za obaviti odredjeni zadatak. Pri tome je barem jedan od [tex]x_1, x_2[/tex] jednak [tex]0[/tex].
Pocetno stanje je [tex](\emptyset, 0, 0, 0, 0)[/tex] (nista nije napravljeno, niti jedan radnik nista ne radi) a ciljno stanje [tex](\lbrace 1, \ldots, 9 \rbrace, 0, 0,0 ,0)[/tex] (sve je napravljeno, radnici mogu na pauzu ).
Jos treba defnirati prijelaze medju stanjima.
Pretpostavimo da smo u stanju [tex](S, x_1, t_1, x_2, t_2)[/tex].
Znamo da je barem jedan od [tex]x_i = 0[/tex]. Pretpostavimo da je to [tex]x_1[/tex], ako nije, onda je sigurno [tex]x_2 = 0[/tex] pa slucaj ide analogno, samo sa zamjenjenim ulogama radnika 1 i 2 (i ne treba paziti da su oba jednaka [tex]0[/tex]).
Sada treba dodijeliti sljedeci zadatak prvom radniku. Za svaki zadatak [tex]\hat{x}[/tex] koji jos nije obavljen i kojeg trenutno ne radi drugi radnik te ciji su prethodnici vec napravljeni ([tex]\hat{x} \in \lbrace 1, \ldots, 9 \rbrace \setminus (S \cup \lbrace x_2 \rbrace), P(\hat{x}) \subseteq S[/tex]) dobivamo novo stanje koje odgovara dodjeljivanju zadatka [tex]\hat{x}[/tex] prvom radniku.
Neka je [tex]\hat{t}[/tex] duljina trajanja zadatka [tex]\hat{x}[/tex].
Imamo sljedece mogucnosti:
1. [tex]\hat{t} > t_2[/tex] (ukljucuje i slucaj [tex]x_2 = 0, t_2 = 0[/tex])
U tom slucaju prvo zavrsava drugi radnik pa je sljedece stanje:
[dtex](S \cup \lbrace x_2 \rbrace, \hat{x}, \hat{t} - t_2, 0, 0)[/dtex]
a cijena prijelaza u to stanje je [tex]t_2[/tex].
Ako je [tex]x_2 = 0[/tex] sve ostaje isto, ali ne dodamo [tex]x_2[/tex] u [tex]S[/tex].
2. [tex] \hat{t} < t_2[/tex]
Prvo zavrsava prvi radnik. Sljedece stanje je:
[dtex](S \cup \lbrace \hat{x} \rbrace, 0, 0, x_2, t_2 - \hat{t})[/dtex]
a cijena prijelaza je [tex]\hat{t}[/tex].
3. [tex] \hat{t} = t_2[/tex]
Oba zavrsavaju u isto vrijeme. Sljedece stanje je:
[dtex](S \cup \lbrace \hat{x}, x_2 \rbrace, 0, 0, 0, 0)[/dtex]
cijena prijelaza [tex]t_2 = \hat{t}[/tex].
Jos ostaje mogucnost da 1. radnik nista ne radi nego prvo priceka drugog radnika, pa kao moguce sljedece stanje treba uzeti i [tex](S \cup {x_2}, 0, 0, 0, 0)[/tex] s cijenom prijelaza [tex]t_2[/tex].
|
