W dniu 2012-02-23 20:23, A.L. pisze:
> On Thu, 23 Feb 2012 11:47:26 +0100, Piotr Chamera
> <p...@p...onet.pl> wrote:
>
>> W dniu 2012-02-23 00:24, n...@m...invalid pisze:
>>>>> 2. Znakujemy węzły rosnąco liczbami wymiernymi wg kolejności w
>>>>> wyjściowym porządku (to można zrobić raz dla wielu kolejnych
>>>>> przekształceń, może być potrzeba dokładnej arytmetyki).
>>> 1: 1/2; 2: 2/3; 3: 3/4; ... ? Co to daje, mogę prosić o objaśnienie?
>>
>> Jeszcze wyjaśnienie dlaczego pisałem o liczbach wymiernych - pomiędzy
>> dwie dowolne liczby wymierne można zawsze wstawić trzecią, co w tym
>> przypadku pozwala nie dotykać znakowania wierzchołków, których nie
>> przesuwamy.
>
> To jest mniej wiecej tak jak ja robie i nazywam "brute force"

Może coś mylę, ale:

zakładam, że graf się nie zmienia, zmieniamy tylko porządek,
więc zbiory poprzedników i następników danego węzła w grafie
są również stałe - można je wyliczyć i zapisać w jakiejś strukturze
dowiązanej do każdego węzła.

> Jak wezly A B C D przeorganizujemy

załóżmy znakowanie w jakimś początkowym porządku topologicznym
od lewej do prawej

(A 1) (B 2) (C 3) (D 4)

jeśli mamy porządek topologiczny, to wszystkie krawędzie wchodzące do
danego węzła X muszą wychodzić z węzłów o znakowaniach mniejszych niż
znakowanie przypisane do X a wychodzące muszą prowadzić do węzłów o
znakowaniach większych niż to przypisane do X.

> na B A D C, to tzreba sprawdzic ze

zmieniamy kolejność i znakowanie tak:
D przesunęliśmy między B i C więc dostał znakowanie mniejsze od C i
większe od B, B przestawiliśmy przed A, który był pierwszy w początkowym
porządku, więc B więc dostał dowolne znakowanie mniejsze od A.

(B 1/2) (A 1) (D 5/4) (C 3)

wystarczy sprawdzić, czy wszystkie krawędzie grafu wchodzące do (B 1/2)
są z nadal z węzłów o znakowaniu mniejszym od obecnego znakowania
węzła B i wszystkie wychodzące z B nadal prowadzą do węzłów o znakowaniu
większym od znakowania węzła B. I analogicznie dla węzła D.

Dla każdego przesuwanego węzła mamy k_we + k_wy sprawdzeń (porównań
liczb, k_we - liczba krawędzi wchodzących do węzła, k_wy - liczba
krawędzi wychodzących z węzła).

> A D C sa w zbiorze nastepnikow B, a BAD jes tw zbiorze poprednikow C i
> tak dalej.
Powyżej piszę o następnikach i poprzednikach w grafie, a nie w porządku.
Węzły zawsze są oznakowane rosnąco, zgodnie z porządkiem wyjściowym, a
po zmianie - testowanym. Jeżeli po zmianie zaburzyliśmy porządek,
to dla któregoś z przesuniętych węzłów X w zbiorze jego poprzedników w
grafie znajdzie się węzeł o znakowaniu większym niż jego własne lub w
zbiorze następników w grafie znajdzie się węzeł o znakowaniu mniejszym
niż jego własne.

> Wle to nie wystarcza, bo oprocz amiany uporatdkowania moze byc
> przesuniecie, na przykald A moze byc przesuniety z pozycji 100 na
> pozycje 50. Moze wtedy "wypasc" ze zbioru nastepnilkow wezlow miedzy
> 50 a 99, wiec te wezly tzreba sprawdzic.
Tak, ale nie interesują nas te, z których nie było bezpośredniej
krawędzi do A, więc jeśli znamy węzły, z których mamy w grafie
bezpośrednie przejście do A (a ten zbiór dla każdego węzła możemy
wyliczyć i zapamiętać raz, na początku, gdyż graf się nie zmienia),
to możemy je łatwo sprawdzić.

Jeśli A przeskoczyło jakiś węzeł X, który w grafie był jego
poprzednikiem, to będzie miało teraz mniejsze od niego znakowanie -
jeśli sprawdzimy listę poprzedników A w grafie, to znajdziemy tam teraz
węzeł X o znakowaniu większym niż A, a pamiętamy, że wszystkie
poprzedniki powinny mieć znakowanie mniejsze niż A - da nam to
informację, że krawędź prowadząca z X do A zmieniła kierunek
i zaburzyliśmy porządek.

Podobnie jahk D soztanie
> pzresyniety z pozycji 100 na pozycje 200, to moze wypasc ze zbioru
> poprzednikow, wiec trzeba sprawdzic wezly od 100 do 200.
>
> Troche dzuo tych sprawdzen, i pytanie - czy nie mozna mniej?...
>
> A.L.

Może w tym co piszę wyżej jest jakaś luka lub błąd, albo źle
zrozumiałem zadanie, jeśli tak, to proszę o jakiś prosty kontrprzykład
do analizy.


--
pozdrawiam
Piotr Chamera