Dynamic Programming for MATLAB

Dynamic Programming has been implemented in MATLAB using two illustrative example
265 descargas
Actualizado 29 Jan 2021

View Matlab Dynamic Programming on File Exchange

Matlab Dynamic Programming

Dynamic Programming has been demostrated by two examples:

  1. Fibonacci sequence
  2. Find number of path in the Grid Map with obstacles

Example 1: Fibonacci squence

Just run the Fibonacci/EVAL_fibo.m file to compare run-time of the following three methods:

  1. Fibo using Recursive method
  2. Fibo using Dynamic programming
  3. Fibo using Matrix Exponentiation (Fastest method)

MATLAB function

  1. Fibonacci/Fibo_R.m: Fibonacci with Recursive approach:

    • Time Complexity: O(2^n)
    • Space Complexity: O(2^n)
  2. Fibonacci/Fibo_DP.m: Fibonacci with Dynamic programming (Memoization):

    • Time Complexity: O(n)
    • Space Complexity: O(n)
  3. Fibonacci/Fibo_M.m: Fibonacci with Matrix Exponentiation:

    • Time Complexity: O(log(n))

Example 2: Find number of path in the Grid Map with obstacles

Just run the Grid Path/EVAL_grid_path.m file to compare run-time of the following two methods:

  1. Count number of path using Recursive method
  2. Count number of path using Dynamic Programming

Usage:

clc, clear

% Define Map (Grid Path)
Map = zeros(15,10);
Map(3,5) = 1;
Map(6,7) = 1;
Map(7,3) = 1;

% Visualize Map (Grid Path)
MapView(Map)
%%
tic;
N1 = GridPath_R(Map, 1,1)
toc;

tic;
N2 = GridPath_DP(Map, 1,1)
toc;

Grid map is as follows:

N1 = 475550
Elapsed time is 8.417751 seconds.

N2 = 475550
Elapsed time is 0.002251 seconds.

Contact

Email: smtoraabi@ymail.com

Citar como

mansour torabi (2024). Dynamic Programming for MATLAB (https://github.com/Mansourt/Matlab_Dynamic_Programming/releases/tag/v1.0), GitHub. Recuperado .

Compatibilidad con la versión de MATLAB
Se creó con R2020b
Compatible con cualquier versión
Compatibilidad con las plataformas
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Versión Publicado Notas de la versión
1.0

Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.
Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.