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

        Àëãîðèòì ðåøåíèÿ çàäà÷è êîììèâîÿæåðà
     Øàã 1. Ðåøàåì çàäà÷ó î íàçíà÷åíèè âåíãåðñêèì àëãîðèòìîì.
Åñëè ïðè ðåøåíèè çàäà÷è î íàçíà÷åíèè ïîëó÷èëñÿ îäèí öèêë,
òî îí áóäåò ðåøåíèåì çàäà÷è êîììèâîÿæåðà. Ïåðåõîäèì ê øàãó 4.
 ïðîòèâíîì ñëó÷àå ïåðåõîäèì ê øàãó 2.
     Øàã 2. Ñêëåèâàåì ïîëó÷åííûå öèêëû â îäèí áîëüøîé.
     Øàã 3. Ïðèìåíÿåì ìåòîä âåòâåé è ãðàíèö. Ñòðîèì äåðåâî
ðåøåíèé äëÿ íîâîé ìàòðèöû, ïðîäîëæàÿ òîëüêî òå âåòâè, êîòî-
ðûå ìîãóò äàâàòü ìåíüøåå çíà÷åíèå Líîâ, ïî ñðàâíåíèþ ñ ïðåäû-
äóùèìè âåòâÿìè. Íà÷èíàåì ñ ëþáîé âåðøèíû. Îêîëî ðåáåð óêà-
çûâàåì çàòðàòû íà ïóòü. Âûáèðàåì íàèáîëåå ïåðñïåêòèâíóþ âåòâü
(ñ íàèìåíüøåé ñòîèìîñòüþ) è ïðîäîëæàåì ñòðîèòü äåðåâî äî
ñëåäóþùåãî óðîâíÿ. Çàòåì ïîâòîðÿåì íàøè äåéñòâèÿ: âûáèðàåì
íàèáîëåå ïåðñïåêòèâíóþ âåòâü. Ïîñòóïàåì òàêèì îáðàçîì, ïîêà
îíà íå áóäåò äîñòðîåíà ïîëíîñòüþ. Ïîäñ÷èòûâàåì ñòîèìîñòü âûá-
ðàííîãî ïóòè è äàëåå èñïîëüçóåì ýòî ÷èñëî çà îñíîâó ïðè àíàëè-
çå îñòàâøèõñÿ âåòâåé. Åñëè åñòü âåòâè, êîòîðûå ìîãóò äàòü êî-
íå÷íóþ ñòîèìîñòü ìåíüøå îñíîâíîé, òî ïðîäîëæàåì ýòè âåòâè
óêàçàííûì âûøå ñïîñîáîì. Îñòàëüíûå âåòâè îãðàíè÷èâàåì. Ïî-
ëó÷åííûé ïóòü áóäåò ÿâëÿòüñÿ îïòèìàëüíûì, à ñòîèìîñòü — ìè-
íèìàëüíîé.
     Øàã 4. Ïîäñ÷èòûâàåì ñòîèìîñòü ïî ïåðâîíà÷àëüíîé ìàòðèöå.
                         Òðóäîåìêîñòü
     Ýòà çàäà÷à îòíîñèòñÿ ê ÷èñëó òðóäíîðåøàåìûõ. Ïðè áîëü-
øîì ÷èñëå ãîðîäîâ âîçíèêàåò ñëèøêîì ìíîãî âàðèàíòîâ (ïîðÿä-
êà n!). Ïåðåñìîòðåòü âñå âîçìîæíûå âàðèàíòû ïðè áîëüøèõ n
íåâîçìîæíî äàæå íà ñóïåðÝÂÌ. Òîãäà ðåêîìåíäóåòñÿ ïðèìåíå-
íèå ýâðèñòè÷åñêîãî àëãîðèòìà.  ýòîì ñëó÷àå ìû íå ìîæåì ãàðàí-
òèðîâàòü, ÷òî ïðåäëîæåííûé íàìè ñïîñîá îáúåçäà ãîðîäîâ îïòè-
ìàëåí.




                              87