20. Оценка на точността на алгоритъма. Определяне на най-добрите и най-лошите оценки за алгоритъма за решаване на задачата на пътуващия търговец с помощта на метода за първо търсене в дълбочина.

Целта на оценката на точността на даден алгоритъм е да се определят границите на грешката на предоставеното от него решение. Очевидно при различни входни данни приблизителният алгоритъм може да даде решение, по-близо до оптималното и по-далеч от него, т.е. има смисъл да се говори за поведението на алгоритъма "в най-добрия" и "в най-лошия му вид".

При определяне на „най-лошата” граница на грешка е необходимо да има гаранция, че за всеки допустим набор от входни данни решението няма да бъде по-лошо от границата, а за „най-добрата” граница, че няма набор от данни, за който решението да е по-близо до оптималното. Чрез анализиране на вида и последователността на операциите, извършвани върху графите в процеса на решаване на задачата,е възможно да се конструират входни данни(или да се формулират изисквания към тях), на които тозиалгоритъм води до най-голямата и най-малката грешкаот гледна точка на функционала. Гаранцията за получените оценки на грешката на алгоритъма се осигурява от доказателството, че конструираните набори от входни данни наистина водят съответно до най-лошите и най-добрите резултати на алгоритъма.

Проблемът на пътуващия търговец (търсене на Хамилтонов цикъл с минимално тегло)

Идеята на алгоритъма за решаване чрез търсене в дълбочина е следната:

определяне на ръбовете, инцидентни на първоначалния връх;

след това изберете и включете в генерирания цикъл ръба с минимално тегло (дължина).

---