Maliyet tablosu
- Algoritmalar kursu
- İleri seviye
- Ders 18/56
- 4 dk
Şehirler arası maliyet tablosunu tanımlarsın.
Maliyet matrisi
Maliyet matrisi cost[i][j], i'den j'ye gitmenin maliyetini verir. Yönlü graf olduğu için cost[i][j] ile cost[j][i] farklı olabilir; bizim örneğimizde yalnızca j > i için değer tanımlıdır.
Bu yapı, dinamik programlama çözümünün temelidir. Matrisin köşegeni sıfırdır çünkü bir şehrin kendisine gitmesinin maliyeti yoktur.
Köşegen sıfır
Matrisin köşegeni her zaman sıfırdır: cost[i][i] = 0. Çünkü bir şehirden yine aynı şehre gitmenin maliyeti yoktur.
Bu özellik, maliyet tablosunun tutarlılığını sağlar ve dinamik programlama çözümünün doğru çalışmasının temelidir.
Uygulama init_cost fonksiyonu
init_cost() yaz. 4x4 maliyet matrisini döndür: köşegen 0, cost[0]=[0,10,25,60]. print(init_cost()) ile matrisi yazdır.
Başlangıç kodu
def init_cities():
# Şehir listesini döndür
return ['A', 'B', 'C', 'D']
def init_cost():
# Maliyet matrisini döndürÖrnek çözüm
def init_cities():
# Şehir listesini döndür
return ['A', 'B', 'C', 'D']
def init_cost():
# Maliyet matrisini döndür
return [[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
print(init_cost())Beklenen çıktı
[[0, 10, 25, 60], [0, 0, 20, 50], [0, 0, 0, 30], [0, 0, 0, 0]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 DP bağıntısı
dp[i] = dp[j] + ____[j][i]dp[i] = dp[j] + cost[j][i]Açıklama: cost doğru.
2 Köşegen neden sıfırdır?
- Hatalı veri
- Aynı şehre maliyet yok Doğru cevap
- Sonsuz maliyet
- Negatif maliyet
Açıklama: Aynı şehre gitmenin maliyeti yoktur.
3 Maliyet tablosu: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
cost[0][1] |
A→B |
cost[1][2] |
B→C |
cost[2][3] |
C→D |
cost[0][3] |
A→D |