เส้นทางต้นทุนขั้นต่ำ

กำหนดเมทริกซ์ของต้นทุนที่แตกต่างกัน นอกจากนี้ยังมีเซลล์ปลายทาง เราต้องหาเส้นทางต้นทุนขั้นต่ำเพื่อไปถึงเซลล์ปลายทางจากเซลล์เริ่มต้น (0, 0)

แต่ละเซลล์ของเมทริกซ์แสดงถึงต้นทุนในการสำรวจผ่านเซลล์นั้น

จากเซลล์ เราไม่สามารถย้ายไปที่ใดก็ได้ เราสามารถย้ายไปทางขวาหรือด้านล่างหรือไปยังเซลล์ในแนวทแยงมุมล่างขวาเพื่อไปยังปลายทางได้

อินพุตและเอาต์พุต

Input:
The cost matrix. And the destination point. In this case the destination point is (2, 2).
1 2 3
4 8 2
1 5 3

Output:
The minimum cost to reach to the destination from (0, 0). The minimum cost is 8.

อัลกอริทึม

minCostPath(destX, destY, cost)

ป้อนข้อมูล - สถานที่ (x, y) ของปลายทาง และเมทริกซ์ต้นทุน

ผลลัพธ์ − ต้นทุนขั้นต่ำในการไปถึงจุดหมายปลายทาง

Begin
   define matrix totalCost, whose order is same as cost matrix
   totalCost[0, 0] = cost[0, 0]

   for i := 1 to destX, do
      totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0]
   done

   for j := 1 to destY, do
      totalCost[0, j] := totalCost[0, j-1] + cost[0, j]
   done

   for all places (i, j) from (1, 1) to (destX, destY), do
      totalCost[i, j] := minimum of totalCost[i-1, j-1], totalCost[i-1, j] and (totalCost[i, j-1] + cost[i,j])
   done

   return totalCost[destX, destY]
End

ตัวอย่าง

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;

int cost[ROW][COL] = {
   {1, 2, 3},
   {4, 8, 2},
   {1, 5, 3}
};

int min(int a, int b, int c) {
   return (a<b)?((a<c)?a:c):((b<c)?b:c);
}

int minCostPath(int destX, int destY) {
   int totalCost[ROW][COL];

   totalCost[0][0] = cost[0][0];

   for (int i = 1; i <= destX; i++)
      totalCost[i][0] = totalCost[i-1][0] + cost[i][0];    //set first col of totalCost array

   for (int j = 1; j <= destY; j++)            //set first row of totalCost array
      totalCost[0][j] = totalCost[0][j-1] + cost[0][j];

   for (int i = 1; i <= destX; i++)            //for second row and column to all
      for (int j = 1; j <= destY; j++)
         totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i- 1][j], totalCost[i][j-1]) + cost[i][j];
   return totalCost[destX][destY];
}

int main() {
   cout << "Minimum Cost: "<< minCostPath(2, 2);    //destination (2, 2)
   return 0;
}

ผลลัพธ์

Minimum Cost: 8