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



pzdr
bartekltg