Dynamic Programming for MATLAB
版本 1.0 (29.8 KB) 作者:
mansour torabi
Dynamic Programming has been implemented in MATLAB using two illustrative example
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
引用格式
mansour torabi (2024). Dynamic Programming for MATLAB (https://github.com/Mansourt/Matlab_Dynamic_Programming/releases/tag/v1.0), GitHub. 检索来源 .
MATLAB 版本兼容性
创建方式
R2020b
兼容任何版本
平台兼容性
Windows macOS Linux标签
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Fibonacci
Grid Path
版本 | 已发布 | 发行说明 | |
---|---|---|---|
1.0 |
要查看或报告此来自 GitHub 的附加功能中的问题,请访问其 GitHub 仓库。
要查看或报告此来自 GitHub 的附加功能中的问题,请访问其 GitHub 仓库。