Đăng ký Đăng nhập
Trang chủ Công nghệ thông tin Kỹ thuật lập trình Ungdungmotsothuattoanvaogiaicacbaitoanxeplichcongviec...

Tài liệu Ungdungmotsothuattoanvaogiaicacbaitoanxeplichcongviec

.DOC
30
376
108

Mô tả:

môc lôc PhÇn i. më ®Çu 1. Lý do chän ®Ò tµi 2. Môc ®Ých cña s¸ng kiÕn kinh nghiÖm 3. §èi tîng vµ ph¹m vi nghiªn cøu 4. C¬ së khoa häc cña ®Ò tµi PhÇn ii. néi dung Ch¬ng 1. øng dông mét sè thuËt to¸n, ®Þnh lÝ vµo viÖc gi¶i c¸c bµi to¸n vÒ xÕp lÞch 1. XÐt bµi to¸n xÕp lÞch 2. øng dông mét sè thuËt to¸n vµo gi¶i c¸c bµi to¸n xÕp lÞch a. ThuËt to¸n Johnson b. Ph¬ng ph¸p Heuristic. c. Ph¬ng ph¸p duyÖt cã ®Æt cËn d. Quy ho¹ch ®éng Ch¬ng 2. Mét sè bµi tËp vÒ s¾p xÕp lÞch PhÇn iii. kÕt luËn vµ kiÕn nghÞ 1 phÇn më ®Çu 1. Lý do chän ®Ò tµi. Bµi to¸n xÕp lÞch c«ng viÖc n¶y sinh tõ nhiÒu vÊn ®Ò thùc tÕ kh¸c nhau: giao viÖc, gia c«ng c¸c chi tiÕt m¸y, ®ãng gãi hµng hãa vµo mét hoÆc nhiÒu thïng, xÕp lÞch thi ®Êu, lÞch häc tËp, hµnh tr×nh du lÞch, chän ®èi tîng vµ ph¬ng ¸n thi c«ng, bµi to¸n vËn t¶i xÕp hµng, ®iÒu hµnh xe, chän ®Þa ®iÓm x©y dùng nhµ m¸y, kÕ ho¹ch s¶n xuÊt c¸c s¶n phÈm, Õp thêi gian cho phÐp (chØ cã thÓ chän ra ph¬ng ¸n tíng ®èi thÝch hîp víi ®iÒu kiÖn d÷ liÖu cô thÓ nµo ®ã), h¬n n÷a nhiÒu bµi díi d¹ng tæng qu¸t cßn ®îc xÕp vµo líp bµi to¸n cßn h¹n chÕ ë mét sè bµi tËp gÆp trong k× thi häc sinh giái Tin häc tríc ®©y vµ nªu mét sè c¸ch gi¶i thÝch hîp. Qua viÖc giíi thiÖu c¸c bµi tËp t«i cè g¾ng minh häa mét sè ph¬ng ph¸p thêng gÆp nhÊt trong bµi to¸n xÕp lÞch LÝ do chñ yÕu ®Ó chän c¸c ph¬ng ph¸p lµ c©n nh¾c tíi møc ®é tiÕp thu cña häc sinh phæ th«ng trung häc. 2. Môc ®Ých cña s¸ng kiÕn kinh nghiÖm. - øng dông c¸c thuËt to¸n ®Ó gi¶i c¸c bµi to¸n vÒ xÕp lÞch, su tÇm mét sè bµi to¸n liªn quan ®Õn xÕp lÞch. - §a vµo båi dìng häc sinh ®i thi häc sinh giái tØnh. - §a vµo tµi liÖu cña tæ chuyªn m«n. 3. §èi tîng vµ ph¹m vi nghiªn cøu: 3.1 §èi tîng nghiªn cøu: - C¸c bµi to¸n vÒ xÕp lÞch ®Ó gi¶ng d¹y cho häc sinh ®i thi häc sinh giái tØnh. 3.2 Ph¹m vi nghiªn cøu: - Víi c¸c thuËt to¸n, ®Þnh lÝ, c¸c bµi to¸n, t«i ¸p dông vµo d¹y häc sinh «n thi häc sinh giái tØnh. 4. C¬ së khoa häc cña ®Ò tµi: 4.1 C¬ së lÝ luËn: C¸c bµi to¸n vÒ xÕp lÞch ®îc øng dông rÊt nhiÒu trong thùc tiÔn, víi sù ph¸t triÓn cña CNTT nh hiÖn nay th× viÖc ¸p dông CNTT vµo c¸c c¬ quan tæ chøc lµ mét viÖc lµm ®óng ®¾n, mµ c«ng viÖc xÕp lÞch rÊt phæ biÕn 4.2 C¬ së thùc tiÔn: - §©y lµ bµi to¸n cã nhiÒu øng dông trong thùc tiÔn, tõ nh÷ng bµi s¾p xÕp lÞch c«ng viÖc ®¬n gi¶n ®Õn c¸c c«ng viÖc phøc t¹p h¬n nh xÕp thêi khãa biÓu cña mét trêng häc,… 2 Néi dung s¸ng kiÕn kinh nghiÖm Ch¬ng 1. øng dông mét sè thuËt to¸n, ®Þnh lÝ vµo viÖc gi¶i c¸c bµi to¸n vÒ xÕp lÞch 1. XÐt bµi to¸n xÕp lÞch sau: Gi¶ sö trong mét phiªn lµm viÖc tõ thêi ®iÓm 0 ®Õn thêi ®iÓm T=8640000, mét trung t©m tÝnh to¸n ph¶i thùc hiÖn N ch¬ng tr×nh, ch¬ng tr×nh i thùc hiÖn tõ thêi ®iÓm a[i] ®Õn thêi ®iÓm b[i], 0 a[i ] b[i]  T . Cho tríc mét ®o¹n thêi gian (P1, Q1). H·y xÐt xem liÖu t¹i mäi thêi ®iÓm cña ®o¹n ®ã lu«n cã ch¬ng tr×nh ch¹y hay kh«ng? Cho tríc mét ®o¹n thêi gian (R1, S1). H·y xÐt xem liÖu t¹i mäi thêi ®iÓm cña ®o¹n ®ã lu«n kh«ng cã ch¬ng tr×nh nµo ch¹y hay kh«ng? H·y t×m ®o¹n thêi gian (P, Q) dµi nhÊt sao cho t¹i mäi ®iÓm cña nã lu«n cã ch¬ng tr×nh ch¹y. H·y t×m ®o¹n thêi gian (R, S) dµi nhÊt sao cho t¹i mäi ®iÓm cña nã ®Òu kh«ng cã ch¬ng tr×nh nµo ch¹y. D÷ liÖu vµo ®îc cho bëi file v¨n b¶n lichtruc.inp cã cÊu tróc - Dßng thø nhÊt ghi sè nguyªn d¬ng N 200 . - Dßng thø i+1 (1 i  N ) ghi hai sè nguyªn kh«ng ©m A[i] vµ B[i] - Dßng thø N+2 ghi hai sè nguyªn kh«ng ©m P1, Q1 ( P1 Q1 ) - Dßng thø N+3 ghi hai sè nguyªn kh«ng ©m R1, S1 ( R1 S1 ) D÷ liÖu ra ghi vµo file v¨n b¶n lichtruc.out cã cÊu tróc - Dßng ®Çu tiªn ghi 1 hoÆc 0 tïy thuéc kÕt qu¶ cô thÓ (t×m ®îc ghi sè 1, kh«ng t×m ®îc ghi sè 0). - Dßng thø hai còng ghi 1 hoÆc 0 theo nghÜa trªn. - Dßng thø ba ghi hai sè P, Q - Dßng thø t ghi hai sè R, S. VÝ dô: LICHTRUC.INP LICHTRUC.OUT 5 1 1000 10000 0 2000 20000 8000000 8500000 20000 100000 500001 7999999 200000 500000 8000000 8500000 1000 100000 0 1000 3 NhËn xÐt: §Ó gi¶i bµi to¸n nµy th× ta cã thÓ dïng m¶ng mét chiÒu A (mçi phÇn tö lµ mét b¶n ghi gåm 2 trêng: thêi ®iÓm ®Çu vµ thêi ®iÓm cuèi cña mçi ch¬ng tr×nh). S¾p m¶ng A theo thêi ®iÓm ®Çu cña mçi ch¬ng tr×nh. Sau ®ã duyÖt m¶ng A ®Ó t¹o m¶ng B (cïng kiÓu víi A) lu c¸c ®o¹n gåm c¸c thêi ®iÓm liªn tiÕp cã ch¬ng tr×nh, vµ t¹o m¶ng C ®Ó lu c¸c ®o¹n gåm c¸c thêi ®iÓm liªn tiÕp kh«ng cã ch¬ng tr×nh nµo. Dùa vµo m¶ng B vµ C dÉn ra kÕt luËn thÝch hîp. Ch¬ng tr×nh const T=8640000; max=1000; fi='lichtruc.inp'; fo='lichtruc.out'; type re=record d,c:longint end; m1=array[1..max] of re; var a,b,c:m1; f:text; n,sd,sr,i,j:integer; p,q,r,s:longint; procedure readfile; var i:integer; g:text; begin assign(g,fi); reset(g); readln(g,n); for i:=1 to n do begin read(g,a[i].d,a[i].c); readln(g); end; readln(g,p,q); readln(g,r,s); close(g); end; procedure sort; var i,j:integer; tgd,tgc:longint; begin for i:=1 to n -1 do for j:=i+1 to n do if a[i].d>a[j].d then begin tgd:=a[i].d; a[i].d:=a[j].d; a[j].d:=tgd; tgc:=a[i].c; a[i].c:=a[j].c; a[j].c:=tgc; end; end; procedure Create_b_c; var i,j:integer; last:longint; begin sd:=1; i:=1; 4 b[sd].d:=a[i].d; last:=a[i].c; while ilast+1 then begin b[sd].c:=last; inc(sd); b[sd].d:=a[i+1].d; last:=a[i+1].c; inc(i); end else begin if a[i+1].c > last then last:=a[i+1].c; inc(i); end; end; b[sd].c:=last; sr:=1; if b[1].d<>0 then begin c[sr].d:=0; c[sr].c:=b[1].d-1; inc(sr); end; i:=2; while i<=sd do begin c[sr].d:=b[i-1].c+1; c[sr].c:=b[i].d-1; inc(sr); inc(i); end; if b[sd].c=q) then begin writeln(f,1); exit; end; writeln(f,0); end; procedure caub; var i:integer; begin for i:=1 to sr do if (c[i].d<=r) and (c[i].c>=s) then begin writeln(f,1); exit; 5 end; writeln(f,0); end; procedure cauc; var ld,lc,lmax:longint; i:integer; begin lmax:=-1; for i:=1 to sd do if (b[i].c-b[i].d)>lmax then begin lmax:=b[i].c-b[i].d; ld:=b[i].d; lc:=b[i].c; end; writeln(f,ld,' ',lc); end; procedure caud; var ld,lc,lmax:longint; i:integer; begin lmax:=-1; for i:=1 to sr do if (c[i].c-c[i].d)>lmax then begin ld:=c[i].d; lc:=c[i].c; lmax:=c[i].c-c[i].d; end; writeln(f,ld,' ',lc); end; begin assign(f,fo); rewrite(f); readfile; sort; create_b_c; caua; caub; cauc; caud; close(f); end. 2. øng dông mét sè thuËt to¸n vµo gi¶i c¸c bµi to¸n xÕp lÞch a. Dïng thuËt to¸n Johnson VÝ dô: LËp lÞch gia c«ng trªn hai m¸y Mét s¶n phÈm gåm N chi tiÕt, mçi chi tiÕt ph¶i gia c«ng lÇn lît trªn hai m¸y A vµ B (A tríc, B sau). Thêi gian thùc hiÖn chi tiÕt i trªn m¸y A lµ A i, trªn m¸y B lµ Bi (i=1, 2, …, N). H·y xÕp lÞch hoµn thµnh s¶n phÈm víi thêi gian Ýt nhÊt. HiÖn lÞch vµ thêi gian hoµn thµnh. D÷ liÖu vµo tõ file giacong.inp cã cÊu tróc: - Dßng ®Çu tiªn lµ sè nguyªn d¬ng N 6 - N dßng tiÕp theo: dßng i+1 lµ hai sè Ai vµ Bi. D÷ liÖu ra ghi vµo file giacong.out cã cÊu tróc: - Dßng ®Çu tiªn lµ thêi gian Ýt nhÊt thùc hiÖn N c«ng viÖc - Dßng thø hai lÇn lît ghi sè hiÖu cña N c«ng viÖc thùc hiÖn theo lÞch tèi u. VÝ dô: giacong.inp 5 33 43 62 57 63 §Ó gi¶i bµi to¸n trªn ta xÐt ®Þnh lÝ sau: * §Þnh lÝ Johnson giacong.out 26 14253 Ph¬ng ¸n v={v[1], v[2],…,v[N]} lÇn lît thùc hiÖn c¸c chi tiÕt v[1], v[2], …, v[N] víi thêi gian nhá nhÊt khi vµ chØ khi Min{Av[k], Bv[k+1]} {Bv[k], Av[k+1]} k 1, 2,..., n  1, trong ®ã Av[k] lµ thêi gian thùc hiÖn v[k] vµ A[k+1] lµ thêi gian thùc hiÖn v[k+1] trªn m¸y A, cßn Bv[k] vµ Bv[k+1] t¬ng øng lµ thêi gian thùc hiÖn v[k] vµ v[k+1] trªn m¸y B. Tõ ®Þnh lÝ trªn cã thÓ ®a ra thuËt to¸n ®Ó gi¶i bµi to¸n trªn, vµ chøng minh sù ®óng ®¾n cña thuËt to¸n sau: * ThuËt to¸n: + Bíc 1: Chia c¸c chi tiÕt thµnh hai nhãm: Nhãm 1: gåm c¸c chi tiÕt i mµ Ai Bi . Nhãm 2: gåm c¸c chi tiÕt i mµ Ai  Bi + Bíc 2: XÕp nhãm 1 theo chiÒu t¨ng cña Ai, xÕp nhãm 2 theo chiÒu gi¶m cña Bi. + Bíc 3: Nèi nhãm 2 vµo sau nhãm 1 * Chøng minh: NÕu c¸c chi tiÕt v[k] vµ v[k+1] cïng thuéc nhãm 1 th× Bv[ k 1]  Av[ k 1]  Av[ k ] nªn Min{Av[k],Bv[k+1]}=Av[k], mÆt kh¸c Av[ k ]  Av[ k 1] , Av[ k ] Bv[ k ] , nªn Av[ k ] Min{Bv[ k ] , Av[ k 1]} VËy Min {Av[k],Bv[k+1]} Min {Bv[k], Av[k+1]} NÕu chi tiÕt v[k] vµ v[k+1] cïng thuéc nhãm 2 th× Bv[ k 1] Bv[ k ]  Av[ k ] nªn Min {A[k], Bv[k]}=Bv[k+1] mÆt kh¸c Bv[ k ] Bv[ k 1] , Av[ k 1] Bv[ k 1] nªn Min {Bv[k], Av[k+1]}  Bv[k+1]. VËy Min {Av[k], Bv[k]}  Min {Bv[k], Av[k+1]}. NÕu chi tiÕt v[k] thuéc nhãm 1 vµ chi tiÕt v[k+1] thuéc nhãm 2 th×: 7 Min {Av[k], Bv[k+1]}  Min {Bv[k], Av[k+1]} do Av[k] Bv[k] vµ Bv[k+1] < Av[k+1]. cã thÓ thùc hiÖn cô thÓ nh sau: X©y dùng dÇn d·y kÕt qu¶ tõ hai ®Çu dån vµo gi÷a (dïng m¶ng mét chiÒu KQ vµ hai biÕn: ®Çu vµ cuèi). 1. G¸n gi¸ trÞ ban ®Çu: ®Çu:=0; cuèi:=N+1; 2. Thùc hiÖn vßng lÆp: trong khi ®Çu < cuèi a. T×m chi tiÕt i cha lµm, cã thêi gian thùc hiÖn nhá nhÊt. b. NÕu i thuéc d·y A th× t¨ng gi¸ trÞ biÕn ®Çu, g¸n KQ[®Çu]:=i, nÕu i thuéc d·y B th× gi¶m gi¸ trÞ biÕn cuèi, g¸n KQ[cuèi]:=i; 3. §¸nh dÊu ®· lµm chi tiÕt i. Cµi ®Æt ch¬ng tr×nh: const max=100; fi='giacong.inp'; fo='giacong.out'; type m1=array[1..2,1..max] of integer; mkq=array[1..max] of byte; mdd=array[1..max] of boolean; var a:m1; kq:mkq; dd:mdd; n:byte; g,f:text; procedure readfile; var i:byte; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readln(f,a[1,i],a[2,i]); close(f); end; function chitietmin(var may:byte):byte; var i,j,chitiet:byte; lmin:integer; begin lmin:=maxint; for i:=1 to 2 do for j:=n downto 1 do if not dd[j] then if (a[i,j]b then max2:=a else max2:=b; end; procedure tinh; var i,j:byte; t1, t2:integer; begin t1:=0; t2:=0; for i:=1 to n do begin t1:=t1+a[1,kq[i]]; t2:=max2(t1,t2)+a[2,kq[i]]; end; writeln(g,t2); end; begin assign(g,fo); rewrite(g); readfile; johnson; tinh; writefile; close(g);; end. b. XÕp lÞch theo heuristic - VÒ thuËt gi¶i heuristic NhiÒu bµi to¸n xÕp lÞch cã d÷ liÖu vµo lín kh«ng thÓ ¸p dông thuËt to¸n cho lêi gi¶i tèi u trong thêi gian cho phÐp, trong nh÷ng trêng hîp ®ã chóng thêng ®îc gi¶i b»ng ph¬ng ph¸p heuristic (mét chiÕn thuËt t×m kiÕm hîp lÝ nµo ®ã) ®Ó cã lêi gi¶i t¬ng ®èi tèi u thùc hiÖn trong thêi gian cho phÐp. Bµi to¸n xÕp lÞch thêng cã 2 yªu cÇu sau: 9 - Yªu cÇu lo¹i 1: gäi lµ yªu cÇu b¾t buéc (néi dung cô thÓ tïy theo tõng bµi to¸n) lµ yªu cÇu ph¶i ®¹t ®îc, nÕu kh«ng ®¹t ®îc th× coi nh lêi gi¶i kh«ng ®îc chÊp nhËn. VÝ dô: yªu cÇu ph¶i xÕp hÕt tÊt c¶ c«ng viÖc, hoÆc ph¶i xÕp xong tríc mét thêi h¹n cho tríc nµo ®ã, hoÆc mçi c«ng viÖc ph¶i tu©n thñ yªu cÇu vÒ thêi gian b¾t ®Çu, thêi gian kÕt thóc, thêi gian hoµn thµnh cña c«ng viÖc Êy, hoÆc c«ng viÖc nµy ph¶i ®îc thùc hiÖn tríc c«ng viÖc kia,… - Yªu cÇu lo¹i 2: Lµ yªu cÇu cã thÓ nh©n nhîng phÇn nµo ®ã (néi dung cô thÓ tïy theo tõng bµi to¸n). VÝ dô: Cho phÐp tæng chi phÝ (hoÆc tæng thêi gian) thùc hiÖn xong c¸c c«ng viÖc ®¹t gi¸ trÞ cµng thÊp cµng tèt (hoÆc xong cµng sím cµng tèt). ChÝnh nhê sù nh©n nhîng nµy mµ ta cã thÓ ®Ò xuÊt ra nh÷ng c¸ch s¾p xÕp mét hoÆc mét nhãm c«ng viÖc tiÕp theo dÔ dµng h¬n, ®ã chÝnh lµ c¸c “heuristic”. ThuËt gi¶i heuristic cã nh÷ng ®Æc ®iÓm sau: - Cho lêi gi¶i gÇn tèi u, thêi gian thùc hiÖn ch¬ng tr×nh lµ hîp lÝ vµ cã thÓ tæ chøc d÷ liÖu ®Ó thùc hiÖn ch¬ng tr×nh. - Cã thÓ thay ®æi mét vµi heuristic trong qu¸ tr×nh gi¶i ®Ó thÝch øng víi c¸c bé d÷ liÖu kh¸c nhau, kÕt hîp so s¸nh kÕt qu¶ thùc hiÖn c¸c heuristic kh¸c nhau vµ gi÷ l¹i kÕt qu¶ tèt h¬n. VÝ dô: Chia N viÖc cho M m¸y Cho N c«ng viÖc, c«ng viÖc i hoµn thµnh trong thêi gian t i. C¸c c«ng viÖc ®îc thùc hiÖn trªn M m¸y (c«ng suÊt nh nhau, mçi m¸y ®Òu cã thÓ thùc hiÖn ®îc c«ng viÖc bÊt k× trong N c«ng viÖc) mçi c«ng viÖc ®îc lµm liªn tôc trªn mét m¸y cho ®Õn khi xong. H·y tæ chøc m¸y thùc hiÖn ®ñ N c«ng viÖc sao cho thêi gian hoµn thµnh cµng nhá cµng tèt. D÷ liÖu vµo tõ file chia.inp cã cÊu tróc: - Dßng ®Çu lµ hai sè N vµ M. - Dßng tiÕp theo lµ N sè t1, t2, …, tN. D÷ liÖu ra ghi vµo file chia.out cã cÊu tróc: - Dßng ®Çu lµ thêi gian hoµn thµnh N c«ng viÖc. - M dßng sau: dßng i+1 ghi sè hiÖu c¸c c«ng viÖc thùc hiÖn trªn m¸y i Test: chia.inp 63 258151 chia.out 8 3 214 56 10 Ph©n tÝch bµi to¸n: Víi bµi to¸n trªn ta cã thÓ thùc hiÖn mét heuristic sau: 1. S¾p xÕp c«ng viÖc theo thø tù thêi gian hoµn thµnh gi¶m dÇn. 2. LÊy M c«ng viÖc ®Çu ph©n c«ng cho M m¸y, mçi m¸y mét viÖc. Gäi maxT lµ thêi gian lín nhÊt cña M c«ng viÖc nµy. 3. Vßng lÆp 1 + Vßng lÆp 2: Chän m¸y cã thêi gian ®· lµm nhá h¬n maxT, xÕp thªm mét c«ng viÖc míi cho m¸y nµy (c«ng viÖc lÊy theo thø tù ®· s¾p) LÆp cho ®Õn khi nÕu thªm c«ng viÖc mêi th× kh«ng cßn mµy nµo cã tæng thêi gian dù kiÕn ®· lµm cña nã nhá h¬n maxT. {HÕt vßng lÆp 2}. + T×m mét m¸y cã thêi gian ®· lµm nhá nhÊt vµ ph©n c«ng c«ng viÖc tiÕp theo cho m¸y nµy, thay ®æi l¹i gi¸ trÞ cña maxT. LÆp cho ®Õn khi hÕt viÖc {HÕt vßng lÆp 1} Cã 6 c«ng viÖc thùc hiÖn trªn 3 m¸y c«ng suÊt nh nhau: Thêi gian thùc hiÖn c¸c c«ng viÖc cho trong b¶ng sau: cv1 cv2 cv3 cv4 cv5 cv6 2 5 8 1 5 1 Ta xÕp theo thø tù gi¶m dÇn cña thêi gian thùc hiÖn cv3 cv2 cv5 cv1 cv4 cv6 8 5 5 2 1 1 B©y giê ta cã thÓ ph©n c«ng c«ng viÖc cho c¸c m¸y nh sau: LÇn ph©n c«ng thø nhÊt: M¸y 1: cv3=8 ®¬n vÞ thêi gian M¸y 2: cv2=5 ®¬n vÞ thêi gian M¸y 3: cv5=5 ®¬n vÞ thêi gian Nh vËy m¸y lµm c«ng viÖc cã thêi gian lµm lín nhÊt lµ M¸y 1 víi cv3=8 ®¬n vÞ thêi gian. LÇn ph©n c«ng thø hai: th× ta ph¶i t×m m¸y nµo cã thêi gian ®· lµm nhá nhÊt th× ta nhËn ®îc kÕt qu¶ lµ M¸y 2 vµ M¸y 3 M¸y 2: thªm cv1+cv4  tæng céng 8 ®¬n vÞ thêi gian M¸y 3: thªm cv6  tæng céng 6 ®¬n vÞ thêi gian Víi c¸ch ph©n c«ng nµy ta thÊy khi m¸y 1 lµm xong cv3 th× m¸y 2 lµm xong cv5+cv1+cv4, m¸y 3 lµm xong cv5+cv6  Thêi gian hoµn thµnh lµ 8 ®¬n vÞ thêi gian Ch¬ng tr×nh cµi ®Æt trªn Pascal uses crt; const maxn=100; 11 fi='chia.inp'; fo='chia.out'; type m1=array[1..maxn] of longint; var t,id:m1; p:m1; n,m,i:integer; maxT:longint; may:m1; procedure readfile; var i:integer; f:text; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to n do begin read(f,t[i]);id[i]:=i; end; close(f); end; procedure sort; var i,j:integer; tg:longint; begin for i:=1 to n -1 do for j:=i+1 to n do if t[i]maxT then maxT:=t[i];{Thời gian lớn nhất hoàn thành công việc} end; inc(i); while i<=n do begin ok:=false; for j:=1 to m do begin if i>n then break; while (may[j]+t[i]<=maxT) do begin ok:=true; may[j]:=may[j]+t[i]; p[i]:=j;{Giao công việc i cho máy j} inc(i); writeln(ok,j); end; end; if not ok then if i<=n then begin j:=tim_may_min; may[j]:=may[j]+t[i]; p[i]:=j; if may[j]>maxT then maxT:=may[j]; inc(i); end; end; end; begin readfile; sort; chia; writefile; readln end. c. Ph¬ng ph¸p duyÖt cã ®Æt cËn 13 Trong ph¬ng ph¸p nµy nÕu chän cËn hîp lÝ víi thêi gian cho phÐp th× lêi gi¶i thêng ®¹t kÕt qu¶ t¬ng ®èi tèi u. Vµi lu ý khi ¸p dông: - Th¬ng s¾p t¨ng hoÆc gi¶m bé d÷ liÖu theo mét khãa gi¸ trÞ nµo ®ã tríc khi duyÖt. - T×m cËn lµ ®iÒu kiÖn cÇn ®Ó khi duyÖt tr¸nh ®i vµo c¸c nh¸nh kh«ng dÉn tíi ®Ých. CËn cµng chÆt chÏ cµng nhanh chãng tíi kÕt qu¶, nhng cÇn ph©n tÝch kÜ ®Ó tr¸nh trêng hîp bÞ mÊt nghiÖm do ®Æt cËn chÆt chÏ qu¸ møc hîp lÝ. VÝ dô: Ta xÐt bµi to¸n sau: Cho N c«ng viÖc, víi mçi c«ng viÖc cho biÕt tiÒn c«ng thu ®îc khi thùc hiÖn c«ng viÖc nµy, thêi gian ®Ó hoµn thµnh, thêi ®iÓm cuèi cïng ph¶i kÕt thóc. H·y xÕp lÞch thùc hiÖn sao cho thu ®îc nhiÒu tiÒn c«ng nhÊt. D÷ liÖu vµo tõ file v¨n b¶n xeplich.inp cã cÊu tróc: - Dßng ®Çu lµ sè nguyªn d¬ng N - N dßng sau, dßng i+1 ghi 3 sè tg, tdkt, gt t¬ng øng lµ thêi gian cÇn thiÕt ®Ó hoµn thµnh, thêi ®iÓm b¾t buéc ph¶i xong, gi¸ trÞ tiÒn c«ng cña c«ng viÖc i. D÷ liÖu ra ghi vµo file xeplich.out cã cÊu tróc: - Dßng ®Çu tiªn lµ tæng gi¸ trÞ tiÒn c«ng. - C¸c dßng tiÕp theo mçi dßng ghi 4 sè: i, T 1, T2, gt t¬ng øng lµ sè hiÖu, thêi ®iÓm b¾t ®Çu, thêi ®iÓm kÕt thóc, gi¸ trÞ cña c«ng viÖc ®îc chän. xeplich.inp xeplich.out 10 329 1 4 89 5 0 1 25 5 5 86 1 1 2 89 4 11 83 3 2 6 83 5 7 84 6 6 9 61 1 2 25 10 9 14 71 3 11 61 6 11 33 4 7 28 3 10 1 5 14 71 NhËn xÐt: - XÕp t¨ng bé d÷ liÖu theo khãa lµ thêi ®iÓm cuèi cïng ph¶i kÕt thóc c«ng viÖc. - §Æt cËn: Tæng tiÒn k c«ng viÖc+Gi¸ trÞ tèi ®a c¸c c«ng viÖc cßn l¹i>Tæng tiÒn cña ph¬ng ¸n tèt nhÊt ®· cã. Ta thÊy r»ng khi thö chän c«ng viÖc k th× cã thÓ dÉn tíi sù kiÖn hµng lo¹t c«ng viÖc kh¸c bÞ lo¹i v× viÖc hoµn thµnh c«ng viÖc k sÏ ®Èy lïi thêi ®iÓm cã thÓ b¾t ®Çu thùc hiÖn c¸c c«ng viÖc nµy dÉn ®Õn ®Èy lïi thêi ®iÓm hoµn thµnh chóng vµ do ®ã cã thÓ 14 lµm cho mét sè c«ng viÖc kh«ng xong tríc thêi h¹n kÕt thóc ®· qui ®Þnh cho nã. Ngîc l¹i nÕu kh«ng chän c«ng viÖc k n÷a th× l¹i t¹o ®iÒu kiÖn cã thÓ thùc hiÖn nh÷ng c«ng viÖc bÞ lo¹i do chän k. Ngoµi ra, mét cËn thø hai lµ: Thêi ®iÓm b¾t ®Çu c«ng viÖc k + thêi gian lµm c«ng viÖc k Thêi ®iÓm kÕt thóc c«ng viÖc k. Cµi ®Æt ch¬ng tr×nh sö dông ng«n ng÷ lËp tr×nh Pascal: uses crt; const max=1000; fi='xeplich.inp'; fo='xeplich.out'; type pt=record tg,tien,tdkt,ten:integer; end; var a,s,ls:array[1..max] of pt; {a[i] chứa thời gian làm, tiền công, thời gian kết thúc, số hiệu công việc i, s[i] chứa các công việc thử chọn, ls[i] chứa các công việc được chọn} d:array[1..max] of integer;{Đánh dấu các công việc} i,n,top,ltop:integer; conlai:longint;{Tổng tiền các công việc còn lại} tien,td,tong:integer;{Lần lượt là tổng tiền đã làm được, thời điểm cuối của phương án đang tạo, tổng tiền của phương án tốt đã có} procedure readfile; var f:text; i:integer; begin assign(f,fi); reset(f); readln(f,n); conlai:=0; for i:=1 to n do begin readln(f,a[i].tg,a[i].tdkt,a[i].tien); conlai:=conlai+a[i].tien; a[i].ten:=i; end; writeln(conlai); close(f); end; procedure swap(var u,v:pt); var tg:pt; begin tg:=u; u:=v; v:=tg; end; procedure sort; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if a[i].tdkt>a[j].tdkt then swap(a[i],a[j]); end; procedure select(k:integer); 15 var j:integer; begin tien:=tien+a[k].tien;{Thêm tiền công của công việc k} d[k]:=k; {đánh dấu đã chọn làm công việc k} conlai:=conlai-a[k].tien;{Tổng giá trị các công việc còn lại} inc(top); s[top].tg:=td; td:=td+a[k].tg; {Tính thời điểm làm xong công việc k} s[top].ten:=a[k].ten; s[top].tdkt:=td; s[top].tien:=a[k].tien; for j:=1 to n do {Điều kiện để loại công việc j do chọn công việc k} if (d[j]=0)and(a[j].tdkttong then save; for k:=1 to n do if (d[k]=0) and (td+a[k].tg<=a[k].tdkt) then begin select(k); if tien+conlai>tong then duyet; remove(k); end; end; procedure writefile; var f:text; k:integer; begin assign(f,fo); rewrite(f); writeln(f,tong); for k:=1 to ltop do writeln(f,ls[k].ten,' ',ls[k].tg,' ',ls[k].tdkt,' ',ls[k].tien); close(f); 16 end; begin fillchar(d,sizeof(d),0); td:=0; readfile; sort; tong:=-maxint; duyet; writefile; readln end. d. Ph¬ng ph¸p quy ho¹ch ®éng Có những bài toán mà quyết định ở bước thứ i phụ thuộc vào quyết định ở các bước trước đó. Nếu ta xác định được hệ thức diễn đạt mối tương quan của quyết đinh ở bước thứ i với quyết định ở bước trước đó thì ta có thể triển khai chương trình theo hệ thức đã tìm được. Khi đó việc giải các bài toán có kích thước lớn sẽ được chuyển về việc giải các bài toán cùng kiểu có kích thước nhỏ hơn.Các thuật toán này thường được thể hiện bằng các chương trình con đệ quy.Tuy nhiên, với kỹ thuật chia để trị thì nhiều bài toán con phải tính lại nhiều lần. Vậy ý tưởng cơ bản của quy hoạch động đó là: Tránh tính toán lại các bài toán con nhiều lần, mà lưu giữ kết quả đã tìm kiếm được vào một bảng làm giá trị giả thiết cho việc tìm kết quả của trường hợp sau. Chúng ta sẽ lấp đầy dần các giá trị của bảng này bởi các kết quả của những trường hợp trước đã được giải. Kết quả cuối cùng chính là kết quả của bài toán cần giải.Cụ thể như sau: Phương pháp quy hoạch động cùng nguyên lý tối ưu được nhà toán học Mỹ R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này đã được áp dụng để giải hàng loạt bài toán thực tế trong các quá trình kỹ thuật của công nghệ, tổ chức sản xuất, kế hoạch hoá kinh tế… Tuy nhiên cần lưu ý rằng có một số bài toán giải bằng quy hoạch động tỏ ra không thích hợp. Trong thực tế, ta thường gặp một số bài toán tối ưu loại sau: Có một đại lượng g hình thành trong một quá trình gồm nhiều giai đoạn và ta chỉ quan tâm đến kết quả cuối cùng là giá trị của g phải lớn nhất hoặc nhỏ nhất, ta gọi chung là giá trị tối ưu của g. Giá trị của g phụ thuộc vào những đại lượng xuất hiện trong bài toán mà mỗi bộ giá 17 trị của chúng được gọi là một trạng thái của hệ thống và cũng phụ thuộc vào cách thức đạt được giá trị g trong từng giai đoạn mà mỗi cách thức được gọi là điều khiển. Đại lượng g thường được gọi là hàm mục tiêu và quá trình đạt được giá trị tối ưu của g được gọi là quá trình điều khiển tối ưu. Bellman phát biểu nguyên lý tối ưu (cũng gọi là nguyên lý Bellman) mà ý tưởng cơ bản là như sau: "Với mỗi quá trình điều khiển tối ưu, đối với trạng thái ban đầu A 0, với mọi trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu". Chú ý rằng nguyên lý này được thừa nhận mà không chứng minh. Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là quy hoạch động. Thuật ngữ này nói lên thực chất của quá trình điều khiển là động:Có thể trong số bước đầu tiên lựa chọn điều khiển tối ưu dường như không tốt nhưng chung cả quá trình lại là tốt nhất. Ta có thể giải thích ý này qua bài toán sau: Cho một dãy số nguyên A 1,A2,….An. Hãy tìm cách xóa đi một số ít nhất số hạng để dãy còn lại là dãy đơn điệu hay nói cách khác hãy chọn một số nhiều nhất các số sao cho dãy B gồm các số hạng đó theo trình tự xuất hiện trong dãy A là đơn điệu. Quá trình chọn dãy B được điều khiển qua N giai đoạn để đạt được mục tiêu là số lượng số hạng của dãy B là nhiều nhất, điều khiển ở giai đoạn i thể hiện việc chọn hay không chọn dãy Ai vào dãy B. Giả sử dãy đã cho là 1 8 10 2 4 6 7. Nếu ta chọn lần lượt 1, 8, 10 thì chỉ chọn được 3 số hạng nhưng nếu bỏ qua 8 và 10 thì ta chọn được 5 số hạng 1, 2, 4, 6, 7. Khi giải một số bài toán bằng cách "chia để trị", chuyển việc giải bài toán kích thước lớn về việc giải nhiều bài toán cùng kiểu có kích thước nhỏ hơn thì các thuật toán này thường được thể hiện bằng các chương trình con đệ quy. Khi đó, trên thực tế, nhiều kết quả trung gian phải được tính nhiều lần. Nói các khác phương pháp quy hoạch động đã thể hiện sức mạnh của nguyên lý chia để trị đến cao độ. 18 Trong một số trường hợp, khi giải một bài toán A, trước hết ta tìm họ bài toán A(p) phụ thuộc tham số p (có thể là một véc tơ) mà A(p 0)=A với p0 là trạng thái ban đầu của bài toán A. Sau đó tìm cách giải họ bài toán A(p) với tham số p bằng cách áp dụng nguyên lý tối ưu của Bellman. Cuối cùng cho p=p0 sẽ nhận được kết quả của bài toán A ban đầu. Các thuật ngữ dùng trong quy hoạch động: Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch động. Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi của quy hoạch động. Tập các bài toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động. Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch động. VÝ dô: Cho thuª m¸y tÝnh T¹i thêi ®iÓm 0, «ng chñ cho thuª m¸y tÝnh nhËn ®îc ®¬n ®Æt hµng thuª sö dông m¸y cña N kh¸ch hµng. C¸c kh¸ch hµng ®îc ®¸nh sè tõ 1 ®Õn N. Kh¸ch hµng i cÇn sö dông m¸y tõ thêi ®iÓm di ®Õn thêi ®iÓm ci (di vµ ci lµ c¸c sè nguyªn vµ 0 - Xem thêm -