Úkol 4

Nastin reseni: -uzijte si jarniho slunicka-

dykstar.m:

Nezlobte se, ale on to fakt neopsal :)

%% funkce dyckstar
% implementace Dijkstrova algoritmu
% INput:    r... starting point
%           W(i,j)... weight matrix (distances between cities i->j)
% OUTput:   dist(i)..distances from start point to other vertices (city i),
% U in slides
%           track(i)..bactracking the route, to city i we got from
%           track(i), ODKUD in slides
function [track,dist] = dyckstar(r,W)
noV=size(W,2); % pocet vrcholu v grafu
V=[1:noV]; % vrcholy v grafu
dist=ones(1,noV).*inf; % init..distances are unknown
dist(r)=0; % dist r=0
track=ones(1,noV).*inf; 
track(r)=-1; % pomocna ukoncovaci podminka
done=[]; % already finished (fixed) vertices) , D in slides

nehotove=setdiff(V,done); % nehotove ..indexy V\done : nejsou inf
while sum(dist(nehotove) ~=inf) > 0
    [bla,zpracovat]=min(dist(nehotove)); % zpracovat ..index minima z dist(nehotove)
    v = nehotove(zpracovat); % hodnota toho vrcholu
    done = [done v]; % uzel 'v' ted udelame a pridame proto k hotovym 
    % pres vsechny vystupni hrany z 'v' : 
    koncoveBody= V(W(v,:)~=inf); % vrcholy, pro ktere vede hrana z 'v'
    for y = koncoveBody
       if dist(v) + W(v,y) < dist(y) % update na kratsi cestu
           dist(y) = dist(v) + W(v,y);
           track(y)=v;
       end
    end
    nehotove=setdiff(V,done);
end
end

createApproxMatrix.m:

%% createApproxMatrix - vytvari matici pouzitou pro aproximaci
%% funkce/obrazku
% W .. vysledna matice vah
% x,f .. data na ose x, a f(x)(resp. y)
% vrcholy [x(i),f(x(i))] predstavuji uzly, 
% graf obsahuje hranu pro kazdou dvojici uzlu i,j: i<j; 
% kde vaha hrany je ohodnoceni chyby aproximace.
function [W] = createApproxMatrix(x,f,alfa,beta)
    % priprava matice vzdalenosti
    vrcholu =size(x,2);
    W = inf(vrcholu);
    % pro vsechna i<j
    for j = 1:vrcholu   
        for i = 1:j-1      
            err = 0;       
            % ta suma; tzn pro vsechny body x_k (i<k<j) pocitame chybu aproximace techto
            % bodu useckou z x_i do x_j
            for k = (i+1):j           
                approx = f(i) + (x(k) - x(i))*(f(j)-f(i))/(x(j)-x(i));    % derivace       
                err = err + (f(k) - approx).^2;           
            end       
            W(i,j) = alfa + beta*err;       % nas vypocet vah - v zavislosti na chybe
        end    
    end
end

approxFce.m:

%% ukol na cv 6 z A4M33KO - hledani nejkratsi cesty, Dijkstruv alg,
%% aproximace fce a obrazku
clc;
clear;
close all;

% koeficienty pro pocet vrcholu a odchylky
alpha = 1;
beta = 1;

% vstupni data 
x = [ 0 1.26 2.51 3.77 5.03 6.28];
f = [ 0.01 1.16 0.70 -0.34 -0.80 0.2100];

W = createApproxMatrix(x,f,alpha,beta);
'matice vzdalenosti: ',W

% Dijkstruv algoritmus
[track,dist]=dyckstar(1,W)

% vyberu vrcholy po nejkratsi ceste
q = size(W,2);
cesta = q;
while track(1,q) ~= -1
    q = track(1,q);
    cesta = [cesta q];
end

cesta = sort(cesta);

% vykresleni 
plot(x,f,'g')
hold on;
plot(x(cesta),f(cesta),'r')

approxObrazku.m: PS: 1)u slidu pisi neco o jinem vypoctu vah nez u fce, ale to je imho zbytecne.

  2)orezal jsem data kvuli rychlosti (netbook:P)

%% ukol na cv 6 z A4M33KO - hledani nejkratsi cesty, Dijkstruv alg,
%% aproximace fce a obrazku
%clc;
%clear;
%close all;

% koeficienty pro pocet vrcholu a odchylky
alpha = 1;
beta = 1;

% vstupni data 
 load czechRepublic.mat
% whos

%% zrychleni pro ukazku: udelejme si mensi republiku
x=x(1:end/5);
y=y(1:end/5);
W = createApproxMatrix(x',y',alpha,beta);
'matice vzdalenosti: ',W;

% Dijkstruv algoritmus
[track,dist]=dyckstar(1,W)

% vyberu vrcholy po nejkratsi ceste
q = size(W,2);
cesta = q;
while track(1,q) ~= -1
    q = track(1,q);
    cesta = [cesta q];
end

cesta = sort(cesta);

% vykresleni 
plot(x,y,'g')
hold on;
plot(x(cesta),y(cesta),'r')