-
Path: news-archive.icm.edu.pl!news.rmf.pl!agh.edu.pl!news.agh.edu.pl!news.onet.pl!.PO
STED!not-for-mail
From: Piotr Chamera <p...@p...onet.pl>
Newsgroups: pl.comp.programming
Subject: Re: Pytanie z algorytmiki
Date: Sun, 22 May 2011 10:24:56 +0200
Organization: http://onet.pl
Lines: 70
Message-ID: <irah8r$4uu$1@news.onet.pl>
References: <ir8h3q$qnv$1@news.onet.pl> <ir8m7l$e55$1@news.onet.pl>
NNTP-Posting-Host: public37386.xdsl.centertel.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: news.onet.pl 1306052699 5086 79.163.146.10 (22 May 2011 08:24:59 GMT)
X-Complaints-To: n...@o...pl
NNTP-Posting-Date: Sun, 22 May 2011 08:24:59 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; pl; rv:1.9.2.17) Gecko/20110414
Lightning/1.0b2 Thunderbird/3.1.10
In-Reply-To: <ir8m7l$e55$1@news.onet.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:190570
[ ukryj nagłówki ]W dniu 2011-05-21 17:37, Piotr Chamera pisze:
> W dniu 2011-05-21 16:10, Jacek Czerwinski pisze:
>> Obiekt ma listę (być może pustą) Obiektów których 'aktywacji' sam wymaga
>> (pewna czynność tzn 'aktywacja' nad nimi musi być chronologiczna).
>> Obrazowo można myśleć o obiektach jak o stworzonych ale nie
>> wystartowanych service'ach.
>>
>> Listę (tablicę, obojętne) takich obiektów posortować.
>> a) pewnie algorytmika zna coś gotowego
>> b) mili widziane (bardzo, nawet można pomyśleć o zerwaniu algorytmu
>> wyjątkiem), kontrola czy z tych zależnościach nie ma sprzeczności.
>>
>> Obiekty dziedziczą ze wspólnego przodka.
>>
>> Ewentualnie
>> c) algorytm bez sortowania, wykonuj wyżej wspomnianą czynność dla
>> wszystkich zaczynając od przypadkowego obiektu, poprzedzając
>> rekurencyjnie akcją dla wymaganych, (profilaktycznie odnotowując co już
>> było wykonane). Nie jest zbyt brutal-force?
>> W razie sprzeczności, "jakoś" się to wykona. Sortowanie bardziej mi się
>> podoba, bo da wyjątek bardzo wcześnie.
>
> Może tak: zbudować graf skierowany, sprawdzić czy jest acykliczny (jeśli
> jest cykl, to sprzeczność w zależnościach), posortować topologicznie.
Nie wiem jaki dokładnie jest cel, ale w ramach nauki Lispu wypociłem
coś jak poniżej (w Common Lispie) na bazie przeglądania grafu wszerz
(wg Cormena).
Procedura sprawdza czy graf jest acykliczny, ale na tej bazie można
wykonać i inne operacje na grafie (np. wylistować wszystkie zależności
danego wierzchołka - wywołać dfsa? dla żądanego wierzchołka i
kolekcjonować informacje o odwiedzonych obiektach).
Przykładowe obiekty mają taką strukturę
(defstruct obj
name ;nieużywany, ale przydaje się kiedy chcemy wydrukować graf
dep ;krawędzie grafu
)
(obj-dep x) jest akcesorem do listy zależności (krawędzi grafu)
(defun check (objects)
(let ((markers (make-hash-table :test 'eq)))
(labels ((work-on (x)
"oznacz wierzchołek jako obecnie przetwarzany"
(setf (gethash x markers) 'working))
(finish-with (x)
"oznacz wierzchołek jako przetworzony wraz z dziećmi"
(setf (gethash x markers) 'finished))
(get-marker (x)
"sprawdz co wiemy o wierzchołku (domyślnie - jeszcze nieodwiedzony)"
(gethash x markers 'virgin))
(dfsa? (v)
"test czy graf widoczny z wierzchołka v jest acykliczny"
(work-on v)
(loop :for x :in (obj-dep v) :do
(case (get-marker x)
(virgin (dfsa? x))
(working (return-from check
(format nil "w grafie jest cykl")))
(finished nil)))
(finish-with v)))
(loop :for v :in objects :do
(when (eq 'virgin (get-marker v))
(dfsa? v)))))
(format nil "w grafie nie ma cykli"))
Następne wpisy z tego wątku
- 27.05.11 20:56 Jacek Czerwinski
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-05-26 O co chodzi?
- 2024-05-26 PJ autobus-tramwaj
- 2024-05-26 Renault Trafic i lampka z czerwonym STOP
- 2024-05-26 cena pięciocyfrowa
- 2024-05-26 Re: Jak dobra KE "okrada" złą Rosję "dla Ukrainy"
- 2024-05-25 supercap
- 2024-05-25 Sulzbach => Technischer Rollouter (d/m/w) <=
- 2024-05-25 Warszawa => Senior Account Manager <=
- 2024-05-25 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-25 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-25 Warszawa => Interactive/Experience Designer <=
- 2024-05-25 Warszawa => Key Account Manager <=
- 2024-05-25 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-25 Warszawa => Key Account Manager <=
- 2024-05-25 Re: znów ten wrocław