eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingTaki problem programistyczny...Re: Taki problem programistyczny...
  • Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!news.icpnet.pl!
    .POSTED!not-for-mail
    From: n...@m...invalid
    Newsgroups: pl.comp.programming
    Subject: Re: Taki problem programistyczny...
    Date: Thu, 23 Feb 2012 00:24:28 +0100
    Organization: ICP News Server
    Lines: 79
    Message-ID: <ji3tf7$3mn$1@news.icpnet.pl>
    References: <m...@4...com>
    <ji3aku$569$1@inews.gazeta.pl> <ji3f8b$jkc$1@inews.gazeta.pl>
    NNTP-Posting-Host: 95.108.117.135
    Mime-Version: 1.0
    Content-Type: text/plain; charset=UTF-8
    Content-Transfer-Encoding: 8bit
    X-Trace: news.icpnet.pl 1329953064 3799 95.108.117.135 (22 Feb 2012 23:24:24 GMT)
    X-Complaints-To: a...@i...pl
    NNTP-Posting-Date: Wed, 22 Feb 2012 23:24:24 +0000 (UTC)
    User-Agent: Mozilla/5.0 (Windows NT 5.2; rv:7.0.1) Gecko/20110929 Thunderbird/7.0.1
    In-Reply-To: <ji3f8b$jkc$1@inews.gazeta.pl>
    Xref: news-archive.icm.edu.pl pl.comp.programming:195646
    [ ukryj 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: