Algorytm znalezienie ścieżki o podanej długości (wadze)

Odpowiedz Nowy wątek
2018-10-30 21:15
1

Siemka,
Mój problem wygląda następująco:
Mam graf spójny nieskierowany, gdzie każdy wierzchołek ma liczbę swoją liczbę punktów. Punkty są zbierane za odwiedzenie danego wierzchołka. Muszę znaleźć ścieżkę pomiędzy podanymi dwoma wierzchołkami, przez którą przechodząc "zbiorę" zadaną liczbę punktów. Czy istnieje jakiś algorytm znajdujący rozwiązanie tego problemu, albo chociaż taki, którego modyfikacja dałaby mi rozwiązanie.
W internecie i literaturze znajduje tylko problemy dotyczące najkrótszych/najlżejszych i td ścieżek.

Pozostało 580 znaków

2018-10-30 23:22
0

Wygląda, że to może być dowolna droga między dwoma wierzchołkami, to nie pozostaje nic innego, jak zpuścic jakiś BFS odnotować sumę punktów do tego wierzchołka w wektorze i poszukać danej wartości.


Pozostało 580 znaków

2018-10-31 08:54
0

Czy możesz dany wierzchołek odwiedzać wielokrotnie? np. 1-2-3 , a szukasz trasy z 1 do 3 o długości 12, np. 1-2-1-2-1-2-3 ?

Pozostało 580 znaków

2018-10-31 19:07
2

Brzmi bardzo NP-zupełnie, w szczególności wygląda, jakby się dawało do tego zredukować problem sumy podzbioru…

Nic istotnie sprytniejszego od brute force’a mi do głowy nie przychodzi.

Może nie NP-zupełne, ale nic lepszego niż DFS nie znajdziesz. - hauleth 2018-11-02 12:39

Pozostało 580 znaków

2018-11-01 18:04
2

Załóżmy, że masz dojść od A do B z punktami K. Znajdujesz wszystkie wierzchołki mogące wystąpić na ścieżce prostej z A do B (nazwijmy ten podgraf X). Następnie puszczasz DFS z dopuszczalnymi powtórzeniami, ale wykluczając chodzenie po cyklach.
Na oko to i tak będzie wykładnicze, ale przy „normalnych” grafach da się pewnie zoptymalizować przez sortowanie quasi topologiczne.

Możesz też stosować dziel i zwyciężaj, dla każdej wartości k <= K i wierzchołka x z X rozbijasz problem na dojście z A do x z kosztem k + dojście z x do B z kosztem K - k.

Pozostało 580 znaków

2018-11-02 11:06
0
yarel napisał(a):

Czy możesz dany wierzchołek odwiedzać wielokrotnie? np. 1-2-3 , a szukasz trasy z 1 do 3 o długości 12, np. 1-2-1-2-1-2-3 ?

Zasadniczo określenie założeń również należy do mnie, ale na początku szukam rozwiązania bardzo ogólnego. Także tak, mogę w szczególności wykonać takie przejście.

To może jeszcze napisz jaki problem faktycznie chcesz rozwiązać. Może da się go wyrazić w inny sposób niż za pomocą grafu i szukania ścieżki o zadanym koszcie. - yarel 2018-11-02 11:10
problem wygląda tak jak napisałem, tzn tak został mi przedstawiony próbowałem znaleźć problem dualny, ale jedyne co wydawało mi się jakkolwiek zbliżone to nawigacja i sieć przepływów (oba problemy prezentowane za pomocą grafu). W przypadku nawigacji wzorowałbym się na algorytmie A*, ale nie potrafię wymyślić dobrej heurystyki, a sieć przepływów sprowadza się do optymalizacji, także to też dużo mi nie daje. - tomsinho123 2018-11-02 11:16

Pozostało 580 znaków

2018-11-02 12:41
1

Jeśli bez cykli, to masz przykład https://www.geeksforgeeks.org[...]ths-given-source-destination/. Z cyklami to nie wiem czy jest coś lepszego niż bruteforce.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0