Минимальная стоимость пути | ДП-6

01.01.2020Динамическое программирование, Математика, Матрицы

Учитывая стоимость матрицы затрат [] [] и позицию (m, n) в стоимости [] [], напишите функцию, которая возвращает стоимость пути минимальной стоимости для достижения (m, n) из (0, 0). Каждая ячейка матрицы представляет собой стоимость прохождения через эту ячейку. Общая стоимость пути для достижения (m, n) представляет собой сумму всех затрат на этом пути (включая как источник, так и пункт назначения). Вы можете перемещаться только вниз, вправо и по диагонали к нижним ячейкам из данной ячейки, то есть из данной ячейки (i, j), ячеек (i + 1, j), (i, j + 1) и (i + 1, j + 1) можно пройти. Вы можете предположить, что все затраты являются положительными целыми числами.

Например, как показано на следующем рисунке, какова минимальная стоимость пути к (2, 2)?

Путь с минимальной стоимостью выделен на следующем рисунке. Путь (0, 0) -> (0, 1) -> (1, 2) -> (2, 2). Стоимость пути составляет 8 (1 + 2 + 2 + 3).

1) Оптимальная субструктура
Путь для достижения (m, n) должен быть через одну из 3 ячеек: (m-1, n-1) или (m-1, n) или (m, n-1). Таким образом, минимальная стоимость для достижения (m, n) может быть записана как «минимум из 3 ячеек плюс стоимость [m] [n]».

minCost (m, n) = min (minCost (m-1, n-1), minCost (m-1, n), minCost (m, n-1)) + стоимость [м] [n]

2) Перекрывающиеся подзадачи
Ниже приводится простая рекурсивная реализация проблемы MCP (Minimum Cost Path). Реализация просто следует рекурсивной структуре, упомянутой выше.

/ * Наивная рекурсивная реализация проблемы MCP (Minimum Cost Path) * /
#include<stdio.h>
#include<limits.h>
#define R 3
#define C 3

int min(int x, int y, int z);

/ * Возвращает стоимость пути минимальной стоимости от (0,0) до (m, n) в мате [R] [C] * /

int minCost(int cost[R][C], int m, int n)

{

if (n < 0 || m < 0)

return INT_MAX;

else if (m == 0 && n == 0)

return cost[m][n];

else

return cost[m][n] + min( minCost(cost, m-1, n-1),

minCost(cost, m-1, n),

minCost(cost, m, n-1) );

}

/ * Вспомогательная функция, которая возвращает минимум 3 целых числа * /

int min(int x, int y, int z)

{

if (x < y)

return (x < z)? x : z;

else

return (y < z)? y : z;

}

/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

int cost[R][C] = { {1, 2, 3},

{4, 8, 2},

{1, 5, 3} };

printf(" %d ", minCost(cost, 2, 2));

return 0;

}

Джава

/ * Наивная рекурсивная реализация
Проблема MCP (путь минимальной стоимости) * /

public class GFG {

/ * Вспомогательная функция, которая возвращает

минимум 3 целых числа * /

static int min(int x, int y, int z)

{

if (x < y)

return (x < z) ? x : z;

else

return (y < z) ? y : z;

}

/ * Возвращает стоимость пути минимальной стоимости

от (0,0) до (m, n) в мате [R] [C] * /

static int minCost(int cost[][], int m,

int n)

{

if (n < 0 || m < 0)

return Integer.MAX_VALUE;

else if (m == 0 && n == 0)

return cost[m][n];

else

return cost[m][n] +

min( minCost(cost, m-1, n-1),

minCost(cost, m-1, n),

minCost(cost, m, n-1) );

}

// Код драйвера

public static void main(String args[])

{

int cost[][] = { {1, 2, 3},

{4, 8, 2},

{1, 5, 3} };

System.out.print(minCost(cost, 2, 2));

}

// Этот код предоставлен Sam007

python3

# Наивная рекурсивная реализация проблемы MCP (Minimum Cost Path)

R = 3

C = 3

import sys

# Возвращает стоимость пути минимальной стоимости от (0,0) до (m, n) в мате [R] [C]

def minCost(cost, m, n):

if (n < 0 or m < 0):

return sys.maxsize

elif (m == 0 and n == 0):

return cost[m][n]

else:

return cost[m][n] + min( minCost(cost, m-1, n-1),

minCost(cost, m-1, n),

minCost(cost, m, n-1) )

# Сервисная функция, которая возвращает минимум 3 целых числа * /

def min(x, y, z):

if (x < y):

return x if (x < z) else z

else:

return y if (y < z) else z

# Драйверная программа для проверки вышеуказанных функций

cost= [ [1, 2, 3],

[4, 8, 2],

[1, 5, 3] ]

print(minCost(cost, 2, 2))

# Этот код предоставлен
# Смита Динеш Семвал

C #

/ * Наивная рекурсивная реализация
Проблема MCP (путь минимальной стоимости) * /

using System;

class GFG

{

/ * Полезная функция, которая

возвращает минимум 3 целых числа * /

static int min(int x,

int y, int z)

{

if (x < y)

return ((x < z) ? x : z);

else

return ((y < z) ? y : z);

}

/ * Возвращает стоимость минимума

Стоимость пути от (0,0) до

(m, n) в мате [R] [C] * /

static int minCost(int [,]cost,

int m , int n)

{

if (n < 0 || m < 0)

return int.MaxValue;

else if (m == 0 && n == 0)

return cost[m, n];

else

return cost[m, n] +

min(minCost(cost, m - 1, n - 1),

minCost(cost, m - 1, n),

minCost(cost, m, n - 1) );

}

// Код драйвера

public static void Main()

{

int [,]cost = {{1, 2, 3},

{4, 8, 2},

{1, 5, 3}};

Console.Write(minCost(cost, 2, 2));

}

// Этот код добавлен
// от shiv_bhakt.

PHP

<?php
/ * Наивная рекурсивная реализация
проблемы MCP (путь минимальной стоимости) * /

$R = 3;

$C = 3;

/ * Возвращает стоимость минимума
Стоимость пути от (0,0) до
(m, n) в мате [R] [C] * /

function minCost($cost, $m, $n)

{

global $R;

global $C;

if ($n < 0 || $m < 0)

return PHP_INT_MAX;

else if ($m == 0 && $n == 0)

return $cost[$m][$n];

else

return $cost[$m][$n] +

min1(minCost($cost, $m - 1, $n - 1),

minCost($cost, $m - 1, $n),

minCost($cost, $m, $n - 1) );

}

/ * Полезная функция, которая
возвращает минимум 3 целых числа * /

function min1($x, $y, $z)

{

if ($x < $y)

return ($x < $z)? $x : $z;

else

return ($y < $z)? $y : $z;

}

// Код драйвера

$cost = array(array(1, 2, 3),

array (4, 8, 2),

array (1, 5, 3));

echo minCost($cost, 2, 2);

// Этот код предоставлен mits.
?>

Выход:

Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. Смотрите следующее дерево рекурсии, есть много узлов, которые появляются более одного раза. Временная сложность этого наивного рекурсивного решения является экспоненциальной и очень медленной.

mC refers to minCost()
                                    mC(2, 2)
                          /            |           \
                         /             |            \             
                 mC(1, 1)           mC(1, 2)             mC(2, 1)
              /     |     \       /     |     \           /     |     \ 
             /      |      \     /      |      \         /      |       \
       mC(0,0) mC(0,1) mC(1,0) mC(0,1) mC(0,2) mC(1,1) mC(1,0) mC(1,1) mC(2,0)

Таким образом, проблема MCP имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив временный массив tc [] [] в порядке снизу вверх.

C ++

/ * Динамическое программирование реализации проблемы MCP * /
#include<stdio.h>
#include<limits.h>
#define R 3
#define C 3

int min(int x, int y, int z);

int minCost(int cost[R][C], int m, int n)

{

int i, j;

// Вместо следующей строки мы можем использовать int tc [m + 1] [n + 1] или

// динамически распределяем память для экономии места. Следующая строка

// используется для упрощения программы и обеспечения ее работы на всех компиляторах.

int tc[R][C];

tc[0][0] = cost[0][0];

/ * Инициализировать первый столбец массива общей стоимости (тс) * /

for (i = 1; i <= m; i++)

tc[i][0] = tc[i-1][0] + cost[i][0];

/ * Инициализировать первую строку массива tc * /

for (j = 1; j <= n; j++)

tc[0][j] = tc[0][j-1] + cost[0][j];

/ * Создаем остаток массива tc * /

for (i = 1; i <= m; i++)

for (j = 1; j <= n; j++)

tc[i][j] = min(tc[i-1][j-1],

tc[i-1][j],

tc[i][j-1]) + cost[i][j];

return tc[m][n];

}

/ * Вспомогательная функция, которая возвращает минимум 3 целых числа * /

int min(int x, int y, int z)

{

if (x < y)

return (x < z)? x : z;

else

return (y < z)? y : z;

}

/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

int cost[R][C] = { {1, 2, 3},

{4, 8, 2},

{1, 5, 3} };

printf(" %d ", minCost(cost, 2, 2));

return 0;

}

Джава

/ * Java-программа для реализации динамического программирования

задачи Min Cost Path * /

import java.util.*;

class MinimumCostPath

{

/ * Вспомогательная функция, которая возвращает минимум 3 целых числа * /

private static int min(int x, int y, int z)

{

if (x < y)

return (x < z)? x : z;

else

return (y < z)? y : z;

}

private static int minCost(int cost[][], int m, int n)

{

int i, j;

int tc[][]=new int[m+1][n+1];

tc[0][0] = cost[0][0];

/ * Инициализировать первый столбец массива общей стоимости (тс) * /

for (i = 1; i <= m; i++)

tc[i][0] = tc[i-1][0] + cost[i][0];

/ * Инициализировать первую строку массива tc * /

for (j = 1; j <= n; j++)

tc[0][j] = tc[0][j-1] + cost[0][j];

/ * Создаем остаток массива tc * /

for (i = 1; i <= m; i++)

for (j = 1; j <= n; j++)

tc[i][j] = min(tc[i-1][j-1],

tc[i-1][j],

tc[i][j-1]) + cost[i][j];

return tc[m][n];

}

/ * Программа драйвера для проверки вышеуказанных функций * /

public static void main(String args[])

{

int cost[][]= {{1, 2, 3},

{4, 8, 2},

{1, 5, 3}};

System.out.println(minCost(cost,2,2));

}

}
// Этот код предоставлен Панкаджем Кумаром

питон

# Динамическое программирование Python-реализация Min Cost Path
# проблема

R = 3

C = 3

def minCost(cost, m, n):

# Вместо следующей строки мы можем использовать int tc [m + 1] [n + 1] или

# динамически размещать памятки для экономии места. Следующее

# строка используется для упрощения работы программы и обеспечения ее работоспособности

# на всех компиляторах.

tc = [[0 for x in range(C)] for x in range(R)]

tc[0][0] = cost[0][0]

# Инициализировать первый столбец массива общей стоимости (тс)

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, 2, 3],

[4, 8, 2],

[1, 5, 3]]

print(minCost(cost, 2, 2))

# Этот код предоставлен Bhavya Jain

C #

// C # программа для реализации динамического программирования
// проблемы Min Cost Path

using System;

class GFG

{

// Полезная функция, которая

// возвращает минимум 3 целых числа

private static int min(int x, int y, int z)

{

if (x < y)

return (x < z)? x : z;

else

return (y < z)? y : z;

}

private static int minCost(int [,]cost, int m, int n)

{

int i, j;

int [,]tc=new int[m+1,n+1];

tc[0,0] = cost[0,0];

/ * Инициализировать первый столбец массива общей стоимости (тс) * /

for (i = 1; i <= m; i++)

tc[i, 0] = tc[i - 1, 0] + cost[i, 0];

/ * Инициализировать первую строку массива tc * /

for (j = 1; j <= n; j++)

tc[0, j] = tc[0, j - 1] + cost[0, j];

/ * Создаем остаток массива tc * /

for (i = 1; i <= m; i++)

for (j = 1; j <= n; j++)

tc[i, j] = min(tc[i - 1, j - 1],

tc[i - 1, j],

tc[i, j - 1]) + cost[i, j];

return tc[m, n];

}

// Драйвер программы

public static void Main()

{

int [,]cost= {{1, 2, 3},

{4, 8, 2},

{1, 5, 3}};

Console.Write(minCost(cost,2,2));

}

// Этот код предоставлен Sam007.

PHP

<?php
// реализация DP
// проблемы MCP

$R = 3;

$C = 3;

function minCost($cost, $m, $n)

{

global $R;

global $C;

// Вместо следующей строки

// мы можем использовать int tc [m + 1] [n + 1]

// или динамически распределяем

// память для экономии места.

// следующая строка используется для сохранения

// программа простая и удобная

// это работает на всех компиляторах.

$tc;

for ($i = 0; $i <= $R; $i++)

for ($j = 0; $j <= $C; $j++)

$tc[$i][$j] = 0;

$tc[0][0] = $cost[0][0];

/ * Инициализировать первый столбец

массив общей стоимости (тс) * /

for ($i = 1; $i <= $m; $i++)

$tc[$i][0] = $tc[$i - 1][0] +

$cost[$i][0];

/ * Сначала инициализировать

строка массива tc * /

for ($j = 1; $j <= $n; $j++)

$tc[0][$j] = $tc[0][$j - 1] +

$cost[0][$j];

/ * Построить остаток

массив tc * /

for ($i = 1; $i <= $m; $i++)

for ($j = 1; $j <= $n; $j++)

// возвращает минимум 3 целых числа

$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 = array(array(1, 2, 3),

array(4, 8, 2),

array(1, 5, 3));

echo minCost($cost, 2, 2);

// Этот код предоставлен mits
?>

Выход:

Сложность времени реализации DP — O (mn), что намного лучше, чем реализация Naive Recursive.

Спросил в: Amazon

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальная стоимость пути | ДП-6

0.00 (0%) 0 votes