Решение на задача 3

Решение на задача 3

---

Трета задача от Конкурса на PC Magazine Bulgaria и Musala Soft беше и Турнир по програмиране на Basscom. За предложената задача не съществува оптимално решение, което позволяваше приложението на различни подходи, което, комбинирано с наградите, предложи много емоции на участниците. Победител в кръга стана Ростислав Руменов, следван от Антони Средков и Милослав Средков. На награждаването Ивелина Захариева беше отличена с наградата “Оригинално решение”. Тя заслужи това за оригиналното си решение, с което не успя да спечели поради дребна грешка в неговата реализация.
Задача 3 спада към клас задачи, в които изискването е да бъдат наредени група задачи в ред, който минимизира специфична характеристика, свързана с тяхното последователно изпълнение. В нашият случай важната характеристика е произведението обем на заеманата памет * време. Подобни проблеми възникват при изпълнението на задачи, където паметта, в която се пазят междинните резултати, е скъпа.
Задачата може да се разгледа в два различни аспекта – като задача, в която се търси най-добрата пермутация на елементите, използвайки останалите характеристики само, за да оценяваме дали дадена пермутация е валидна и колко е добра. Другият подход включва наблягането на специфичните характеристики на задачата и зависимостите между нейните елементи, което превръща задачата в задача от теория на графите.
Един от най-добрите подходи за решаване на задачи, в които се търси колкото се може по-добра пермутация, са генетичните алгоритми. Стъпките, които характеризират един генетичен алгоритъм, са:
1. Генериране на начално множество от решения.
2. Модифициране на решенията от текущото множество, създавайки нови такива, не задължително по-добри (генериране на поколение).
3. Избиране на най-добрите решения от текущите и от поколението, които стават новото текущо множество.
4. Стъпките 2-3 се повтарят, докато е считано за необходимо или докато времето за изпълнението на програмата не приключи.
Всяка от изложените стъпки може да се реализира много лесно и без особени усилия и това да даде добра начална точка за вашето решение. Всички следващи подобрения обикновено са свързани със задълбочаване в спецификата на задачата и модифициране на някоя от стъпките.
Съществува теория на графите, която се занимава с подобни на нашата задача проблеми, известни като Minimum Linear Arrangements (MLA). Теория, която е прекалено дълга и тежка на моменти за излагане в настоящия анализ. Само ще споменем, че в теорията могат да се намерят добри приблизителни алгоритми (approximation algorithms), които биха дали добро начално множество от решения, както и техники като Spreading Metrics, с които да се ограничава пренареждането на елементите, и получаването на по-добри решения от текущото множество.

---