โปรแกรม C สำหรับเส้นทางต้นทุนขั้นต่ำ

ในที่นี้ เราจะแก้ปัญหาพาธต้นทุนขั้นต่ำใน C โดยนัยนี้เกิดขึ้นบนเมทริกซ์ 2 มิติ โดยที่แต่ละเซลล์มีค่าใช้จ่ายในการเดินทาง เราต้องหาเส้นทางจากมุมบนซ้ายไปมุมล่างขวาด้วยค่าเดินทางขั้นต่ำ คุณสามารถสำรวจเซลล์ด้านล่างและด้านขวาล่างจากเซลล์ที่กำหนดเท่านั้น

ในการแก้ปัญหานี้โดยเฉพาะการเขียนโปรแกรมแบบไดนามิกนั้นดีกว่าการเรียกซ้ำ

กำหนดเมทริกซ์ต้นทุน c ost[ ][ ] และตำแหน่ง (m,n) เราต้องเขียนฟังก์ชันที่ส่งคืนต้นทุนของเส้นทางขั้นต่ำในการเข้าถึง (m,n) จาก (0,0) ต้นทุนรวมของเส้นทางที่จะไปถึง (m, n) คือผลรวมของต้นทุนทั้งหมดบนเส้นทางนั้น (รวมทั้งต้นทางและปลายทาง)

สมมติฐาน - ค่าใช้จ่ายทั้งหมดเป็นบวก ไม่มีวงจรต้นทุนติดลบในเมทริกซ์อินพุต

ตัวอย่าง

ค้นหาเส้นทางต้นทุนขั้นต่ำไปยัง (2,2)

ค่าใช้จ่ายจะได้รับภายในภาพเอง เส้นทางจะเป็น (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2) ค่าของเส้นทางคือแปด (1 +2+2+ 3)

แนวทาง − สร้างเมทริกซ์คำตอบที่มีขนาดใกล้เคียงกับเมทริกซ์ที่กำหนด

เติมเมทริกซ์นี้ในลักษณะจากล่างขึ้นบน

มอบให้ − arrA[ ][ ]. ในแต่ละเซลล์ เรามี 2 ตัวเลือก (ไปทางขวาหรือลง) และเราสามารถเลือกอย่างน้อย 2 ตัวเลือกนั้นสำหรับเซลล์ i,j

solution[i][j]=A[0][j] if i=0, 1st row
   =A[i][0] if j=0, 1st column
=A[i][j]+Min(solution[i=1],[j],solution[i][j-1]) if i>0 && j>0

แนวทางที่ตามมาในคำตอบอัลกอริธึมสามารถใช้เพื่อแก้ปัญหานี้ได้อย่างมีประสิทธิภาพโดยใช้การเขียนโปรแกรมแบบไดนามิก สร้างตารางเส้นทางต้นทุนขั้นต่ำขนาด m,n และกำหนด−

minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)

อย่างชัดเจน

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero
minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero

ต่อไป เราจะเติมเมทริกซ์เส้นทางต้นทุนขั้นต่ำโดยใช้สูตรที่คล้ายคลึงกันที่เราใช้ในอัลกอริทึม เนื่องจากค่าก่อนหน้านี้ทั้งหมดจะได้รับการคำนวณแล้วในเมทริกซ์เส้นทางต้นทุนขั้นต่ำ เราจะไม่คำนวณค่าเหล่านี้ใหม่เหมือนที่เราทำในคำตอบของอัลกอริทึม

minimumCostPath[i][j] = costMatrix[i][j] +minimum(minimumCostPath[i - 1][j - 1],minimumCostPath[i - 1][j],minimumCostPath[i][j - 1])

ที่นี่สำหรับการคำนวณ maximumCostPath[i][j] เรามักจะใช้ maximumCostPath[i - 1][j - 1], maximumCostPath[i - 1][j] และ maximumCostPath[i][j - 1] เป็นผล เซลล์เหล่านี้เป็นเซลล์ที่อนุญาตเพียงเซลล์เดียว ซึ่งเราจะไปถึงค่าต่ำสุดของค่าพาธ[i][j] ในที่สุด เราจะคืนค่าค่าต่ำสุดของค่าพาธ[m][n]

ความซับซ้อนของเวลาของอัลกอริธึมการเขียนโปรแกรมแบบไดนามิกคือ O(mn)

ตัวอย่าง

#include <iostream>
using namespace std;
int min_(int a, int b, int c){
   if (a < b)
      return (a < c) ? a : c;
   else
      return (b < c) ? b : c;
}
int min_cost(int cost[4][4], int m, int n){
   int i, j;
   int tot_cost[4][4];
   tot_cost[0][0] = cost[0][0];
   for (i = 1; i <= m; i++)
   tot_cost[i][0] = tot_cost[i - 1][0] + cost[i][0];
   for (j = 1; j <= n; j++)
      tot_cost[0][j] = tot_cost[0][j - 1] + cost[0][j];
   for (i = 1; i <= m; i++)
      for (j = 1; j <= n; j++)
         tot_cost[i][j] = min_(tot_cost[i - 1][j - 1], tot_cost[i - 1][j], tot_cost[i][j - 1]) + cost[i][j];
      return tot_cost[m][n];
}
int main(){
   int cost[4][4] = {
      { 9, 9, 4 },
      { 8, 0, 9 },
      {1, 2, 8}
   };
   cout<<" The minimum cost is "<<min_cost(cost, 2, 2);
   return 0;
}

ผลลัพธ์

The minimum cost is 17