মিন কস্ট পাথের পাইথন প্রোগ্রাম

এই আর্টিকেলে আমরা নিচের সমস্যা সমাধানের কথা শিখব।

সমস্যা: একটি কস্ট ম্যাট্রিক্স এবং একটি পজিশন (m, n) দেওয়া আছে, আমাদের (0, 0) থেকে (m, n) পৌঁছানোর মিনিমাম কস্ট পাথ বের করতে হবে। প্রতিটি সেল একটি কস্ট রিপ্রেজেন্ট করে এক সেল থেকে অন্য সেলে যাওয়ার জন্য।

চলুন নিচের ইমপ্লিমেন্টেশনে সমাধানটি পর্যবেক্ষণ করি।

উদাহরণ

# ডাইনামিক অ্যাপ্রোচ
R = 3
C = 3

def minCost(cost, m, n):
    # ইলিশিয়ালাইজেশন
    tc = [[0 for x in range(C)] for x in range(R)]
    # বেস কেস
    tc[0][0] = cost[0][0]
    # টোটাল কস্ট (tc) অ্যারে
    for i in range(1, m + 1):
        tc[i][0] = tc[i-1][0] + cost[i][0]
    # tc অ্যারে
    for j in range(1, n + 1):
        tc[0][j] = tc[0][j-1] + cost[0][j]
    # বাকি tc অ্যারে
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]
    return tc[m][n]

# মেইন
cost = [[1, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Total Cost:", minCost(cost, 2, 1))

আউটপুট

Total Cost: 13

সभी ভেরিয়েবল লোকাল স্কোপে ঘোষণা করা হয়েছে এবং তাদের রেফারেন্স উপরের চিত্রে দেখা যাচ্ছে।

উপসংহার

এই আর্টিকেলে আমরা শিখেছি কিভাবে মিন কস্ট পাথের পাইথন প্রোগ্রাম লিখতে হয়।