Poisk kratchajshego puti

Rassmatrivaetsya tochnyj metod optimizacii marshruta obhoda obektov obrabotki, zadannyh dekartovymi koordinatami, putem pourovnevogo postroeniya i sinteza dopustimyh fragmentov marshruta. Testirovanie na klasse obektov obrabotki, vybrannyh bez yavnyh zakonomernostej s raspredeleniem obektov sluchajnym obrazom, dajot dlya zadannogo klassa predvaritel'nuju statisticheskuju ocenku vychislitel'noj slozhnosti metoda blizkoj k polinomial'noj. Zametnaya chuvstvitel'nost' skorosti dostizheniya optimuma ot velichiny raschetnoj dliny summarnyh prirashhenij pervonachal'nogo marshruta pobudila k razrabotke novogo metoda opredeleniya pervonachal'nogo kriteriya optimal'nosti, dajushhego naibolee blizkij k minimal'no vozmozhnomu po znacheniju rezul'tat. Dlya obespecheniya dostupa k ispol'zovaniju testovyh primerov bol'shoj razmernosti, gde obekty obhoda zadany tablicej rasstoyanij, predlozheno rasshirenie metoda poiska kriteriya optimal'nosti na jetot sluchaj. Modifikaciya metoda poiska pozvolila otnositel'no bystro i tochno dostigat' s ego pomoshh'ju rasschitannogo v bol'shih kolichestvah testov optimal'nogo (naikratchajshego) ili zayavlennogo takovym znacheniya minimal'noj dliny marshruta.