Евристически алгоритми

Алгоритмите на пълното изброяване (още - точни оптимизационни алгоритми) дават оптимален резултат. При тях се изследват всички възможни решения на задачата и от тях се избира оптималното решение. Търсенето на оптимален резултат се прави явно или неявно с т.нар. “Дърво на търсене” [8]. Неблагоприятните случаи, които съществуват при точните оптимизационни алгоритми, са:

- алгоритъмът е толкова сложен, че никога не може да се състави;

- алгоритъмът може да бъде съставен, но времето за неговото изпълнение нараства толкова бързо, че практичски за реални размери на решаваните задачи не може да се използва;

- необходимата ОП за алгоритъма е толкова голяма, че не може да се осигури.

Във всички тези случаи се налага да се създават и използват евристически алгоритми (ЕА). ЕА използват различни подходи и критерии за търсене на решение. Например, една оптимизационна задача може да се реши не чрез търсене на глобалния оптимум, а чрез сумиране на оптималните решения на отделните подзадачи, или чрез сумиране на оптималните решения на отделните стъпки на алгоритъма на решаваната задачата[2].

Алгоритмите на пълното изброяване, обратно на евристичните, генерират и проверяват всички възможни варианти на решение. Тези алгоритми имат обикновено висока асимптотична сложност – пропорционална на N!, N^N, e^N, a^N и т.нат.

Задача 1: Задача за търговския пътник

Формулирането на задачата е следнто: Търговски пътник трябва да обходи N града, като тръгне от един град, приет за начален, и се върне в него, без да преминава два пъти през един и същ град и цената на транспортните разходи да е минимална. Да се определи маршрутът на търговския пътник, ако са известни пътните разходи между градовете, (когато такъв път съществува)

Алгоритъмът на пълното изброяване за решаване на тази задача образува всички възможни маршрута ,(N-1)! на брой, оценява стойността на всеки и избира маршрутът с минимална стойност. Схематично(чрез псевдокод), алгоритъмът на пълното изброяване е представен на следващите редове.

Алгоритъм

{Въвеждане на входните данни

Suma = max // max е някакво голямо число

for (I=1; I<=(N-1)!; I++){

Образуване на поредната пермутация Pi от N-1 града.

Изчисляване сумата Si на маршрута Pi.

if (Si

Path=Pi;

Suma=Si;

Масив CENA :

1 2 … N

1
2
…			Cij
N

Nach - номер на началния град

Suma – сумарна цена на маршрута

Масив Path:

Nach

….....

Nach

Евристическо решение:

Съществуват различни идеи за евристическо решение на тази задача. Едно от решенията използва “метод на частните цели”, който се състои в следното: Когато търговският пътник се намира в град I, се търси непосетен до този момент град J, с минимална цена на транспортните разходи до него спрямо другите, непосетени до този момент градове, имащи връзка с I. Чрез този подход се получава неоптимално решение, а близко до оптималното, което може да се види от следващата фигура.




Path Suma

1 4 3 2 5 1 29

Разстояния:

Псевдокодът на евристическия алгоритъм е следния:

{ Въвеждане на входни данни.

Suma=0; Br=0;

Path[Br]=Nach;

While (Br

I=Path[Br];

Избира се следващ град J, за който C[I,j] е минимално спрямо цената от I до останалите непосетени до момента градове.

Suma=Suma+Cena[I,j];

Br=Br+1;

}

Suma=Suma+Cena(Path[Br], Nach);

1. Напишете програма на С/С++, която използва алгоритъма на пълното изброяване и определя оптималния маршрут. За примерни данни използвайте даните от фиг.15.1. Колко оптимални маршрута има и защо?