Poszukuję algorytmu aproksymacji dla następującego problemu - Mam nieważony, nieukierunkowany wykres, z cyklami, i chcę znaleźć najdłuższą ścieżkę zaczynającą się od danego węzła. Ja cenię szybkość nad wydajnością (więc algorytm O (n^5) prawdopodobnie byłby przesadą).Najdłuższy algorytm aproksymacji ścieżki z danego węzła
To nie jest praca domowa (przysięgam!) Lub związane z pracą, ale doceniam każdą wskazówkę, jaką możesz mieć.
szukam algorytmu aproksymacji dla następującego problemu ...
Naukowcy szukają dla niego również. Mają także proved, że aproksymacja wielomianu stałoprądowego nie istnieje, jeśli P ≠ NP. I streszczenie artykułu this twierdzi, że zawiera algorytm aproksymacji dla twojego problemu.
Wow, nie wiedziałem tego. Myślałem, że uogólniony problem ma stały algorytm aproksymacji czynników. Co dalej ograniczać problem, utrzymując maksymalną liczbę sąsiadów? – r0u1i
@ r0u1i, Whoops, pierwszy artykuł, który łączyłem, zawiera również dowód, że takie ograniczenie nie pomaga :-). –
Dzięki, Ty wygrasz :) – r0u1i
jest to dla konkursu google? Tak się tu dostałem, haha! – aramadia
Znasz mnie zbyt dobrze :) – r0u1i