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

UptoLike

ВУЗ: 

ВолГУ | Волгоград

Составители: 

Рубрика: 

83
1
2 3 4 5
3 4 5 2 4 5 2 3 5 2 3 4
4 5 3 5 3 4 4 5 2 5 2 4
3 5 2 5 2 3 3 4 2 4 2 3
5 4 5 3 4 3 5 4 5 2 4 2 5 3 5 2 3 2 4 3 4 2 3 2
Îáùåå ÷èñëî âàðèàíòîâ ðàâíî (n-1)!
Òàêèå äåðåâüÿ ìîæíî èñïîëüçîâàòü ïðè ðåøåíèè ñëîæíûõ
çàäà÷ äàæå â òîì ñëó÷àå, êîãäà ìû íå ìîæåì ôîðìàëèçîâàòü
ïðîöåññ ðåøåíèÿ. Íàïðèìåð, ìû ðåøàåì, êàê âñòðåòèòü Íîâûé
ãîä. Ïðè ýòîì íóæíî âûáðàòü, ñ êåì åãî âñòðåòèòü, ãäå, êàêèå
ïîäàðêè äàðèòü è ò. ä. Îòâåòèòü íà ýòè âîïðîñû ìû äîëæíû â
êàêîì-òî ïîðÿäêå, è âîçìîæíûå îòâåòû íà î÷åðåäíîé âîïðîñ
ìîãóò çàâèñåòü îò òîãî, êàê ìû îòâåòèëè íà ïðåäûäóùèé âîïðîñ.
Ïîñòðîåíèå äåðåâà âàðèàíòîâ èìååò ñâîè íåäîñòàòêè è ïðå-
èìóùåñòâà. «Ïðîãóëÿâøèñü» ïî âñåì âåòâÿì íàøåãî äåðåâà, ìû
îáÿçàòåëüíî íàéäåì ëó÷øèé âàðèàíò, îäíàêî äåðåâî ìîæåò îêà-
çàòüñÿ ñëèøêîì áîëüøèì. Äëÿ óìåíüøåíèÿ ïåðåáîðà ïðèìåíÿåò-
ñÿ ìåòîä âåòâåé è ãðàíèö. Â íåì ìû òàêæå áóäåì ñòðîèòü âåòâè
äåðåâà âàðèàíòîâ. Ïîýòîìó ìåòîä íàçûâàåòñÿ ìåòîäîì âåòâåé. Ìû
íå áóäåì ðèñîâàòü âñå âåòâè. Çàâåäîìî ïëîõèå âåòâè áóäåì îòáðà-
ñûâàòü. Ïîýòîìó ìåòîä íàçûâàåòñÿ ìåòîäîì ãðàíèö. Ýòî ìåòîä
ðàçóìíîãî ïåðåáîðà. Ñ îäíîé ñòîðîíû, ýòî ïåðåáîð, è ìû íå
ïîòåðÿåì îïòèìàëüíûé âàðèàíò. Ñ äðóãîé ñòîðîíû, ýòî ðàçóìíûé
ïåðåáîð. Ìû íå ðàññìàòðèâàåì çàâåäîìî ïëîõèå âàðèàíòû.
Ìû áóäåì ðàññìàòðèâàòü ìàòðèöû ñòîèìîñòåé áåç îòðèöà-
òåëüíûõ ýëåìåíòîâ. Ïóñòü ëó÷øèé èç íàéäåííûõ ñïîñîáîâ îáúå-
õàòü âñå ãîðîäà èìååò ñòîèìîñòü a. Åñëè â äàëüíåéøåì, ïðè ðàñ-
ñìîòðåíèè äåðåâà âàðèàíòîâ, íà óæå ñäåëàííûõ øàãàõ ìû çàòðà-
òèëè íå ìåíüøå a, òî òàêîé âàðèàíò ìîæíî îòáðîñèòü. Òàê êàê â
ìàòðèöå íåò îòðèöàòåëüíûõ ÷èñåë, òî ñòîèìîñòü âàðèàíòà íå ìî-
æåò óìåíüøèòüñÿ, à ìîæåò òîëüêî óâåëè÷èòüñÿ.
                                                                            1




                2                                           3                                   4                           5



    3       4           5                   2       4               5               2       3       5           2       3        4



4   5   3   5       3       4       4   5       2       5       2       4       3   5   2       5   2   3   3   4   2       4    2   3



5   4   5   3       4       3   5       4       5    2          4       2       5   3   5       2   3   2   4   3   4        2   3       2

     Îáùåå ÷èñëî âàðèàíòîâ ðàâíî (n-1)!
     Òàêèå äåðåâüÿ ìîæíî èñïîëüçîâàòü ïðè ðåøåíèè ñëîæíûõ
çàäà÷ äàæå â òîì ñëó÷àå, êîãäà ìû íå ìîæåì ôîðìàëèçîâàòü
ïðîöåññ ðåøåíèÿ. Íàïðèìåð, ìû ðåøàåì, êàê âñòðåòèòü Íîâûé
ãîä. Ïðè ýòîì íóæíî âûáðàòü, ñ êåì åãî âñòðåòèòü, ãäå, êàêèå
ïîäàðêè äàðèòü è ò. ä. Îòâåòèòü íà ýòè âîïðîñû ìû äîëæíû â
êàêîì-òî ïîðÿäêå, è âîçìîæíûå îòâåòû íà î÷åðåäíîé âîïðîñ
ìîãóò çàâèñåòü îò òîãî, êàê ìû îòâåòèëè íà ïðåäûäóùèé âîïðîñ.
     Ïîñòðîåíèå äåðåâà âàðèàíòîâ èìååò ñâîè íåäîñòàòêè è ïðå-
èìóùåñòâà. «Ïðîãóëÿâøèñü» ïî âñåì âåòâÿì íàøåãî äåðåâà, ìû
îáÿçàòåëüíî íàéäåì ëó÷øèé âàðèàíò, îäíàêî äåðåâî ìîæåò îêà-
çàòüñÿ ñëèøêîì áîëüøèì. Äëÿ óìåíüøåíèÿ ïåðåáîðà ïðèìåíÿåò-
ñÿ ìåòîä âåòâåé è ãðàíèö. Â íåì ìû òàêæå áóäåì ñòðîèòü âåòâè
äåðåâà âàðèàíòîâ. Ïîýòîìó ìåòîä íàçûâàåòñÿ ìåòîäîì âåòâåé. Ìû
íå áóäåì ðèñîâàòü âñå âåòâè. Çàâåäîìî ïëîõèå âåòâè áóäåì îòáðà-
ñûâàòü. Ïîýòîìó ìåòîä íàçûâàåòñÿ ìåòîäîì ãðàíèö. Ýòî ìåòîä
ðàçóìíîãî ïåðåáîðà. Ñ îäíîé ñòîðîíû, ýòî ïåðåáîð, è ìû íå
ïîòåðÿåì îïòèìàëüíûé âàðèàíò. Ñ äðóãîé ñòîðîíû, ýòî ðàçóìíûé
ïåðåáîð. Ìû íå ðàññìàòðèâàåì çàâåäîìî ïëîõèå âàðèàíòû.
     Ìû áóäåì ðàññìàòðèâàòü ìàòðèöû ñòîèìîñòåé áåç îòðèöà-
òåëüíûõ ýëåìåíòîâ. Ïóñòü ëó÷øèé èç íàéäåííûõ ñïîñîáîâ îáúå-
õàòü âñå ãîðîäà èìååò ñòîèìîñòü a. Åñëè â äàëüíåéøåì, ïðè ðàñ-
ñìîòðåíèè äåðåâà âàðèàíòîâ, íà óæå ñäåëàííûõ øàãàõ ìû çàòðà-
òèëè íå ìåíüøå a, òî òàêîé âàðèàíò ìîæíî îòáðîñèòü. Òàê êàê â
ìàòðèöå íåò îòðèöàòåëüíûõ ÷èñåë, òî ñòîèìîñòü âàðèàíòà íå ìî-
æåò óìåíüøèòüñÿ, à ìîæåò òîëüêî óâåëè÷èòüñÿ.



                                                                            83

Страницы