Математические методы в экономике. Копылов Г.Н - 82 стр.

ñòðîêå 5 ìèíèìàëüíûé ýëåìåíò 3, ýòî ñ53, íî â 3-ì ãîðîäå ìû
áûëè. Ìû áûëè âåçäå êðîìå ãîðîäà 4. Òîãäà èç ãîðîäà 5 ïîåäåì â
4-é, à îòòóäà âåðíåìñÿ â ãîðîä 1. Ïîëó÷èëè õ = (1, 3, 2, 5, 4).
                   2   0   1   7   6
                 1 → 3 →2 → 5 → 4 → 1
      Çäåñü f(x) = ñ13+ ñ32 +ñ25 +ñ54+ ñ41 = 16. Ýòîò ðåçóëüòàò
ñóùåñòâåííî ëó÷øå ïðåäûäóùåãî. Ìû ïðèìåíèëè àëãîðèòì «èäè
â áëèæàéøèé», êîòîðûé äîñòàòî÷íî ðàçóìåí, íî íå ãàðàíòèðóåò
íàõîæäåíèå îïòèìàëüíîãî âàðèàíòà. Òàêèå àëãîðèòìû íàçûâàþò
ýâðèñòè÷åñêèìè.  äàííîì ñëó÷àå àëãîðèòì ñìîòðèò íà îäèí øàã
âïåðåä è âûáèðàåò ðåøåíèå, îïòèìàëüíîå íà ýòîì øàãó. Òàêèå
ýâðèñòè÷åñêèå àëãîðèòìû íàçûâàþò æàäíûìè. Äëÿ íåêîòîðûõ çà-
äà÷ æàäíûå àëãîðèòìû äàþò îïòèìàëüíîå ðåøåíèå. Íî ìîæíî
ïðèäóìàòü ïðèìåð, êîãäà àëãîðèòì «èäè â áëèæàéøèé» äàåò íàè-
õóäøåå èç âñåõ âîçìîæíûõ ðåøåíèé. Îäíàêî â áîëüøèíñòâå ñëó-
÷àåâ îí äàåò äîñòàòî÷íî õîðîøåå ðåøåíèå.
      Åñëè ìíîæåñòâî âàðèàíòîâ â êàêîé-òî çàäà÷å ÿâëÿåòñÿ êî-
íå÷íûì, òî òåîðåòè÷åñêè ìîæíî íàéòè íàèëó÷øèé âàðèàíò ïåðå-
áîðîì âñåõ âîçìîæíûõ âàðèàíòîâ. Èíîãäà òàêîé ïåðåáîð óäîáíî
äåëàòü ñ ïîìîùüþ ïîñòðîåíèÿ äåðåâà ðåøåíèé. Âåðøèíû åãî ñî-
îòâåòñòâóþò ìîìåíòàì ïðèíÿòèÿ ðåøåíèé, à ðåáðà — âîçìîæ-
íûì ðåøåíèÿì.
      Ïîñòðîèì äåðåâî âàðèàíòîâ äëÿ ðàññìàòðèâàåìîé çàäà÷è. Â
ýòîé çàäà÷å ìû èùåì öèêë, ïðîõîäÿùèé ÷åðåç âñå ãîðîäà. Âàðè-
àíòû «1 → 2 → 3 → 4 → 5 → 1» è «3 → 4 → 5 → 1 → 2 → 3»
îïðåäåëÿþò îäèí è òîò æå öèêë. Ïîýòîìó, áåç îãðàíè÷åíèÿ îáù-
íîñòè, ìîæíî ñ÷èòàòü, ÷òî âñå âàðèàíòû íà÷èíàþòñÿ ñ 1. Ïðåä-
ïîëîæèì, ìû âûåõàëè èç ãîðîäà 1. Äàëåå ìîæíî ïîåõàòü â ãîðîä
2, 3, 4 èëè 5. Ïóñòü ìû âûáðàëè ãîðîä 4. Òàê êàê ìû óæå áûëè â
ãîðîäå 1, òî èç ãîðîäà 4 ìîæíî ïîåõàòü â ãîðîä 2, 3 èëè 5.
Âûáèðàåì, íàïðèìåð, 2. Êóäà ìû ìîæåì ïîåõàòü èç íåãî? Òàê
êàê ìû áûëè óæå â ãîðîäàõ 1 è 4, òî èç 2 ìîæíî ïîåõàòü ëèáî â
3, ëèáî â 5. Âûáèðàåì ãîðîä 3. Ïîñëåäíèé ãîðîä, â êîòîðîì ìû
íå áûëè — ýòî 5, ïîýòîìó èç 3 ìû âûíóæäåíû ïîåõàòü â 5 è
çàòåì âîçâðàùàåìñÿ â 1. Ëåãêî ïðîñëåäèòü òàêîé ïóòü ñëåäîâàíèÿ
íà íàøåì äåðåâå âàðèàíòîâ.




                              82