Dana jest tablica \(\displaystyle{ n\times n}\), \(\displaystyle{ n>1}\), w której w każde pole wpisano liczbę całkowitą. Chcemy przejść z dolnego lewego rogu (z \(\displaystyle{ \left( 1,1 \right)}\) ) do górnego prawego rogu (do \(\displaystyle{ \left( n,n \right)}\) ) i wrócić, idąc w drodze z \(\displaystyle{ \left( 1,1 \right)}\) zawsze w prawo lub w górę, a z powrotem - w lewo lub w dół. Z danego pola można przejść tylko na pola sąsiednie (współrzędne różnią się o \(\displaystyle{ 1}\) na dokładnie jednej pozycji). Żadne pole nie może się pojawić na całej trasie (czyli tam i z powrotem) więcej niż raz, poza polem \(\displaystyle{ \left( 1,1 \right)}\), które pojawia się na początku i na końcu trasy. Zaprojektuj algorytm znajdowania najtańszej trasy, czyli takiej, na której suma wartości pól jest najmniejsza.
Ma ktoś na to pomysł ?
[Algorytmy] Rozłączny cykl o najmniejszej wadze w macierzy.
-
matinf
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
[Algorytmy] Rozłączny cykl o najmniejszej wadze w macierzy.
Ostatnio zmieniony 13 lis 2014, o 12:46 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Afish
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Rozłączny cykl o najmniejszej wadze w macierzy.
Trudno jest mi odpowiedzieć, bo nie znam algorytmu, jedynie użyłem gugla.
... 8X97001212
To twierdzi, że ogólny problem (gdy pary wierzchołków są różne, a k jest zmienne) jest NP-zupełny, jednocześnie podaje algorytm wielomianowy dla \(\displaystyle{ k=2}\). Jednocześnie tutaj: ... Tholey.pdf
jest informacja, że dla grafów nieskierowanych problem jest w P, jednak nie widzę nigdzie znajdowania minimum, a jedynie znajdowanie ścieżek. Podany przeze mnie w poprzedniej wiadomości papier znajduje dwie najkrótsze ścieżki, ale wykorzystuje Monte Carlo, więc zapewne nie jest w pełni deterministyczny. Pozostaje zagłębienie się w lekturę.
... 8X97001212
To twierdzi, że ogólny problem (gdy pary wierzchołków są różne, a k jest zmienne) jest NP-zupełny, jednocześnie podaje algorytm wielomianowy dla \(\displaystyle{ k=2}\). Jednocześnie tutaj: ... Tholey.pdf
jest informacja, że dla grafów nieskierowanych problem jest w P, jednak nie widzę nigdzie znajdowania minimum, a jedynie znajdowanie ścieżek. Podany przeze mnie w poprzedniej wiadomości papier znajduje dwie najkrótsze ścieżki, ale wykorzystuje Monte Carlo, więc zapewne nie jest w pełni deterministyczny. Pozostaje zagłębienie się w lekturę.