İl Afet ve Acil Durum (AFAD) koordinasyon merkezinden (A düğümü), afet bölgesindeki bir to… — KPSS İstatistik

İl Afet ve Acil Durum (AFAD) koordinasyon merkezinden ( $A$ düğümü), afet bölgesindeki bir toplanma alanına ( $G$ düğümü) özel donanımlı bir arama kurtarma aracının en hızlı şekilde ulaşması hedeflenmektedir. Güzergâh üzerindeki yolların mevcut durumu incelenmiş ve düğümler arası tahmini geçiş süreleri (dakika cinsinden) aşağıdaki tabloda özetlenmiştir:

Başlangıç	Bitiş	Süre (dk)
$A$	$B$	$12$
$A$	$C$	$15$
$B$	$D$	$19$
$B$	$E$	$20$
$C$	$D$	$10$
$C$	$F$	$25$
$D$	$E$	$5$
$D$	$F$	$14$
$E$	$G$	$14$
$F$	$G$	$9$

Buna göre, arama kurtarma aracının $A$ düğümünden $G$ düğümüne ulaşabileceği en kısa süre kaç dakikadır?

A
46
B
54
44Cevap
D
48
E
50

Cevap

Dijkstra algoritması uygulandığında en kısa rotanın

A \rightarrow C \rightarrow D \rightarrow E \rightarrow G

olduğu ve sürenin 44 dakika olduğu görülür.

Düğüm etiketleri sırasıyla hesaplandığında;

A(0)

B(12)

C(15)

olarak bulunur.

D

düğümüne en kısa ulaşım

C

üzerinden

15+10=25

dakikadır.

E

düğümüne en kısa ulaşım

D

üzerinden

25+5=30

dakikadır.

F

düğümüne en kısa ulaşım

D

üzerinden

25+14=39

dakikadır.

G

hedefine ise

E

(

30+14=44

) ve

F

(

39+9=48

) üzerinden gelinebilmektedir. Minimum süre 44 dakikadır ve bu süreye

A \rightarrow C \rightarrow D \rightarrow E \rightarrow G

rotası ile ulaşılır.

Adım Adım Çözüm

Başlangıç düğümünün etiketlenmesi ve komşularının hesaplanması.

A

düğümünün etiketi

0

olur.

B

düğümüne

0+12=12

C

düğümüne

0+15=15

sürede ulaşılır.

Dijkstra algoritmasında başlangıç noktası

0

alır ve doğrudan gidilebilen ilk düğümlerin etiketleri başlangıç ağırlıklarıyla belirlenir.

D

düğümü için en kısa geliş yolunun belirlenmesi.

B

üzerinden geliş:

12 + 19 = 31

C

üzerinden geliş:

15 + 10 = 25

. Küçük olan seçilir,

D

'nin etiketi

25

olarak güncellenir.

Bir düğüme gelen alternatif yollar karşılaştırılarak en küçük değere sahip olan kalıcı etiket olarak seçilir.

E

F

düğümleri için minimum etiketlerin hesaplanması.

E

için:

B

'den

12+20=32

;

D

'den

25+5=30

E

'nin etiketi

30

olur.

F

için:

C

'den

15+25=40

;

D

'den

25+14=39

F

'nin etiketi

39

olur.

Ağ üzerindeki ilerleyişte her düğüm, kendisine gelen tüm okların başlangıç etiketleri ve dal ağırlıkları toplanarak optimize edilir.

Hedef düğüm olan

G

için son hesaplamanın yapılması.

E

'den geliş:

30 + 14 = 44

F

'den geliş:

39 + 9 = 48

. Minimum değer

44

olarak bulunur.

Hedef düğüme ulaşan tüm alternatif yollar içindeki minimum süre, şebekenin en kısa yolunu (optimum çözümü) verir.

Anahtar Kavram

Dijkstra algoritması kullanılarak düğüm etiketlerinin ileriye doğru güncellenmesi ve en kısa yolun tespiti.

Tahmini Süre:2m 30s

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru