Witam.

Mam problem, zapewne latwy, niemniej jednak ostatnio z teoria
informatyki u mnie kiepsko, przyznaje :)

Jest skonczona, niewielka ilosc, animacji, z ktorych kazda pokazuje
przejscie pomiedzy dwoma stanami (punktami).

Animacje mozna puszczac w dowolnym kierunku.

Z listy animacji wyciagam wszystkie stany ukazywane przez te animacje.
Na przyklad, przy skladni Anim[poczatek, koniec]:

Anim1[a, b]
Anim2[d, a]
Anim3[c, b]
Anim4[b, e]

Z powyzszej listy animacji wyciagam liste unikatowych stanow: {a, b, d, c}.

I na koniec musze tylko wyznaczyc najmniejszy zbior animacji pomiedzy
dwoma stanami, na czym sie wykladam :)
Chodzi o to, zeby wyznaczyc najkrotsza sciezke skladajaca sie z jednej
lub kilku animacji, gdzie wyznacznikiem odleglosci nie jest dlugosc
animacji, tylko ich ilosc. Przykladowo, jesli znajduje sie w stanie
(punkcie) [a] i chce dojsc do punktu [c], powiniy sie odpalic:

<jestem w [a]>
Anim1();
<jestem w [b]>
Anim3(od_tylu);
<jestem w [c]>
<koniec>

Ale jesli oczywiscie istnialaby animacja

Anim5[a, c]

to ma ona zostac wybrana jako najkrotsza droga, bez wzgledu na jej czas
trwania, bo po jej wybraniu bedzie trzeba uruchomic MNIEJ ANIMACJI.

Zalozenia:
- skonczona ilosc animacji
- skonczona ilosc stanow (punktow)
- obie te ilosc nie przekraczaja 20

Kojarzy mi sie to ze znajdywaniem najblizszego znajomego w grono.net,
czy co to tam bylo. Niestety Google podpowiadaja mi niewiele w chwili
obecnej.

Czy ktos mnie moze naprowadzic?

Podpowiem, ze chodzi o oprogramowanie pliku PDF 3D w JavaScript :)


Pozdrawiam.
--
[= WRonX =] [= W...@-...NET =] [= http://WRonX.NET =]
[ "...yet the blood of the wicked shall flow like a river." ]
[ GCC d- s+:- a-- C++ US P+ L+ !E W+++ N+++ w++ !O M-- !V ]
[ PS Y- t-- X+++ R+++ tv- !PGP b++ DI++ D+ G+ e h! r++ y? ]

do góry

Dnia 10.03.2009 WRonX <w...@-...net> napisał/a:

> I na koniec musze tylko wyznaczyc najmniejszy zbior animacji pomiedzy
> dwoma stanami, na czym sie wykladam :)

[...]

> Czy ktos mnie moze naprowadzic?

http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

--
Daniel 'Nathell' Janus, m...@n...korpus.pl, http://korpus.pl/~nathell
Nothing smells more like a slaughterhouse than a graduate seminar.
-- Leonard Cohen, "The Favourite Game"

do góry

Daniel Janus pisze:

> http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

No wlasnie probowalem toto ominac, bo chyba powinien istniec prostszy
sposob, jesli zakladam identyczna odleglosc pomiedzy polaczonymi
wierzcholkami grafu?


Pozdrawiam.
--
[= WRonX =] [= W...@-...NET =] [= http://WRonX.NET =]
[ "...yet the blood of the wicked shall flow like a river." ]
[ GCC d- s+:- a-- C++ US P+ L+ !E W+++ N+++ w++ !O M-- !V ]
[ PS Y- t-- X+++ R+++ tv- !PGP b++ DI++ D+ G+ e h! r++ y? ]

do góry

WRonX pisze:

> No wlasnie probowalem toto ominac, bo chyba powinien istniec prostszy
> sposob, jesli zakladam identyczna odleglosc pomiedzy polaczonymi
> wierzcholkami grafu?

Jeszcze cos. Wiki pisze: Jeśli graf nie jest ważony (wszystkie wagi mają
wielkość 1), zamiast algorytmu Dijkstry wystarczy algorytm
przeszukiwania grafu wszerz.

Pytanie, czy to zadziala, jesli nie mam hierarchii na zasadzie drzewa?
Tzn. jesli moj graf wygladalby tak, jak na rysunku z wiki:
http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz
ale przykladowo pole 6 laczylo sie poziomo z 7 a np. 5 z 11?



Pozdrawiam.
--
[= WRonX =] [= W...@-...NET =] [= http://WRonX.NET =]
[ "...yet the blood of the wicked shall flow like a river." ]
[ GCC d- s+:- a-- C++ US P+ L+ !E W+++ N+++ w++ !O M-- !V ]
[ PS Y- t-- X+++ R+++ tv- !PGP b++ DI++ D+ G+ e h! r++ y? ]

do góry

Daniel Janus pisze:

> http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

Dijkstry chcialem uniknac ze wzgledu na zalozenia mojego problemu i
chyba mi sie udalo, bo z artykulu o Dijkstrze przeszedlem do
http://pl.wikipedia.org/wiki/Przeszukiwanie_wszerz a stad, jako ze nie
bede mial drzewa, tylko graf, do
http://pl.wikipedia.org/wiki/Przeszukiwanie_w_g%C5%8
2%C4%85b :) To chyba to.

Niemniej jakby ktos mial inne pomysly, chetnie poslucham.



Pozdrawiam.
--
[= WRonX =] [= W...@-...NET =] [= http://WRonX.NET =]
[ "...yet the blood of the wicked shall flow like a river." ]
[ GCC d- s+:- a-- C++ US P+ L+ !E W+++ N+++ w++ !O M-- !V ]
[ PS Y- t-- X+++ R+++ tv- !PGP b++ DI++ D+ G+ e h! r++ y? ]

do góry