A list,

Dynamic programming is suitable for solving optimal problems, finding maximum and minimum values, and can significantly reduce time complexity.

Dynamic programming algorithm thought: a model: multi-stage decision optimal solution model.

Three characteristics:

Optimal substructure: the optimal solution of the text graph contains the optimal solution of the subproblem; No aftereffect: when deducing the state of the later stage, it only cares about the state value of the previous stage, and does not care about the origin of the state. The state of a certain stage will not be affected by the state of the later stage. Repetition subproblem: different decision sequences, reaching the same stage may produce a repeat state. Summary of solution to dynamic programming problem: State transfer table method: solve the problem into a state table, fill each state of the state table in stages. Solution idea: backtracking algorithm implementation – define state – draw recursion tree – find repeating subproblem – draw state transfer table – fill the table according to the recursion relation – translate the table filling process into code. State transfer equation method: how a problem is solved recursively by subproblems, also known as optimal substructure. According to the optimal substructure, write the recursive formula, also known as the state transition equation, the code can be implemented by recursion plus “memo” or iterative recursion. The general idea can be summarized as: find the optimal substructure – write the state transition equation – translate the state transition equation into code. 0-1 knapsack problem: backtracking algorithm idea: exhaustive search for all possible decoration, and then find the maximum conditions meet. Use a “memo” method to record calculated values when there are duplicates to avoid redundant calculations.

2. Dynamic programming solution: the problem is decomposed into multiple stages, and each stage corresponds to a decision. We record the set of reachable states at each stage (excluding duplicates), and then use the set of states at the current stage to derive the set of states at the next stage, dynamically moving forward.

Greedy algorithm: is a special case of dynamic programming algorithms. It solves problems more efficiently and code implementation is simpler. But the problems it can solve are also more limited. The problems it can solve need to meet three conditions, optimal substructure, no aftereffect and greedy selection;

Divide-and-conquer algorithm: although most of the problems solved are also optimal solutions, most of them cannot be abstracted into multi-stage decision models.

Backtracking algorithm: equivalent to exhaustive search. Take all the cases and compare them to get the best solution. However, the time complexity of backtracking algorithm is very high and is exponential, which can only be used to solve the problem of small data. For large-scale data problems, the implementation efficiency of backtracking algorithm is very low.

Dynamic programming: more efficient than backtracking algorithm, it needs to meet three characteristics, optimal substructure, no aftereffect and repetitive subproblem. Divide-and-conquer algorithm cannot have repeating subproblems. Dynamic programming is efficient because there are a lot of repeating subproblems in backtracking algorithm implementation.

Ii. Source code

Unction varargout = FindSP(varargin) % find the shortest path, GUI display gui_Singleton =1;
gui_State = struct('gui_Name',       mfilename, ...
                   'gui_Singleton',  gui_Singleton, ...
                   'gui_OpeningFcn', @FindSP_OpeningFcn, ...
                   'gui_OutputFcn',  @FindSP_OutputFcn, ...
                   'gui_LayoutFcn', [],...'gui_Callback'[]);if nargin && ischar(varargin{1})
    gui_State.gui_Callback = str2func(varargin{1});
end

if nargout
    [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
    gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT


% --- Executes just before FindSP is made visible.
function FindSP_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
% varargin   command line arguments to FindSP (see VARARGIN)

% Choose default command line output for FindSP
handles.output = hObject;

% Update handles structure
guidata(hObject, handles);

% UIWAIT makes FindSP wait for user response (see UIRESUME)
% uiwait(handles.figure1);


% --- Outputs from this function are returned to the command line.
function varargout = FindSP_OutputFcn(hObject, eventdata, handles) 
% varargout  cell array for returning output args (see VARARGOUT);
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure
varargout{1} = handles.output;







% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)% Calculates the shortest path and displays it on the interfaceif(handles.dimension==2)% 2 d [handles. SP, handles data]=findSP_2D(handles.A); % find the shortest path, handles.SP is the minimum sum, handles. Data is the shortest pathset(handles.text1,'string',num2str(handles.SP)); % displays minimum in text1 and % displays shortest path to Excel data = mat2cell(handles.A,ones()1,size(handles.A,1)),ones(1,size(handles.A,2)));
    n=size(handles.data,1);
    for i=1:n
        j=handles.data(i,1);
        k=handles.data(i,2);
        data{j,k}=['<html><table><tr><td width=100 bgcolor="yellow">'.'<FONT face="Times New Roman"size="4"color=black">',num2str(data{j,k},'%5d'), '</table></html>'];
    end
    set(handles.uitable1,'data',data); % display shortest path get(handles. Uitable1,'ColumnWidth')

    guidata(hObject, handles);
end
if(handles.dimension==3)% 3 d [handles. SP, handles data]=findSP_3D(handles.A); [m,n,p]=size(handles.A);set(handles.text1,'string',num2str(handles.SP)); % displays min in text1 and % dynamically displays path axes(handles.axes1); h = plot3(1.1.1);
    axis([1,m,1,n,1,p]);
    grid on
    for k = 1:numel(handles.data(:,1))
         set(h,'XData',handles.data(1:k,1),'YData',handles.data(1:k,2),'ZData',handles.data(1:k,3));
         drawnow;
         axis([1,m,1,n,1,p]);
         pause(0.3);
    end
    guidata(hObject, handles);
end

    


% --------------------------------------------------------------------
function Untitled_1_Callback(hObject, eventdata, handles)
% hObject    handle to Untitled_1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)


% --------------------------------------------------------------------
function Untitled_2_Callback(hObject, eventdata, handles)% Open file dialog box to read 2d matrix (TXT format) filename=uigetfile('.txt');
fid=fopen(filename);
handles.A=readData(fid);
handles.dimension=2; % marks the dimension,2Represents two-dimensional FCLOSE (FID);set(handles.uitable1,'visible'.'on'.'data',handles.A); Axes (handles. Axes1); cla reset; % Clears path information in the coordinate axesset(handles.axes1,'visible'.'off'); Hides the axes that display the 3d pathset(handles.text1,'string'.' '); % Empty the minimum and Guidata (hObject, handles) shown in text1 (textbox); % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --function Untitled_5_Callback(hObject, eventdata, handles)
% hObject    handle to Untitled_5 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)


% --------------------------------------------------------------------
function Untitled_3_Callback(hObject, eventdata, handles)% Create random matrix % Pop up input dialog box for determining the size of random matrix, matrix elements value range and other information prompt= {'lines'.'the number of columns.'Range of matrix element values'};
title='Random Matrix Parameter Settings';
lines=[1 1 1];
def={'6'.'6'.10 '0'}; 
answer=inputdlg(prompt,title,lines,def);
m=str2double(answer{1});
n=str2double(answer{2});
range=str2num(answer{3});
min=range(1); max=range(2); handles.A=round((rand(m,n))*(max-min)+min); % original matrix handles. Dimension =2; % 2 dset(handles.uitable1,'visible'.'on'.'data',handles.A); Axes (handles. Axes1); cla reset; % Clears path information in the coordinate axesset(handles.axes1,'visible'.'off'); Hides the axes that display the 3d pathset(handles.text1,'string'.' '); % Empty the minimum and Guidata (hObject, handles) shown in text1 (textbox); % -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --function Untitled_4_Callback(hObject, eventdata, handles)% Save path results(2d) FID =fopen('result_2D.txt'.'w');
fprintf(fid,'Minimum sum: %d\r\n Shortest path: (row number, column number)\r\n',handles.SP);
[m,n]=size(handles.data);
for i=1:m
    fprintf(fid,'(%d, %d) \r\n',handles.data(i,1),handles.data(i,2));
end
Copy the code

3. Operation results



Fourth, note

Version: 2014a complete code or write plus 1564658423