eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingTaki problem programistyczny...Re: Taki problem programistyczny...
  • Data: 2012-02-22 23:24:28
    Temat: Re: Taki problem programistyczny...
    Od: n...@m...invalid szukaj wiadomości tego autora
    [ pokaż wszystkie nagłówki ]

    W dniu 22.02.2012 r. 20:21, Piotr Chamera pisze:
    > 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).
    1: 1/2; 2: 2/3; 3: 3/4; ... ? Co to daje, mogę prosić o objaśnienie?

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

    --
    Pozdr

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: