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