On Wed, 22 Feb 2012 13:20:15 +0100, bartekltg <b...@g...com>
wrote:

>W dniu 2012-02-21 22:52, A.L. pisze:
>> Od niejakiego czasu zaprzata mnie nastepujacy problem:
>>
>> Dany jest skierowany graf acykliczny. Jak wiadomo, taki graf mozna
>> posortowac topologicznie. Takich porzadkow topologicznych jest
>> olbrzymia ilosc.
>>
>> I teraz problem:
>>
>> 1. W praktycznych zadaniach ten graf moze byc bardzo duzy - setki
>> tysiecy wezlow
>> 2. Graf nie musi byc spojny
>> 3. Dane jest uporzadkowanie topologiczne, jedno z mozliwych
>> 4. Chce sie zmienic polozenie N wezlow w tym porzadku, gdzie N jest
>> nieduze (kilka). Wezly sa wybrane przypadkowo
>>
>> Pytanie:
>>
>> 1. Czy ta zmiana polozenia N wezlow narusza uporzadkowanie
>> topologiczne, to znaczy czy po przestawieniu otrzymamy znow porzadek
>> topologiczny czy nie
>> 2. Takie sprawdzenie musi byc EXTREMALNIE wydajne, bo powtarzane jest
>> miliony razy, a program musi sie wykonywac bardzo szybko.
>>
>> Oczywiscie, "brute force" jest trywialne. Ale "nie brute force"
>
>Rozumiem, że brute force to przejście od naszych N przesuwanych
>wierzchołków krawędziami w przód i w tył (ok, trzeba mieć
>krawedzie wstaczne) i sprawdzenie, czy nie odwróciliśmy
>kierunku w porządku.
>
>
>> niekoniecznie jest trywialne. Tyle ze "brute force" strasznie dlugo
>> sie wykonuje, nawet przy maksymalnej optymalizacji kodu
>>
>> Rzecz potrzebna w pewnych algorytmach "constraint programming"
>> zwiazanymi z planowaniem kalendarzowym i routingiem. Dopuszczalny jest
>> "preprocessing" grafu w celu utworzenia struktur danych
>> przyspieszajacych proces. Pamiec nie jest ograniczeniem.
>>
>> Jak ktos nie ma nad czym myslec, to proponuje nad tym
>
>
>Ciężko będzie szybciej:) Mam coś, co samo sprawdzenie robi
>w O(N) + sprawdzenie czy w nasze N wierzchołkow jest ok,
>ale potem i tak trzeba 'poprawić dane' we wszystkich
>wierzchołkach z którymi styka się zbiór N. Więc
>jeśli nie wpadne, jak ro zrobić 'leniwie' wychodzi
>to samo co BF powyżej. (Trzymam listę krawędzi
>posortowaną po pozycjach w porządku. Sprawdzenie
>czy przesuniecie wierzchołka zachowuje porzadek
>jest natychmiastowe, ale trzeba jeszcze rozpropagować
>informacje o zmianie swojej pozycji).
>

BF to takie ze dla kazdego wezla oblicze sei "follower set" czyli
zbior wezlow ktore musa byc pozniej niz dany wezel, i "predecessor
set" ktory zawiera zbior wierzcholkow ktore musza byc wczesniej. Gdy
sie chce pzrestawic wezly, tzreba zprawdzic czy ktoryz z wezlow by nie
"wypadl" z follower set czy predecessor set. Co wymaga sprawdzenia
wszystkich wezlow.

Pytanei wiec, czy nei da sie testowac tylko niektorych wezlow, a
jezeli tak, to ktore?

A.L.