Musala Soft and PC Magazine Bulgaria

Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria

Състезателна система

Описание на използвания алгоритъм :

Идеята за решение на задачата се базира на алгоритъма на Дейкстра за намиране на оптимален път в граф. При повечето реализации на алгоритъма се търси път с минимална дължина, под минимална дължина на път се разбира сумата от теглата на рабрата участващи в пътя. Алгоритъма в този вид е неприложим, тъй като ние търсим път с максимална оценка. Естествено можем да съпоставим на всяко
ребро число отговарящо на разликите в оценките на пътищата и да търсим път, който има най-малка сума от разлики. Тази идея използва факта, че ако от източника тръгнем по ребро, което има оценка Ep=p, то всеки път включващ това ребро ще има оценка Ep1 Ј p това се вижда от формулата по която се изчислява Ep на даден път. Ето защо можем да определим Ep като монотонно намаляваща величина докато "строим" път неговата Ep оценка непрекъснато намалява или се запазва като стойност. Понеже Ep е монотонно намаляваща това означава че всеки път, с поне един цикъл, има Ep, която е Ј от оценката на същия път без цикъла (циклите).

В програмата ZAD_3_7.EXE алгоритъма на Дейкстра е реализиран по следния начин :
1.) Вземаме върхът източник (Source) и го включваме във FIFO опашка (Queue).
2.) Началото на опашката (Head) сочи първия елемент.
В специален масив (Path) запазваме Ep оценките на най-добрия път до връх i:
Path[i].p показва произведението от надежностите на ребрата до връх i
Path[i].MinQ показва пропускливоста на най-добрия път до връх i
Path[i].parent показва върхът от който се стига с оценка
Ep = Path[i].p*Path[i].MinQ до връх i
3.) Намираме всички съседи на Head елемента на опашката и ако не са включени в опашката (Queue) ги включваме.На всяко включване на елемент в опашката увеличаваме count.(count е броя на елементите в опашката)
4.) За всеки елемент от Head+1 (за да не допускаме намирането на път с цикли) до count от опашката повтаряме :
a) Проверяваме дали пътя до разглеждания връх през Queue[Head] не е с по-голяма Ep оценка.
b) Ako е вярно a) променяме даните в Path[i] за върхът i
5.) Head се премества на следващия елемент след като стигнем до елемента count от опашката (Queue).
6.) Повтаряме стъпки 3.),4.) и 5.) докато не стане истина Head >= count+1 (докато в опашката има елементи)

Алгоритъмът се основава на правилото на триъгълника.
Алгоритъмът за намиране на оптимален път има :
O(n) по отношение на памет
О(n*(n-1)/2) по отношение на брой операции
или имаме полиномиален алгоритъм за намиране на оптимален път.
Пътя по който се стига до целта (reciever) се получава от Path[i].parent полето. Лошото е че пътя е в обратен ред от целта до източника, но това се поправя лесно, може чрез рекурсия или чрез допълнителен масив (стек).
Оценката на пътя от източника (source) до целта (reciever) е произведението : Path[reciever].MinQ*Path[reciever].p
Ako няма път от source до reciever тогава Path[reciever].parent = 0 и програмата записва във файла NETWORK.OUT "0 0".

Илиян Ненов

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.