-
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
Następne wpisy z tego wątku
- 23.02.12 07:55 Piotr Chamera
- 23.02.12 10:47 Piotr Chamera
- 23.02.12 19:23 A.L.
- 23.02.12 23:14 Piotr Chamera
- 24.02.12 14:01 A.L.
- 24.02.12 16:37 Piotr Chamera
Najnowsze wątki z tej grupy
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
Najnowsze wątki
- 2024-11-11 Wyważanie kół rowerowych
- 2024-11-11 Kosz, gdzie??
- 2024-11-11 Coraz mniej ludzi robi prawo jazdy
- 2024-11-11 Opole => SAP HANA Cloud Dev / Data Engineer <=
- 2024-11-11 Warszawa => Spedytor Międzynarodowy <=
- 2024-11-11 Lublin => Senior PHP Developer <=
- 2024-11-11 Marki => Senior PHP Symfony Developer <=
- 2024-11-11 Chrzanów => Team Lead / Tribe Lead FrontEnd <=
- 2024-11-11 Gliwice => Specjalista ds. public relations <=
- 2024-11-11 Gdańsk => Kierownik Działu Spedycji Międzynarodowej <=
- 2024-11-11 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-11-11 Warszawa => Sales Development Representative (in German) <=
- 2024-11-11 Marsz niepodległości
- 2024-11-08 Belka
- 2024-11-09 pierdolec na punkcie psa