Dynamic Programming for MATLAB
Matlab Dynamic Programming
Dynamic Programming has been demostrated by two examples:
- Fibonacci sequence
- 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:
- Fibo using Recursive method
- Fibo using Dynamic programming
- Fibo using Matrix Exponentiation (Fastest method)
MATLAB function
-
Fibonacci/Fibo_R.m: Fibonacci with Recursive approach:
- Time Complexity: O(2^n)
- Space Complexity: O(2^n)
-
Fibonacci/Fibo_DP.m: Fibonacci with Dynamic programming (Memoization):
- Time Complexity: O(n)
- Space Complexity: O(n)
-
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:
- Count number of path using Recursive method
- 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
Cita come
mansour torabi (2024). Dynamic Programming for MATLAB (https://github.com/Mansourt/Matlab_Dynamic_Programming/releases/tag/v1.0), GitHub. Recuperato .
Compatibilità della release di MATLAB
Compatibilità della piattaforma
Windows macOS LinuxTag
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Scopri Live Editor
Crea script con codice, output e testo formattato in un unico documento eseguibile.
Fibonacci
Grid Path
Versione | Pubblicato | Note della release | |
---|---|---|---|
1.0 |