En Kısa Yol Problemi Practice Questions — KPSS İstatistik

Question 1Question →

Bir lojistik ağında merkez depo olan $1$ numaralı düğümden, teslimat noktası olan $6$ numaralı düğüme en kısa mesafe üzerinden sevkiyat yapılacaktır. Düğümler arasındaki bağlantılar ve bu bağlantıların mesafeleri (birim cinsinden) aşağıda verilmiştir:

Başlangıç Düğümü	Bitiş Düğümü	Mesafe (Birim)
1	2	4
1	3	3
2	3	2
2	4	5
3	4	3
3	5	6
4	5	1
4	6	5
5	6	2

Buna göre, $1$ numaralı düğümden $6$ numaralı düğüme giden en kısa yolun toplam mesafesi kaç birimdir?

8

9

11

12

14

Show answer & explanation

Answer: 9

Answer

En kısa yolun toplam mesafesi 9 birimdir.

Yapılan adım adım analizde (Dijkstra yaklaşımı), 1-3 (

3

), 3-4 (

3

), 4-5 (

1

) ve 5-6 (

2

) yayları takip edildiğinde toplam mesafenin

3+3+1+2=9

birim olduğu görülür. Diğer tüm kombinasyonlar (örneğin düğüm 2 üzerinden gitmek veya 4'ten 6'ya doğrudan atlamak) daha yüksek toplam maliyet/mesafe üretmektedir.

Step-by-Step Solution

1

Başlangıç düğümünden (1) komşu düğümlere olan mesafeleri belirleme

Düğüm 2 için mesafe 4, Düğüm 3 için mesafe 3 birimdir.

Dijkstra algoritması mantığına göre başlangıç noktasından çevreye yayılınır.

2

Düğüm 3 üzerinden Düğüm 4'e geçişi değerlendirme

Düğüm 4'e 1-3-4 yoluyla

3 + 3 = 6

birimle ulaşılır.

1-2-4 yolu

4 + 5 = 9

birim olduğundan, 1-3-4 yolu daha avantajlıdır.

3

Düğüm 4 üzerinden Düğüm 5'e geçişi değerlendirme

Düğüm 5'e 1-3-4-5 yoluyla

6 + 1 = 7

birimle ulaşılır.

Doğrudan 1-3-5 yolu

3 + 6 = 9

birim olduğundan, 4 numaralı düğüm üzerinden geçmek yolu kısaltır.

4

Düğüm 5 üzerinden hedef Düğüm 6'ya ulaşma

Düğüm 6'ya 1-3-4-5-6 yoluyla

7 + 2 = 9

birimle ulaşılır.

Alternatif olan 1-3-4-6 yolu

6 + 5 = 11

birim olduğundan, 9 birimlik yol en kısa çözümdür.

Key Concept

En kısa yol problemlerinde (Dijkstra algoritması vb.) her bir düğüm için kalıcı etiketler oluşturulurken, o düğüme gelen tüm alternatif yollar kıyaslanmalı ve en küçük değer seçilmelidir.

Hints

1

Şebeke üzerinde her düğüme ulaşmak için mümkün olan en küçük toplam değerleri not ederek ilerleyin.

2

Düğüm 4'e ulaştığınızda (toplam 6 birim), Düğüm 6'ya gitmek için 4-6 yayını mı yoksa 4-5-6 güzergahını mı kullanmanın daha kısa olacağını karşılaştırın.

3

En kısa güzergah 1-3-4-5-6 şeklindedir; bu yolun üzerindeki tüm rakamları toplayın.

Practice More

Benzer bir şebekede 'Maksimum Akış' miktarını hesaplamayı deneyerek kapasite kısıtlarını pekiştirebilirsiniz.

Alternative Method

Şebekeyi küçük bir ağ olduğu için deneme-yanılma (inspection) yöntemiyle tüm yolları listeleyerek de çözebilirsiniz: 1-2-4-6 (14), 1-2-4-5-6 (12), 1-3-4-6 (11), 1-3-5-6 (11), 1-3-4-5-6 (9).

Estimated Time:1m 30s

Question 2Question →

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?

10

11

12

13

15

Show answer & explanation

Answer: 10

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

1

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.

2

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.

3

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

ve

K_5

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

4

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.

5

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.

6

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 3Question →

İ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?

46

54

44

48

50

Show answer & explanation

Answer: 44

Answer

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.

Step-by-Step Solution

1

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.

2

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.

3

E

ve

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.

4

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.

Key Concept

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

Estimated Time:2m 30s

En Kısa Yol Problemi

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Hints

Practice More

Alternative Method

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Answer

Step-by-Step Solution

Key Concept

Common Mistakes