Orman Genel Müdürlüğüne bağlı bir bölge müdürlüğünde, Yangın Yönetim Merkezi (M) ile acil … — KPSS İstatistik

Orman Genel Müdürlüğüne bağlı bir bölge müdürlüğünde, Yangın Yönetim Merkezi ( $M$ ) ile acil müdahale gerektiren bir ormanlık alan ( $H$ ) arasındaki ulaşım ağı planlanmaktadır. Şebekedeki diğer düğümler ( $K_1, K_2, K_3, K_4, K_5, K_6$ ) orman yollarının kesişim noktalarını (kavşakları) göstermektedir. Düğümler arası bağlantılar ve bu bağlantılardaki tahmini seyahat süreleri (dakika) aşağıdaki tabloda verilmiştir:

Başlangıç Düğümü	Bitiş Düğümü	Seyahat Süresi (dk)
$M$	$K_1$	2
$M$	$K_2$	5
$M$	$K_3$	4
$K_1$	$K_2$	2
$K_1$	$K_4$	7
$K_2$	$K_4$	3
$K_2$	$K_5$	8
$K_3$	$K_5$	6
$K_3$	$K_6$	3
$K_4$	$H$	4
$K_5$	$H$	2
$K_6$	$K_5$	1
$K_6$	$H$	5

(Not: Yollar çift yönlü olup her iki yönde de seyahat süreleri eşittir.)

Buna göre, Yangın Yönetim Merkezinden ( $M$ ) hareket eden bir arazözün yangın bölgesine ( $H$ ) ulaşabileceği en kısa süre kaç dakikadır?

10Answer
B
11
C
12
D
13
E
15

Answer

En kısa süre 10 dakikadır.

En kısa seyahat süresi veren rota

M \rightarrow K_3 \rightarrow K_6 \rightarrow K_5 \rightarrow H

güzergahıdır. Bu güzergahın toplam süresi

4 + 3 + 1 + 2 = 10

dakikadır. Bu değer, Dijkstra algoritması tüm düğümlere eksiksiz uygulandığında elde edilen minimum değerdir.

Step-by-Step Solution

Başlangıç düğümünden (

M

) ulaşılan ilk düğümlerin mesafelerini etiketle.

M=0

olmak üzere;

K_1=2

K_2=5

K_3=4

olarak etiketlenir.

Dijkstra algoritmasının başlangıç adımı uyarınca komşu düğümlerin başlangıca olan uzaklıkları atanır.

Etiketi en küçük olan

K_1

(2) üzerinden komşularını güncelle.

K_2

için yeni etiket

\min(5, 2+2) = 4

olur.

K_4

için etiket

2+7 = 9

olur.

K_1

üzerinden geçmek,

K_2

'ye doğrudan gitmekten (5 > 4) daha kısadır.

Sıradaki en küçük etiketli düğüm

K_3

(4) üzerinden komşularını güncelle.

K_6

için etiket

4+3 = 7

olur.

K_5

için etiket

4+6 = 10

olur.

K_3

üzerinden geçilerek

K_6

K_5

düğümlerine ilk tahmini en kısa mesafeler belirlenir.

Güncellenmiş

K_2

(4) üzerinden komşularını güncelle.

K_4

için yeni etiket

\min(9, 4+3) = 7

olur.

K_5

için etiket

\min(10, 4+8) = 10

olarak kalır.

K_2

üzerinden

K_4

'e ulaşmak (4+3=7), önceki güzergahtan (9) daha kısadır.

K_6

(7) ve

K_4

(7) üzerinden kalan bağlantıları ve hedefi (

H

) güncelle.

K_6

üzerinden

K_5

etiketi

\min(10, 7+1) = 8

olarak güncellenir.

K_6

üzerinden

H

etiketi

7+5=12

olur.

K_4

üzerinden

H

etiketi

7+4=11

olur.

K_6

'dan

K_5

'e olan 1 dakikalık kısa yol,

K_5

'in etiketini 10'dan 8'e düşürür. Bu adım algoritmanın kritik güncellemesidir.

Güncellenmiş

K_5

(8) üzerinden hedefi (

H

) son kez güncelle.

H

için nihai etiket

\min(11, 8+2) = 10

olarak bulunur.

K_5

üzerinden hedefe ulaşmak (

8+2=10

), diğer tüm alternatiflerden (

K_4

üzerinden 11,

K_6

üzerinden 12) daha kısadır.

Key Concept

Şebeke analizi kapsamında düğüm etiketlerinin iteratif olarak güncellenmesi ve en kısa yolun (Dijkstra algoritması) bulunması.

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Topics

More questions from this topic