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 리포지토리로 가십시오.