On Tue, 07 Apr 2009 09:33:46 +0200, Pawe? Kierski <n...@p...net>
wrote:

>A.L. wrote:
>>
>>
>> Czy ja gdzies pisalem ze nie?...
>
> Tu:
>http://groups.google.pl/group/pl.comp.programming/m
sg/154593d9ef569106
>
>"Droki Kolego, problemy NO-completne maja to do siebie ze petelkami sie
>ich nei rozwiaze." (pisownia oryginalna)

Zalaczam calsy ciag oryginalnej pisowni z ktorej ejstem dumny:

"
Droki Kolego, problemy NO-completne maja to do siebie ze petelkami sie
ich nei rozwiaze. Slynny problem komiwojazera - jaka jest najkrotsza
droga laczaca N miast, nla N = 20 wymaba przejrzenai 2,5 10^18
wariantow. Jasne, dla nowoczesnych komputerow to zaden problem. Tyle
ze czas Wszechswiata liczony w milisekundaych to cos 10^20..."

Latwo sprawdzic samemu ze 3 miasta sie rowiaze. Nawet bez komputera.
Jak komus potzrebny komputer, to widac ma wiecej niz 3 miasta.

A.L.

P.S. Dziekuje Koledze za troske o moja ortografie. Musle jednak ze
lepiej by bylo gdyby KOlega zadbal o siebie

do góry

On 6 Kwi, 23:29, Michoo <m...@v...pl> wrote:

> > Tak zupelnie to nie. Jezeli mamy miasta polaczone drogami
> > niekoniecznei kazde z kazdym, to problemy poszukiwania JAKIEJKOWIEK
> > drogi przechodzacej przez wszystkie miasta, czy tez stwierdzenia czy
> > taka droga w ogole istnieje znana sa jako "problem poszukiwania
> > sciezki Hamiltonowskiej" i oba sa NP-zupelne.
>
> I mimo tego dla małych n są rozwiązywalne metodą brute-force (pytający
> pisał o *3* pracownikach). Dla większych n dostaje się całkiem
> przyzwoite wyniki w ciągu kilku minut za pomocą choćby local-search czy
> symulowanego wyżarzania.
>
Rozwiązywalność metodą brute-force jest bardzo względne.
Właśnie skończyłem projekt, gdzie algorytm brute-force (pętelki ;) )
działał około 11 wolniej niż rozwiązanie oparte na dość zaawansowanej
matematyce.
Problem nie był tak trudny obliczeniowo (chociaż złożoność reguł
była duża ) jak problem komiwojażera i wydawało się, że nic lepszego
od
brute-force'a (z prostymi optymalizacjami kodu) nie da się
zaproponować.
Chodziło o przyspiesznie obliczeń z 1 minuty do 5 sekund :). Takiej
redukcji
nie dało się zrobić zwykłymi trikami programistycznymi, także local-
search
czy symulowane wyżarzanie odpadały (nie mówiąc o innych cudach typu
algorytmy genetyczne).
Podsumowując. Wszystko jest względne i nie tylko wielkość zadania
jest ważna. Także to jakie są oczekiwania zlecającego w stosunku do
dostarczonego rozwiązania.

Pozdrawiam,
Wit [ http://wlogsolutions.pl ]

do góry

A.L. pisze:
> On Sun, 05 Apr 2009 20:35:22 +0200, Jacek Czerwinski <...@...z.pl> wrote:
>
>> Rzecz ciekawa, zachodni świat z jednolicie wykształconymi manago (i
>> systemami optymalizacji drobna złośliwość) wdepnął z własnej woli w
>> kryzys wirtualnego pieniądza, gdy ta część zarządzana na talent,
>> rozsądek i intuicję nie wlazła w gówno (do tego stopnia i z własnej woli
>> - wierzę, nie mam dowodów).
>> Wirus zawsze łatwiej atakuje monokulturę.
>>
>
> A tego to nei rozumiem.
Mam na myśli wirus zupełnie niekomputerowy, jakąś muszkę w kraju
nastawionym wyłącznie na kukurydzę itd. Drobna 'pomyłka' biologiczna
staje się katastrofą.

> Te firmy ktore maja sie dobrze, to o ile mi
> wiadomo, rowniez (a moze pzrede wsystkim) kupuja soft do
> optymalizacji. Mimo "kryzysu". Twierdzi Kolega ze "wyksztalciuchy" w
> przemysle sie nie sprawdzaja, liczy sie tylko "nie matura a chec
> szczera"?

Nie mam na mysli 'oficera'. Jest znakiem czasów, potrzebą i
koniecznością specjalistyczne wykształcenie zawodowe. Dostrzegam w nim
jednolitość: belgijska szkoła jaką kończył manager, niemiecki program do
zarządzania we francuskiej firmie, oddział w Hiszpanii, koncepcje są
wspólne, jest to OK. Jednak nie ma róży bez kolców: w wysoko
ujednoliconych społecznościach specjalistów (nie ma już szkoły
falenickiej i otwockiej) jest słaby dyskurs, nie ma tego co kojarzę pod
kulturą 'universitas', zwłaszcza że panują dosłownie religijne mody
stawiające przeciwników w roli zacofanych idiotów.

Pamiętasz, kto w bajce krzyknął "Król jest nagi" ?

http://wiadomosci.onet.pl/1551510,2678,1,eksperci_br
edza,kioskart.html

Dodam od siebie, że parametry finansowe bankrutujących instytucji tez
obliczało jakieś (zaprojektowane i wytestowane) oprogramowanie wdrożone
przez jakiś współczesnych informatyków dla współczesnych managerów, i
ktoś komuś te kolorowe 'serki' podtykał przed twarz. Czy Excell, czy
soft za kilka zer, może nie równym stopniu, ale NIEKIEDY nadają sie do
uzasadnienia bzdur.


To, co zakodowałem w głowie z podwójnej magisterki (bynajmniej nie w
szkole oficerskiej), to "prawdziwa nauka zna swoje granice"

do góry

On Wed, 08 Apr 2009 07:46:56 +0200, Jacek Czerwinski <...@...z.pl> wrote:

>
>Nie mam na mysli 'oficera'. Jest znakiem czasów, potrzebą i
>koniecznością specjalistyczne wykształcenie zawodowe. Dostrzegam w nim
>jednolitość: belgijska szkoła jaką kończył manager, niemiecki program do
>zarządzania we francuskiej firmie, oddział w Hiszpanii, koncepcje są
>wspólne, jest to OK. Jednak nie ma róży bez kolców: w wysoko
>ujednoliconych społecznościach specjalistów (nie ma już szkoły
>falenickiej i otwockiej) jest słaby dyskurs, nie ma tego co kojarzę pod
>kulturą 'universitas', zwłaszcza że panują dosłownie religijne mody
>stawiające przeciwników w roli zacofanych idiotów.

Nie wiem jak jest w Hiszpanii. W ekonomii natomiast sa wyrazne szkoly
(na przyklad znaczaca i liczaca sie bardzo Szkola Austriacka").
Podobnie rozniece istnieje w USA miedzy Wharton School of Business na
przyklad Stern School of Buiiness. Oraz Paparazoo School of Busines, i
zatrudniajacy dokladnei wie kogo zatrudnia patrzac na dyplom.

Niestety, namnozylo sie "domoroslych" ekspertow, chetnei sluchanych
przez pobliczke, albowiem ci "eksperci" glosza to co publiczka lubi.
Publiczka nei slucha prawdziwych ekspertow, albowiem mowia to co mysla
i na ogol sie to publiczce nie podoba, albo mowia zbyt trudnym
jezykiem

>
>Dodam od siebie, że parametry finansowe bankrutujących instytucji tez
>obliczało jakieś (zaprojektowane i wytestowane) oprogramowanie wdrożone
>przez jakiś współczesnych informatyków dla współczesnych managerów, i
>ktoś komuś te kolorowe 'serki' podtykał przed twarz. Czy Excell, czy
>soft za kilka zer, może nie równym stopniu, ale NIEKIEDY nadają sie do
>uzasadnienia bzdur.

A to i owszem, ale to sie bierze z postepujacego debilnienia
spoleczenstwa. Na calym swiecei jakby. Owszem, modele sa budowane
przez ekspertow, ale uzywane przez idiotow

http://www.forbes.com/forbes/2008/1117/044.html

NA ktoreks z grup (ekonomiczne, business lub alt.matematyka) puscilem
wiecej linkow na ten temat

A.L.

do góry

Losowanie i sprawdzenie będzie w porządku o ile prawdopodobieństwo
wylosowania dostatecznie dobrego układu nie jest zbyt małe. Jak będzie
zbyt małe to zwykle nie doczekasz się wylosowania dobrego grafiku i
twój program powie "niedasie". Ile wynosi to prawdopodobieństwo,
zależy od przyjętych ograniczeń, więc trudno powiedzieć.

Losując warto też przemyśleć sposób losowania, żeby było
"sprawiedliwie". W przypadku uwzględniania przy losowaniu na wstępie
"kilku prostszych warunków" wypada uważać, żeby niechcący nie zaburzyć
tej "sprawiedliwości".

Co do lepszego algorytmu - niestety nikt z nas grupowiczów nie zna tak
dobrze kodeksu pracy, a już na pewno życzeń pracowników i szefostwa. I
nie będziemy za ciebie analizować przepisów polskiego kodeksu pracy.
Jeśli te reguły ograniczeń są dowolnej postaci, to problem jest NP-
trudny (tak jak SAT), co nie znaczy, że nie da się go rozwiązywać
szybciej lub wolniej. A możliwe, że te reguły ograniczeń są tak
specyficzne, że wychodzi algorytm wielomianowy (np. problem 2-SAT), co
też nie znaczy, że nie da się go implementować szybciej lub wolniej.

Jeśli zależy ci na prędko napisanym jako-takim prototypie, możesz np.
przekształcać ograniczenia na wejscie do SAT-solvera czy czegoś w tym
stylu.

do góry