Анализ на решението на първа задача

---

Първата задача в kонкурса по програмиране тази година е представител на широк кръг от задачи за планиране на процеси. Тези задачи разглеждат процеси, които трябва да бъдат изпълнени на един или няколко процесора, и имат различни оптимизационни цели - необходим брой процесори, време за изпълнение, време на бездействие на процесорите, време за чакане и др. Процесите могат да бъдат взаимно зависими - започването на изпълнението на един процес да изисква приключването на друг, да са динамични - не всички процеси са предварително известни, да имат различна важност (ценност или приоритет) и др.
В нашата задача процесите са независими, статични (известни предварително) и еднакво важни и целта е сумарното време на чакане на процесите да е минимално. За чакане на един процес се брои времето от появата (времето за пристигане в орбита на кораб) до започване на изпълнението му (моментът, когато корабът започва да каца). Всеки процес има две характеристики - време на поява и време за изпълнение. Ако някоя от тях беше константна - еднаква за всички процеси - то решението щеше да е лесно.
Ако всички процеси имат еднакво време на поява, то е очевидно (и лесно може да се докаже), че процесите трябва да бъдат изпълнявани в нарастващ ред според времето им за изпълнение. Например, ако имаме само два процеса А и В с време на поява 1 и време за изпълнение съответно 5 и 50, и налице е само един процесор, то ако изпълним първо А, общото време за чакане ще е 5, а ако изпълним първо В, общото време за чакане ще е 50.
Ако пък всички процеси имат еднакво време за изпълнение, то процесите трябва да бъдат изпълнявани в реда на появата им, защото няма полза един процес, който може да бъде изпълнен, да изчаква друг, след като няма разлика във времената им за изпълнение и само би се увеличило общото време за чакане. А когато са се натрупали много процеси, чакащи за изпълнение, то за нас няма значение кой от тях ще изпълним по-напред и затова редът, в който са се появили, е една напълно приемлива наредба за изпълнението им.
Поглеждайки тестовите примери, с които е извършена проверката, ще забележим, че първите четири от тях реализират точно тези два лесни случая. Интересен е резултатът на Александър Андонов - ако програмата му не даваше грешка по време на изпълнението на тези четири тестови примери, вероятно той щеше да заеме първото място. Решението му отстъпва реално само в един тест на решението на Васил Поповски, който реализира генетичен алгоритъм. Използването на такъв алгоритъм се среща рядко на програмистки състезания с алгоритмичен характер, но резултатът в случая е задоволителен - най-добър общ резултат на първите шест тестови примера и 5-то място в класирането.
Една възможна идея за решение е “симулация” на времето. Имаме таймер с начална стойност 0. На всяка стъпка той се увеличава с едно, след това в списъка на чакащите процеси се добавят процесите, които се появяват в този момент, след това в списъка на свободните процесори се добавят тези, които приключват обработката на процес и накрая на свободните процесори даваме да се обработват чакащите процеси. Ако има повече чакащи процеси, отколкото свободни процесори, то логично е да изберем тези, които ще се изпълняват за по-кратко време. Така обаче не се възползваме от това, че процесите са статични и при следния кратък пример - един процесор, два процеса с време на поява 1 и 2 и съответни времена за изпълнение 50 и 5 - се вижда, че решението може да направи доста лошо планиране и в конкретния пример да се получи общо време за чакане 49 вместо 7.
Идея, използваща статичността на процесите, е например тази, реализираща планиране в ред на възможно най-ранно завършване. Първо, определяме да се изпълни процесът, който може да завърши най-рано. След това следващият процес, който може да завърши най-рано от останалите и т.н. Това се реализира лесно за един процесор и се обобщава за N процесора. Внимателният читател вероятно е забелязал, че гореизложените случаи, когато едната от характеристиките на процесите е константа, се решават правилно от алгоритъм, използващ планиране с най-ранно завършване. Решение, реализиращо тази идея, би имало приблизително 86.5 точки, ако беше включено в класирането.
Разбира се, една програма може да реализира няколко алгоритъма и да се изведе отговорът на този, даващ най-доброто решение за текущия тестов пример или да се реализира изчерпващо решение, използващо таймер. Комбинация между тези две идеи също е възможна. Идеята за реализиране на няколко алгоритъма и избирането на по-добрия може да се намери в решението на Кирил Минков - заел второ място - който използва два “лакоми” алгоритъма. Първият от тях на всяка стъпка избира този процес от всички чакащи, който има най-малко време за изпълнение и го изпълнява на процесора, който се освобождава най-рано, а вторият реализира идеята от предходния параграф.
Първите три места в класирането от задача 1 са заети от Иван Пешев, Кирил Минков и Борис Даскалов съответно с 99.19, 99.02 и 98.98 точки. Разликата между тях е минимална и единствено те са успели да съберат над 90 точки, което показва, че всеки от тях е намерил успешен път за реализирането на добро решение на задачата. Все пак, победителят е само един и това е Иван Пешев.