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.


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