Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 10

[10-11 Sorular için açıklama]
Birden fazla alt projeden oluşan büyük bir projeyi gerçekleştirmek istiyorsunuz. Örneğin
büyük projeniz bir ev inşa etmek olsun, bunun için tamamlanması gereken alt projeler ise
temelin kazılması, duvarların inşa edilmesi, camların takılması, iç mekanların yapılması
gibi faaliyetler olabilir. Bu alt projeleri alt yüklenici firmalar gerçekleştirecek olsun. Alt
projelerden bazıları, diğerlerinin kendilerinden önce yapılmasını gerektirecektir (örneğin
duvarları inşa etmeden pencereleri takamazsınız), bazıları ise aynı anda yapılabilir. Her alt
projeyi bitirmek için gereken tahmini bir süre olduğunu varsayın. Büyük projenin ne kadar
zamanda tamamlanabileceğini ve çeşitli alt projelere en erken ne zaman başlanabileceğini
önceden bilmek istiyorsunuz ki alt yüklenicileri ayarlayabilesiniz.
Aşağıdaki örnek tabloda A, B, C ve D olarak isimlendirilmiş toplam 4 alt projeden oluşan
bir büyük proje için, her alt projenin süresi (tam gün olarak ve sıfırdan büyük), ve her alt
projenin başlatılabilmesi için tamamlanmış olması gereken alt projelerin listesi verilmiştir.
Alt projelerin başladığı günün sabahında başlayıp, bittiği günün sonunda bittiğini varsayın.
Örneğin A projesi 1. günün sabahında başlarsa, 10. günün sonunda tamamlanacaktır. B
projesi en erken A projesinin bittiği günün ertesi günü sabahında (11. gün sabahında)
başlayıp, 25. günün sonunda tamamlanacaktır. C projesi de en erken A projesinin bittiği
günün ertesi günü sabahında (11. gün sabahında) başlayıp, 35. gün sonunda
tamamlanacaktır. D alt projesi B ve C bitmeden başlayamayacağı için en erken 36. günün
sabahında başlayıp 43. gün sonunda tamamlanacaktır. Projenin tamamı 43. günün sonunda
tamamlanmış olacaktır.

<table><tr><td>Alt Proje</td><td>Süre (tam gün)</td><td>Kendisinden önce tamamlanmış olması gereken alt projeler</td></tr><tr><td>A</td><td>10</td><td>-</td></tr><tr><td>B</td><td>15</td><td>A</td></tr><tr><td>C</td><td>25</td><td>A</td></tr><tr><td>D</td><td>8</td><td>B, C</td></tr></table>

---

Her alt projenin vakit kaybedilmeden başlayabileceği en erken zamanda başladığını
varsayarsak, aşağıda verilen alt proje tablosuna göre projenin tamamı en erken kaçıncı
günün sonunda tamamlanacaktır?

<table><tr><td>Alt Proje</td><td>Süre (gün)</td><td>Kendisinden önce tamamlanmış olması gereken alt projeler</td></tr><tr><td>A</td><td>10</td><td>F</td></tr><tr><td>B</td><td>12</td><td>A, C</td></tr><tr><td>C</td><td>8</td><td>A, F</td></tr><tr><td>D</td><td>3</td><td>C, E, G</td></tr><tr><td>E</td><td>7</td><td>K</td></tr><tr><td>F</td><td>5</td><td>-</td></tr><tr><td>G</td><td>9</td><td>C, F, K</td></tr><tr><td>H</td><td>20</td><td>B, D, E</td></tr><tr><td>K</td><td>24</td><td>-</td></tr></table>

Şıklar:
A) 45
B) 56
C) 47
D) 53
E) 54

Cevap: B 56

Çözüm:
Bu problemi bir çizge ile modelleyelim. Her alt proje bir düğümle temsil edilsin. Bir u alt
projesinin v alt projesinden önce tamamlanmış olması gerekiyorsa u düğümünden v
düğümüne yönlü bir kenar olsun. a(u,v), u düğümünden v düğümüne giden yönlü kenarın
ağırlığını göstersin. u’ya gelen bütün kenarlara ağırlık olarak u’nun süresini atayalım.
Öncelikle projenin bitirilebilir olması için bu çizgenin döngüsüz bir çizge olması
gerekmektedir, verilen tablo ile oluşturduğumuz çizge döngü içermemektedir. Düğümleri
1’den 9’a kadar şu şekilde numaralandıralım: eğer u’dan v’ye bir kenar varsa u’nun
numarası v’ninkinden küçük olsun. Bu numaralama birden fazla şekilde yapılabilir.
Örneğin F:1, K:2, A:3, C:4, G:5, E:6, B:7, D:8, H:9 olsun.
t[i], i. düğümün temsil ettiği alt projenin süresini, s[i] ise i. düğümün temsil ettiği alt
projenin bitebileceği en erken zamanı (s[i]. günün sonu) göstersin. Başlangıçta bütün
düğümler için s[i]=t[i] olarak atansın.
Küçükten büyüğe numara sırasıyla her bir i
düğümü ele alalım: i’ye gelen hiç kenar yoksa s[i] değişmez ve bir sonraki düğüm ile
devam ederiz. Aksi takdirde, i düğümüne gelen kenarların (u1,u2,…uj) numaralı
düğümlerden geldiğini düşünelim. Numaralama koşulumuzdan dolayı, her j için uj < i
olacağından ve düğümleri numara sırasıyla ele aldığımız için bu aşamada s[uj]’nin son
değeri hesaplanmıştır ve s[i]=max (s[u1]+ a(u1 ,i), s[u2]+ a(u2 ,i),…,s[uj]+ a(uj ,i)) olarak
güncellenir. Sırasıyla i=1,2,…,9 için s[i] değerleri bu şekilde hesaplanmış olur: s[1] = 5,
s[2] = 24, s[3] = 15, s[4] = 23, s[5] = 33, s[6]=31, s[7]= 35, s[8]= 36, ve s[9]=56’dır.
s[9]=56 değeri 9 numaralı H alt projesinin en erken 56. günün sonunda bitebileceği
anlamına gelir. H herhangi başka bir alt projenin önkoşul değildir. Bu durumda en geç
tamamlanan alt proje H’dir ve bu büyük projenin de en erken H’nin tamamlanacağı 56.
günün sonunda tamamlanabileceğini gösterir.
Bu problem çizgedeki en uzun yol problemi olarak da formüle edilebilir, öyle ki çizgeye
ek olarak 0 numaralı bir düğüm eklediğimizi, t[0]=0, ve s[0]=0 olduğunu düşünelim.
Orijinal çizgede hiç gelen kenarı olmayan her i düğümüne 0. düğümden gelen bir kenar
ekleyelim ve i. düğüme gelen bu yeni kenara da ağırlık olarak i. düğümün süresini
atayalım. Örneğin bu sorudaki tablo için 0 numaralı düğümden 1 ve 2 numaralı düğümlere
giden, sırasıyla 5 ve 24 ağırlıklarına sahip, birer kenar eklenir. Oluşturduğumuz bu
çizgedeki en uzun yolun uzunluğu projenin en erken bitebileceği günü verir. Örneğin bu
sorudaki çizge için 0.düğüm->K->G->D->H en uzun yoldur ve uzunluğu
24+9+3+20=56’dır.