Ãëàâíàÿ ñòðàíèöà


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)
 
 

Âåðíóòüñÿ ê ñïèñêó òåì, ñîðòèðîâàííûõ ïî: âîçðàñòàíèå äàòû  óìåíüøåíèå äàòû  òåìà  àâòîð 

 Òåìà:    Àâòîð:    Äàòà:  
 faq   Mike Galushkin   06 Apr 2003 13:18:22 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:08:30 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 07:57:54 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 07:59:52 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 07:59:52 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:00:48 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:00:48 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:18 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:18 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:52 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:52 
 3 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:52 
 3 faq   Stanislav Shwartsman   10 Apr 2003 08:11:45 
 3 faq   Andrey Dashkovsky   11 Apr 2003 23:00:43 
 3 faq   Stanislav Shwartsman   12 Apr 2003 10:39:21 
 3 faq   Andrey Dashkovsky   13 Apr 2003 11:31:29 
 3 faq   Stanislav Shwartsman   14 Apr 2003 08:20:45 
 3 faq   Andrey Dashkovsky   14 Apr 2003 22:21:35 
 3 faq   Ruslan Tebuev   14 Apr 2003 11:51:21 
 3 faq   Andrey Dashkovsky   14 Apr 2003 22:38:11 
 3 faq   Ruslan Tebuev   15 Apr 2003 16:46:02 
 3 faq   Moderator   14 Apr 2003 23:26:48 
 3 faq   Zahar Kiselev   13 Apr 2003 19:07:12 
 3 faq   Moderator   14 Apr 2003 23:30:46 
 3 faq   Stanislav Shwartsman   15 Apr 2003 08:10:17 
 3 faq   Andrey Dashkovsky   14 Apr 2003 22:19:31 
 Re: 3 faq - àïïðîêñèìàöèÿ   Yuri Burger   15 Apr 2003 14:49:50 
Àðõèâíîå /ru.algorithms/143013e953302.html, îöåíêà 2 èç 5, ãîëîñîâ 10
ßíäåêñ.Ìåòðèêà
Valid HTML 4.01 Transitional