|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Comoderator Of Ru Algorithms 2:5002/46.4 10 Apr 2003 08:01:18 To : All Subject : faq -------------------------------------------------------------------------------- 06 Àïð 03 12:18, Mike Galushkin wrote to ilya voronin: === Hà÷àëî q_21-30.txt === ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ ³ ³Îòâåòû íà ÷àñòî çàäàâàåìûå âîïpîñû êîíôåpåíöèé RU.ALGORITHM è NICE.SOURCES³ ³ ³ ³ Ñîñòàâèòåëè: Alexander Dedusenko [2:462/42] ³ ³ Dmitry Pryadkin [2:5010/207.3],³ ³ polox@chel.ru ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Îòêðûòûå âîïðîñû: ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ !Q1. Àëãîðèòì ïåðåáîðà âñåõ êîìáèíàöèé ñèìâîëîâ ñòðîêè áåç èñïîëüçîâàíèÿ ðåêóðñèè. Ïðèìå÷àíèå: âû ìîæåòå çàäàâàòü âîïðîñû ïðÿìî â netmail: 2:5010/207.3 èëè e-mail: polox@chel.ru. Åñëè îíè áóäóò ðàñöåíåíû êàê ïîäïàäàþùèå ïîä òåìàòèêó óêàçàííûõ êîíôåðåíöèé, òî îíè áóäóò âêëþ÷åíû â äàííûé ñïèñîê. ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Îãëàâëåíèå (îòâå÷åííûå âîïðîñû): ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q21. Hàõîæäåíèå êpàò÷àéøèõ ïyòåé â ãpàôå Q22. Îápàòíàÿ ïîëüñêàÿ íîòàöèÿ Q23. Ýôåêò pàçâèâàþùåãîñÿ ôëàãà Q24. ×òî òàêîå íåéðîííûå ñåòè Q25. Ìåòîä äåôîðìèðóåìîãî ìíîãîãðàííèêà Q26. Áûñòðîå ïðåîáðàçîâàíèå Ôóðüå (ÁÏÔ) Q27. Ãåíåòè÷åñêîå îáó÷åíèå íåéðîííûõ ñåòåé Q28. Òî÷êà â ìíîãîóãîëüíèêå Q29. Wavelet-ïðåîáðàçîâàíèÿ Q30. Âîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q21. Hàõîæäåíèå êpàò÷àéøèõ ïyòåé â ãpàôå A. (Alex Chernobaev 2:5020/394.36) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ 1. Åñëè íyæíî íàéòè êpàò÷àéøèé ïyòü ìåæäy äâyìÿ âåpøèíàìè, ìîæíî èñïîëüçîâàòü "âîëíîâîé" àëãîpèòì. Ïyñòü äàí íåïyñòîé ãpàô G=(V,E); èùåòñÿ êpàò÷àéøèé ïyòü îò s ê t (s <> t). (1) âñåì âåpøèíàì vi ïpèïèñûâàåòñÿ öåëîå ÷èñëî T(vi) - âpåìåíí'àÿ ìåòêà ñ íà÷àëüíûì çíà÷åíèåì, pàâíûì 0; (2) çàâîäÿòñÿ äâà ñïèñêà "ôpîíòà âîëíû" (NewFront, OldFront), à òàêæå ïåpåìåííàÿ T (òåêyùåå âpåìÿ); (3) OldFront:={s}; NewFront:={}; T:=1; (4) äëÿ êàæäîé èç âåpøèí, âõîäÿùèõ â OldFront, ïpîñìàòpèâàþòñÿ ñîñåäíèå âåpøèíû uj, è åñëè T(uj) = 0, òî T(uj):=T, NewFront:=NewFront + {uj}; (5) åñëè NewFront = {}, òî ïyòè íå ñyùåñòâyåò; ÂÛÕÎÄ; (6) åñëè îäíà èç âåpøèí uj ñîâïàäàåò t, òî íàéäåí êpàò÷àéøèé ïyòü äëèíû T; ÂÛÕÎÄ; èíà÷å (7) OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4) Åñëè íà øàãå (6) áûëà äîñòèãíyòà âåpøèíà t, òî âîññòàíîâèòü êpàò÷àéøèé ïyòü ìîæíî ñëåäyþùèì îápàçîì: ñpåäè ñîñåäåé âåpøèíû t íàõîäèòñÿ âåpøèíà ñ âpåìåíí'îé ìåòêîé T-1, ñpåäè ñîñåäåé ïîñëåäíåé - âåpøèíà ñ ìåòêîé T-2, è ò.ä., ïîêà íå äîñòèãíåì s; åñëè "ïåpåâåpíyòü" ïîëy÷åííûé ñïèñîê âåpøèí, òî ïîëy÷èòñÿ îäèí èç êpàò÷àéøèõ ïyòåé îò s ê t. Hà ïpàêòèêå âûãîäíåå ñîõpàíÿòü íà øàãå (4) èíôîpìàöèþ î òîì, èç êàêîé âåpøèíû âîëíà ïpèøëà â âåpøèíy uj - òîãäà âîññòàíîâëåíèå ïyòè ìîæíî îñyùåñòâèòü áûñòpåå. 2. Åñëè òpåáyåòñÿ íàéòè êpàò÷àéøèé ïyòü âî âçâåøåííîì ãpàôå, ãäå påápàì ïpèïèñàíû âåùåñòâåííûå ÷èñëà - âåñà, è ýòè âåñà íåîòpèöàòåëüíû, ìîæíî èñïîëüçîâàòü àëãîpèòì Äåéêñòpû. Ïpè íàëè÷èè påáåp ñ îòpèöàòåëüíûì âåñîì êpàò÷àéøèé ïyòü ìîæåò íå ñyùåñòâîâàòü äàæå äëÿ ñâÿçíîãî ãpàôà. Êpàò÷àéøèé ïyòü ñyùåñòâyåò, òîëüêî åñëè â ãpàôå íåò öèêëîâ îòpèöàòåëüíîãî ñyììàpíîãî âåñà - ïî òàêîìy öèêëy ìîæíî êpyòèòüñÿ ñêîëüêî yãîäíî, yìåíüøàÿ äëèíy äî áåñêîíå÷íîñòè. Äëÿ îáùåãî ñëy÷àÿ ïîäõîäèò àëãîpèòì Ôëîéäà, êîòîpûé ïîçâîëÿåò ëèáî íàéòè êpàò÷àéøèå ïyòè, ëèáî îáíàpyæèòü öèêëû îòpèöàòåëüíîé äëèíû. Óïîìÿíyòûå àëãîpèòìû ÿâëÿþòñÿ êëàññè÷åñêèìè è îïèñàíû â pàçëè÷íûõ êíèãàõ ïî òåîpèè ãpàôîâ (íàïp.: H.Êpèñòîôèäåñ. Òåîpèÿ ãpàôîâ. Àëãîpèòìè÷åñêèé ïîäõîä. Ì., "Ìèp", 1978). Ñyùåñòâyåò îãpîìíîå êîëè÷åñòâî äpyãèõ àëãîpèòìîâ, áîëåå âûãîäíûõ â êàêèõ-òî ñëy÷àÿõ. ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q22. Îápàòíàÿ ïîëüñêàÿ íîòàöèÿ A. (Alexey Olkhovsky aolkhov@messages.to) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Èñïîëüçyåòñÿ äëÿ âû÷èñëåíèÿ àpèôìåòè÷åñêèõ âûpàæåíèé. Äëÿ ïåpåâîäà â íåå íåîáõîäèì ñòåê àpèôìåòè÷åñêèõ îïåpàöèé. Àëãîpèòì ïåpåâîäà ïpîèçâîëüíîãî âûpàæåíèÿ â ÎÏH î÷åíü ïpîñò: Âûpàæåíèå ñêàíèpyåòñÿ ñëåâà íàïpàâî, ïpè ýòîì pàçáèâàÿñü íà òîêåíû - ÷èñëà è çíàêè àpèôìåòè÷åñêèõ îïåpàöèé. Åñëè î÷åpåäíîé òîêåí - ÷èñëî, íå ãëÿäÿ ïèøåì åãî â âûõîäíyþ ñòpîêy. Èíà÷å, âûòàëêèâàåì èç ñòåêà è ïèøåì â âûõîäíyþ ñòpîêy âñå îïåpàöèè ñ ïpèîpèòåòîì âûøå òåêyùåé, à ñàìy îïåpàöèþ ïèõàåì â ñòåê. Ëåâàÿ ñêîáêà âñåãäà ïèøåòñÿ â ñòåê (åå ïpèîpèòåò - ñàìûé íèçêèé). Ïpàâàÿ ñêîáêà âûòàëêèâàåò èç ñòåêà âñå îïåpàöèè âïëîòü äî ëåâîé ñêîáêè âêëþ÷èòåëüíî, ñàìà îíà â ñòåê íå ïèøåòñÿ. Êîãäà äîñòèãíyò êîíåö âõîäíîãî âûpàæåíèÿ, ïpîñòî âûòàëêèâàåì èç ñòåêà âñå ÷òî â íåì åñòü. Ïpèìåp: (2+3)*4+5 ëåâàÿ ñêîáêà - ïèõàåì â ñòåê 2 - ïèøåì â âûõîäíyþ ñòpîêy + - ñòåê ïyñò, ïîýòîìy íè÷åãî íå äîñòàåì, à íàïpîòèâ, ïèõàåì ïëþñ 3 - ïèøåì â âûõîäíyþ ñòpîêy ïpàâàÿ ñêîáêà - âûòàëêèâàåì ïëþñ è ëåâyþ ñêîáêy * - ñòåê ñíîâà ïyñò, ïèõàåì yìíîæåíèå 4 - ïèøåì â âûõîäíyþ ñòpîêy + - ïpèîpèòåò yìíîæåíèÿ - âûøå, ïîýòîìy åãî äîñòàåì, à ïëþñ - ïèõàåì 5 - ïèøåì â âûõîäíyþ ñòpîêy EOF - äîñòàåì èç ñòåêà ïëþñ Èìååì: 2 3 + 4 * 5 + Îápàòè âíèìàíèå íà ñëåäyþùåå: - Âìåñòî çàïèñè â âûõîäíyþ ñòpîêy ìîæíî òyò æå âû÷èñëÿòü âûpàæåíèå, äëÿ ýòîãî íåîáõîäèì åùå îäèí ñòåê (ïî÷åìy - ñîîápàçè ñàì) - Åñëè âûòàëêèâàòü èç ñòåêà îïåpàöèè ñ ïpèîpèòåòîì âûøå èëè pàâíûì òåêyùåìy, òî âûïîëíåíèå îïåpàöèé ñ îäèíàêîâûì ïpèîpèòåòîì áyäåò ïpîèçâîäèòüñÿ ñëåâà íàïpàâî, ò.å. êàê âñå ìû ïpèâûêëè, äà è åãî ãëyáèíà yìåíüøèòüñÿ (õîòü ýòî è íå êpèòè÷íî) - Ñêîáêè â âûõîäíyþ ñòpîêy íå ïèøyòñÿ, òàê êàê èõ ïpèîpèòåò y÷èòûâàåòñÿ àâòîìàòè÷åñêè; îäíàêî èõ áàëàíñ ëåãêî ïpîâåpÿåòñÿ. ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q23. Ýôåêò pàçâèâàþùåãîñÿ ôëàãà A. (Alex Gashper 2:469/79.77) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Program Rulz; Const SloFake : Array[1..17,1..50] of Byte = ( (2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,1,1,1,1,1,1,2,2,3,3,3,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,1,1,1,1,1,2,2,2,2,1,2,3,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,4,4,1,1,2,2,2,2,2,1,2,2,3,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,4,4,1,1,1,2,2,2,2,2,1,2,2,3,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,3,1,1,1,1,1,1,1,2,2,2,2,2,1,2,2,3,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,3,1,1,1,1,1,1,2,2,2,2,2,1,2,2,1,2,3,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,3,1,4,4,1,1,2,2,2,2,2,2,1,2,2,1,2,2,3,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,3,1,4,4,1,1,2,2,2,2,2,2,2,1,2,2,1,2,3,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,3,1,1,1,1,1,1,2,2,2,2,2,2,1,2,2,1,3,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,3,1,1,1,1,1,1,1,2,2,2,2,1,2,2,1,3,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,4,4,1,1,1,2,2,2,2,1,2,2,1,3,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,4,4,1,1,2,2,2,2,2,2,1,1,3,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,1,1,1,1,1,2,2,2,2,2,1,3,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,3,1,1,1,1,1,1,1,2,2,3,3,3,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3), (2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3,3,3,3,3,3 , 3,3,3,3,3,3,3,3,3,3,3)); Type SloType = array[1..80,1..50] of Byte; ScreenType = Array[1..200,1..320] of Byte; SloPointType = array[1..80,1..50] of record X, Y : Word; end; Var Slo : SloType; FS : SloPointType; CosBuffer : array[0..63] of ShortInt; Sk: ^ScreenType; Fo, Ka : Byte; X, Y, Fx, Fy, Cnt : Word; Procedure SetPal(Color,R,G,B:Byte); Begin Port[$3C8] := Color; Port[$3C9] := R; Port[$3C9] := G; Port[$3C9] := B; End; Function KeyPressed:boolean; Begin KeyPressed := Mem[$40:$1C] - Mem[$40:$1A] <> 0; end; Begin {Telo programa} WriteLn('Copyright '); WriteLn; New(Sk); Ka := 0; While (Char(Ka) < '1') or (Char(Ka) > '5') do Begin Write('Enter Waving 1 - 5 : '); ReadLn(Char(Ka)); End; Ka := Ka - Byte('1') + 7; asm mov ax,19; int 10h; end; For Fo := 1 to 80 do Move(SloFake[17],Slo[Fo],50); For Fo := 1 to 17 do Move(SloFake[Fo],Slo[Fo+5],50); For Fo := 1 to 64 do CosBuffer[Fo-1] := Round(Cos(Fo/10)*Ka); For Fo := 1 to 31 do SetPal(Fo,0,0,Fo*2-10); For Fo := 32 to 63 do SetPal(Fo,(Fo-32)*2-10,(Fo-32)*2-10,(Fo-32)*2-10); For Fo := 64 to 95 do SetPal(Fo,(Fo-64)*2-10,0,0); For Fo := 96 to 127 do SetPal(Fo,(Fo-96)*2-10,(Fo-96)*2-10,0); Cnt := 0; Repeat Inc(Cnt,2); FillChar(Sk^,64000,0); FillChar(Fs,850*2,0); For X := 1 to 80 do For Y := 1 to 50 do Begin Fs[X,Y].Y := 20+Y*3+CosBuffer[(X+Y+Cnt) mod 64]; Fs[X,Y].X := 40+X*3+CosBuffer[(Y+X+Cnt) mod 64]; For Fx := Fs[X-1,Y].X to Fs[X,Y].X-1 do For Fy := Fs[X,Y-1].Y to Fs[X,Y].Y-1 do Sk^[Fy,Fx] := (SLO[X,Y])*32 - CosBuffer[(X+Y+Cnt) mod 64] - 12; End; asm cli; mov bx,ds; lds si,Sk; mov ax,0A000h; mov es,ax; xor di,di; mov cx,32000; REP movsw; mov ds,bx; sti; end; Until KeyPressed; asm mov ax,3; int 10h; end; Dispose(Sk); End. + Origin: [Team ÑÀÏÐ] (2:462/42) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q24. ×òî òàêîå íåéðîííûå ñåòè A. (Dmitry Pryadkin 2:5010/207.3, polox@chel.ru) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Håéðîííûå ñåòè (HÑ) - ýòî ñðåäñòâà, ôóíêöèîíèðóþùèå áëàãîäàðÿ ôîðìóëàì, ïîçâîëÿþùèå ðåøàòü äîñòàòî÷íî øèðîêèé êðóã çàäà÷. HÑ êëàññèôèöèðóþòñÿ ïî ñëåäóþùèì ïðèçíàêàì: 1) Îáó÷àåìîñòü/íåîáó÷àåìîñòü 2) Îáó÷åíèå áåç ó÷èòåëÿ/ñ ó÷èòåëåì 3) Îòñóòñòâèå/ïðèñóòñòâèå îáðàòíûõ ñâÿçåé 4) Êîëè÷åñòâî ñëîåâ/íåéðîíîâ â ñëîå 5) è ò.ä... HÑ ñîñòîÿò èç íåêîòîðîãî ÷èñëà íàèìåíüøèõ ñòðóêòóðíûõ åäèíèö - ìàòåìà- òè÷åñêèõ íåéðîíîâ. Êàæäûé íåéðîí îñóùåñòâëÿåò âçâåøåííîå ñóììèðîâàíèå ñâîèõ âõîäîâ ñ êîýôôèöèåíòàìè ñèíàïòè÷åñêèõ ñâÿçåé, ïîòîì ðåçóëüòàò îòïðàâëÿåòñÿ íà àêòèâàöèîííóþ ôóíêöèþ â êà÷åñòâå àðãóìåíòà. Ïîòîì ýòà ôóíêöèÿ âûäàåò ðåçóëüòàò, êîòîðûé íàçûâàåòñÿ ðåàêöèåé íåéðîíà íà âõîäíóþ èíôîðìàöèþ. Håéðîíû ìîãóò áûòü ñâÿçàíû ðàçëè÷íûì îáðàçîì(âûõîäû îäíèõ ñîåäèíåíû ñî âõîäàìè äðóãèõ), ÷òî íàäåëÿåò HÑ íåêîòîðûìè ñïîñîáíîñòÿìè ïî ðåøåíèþ òîé èëè èíîé ïîñòàâëåííîé çàäà÷è. Áîëåå ïîäðîáíî ïî÷èòàòü ïðî HÑ ìîæíî òóò: http://www.neuropower.de/rus/books/ http://nncourse.chat.ru (ÿ çàáûë, åñòü ëè â àäðåñå www ;-) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q25. Ìåòîä äåôîðìèðóåìîãî ìíîãîãðàííèêà. A. (Alexander Tsyplakov, tsy@land4.nsu.ru) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q> Ãäå ïpî ñàáæ ïî÷èòàòü ìîæíî. Hàäî åãî påàëèçîâàòü íà Q> C++. Ýòî î÷åíü õîðîøèé ìåòîä îïòèìèçàöèè, íå òðåáóþùèé âçÿòèÿ ïðîèçâîäíûõ. Åùå åãî íàçûâàþò ñèìïëåêñíûì ìåòîäîì (ïîñêîëüêó ìíîãîãðàííèê â äàííîì ñëó÷àå ñèìïëåêñ) èëè àëãîðèòìîì Håëäåðà-Ìèäà (ïî èìåíè àâòîðîâ). Hà ðóññêîì ÿ çíàþ îïèñàíèå òîëüêî â êíèãå "Ïîèñê îïòèìóìà" Æèëèíñêàñà è Øàëòÿíèñà. Ïîïðîáóþ ïåðåñêàçàòü. Ïóñòü ìèíèìèçèðóåòñÿ ôóíêöèÿ n ïåðåìåííûõ f(X). Ïðîùå âñåãî ïîíÿòü ìåòîä áåç äåôîðìàöèè ñèìïëåêñà. Áåðåì ñèìïëåêñ ñ ðàâíûìè ñòîðîíàìè (íà ïëîñêîñòè - ïðàâèëüíûé òðåóãîëüíèê, â òðåõìåðêå - ïðàâèëüíûé òåòðàýäð è ò.ä.) è â êàæäîé âåðøèíå ñ÷èòàåì öåëåâóþ ôóíêöèþ f. Çàòåì íàõîäèì "íàèõóäøóþ" âåðøèíó è ïåðåâîðà÷èâàåì ñèìïëåêñ çåðêàëüíî îòíîñèòåëüíî ïðîòèâîïîëîæíîé ãðàíè (ò.å. êàæäûé ðàç "õóäøóþ" âåðøèíó çàìåíÿåì íà íîâóþ). Òàê è øàãàåì, ñêàòûâàÿñü â ìèíèìóì, ïîêà ïîëó÷àåòñÿ. Êîãäà ïåðåñòàíåò ïîëó÷àòüñÿ, ñèìïëåêñ ñëåäóåò ñæàòü ãîìîòåòèåé, îñòàâëÿÿ íà ìåñòå "ëó÷øóþ" âåðøèíó. Hî ýòîò óïðîùåííûé ìåòîä íåäîñòàòî÷íî õîðîøî ðàáîòàåò. Hà íåêîòîðûõ îâðàæíûõ ôóíêöèÿõ îí æåñòîêî òîðìîçèò. Ïîýòîìó ñèìïëåêñ ñëåäóåò äåôîðìèðîâàòü, ÷òîáû îí "ïîäñòðàèâàëñÿ" ïîä ìèíèìèçèðóåìóþ ôóíêöèþ. Îáîçíà÷èì êîîðäèíàòû âåðøèí ñèìïëåêñà ÷åðåç X[i], i=1...(n+1). * Hà÷àëî Hàõîäèì âåðøèíû, â êîòîðûõ f ìèíèìàëüíà è ìàêñèìàëüíà. Îáîçíà÷èì èõ íîìåðà ÷åðåç l è h ñîîòâåòñòâåííî. Ðàáîòà ìåòîäà ñîñòîèò èç ñëåäóþùèõ îïåðàöèé: îòðàæåíèå, ðàñòÿæåíèå, ñæàòèå è ðåäóêöèÿ. Hà÷èíàåì ñ îòðàæåíèÿ - ýòî îáÿçàòåëüíûé øàã. * Îòðàæåíèå ×åðåç X[n+2] îáîçíà÷èì öåíòð òÿæåñòè âñåõ âåðøèí, èñêëþ÷àÿ õóäøóþ (ò.å. h): X[n+2] = 1/n * (Sum{i=1...(n+1), i!=h} X[i]) Îòðàæåíèå - ýòî ïðîåêöèÿ òî÷êè X[h] ÷åðåç öåíòð òÿæåñòè X[n+2]: X[n+3] = X[n+2] + a * (X[n+2] - X[h]), ãäå êîýôôèöèåíò îòðàæåíèÿ a > 0, íàïðèìåð, a = 1.  ðåçóëüòàòå îòðàæåíèÿ âîçìîæíû 4 ñëó÷àÿ: (1) f(X[n+3]) < f(X[l]) (îòðàæåíèå ïðîøëî êëàññíî) Äåëàåì ðàñòÿæåíèå (2) f(X[n+3]) > f(X[h]) (îòðàæåíèå ïðîøëî ñîâñåì õðåíîâî) Äåëàåì ðåäóêöèþ (3) f(X[n+3]) <= f(X[h]), íî f(X[n+3]) > f(X[i] äëÿ âñåõ i êðîìå h (îòðàæåíèå ïðîøëî íå î÷åíü óñïåøíî) Äåëàåì ñæàòèå (4) Hè÷òî èç âûøåïåðå÷èñëåííîãî (îòðàæåíèå ïðîøëî ñðåäíåíüêî) Çàìåíÿåì õóäøóþ òî÷êó íà X[n+3], ò.å. X[h] := X[n+3], è íà÷èíàåì ñíà÷àëà * Ðàñòÿæåíèå Ïðîñòî ïðîäîëæàåì äâèãàòüñÿ â òó æå ñòîðîíó, êóäà óæå øàãíóëè: X[n+4] = X[n+2] + c * (X[n+3] - X[n+2]) ãäå êîýôôèöèåíò ðàñòÿæåíèÿ c > 1, íàïðèìåð, c = 2. Åñëè f(X[n+4]) < f(X[l]), òî çàìåíÿåì X[h] := X[n+4], èíà÷å çàìåíÿåì X[h] := X[n+3]. Hà÷èíàåì ñíà÷àëà. * Ñæàòèå Ñæèìàåì èñõîäíûé ñèìïëåêñ, ñäâèãàÿ "õóäøóþ" âåðøèíó X[h] â ñòîðîíó öåíòðà òÿæåñòè X[n+2]: X[h] := X[n+2] - b * (X[n+2] - X[h]) ãäå êîýôôèöèåíò ñæàòèÿ 0 < b < 1, íàïðèìåð, b = 1/2. Hà÷èíàåì ñíà÷àëà. * Ðåäóêöèÿ "Ëó÷øàÿ" âåðøèíà X[l] ñòîèò íà ìåñòå, à îñòàëüíûå ïðèáëèæàþòñÿ ê íåé â îäèíàêîâîé ïðîïîðöèè (ãîìîòåòè÷íî): X[i] := X[l] - d * (X[l] - X[i]) äëÿ âñåõ i = 1...(n+1) êðîìå l Çäåñü êîýôôèöèåíò ðåäóêöèè 0 < d < 1, íàïðèìåð, d = 1/2. Hà÷èíàåì ñíà÷àëà. Êàêîé êðèòåðèé îñòàíîâêè âûáðàòü - äåëî âêóñà. Åñòü ðåàëèçàöèÿ íà Ôîðòðàíå èç æóðíàëà Applied Statistics http://lib.stat.cmu.edu/apstat/47 Òàì íåìíîãî ïî äðóãîìó, ÷åì ÿ çäåñü îïèñàë. Ñ ïîæåëàíèåì âñÿ÷åñêèõ óñïåõîâ, Àëåêñàíäð Öûïëàêîâ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Q26. Áûñòðîå ïðåîáðàçîâàíèå Ôóðüå (ÁÏÔ) A. (Vladimir Mikhailov, 2:5030/991.20) ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ Âîò pàáîòàþùàÿ ôyíêöèÿ påàëèçyþùàÿ ÁÏÔ (÷åé àëãîpèòì - íå â êypñå). Èñòî÷íèê - Â.Êàïïåëèíè "Öèôpîâûå ôèëüòpû è èõ ïpèìåíåíèå" - òàì ýòà ïpîãà íà Ôîpòpàíå. n - ÷èñëî òî÷åê (îáÿçàòåëüíî ñòåïåíü 2-õ, ò.å. 64, 128, 256, 512, 1024, è ò.ä.) m = log(n)/log(2) dir - =1 - ïpÿìîå ïpåîápàçîâàíèå; =0 - îápàòíîå ---- || ----; x1,x2- --- GoldED+/386 1.1.4.7 * Origin: Âñ¸ôèãíÿ êðîìå ï÷¸ë,õîòÿ ï÷¸ëû,åñëèïîäóìàòü,òîæå ôèãíÿ (2:5002/46.4) Âåðíóòüñÿ ê ñïèñêó òåì, ñîðòèðîâàííûõ ïî: âîçðàñòàíèå äàòû óìåíüøåíèå äàòû òåìà àâòîð
Àðõèâíîå /ru.algorithms/143013e953302.html, îöåíêà èç 5, ãîëîñîâ 10
|