Maliyet tablosu

Ş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.

Örnek çözümü göster

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())

Kendini test et

DP bağıntısı

dp[i] = dp[j] + ____[j][i]

Cevabı göster

dp[i] = dp[j] + cost[j][i]

Köşegen neden sıfırdır?
- Hatalı veri
- Aynı şehre maliyet yok
- Sonsuz maliyet
- Negatif maliyet
Cevabı göster

Aynı şehre maliyet yok — Aynı şehre gitmenin maliyeti yoktur.
Maliyet tablosu: kavramları eşleştir

cost[0][1]

A→B
cost[1][2]

B→C
cost[2][3]

C→D
cost[0][3]

A→D

Sıradaki ders: DP çözümü

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler