W dniu 2012-02-22 19:03, Piotr Chamera pisze:
> 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"
>> 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
>>
>> A.L.
>
> 1. Każdy węzeł grafu reprezentujemy tak, że znane są listy jego
> poprzedników i następników w grafie.
>
> 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).
>
> 3. Typujemy N wierzchołków do zmiany miejsca.
>
> 4. Dla każdego z N wierzchołków wyliczamy nowe znakowanie jako liczbę
> pośrednią między poprzednikiem i następnikiem w docelowym porządku (np
> średnia arytmetyczna ze znakowań poprzednika i następnika w porządku
> docelowym).
>
> 5. Dla każdego z N wierzchołków bierzemy listę jego poprzedników w grafie.
>
> 5a Dla każdego poprzednika z powyższej listy sprawdzamy, czy na liście
> jego następników nie ma wierzchołka ze znakowaniem mniejszym niż jego
> własne.

Mam problem z 5 punktem, to czy powinniśmy sprawdzić poprzedniki czy
następniki zależy od kierunku przesunięcia węzła w grafie.
Jeśli dany węzeł wędruje ,,do tyłu" względem wyjściowego porządku trzeba
sprawdzić następniki jego poprzedników. Jeśli ,,do przodu", to należy
porównać poprzedniki jego następników.

Ale być może bredzę - dziś już zmęczony jestem... może jest jeszcze
więcej możliwych przypadków...

> Jeśli to zadziała, to w najgorszym wypadku mamy do sprawdzenia N x m x o
> porównań, gdzie m to max liczba poprzedników, a o max liczba następników
> węzła w zbiorze węzłów N.
>
> Rysowałem sobie to na kartce, mogłem jakiś przypadek pominąć lub źle
> zrozumieć zadanie...