-
Path: news-archive.icm.edu.pl!news.icm.edu.pl!news.nask.pl!news.nask.org.pl!goblin2!g
oblin.stu.neva.ru!newsfeed1.swip.net!news.glorb.com!news-in-01.newsfeed.easynew
s.com!easynews!core-easynews-01!easynews.com!en-nntp-16.dc1.easynews.com.POSTED
!not-for-mail
From: A.L. <l...@a...com>
Newsgroups: pl.comp.programming
Subject: Taki problem programistyczny...
Message-ID: <m...@4...com>
X-Newsreader: Forte Agent 4.2/32.1118
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 35
X-Complaints-To: a...@e...com
Organization: Forte Inc. http://www.forteinc.com/apn/
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will
be unable to process your complaint properly.
Date: Tue, 21 Feb 2012 15:52:27 -0600
X-Received-Bytes: 2038
Xref: news-archive.icm.edu.pl pl.comp.programming:195602
[ ukryj nagłówki ]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.
Następne wpisy z tego wątku
- 22.02.12 02:48 Daniel Janus
- 22.02.12 12:20 bartekltg
- 22.02.12 14:52 A.L.
- 22.02.12 15:04 A.L.
- 22.02.12 18:03 Piotr Chamera
- 22.02.12 19:21 Piotr Chamera
- 22.02.12 23:24 n...@m...invalid
- 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
- 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
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-06 Nowy sprytny tel. z Androidem 13. - OSTRZEŻENIE!!!
- 2024-06-08 czarny punkt - Małdyty
- 2024-06-08 Protesters attempt to storm Tesla's factory in Germany
- 2024-06-07 przydałaby się grupa o wszystkim
- 2024-06-07 Rowerzyści! Co się z wami dzieje?!
- 2024-06-07 Peltier
- 2024-06-07 Jakie znacie działające serwery grup dyskusyjnych?
- 2024-06-07 nerwica lękowa
- 2024-06-07 Jakie znacie działające serwery grup dyskusyjnych?
- 2024-06-07 Jakie znacie działające serwery grup dyskusyjnych?
- 2024-06-08 Warszawa => Spedytor międzynarodowy <=
- 2024-06-08 Warszawa => QA Manager <=
- 2024-06-08 Warszawa => Projektant/Programista React Native <=
- 2024-06-08 Zabrze => Junior HelpDesk <=
- 2024-06-08 Warszawa => Business Development Manager <=