Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
Evgeny Ivanko · Vestnik Udmurtskogo Universiteta Matematika Mekhanika Komp yuternye Nauki · 2011
c Å. Å. Èâàíêî ÊÐÈÒÅÐÈÉ ÓÑÒÎÉ×ÈÂÎÑÒÈ ÎÏÒÈÌÀËÜÍÎÃÎ ÌÀÐØÐÓÒÀ  ÇÀÄÀ×Å ÊÎÌÌÈÂÎßÆÅÐÀ ÏÐÈ ÄÎÁÀÂËÅÍÈÈ ÂÅÐØÈÍÛ 1Ïîëó÷åíû íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ, îáåñïå÷èâàþùèå ñîõðàíåíèå îïòèìàëüíîñòè ìàðøðóòà îáõîäà ìíîæåñòâà âåðøèí ïðè âñòàâêå íîâîé âåðøèíû ìåæäó äâóìÿ ïîñëåäîâàòåëüíûìè (â ñìûñëå ñóùåñòâóþùåãî îïòèìàëüíîãî ìàðøðóòà) âåðøèíàìè.Ïðåäëîæåí àëãîðèòì ïîñòðîåíèÿ îáëàñòåé óñòîé-÷èâîñòè, ïðîâåäåí ðÿä ýêñïåðèìåíòîâ äëÿ çàäà÷è êîììèâîÿæåðà íà åâêëèäîâîé ïëîñêîñòè.Êëþ÷åâûå ñëîâà: çàäà÷à êîììèâîÿæåðà, óñòîé÷èâîñòü.Ââåäåíèå  íàñòîÿùåé ðàáîòå ìû èíòåðåñóåìñÿ óñòîé÷èâîñòüþ êðàò÷àéøåãî ìàðøðóòà â çàäà÷å êîììèâîÿæåðà ïðè èçìåíåíèè ìíîæåñòâà ïîñåùàåìûõ âåðøèí.Çàäà÷à êîììèâîÿæåðà ñ÷èòàåòñÿ îäíîé èç êëàññè÷åñêèõ òðóäíîðåøàåìûõ çàäà÷.Ãëàâíûì îáðàçîì ýòà çàäà÷à âîçíèêàåò ïðè âûÿâëåíèè öåëåñîîáðàçíîãî ïîðÿäêà íà ìíîæåñòâàõ, íàïðèìåð â ìàðøðóòíûõ ïîñòàíîâêàõ, ïðîáëåìàõ âîññòàíîâëåíèÿ õðîíîëîãèè ñîáûòèé è óïîðÿäî÷èâàíèÿ ìíîãîìåðíûõ äàííûõ.Çàäà÷à êîììèâîÿæåðà õîðîøî èçó÷åíà êàê òåîðåòè÷åñêè, òàê è àëãîðèòìè÷åñêè, íàïðèìåð â òàêèõ ðàáîòàõ, êàê [13].Èññëåäîâàíèå âëèÿíèÿ èçìåíåíèÿ íà÷àëüíûõ äàííûõ íà ðåøåíèå çàäà÷è ïðåäñòàâëÿåò èíòåðåñ â ðàçëè÷íûõ îáëàñòÿõ ìàòåìàòèêè.Îäíèì èç âàæíûõ ÷àñòíûõ ñëó÷àåâ â ýêñòðåìàëüíûõ çàäà÷àõ ÿâëÿåòñÿ âûÿâëåíèå èçìåíåíèé íà÷àëüíûõ äàííûõ, ïðè êîòîðûõ íàéäåííûé ýêñòðåìóì ñîõðàíÿåòñÿ. òàêèõ ñëó÷àÿõ ãîâîðÿò îá óñòîé÷èâîñòè ðåøåíèÿ ýêñòðåìàëüíîé çàäà÷è.Ñóùåñòâóåò áîëüøîå êîëè÷åñòâî ðàáîò, ïîñâÿùåííûõ óñòîé÷èâîñòè ðåøåíèé äèñêðåòíûõ îïòèìèçàöèîííûõ çàäà÷ â öåëîì [47] è çàäà÷è êîììèâîÿæåðà â ÷àñòíîñòè [810].Îáû÷íî, îäíàêî, óñòîé÷èâîñòü îïòèìàëüíîãî ðåøåíèÿ çàäà÷è êîììèâîÿæåðà èññëåäóåòñÿ â ñëó÷àå èçìåíåíèÿ ñòîèìîñòåé ïîïàðíûõ ïåðåìåùåíèé ìåæäó âåðøèíàìè ïðè íåèçìåííîì êîëè÷åñòâå âåðøèí.Ðàíåå [11] àâòîðîì áûëè ïîëó÷åíû äîñòàòî÷íûå óñëîâèÿ óñòîé÷èâîñòè îïòèìàëüíîãî ìàðøðóòà ïðè äîáàâëåíèè èëè óäàëåíèè îäíîé âåðøèíû