Informatyka UJ forum

Rogal

Nieco dziwne, jutro kolos a tu odpowiedniego wątku na forum nie ma. No to zakładam 8)

Spectro

Dopiero po kolosie pojawią się tu sensowne komentarze :P . Przed kolosem to lepiej bombardować pytaniami forum TCS.

Rogal

A co jeśli ktoś ma jakiś przeciek? :twisted:

Ja znam na razie treść tylko 1 zadania :roll:

ostoj

taaak? :) a podziel sie :)

Rogal

No dobra, jak ujawnię 1 zadanie to chyba nic się złego nie stanie :twisted:

"Mając dany graf skierowany (V,E), bez cykli o dodatnich wagach, oraz wierzchołki a, b należące do V wyznacz najdłuższą ścieżkę pomiędzy a i b. "

Od redakcji: w zadaniu nie ma słowem wspomniane, że nie ma cykli wogóle albo że wagi ścieżek nie mogą być ujemne więc zakładam że jedno i drugie może mieć miejsce.

Tylko cśśś, nikomu z TCS ani słowa :!:

ostoj

hmm a jak to idzie? bellman-ford ze zmienionym znakiem nierownosci w relax?

Rogal

Jak dla mnie to zmodyfikowana Dijkstra. Ale zobaczymy.

Makros

Dla mnie też... bo niema krawędzi dodatnich...

chlebek

a ja bym zastosowal algorytm DAG-paths bo po pierwsze graf nie ma cykli, a ten algorym stosuje sie do grafow acyklicznych, a po drugie na dole strony z tym algorytmem jest taki problem jak Rogal napisal :D, chyba ze jak Rogal wspominal moga byc cykle ujemne wtedy Dijkstra, ale chyba z 2 modyfikacjami.

Rogal

Krawędzie mogą być dodatnie, cykle nie mogą być. Nie mniej zwykła Dijkstra z odwróconym Relaxem powinna wystarczyć. Dowód poprawności jest de facto praktycznie identyczny z dowodem na poprawność Dijkstry.

edited: Właśnie graf może mieć cykle, tyle że ujemne. Wydaje mi się, że Dag się na tym wyłoży.

edited 2: jak dla mnie wystarczy zmodyfikować Relax, a kolejka priorytetowa zostaje normalna, tj. też zawsze ściągamy wierzchołek o najmniejszym czasie.

Robson

Belman-ford tez pójdzie, tylko
D[i] = - nieskonczonosc; V i <> a
D[a] = 0;

i oczywiscie zmiana nierownosci w relax

Dijkstra sie moze wyłozyć, bo mamy krawedzie tak dodatnie jak i ujemne... nie udowodnie tego ale chyba:
Problem jest rownoważny: Znależć najkrotszą scieżkę w grafie w którym zmienimy koszty na przeciwne.

Rogal

B-F pójdzie, ale jest istotnie wolniejszy, więc mniej punktów.

Drakk

dijkstra sie wylozy przez dodatnie krawedzie...

Robson

Z tego co pamietam to Śluman własnie przy okazji B-F omawiał problem znajdowania najdłuższych scieżek w grafie, a przy dijkstrze tego nie było...

ostoj

a takie pytanie z innej beczki - dlaczego w zwyklej dijkstrze jest zalozenie ze nie moze byc krawedzi ujemnych?

Rogal

Dijkstra się nie wyłoży. Normalna się wykłada dlatego, że jeśli mamy krawędź ujemną to może się zdarzyć, że po jej zrelaksowaniu otrzymany wierzchołek był już "przerabiany", tj. wszystkie wychodzące z niego krawędzie były już relaksowane, a teraz trzebaby je zrelaksować ponownie (czego algorytm nie robi).

Natomiast w tym przypadku nam to nie grozi, bo krawędzie nie są relaksowane "w dół" tylko "w górę". Jest tylko problem z początkowym ustawieniem wartości w wierzchołkach. Trzeba albo je ustawić wszystkie na 0 i do kolejki priorytetowej wrzucać na bierząco tylko niezerowe (nie licząc źródła) albo ustawić na +infinity i w relaksie sprawdzać, czy jest infinty czy nie. Moim zdaniem łatwiej zmienić relaxa.

btw. Możliwe, że dostanę jeszcze jedno zadanie, ale raczej jest to mało prawdopodobne :?

Madras

Z tym zadaniem to poważnie? Przecież jak ktoś to zobaczy, to i tak zmieni (jeśli przed) albo unieważni (jeśli po)... No chyba, że sobie jaja robisz ;p.

Rogal

Przecież nikt z TCS nie przegląda tego forum. Nie bój żaby Madras :wink:

Madras

Założymy się?

Robson

Moment czy ja dobrze rozumiem. Chcesz tylko zmienić nierówność w relaxie i kirunek przesiewania ( zamiast w gore to w dół na kopcu)?
Czyli nadal bedziesz sciagał z kopca u takie ze D[u] jest najmniejsze i dla jego nastepników robił relax?
Jak dla mnie szalony pomysł. Bo przeciez moze sie okazać ze droga wiodaca przez inny wierzcholek do tego usowanego jest dłuższa
np:
a --- 5 ---> b
a----- 8 ----> c ---- 6 -----> b
b ----- 13 ---> d
zalozmy ze w jakims kroku sciagles krawedz droge a->b (5) poprawiles droge z a -> d na 8
Potem wzioles sie za droge a->c i poprawiles droge do b. teraz droga z a->b jest dluzsza (14 zamiast 5) ale juz jej nie przetestujesz bo ona z kopca spadła...

-------------------------------------------------------
@Madras, ja bym sie na twoim miejscu co najmniej o 200 założył ;)
@ Rogal: nie przyjmowałbym tego zakładu na twoim miejscu ;)

kap00ch

przeciez ten post to zart ;] poza tym rogal nie jest (jeszcze?) az taka lamka zeby na publica dawac leaka :>

Rogal

...

No to żegnajcie, dziś w nocy przyjdą po mnie panowie w czarnych garniturach (tzw. Nazgule) i już się więcej nie zobaczymy.

edited: Robson, masz rację. Więc muszę od nowa pisać gotowca.

Robson

A kto to wie... no ale jesli przypadkiem bedzie... co jest w sumie prawdopodobne...
No zawsze moze być zadanie: znajdz w grafie drzewo rozpinajace ktore spełnia warunki AVLa lub napisz BRAK gdy nie da sie zbudować...
dalej sie zastanawiam czy to nie jest problem NP....

kap00ch

jak na moj gust bezspecjalnych zalozen to jest ;p

Rogal

@Robson: To się chyba da zrobić kwadratowo, a może nawet szybciej. Ale nie jestem pewien czy to będzie na 100% działać :wink: