Poisk kratchajshego puti

Rassmatriwaetsq tochnyj metod optimizacii marshruta obhoda ob#ektow obrabotki, zadannyh dekartowymi koordinatami, putem pourownewogo postroeniq i sinteza dopustimyh fragmentow marshruta. Testirowanie na klasse ob#ektow obrabotki, wybrannyh bez qwnyh zakonomernostej s raspredeleniem ob#ektow sluchajnym obrazom, daöt dlq zadannogo klassa predwaritel'nuü statisticheskuü ocenku wychislitel'noj slozhnosti metoda blizkoj k polinomial'noj. Zametnaq chuwstwitel'nost' skorosti dostizheniq optimuma ot welichiny raschetnoj dliny summarnyh priraschenij perwonachal'nogo marshruta pobudila k razrabotke nowogo metoda opredeleniq perwonachal'nogo kriteriq optimal'nosti, daüschego naibolee blizkij k minimal'no wozmozhnomu po znacheniü rezul'tat. Dlq obespecheniq dostupa k ispol'zowaniü testowyh primerow bol'shoj razmernosti, gde ob#ekty obhoda zadany tablicej rasstoqnij, predlozheno rasshirenie metoda poiska kriteriq optimal'nosti na ätot sluchaj. Modifikaciq metoda poiska pozwolila otnositel'no bystro i tochno dostigat' s ego pomosch'ü rasschitannogo w bol'shih kolichestwah testow optimal'nogo (naikratchajshego) ili zaqwlennogo takowym znacheniq minimal'noj dliny marshruta.