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"

Jak wezly A B C D przeorganizujemy na B A D C, to tzreba sprawdzic ze
A D C sa w zbiorze nastepnikow B, a BAD jes tw zbiorze poprednikow C i
tak dalej.

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. 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.

do góry

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

do góry

On Fri, 24 Feb 2012 00:14:55 +0100, Piotr Chamera
<p...@p...onet.pl> wrote:

>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.

Musze pzreczytac i sie zastanowic. Co uczynie w weekend :)

A.L.

do góry

W dniu 2012-02-24 15:01, A.L. pisze:
> Musze pzreczytac i sie zastanowic. Co uczynie w weekend :)

To jeszcze mała graficzka ilustrująca problem dla ułatwienia
(kropki to węzły):
http://chamera.eu/temp/porzadek_topologiczny.gif

do góry