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



Дата31.12.2017
Размер46.56 Kb.
ЛУ- 14,15:

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

Цел: Упражняване в създаване и изследване на алгоритми за пълно изброяване и евристически алгоритми за намиране на решения, близки до оптималното

Теоретична част:

Алгоритмите на пълното изброяване (още - точни оптимизационни алгоритми) дават оптимален резултат. При тях се изследват всички възможни решения на задачата и от тях се избира оптималното решение. Търсенето на оптимален резултат се прави явно или неявно с т.нар. “Дърво на търсене” [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













Cij - цена на маршрута между I-я и J-я градове.

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



Резултатите са:

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

Масив Path:


Nach







….....

Nach

Асимптотичната оценка на този алгоритъм е O(N!), което даже за малки стойности на N е неприемливо.

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

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




Path Suma

1 4 3 2 5 1 29

Разстояния:



1-2=5 1-3=15 1-4=1 1-5=9

2-3=7 2-4=8 2-5=9

3-4=3 3-5=12 4-5=21
Фиг.15.1. Примерен граф на задачата за търговския пътник
Маршрутът 143251 е получен с евристически алгоритъм с начален град - 1. (Той се оказва и оптимален за този граф)

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

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

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;


Path[Br]=J;

}

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



} /* край */
Асимптотичната оценката на този алгоритъм е O(N*N), тъй като основният цикъл се повтаря N-1 пъти, а във всеки цикъл има около N на брой операции.
Въпроси по темата и задачи за изпълнение:

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



2. Да се състави евристичен алгоритъм и се напише програма на С/С++ за следната задача: Даден е куфар с обем V и неограничен запас от видове предмети, като всеки предмет I има обем vi и цена ci. В раницата могат да се поставят само цяло число предмети. Да се напълни куфара с предмети, така че да се получи максимална цена на предметите в него, без значение от какъв вид са те.


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница