navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4b35ko:ukol4 [2010/03/14 21:24] r.polasek created |
courses:a4b35ko:ukol4 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| ====== Úkol 4 ====== | ====== Úkol 4 ====== | ||
| + | Nastin reseni: -uzijte si jarniho slunicka- | ||
| + | dykstar.m: | ||
| + | <code> | ||
| + | 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 | ||
| + | </code> | ||
| + | |||
| + | createApproxMatrix.m: | ||
| + | <code> | ||
| + | %% 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 | ||
| + | </code> | ||
| + | |||
| + | approxFce.m: | ||
| + | <code> | ||
| + | %% 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') | ||
| + | </code> | ||
| + | |||
| + | 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) | ||
| + | |||
| + | <code> | ||
| + | %% 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') | ||
| + | </code> | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
