Problem najkrótszej ścieżki z bazowymi zmiennymi ciągłymi
Niedawno zainteresowałem się następującą odmianą problemu najkrótszej ścieżki. Szukałem w literaturze przez kilka dni, ale nie mogłem znaleźć żadnego artykułu zajmującego się tym problemem. Chciałbym zapytać, czy widzieliście już ten problem (lub podobny problem) i czy moglibyście wskazać mi odpowiednią literaturę.
W kilku słowach problem jest następujący. Mamy ukierunkowany wykres$G = (V, E)$. Dla każdego wierzchołka$v \in V$ mamy zestaw $S_v \in \mathbb R^m$ (powiedz wypukłe) i punkt w nim $x_v \in S_v$. Długość krawędzi$(u,v) \in E$ to np. odległość euklidesowa pomiędzy $x_u$ i $x_v$. Ścieżka$P$ ze źródła $s \in V$ do miejsca przeznaczenia $d \in V$jest definiowana w zwykły sposób. Długość ścieżki$P = (v_1=s, v_2, \ldots, v_{n-1}, v_n=d)$z drugiej strony jest definiowany jako minimum względem lokalizacji punktów $x_{v_1} \in S_{v_1}, \ldots, x_{v_n} \in S_{v_n}$ sumy długości krawędzi $(v_1, v_2), \ldots, (v_{n-1}, v_n)$. Wśród wszystkich ścieżek z$s$ do $d$, szukamy jednego o minimalnej długości.
Ten problem ma posmak „Najkrótszej ścieżki euklidesowej” (patrz np. Sharir i Schorr, „Na najkrótszych ścieżkach w przestrzeni wielościennej”), który jest powszechny w nawigacji robotów, ale ma istotne różnice. Widziałem również problemy z najkrótszą ścieżką przy uogólnionych długościach łuków (patrz np. Frieze, „Minimalne ścieżki w grafach skierowanych”), ale to sformułowanie problemu również nie pasuje do powyższego.
Jakieś przemyślenia / pomysły?
Odpowiedzi
Odpowiadając na pierwotne pytanie, nie widziałem tego wcześniej problemu. Głosowałem za odpowiedzią Kuifje, ponieważ w przybliżeniu powinno być dość wydajne obliczeniowo, jeśli dyskretyzacja nie tworzy zbyt wielu punktów.
Innym podejściem, które moim zdaniem sprawdziłoby się, byłoby riff na dekompozycji Bendersa. Wymaga, aby zbiory wypukłe były wielościenne i podane algebraicznie (albo jako zbiory punktów ekstremalnych i promieni ekstremalnych, albo jako rozwiązania zbiorów liniowych nierówności). Głównym problemem byłby program liniowy z mieszanymi liczbami całkowitymi, który wybiera „ścieżkę wirtualną” (ścieżkę na wykresie). Zbiory wypukłe i ich punkty nie pojawiłyby się w zadaniu głównym. Podproblem byłby program stożkowy drugiego rzędu, który dla kandydata „ścieżki wirtualnej” obliczałby najkrótszą odpowiadającą mu „ścieżkę fizyczną” (wybierając punkty ze zbiorów wypukłych). Gdyby główny problem nie doceniał długości fizycznej ścieżki, do głównego problemu dodawano by „cięcie optymalizacyjne” i zabawa byłaby wznowiona. Mam wstępne sformułowanie, ale nie jestem pewien, czy jest przydatne.
Aktualizacja : „Popularny wniosek”, oto mój pomysł. Ktoś powinien sprawdzić moją matematykę. Najpierw trochę terminologii. Ścieżka wirtualna to ścieżka na wykresie. Ścieżka fizyczna to odpowiednia sekwencja odcinków linii łączących punkty w powiązanych zestawach wypukłych. Użyję$s$ i $t$ do oznaczenia odpowiednio początku i miejsca przeznaczenia ścieżki wirtualnej.
Przed sformułowaniem problemu głównego obliczamy najkrótszą odległość fizyczną odpowiadającą każdej krawędzi w $E$. Pozwolić$$d_{i,j}=\min\left\{ \left\Vert x_{i}-x_{j}\right\Vert :x_{i}\in S_{i},x_{j}\in S_{j}\right\} \ \forall(i,j)\in E.$$
Główny problem dotyczy tylko części wirtualnej (tj. Wykresu), a nie części fizycznej. Na każdą krawędź$(i,j)\in E$ mamy zmienną binarną $y_{i,j}$to jest 1 wtedy i tylko wtedy, gdy ta krawędź jest częścią wybranej ścieżki. Mamy również zmienną nieujemną$w$to jest surogat długości fizycznej ścieżki. Główny problem to:\begin{alignat*}{1} \min & \ \ w\\ \textrm{s.t.} & \sum_{(i,j)\in E}y_{i,j}-\sum_{(j,i)\in E}y_{j,i}=\begin{cases} 1 & i=s\\ -1 & i=t\\ 0 & s\neq i\neq t \end{cases}\forall i\in V\\ & w\ge\sum_{(i,j)\in E}d_{i,j}y_{i,j}\\ & \dots \end{alignat*}gdzie wielokropek reprezentuje cięcia Bendera (przyszłe). Pierwszy zestaw ograniczeń to typowe elementy przepływu ścieżek; ostatnie ograniczenie to prawidłowa dolna granica dla każdej możliwej ścieżki.
Podproblem jest problem ze stożkiem drugiego rzędu (myślę - ktoś naprawdę powinien to sprawdzić, ponieważ normalnie nie zadzieram z SOCP). Podproblem jest zbudowany wokół proponowanej ścieżki wirtualnej$P$. używam$P_V$ oznaczać wierzchołki na ścieżce i $P_E$do oznaczenia krawędzi na ścieżce, obie postrzegane jako zestawy. Używa zmiennych nieujemnych$z_{i,j}$ reprezentowanie długości euklidesowej segmentu fizycznego odpowiadającego krawędzi $(i,j)\in P_E$. \begin{alignat*}{1} \min & \sum_{(i,j)\in P_{E}}z_{i,j}\\ \mathrm{s.t.} & \ \ x_{i}\in S_{i}\ \ \forall i\in P_{V}\\ & z_{i,j}\ge\left\Vert x_{i}-x_{j}\right\Vert \ \ \forall(i,j)\in P_{E}. \end{alignat*}
Pierwsze ograniczenie ($x_i \in S_i$) należy przełożyć na liniową równość lub ograniczenia nierówności. (Przypomnij sobie, że zakładam$S_i$ jest wielościenny.) Jeśli $S_i$jest podawany jako zbiór skrajnych punktów (i być może zbiór ekstremalnych promieni), to pociąga za sobą dodanie grupy zmiennych wagi używanych do obliczania wypukłych kombinacji skrajnych punktów i nieujemnych kombinacji ekstremalnych promieni. Zwróć uwagę, że jeśli ścieżka wirtualna to tylko jedna krawędź$(i,j)$, ten problem można wykorzystać do obliczenia $d_{i,j}$.
Chodzi o to, aby rozwiązać główny problem i uzyskać wirtualną ścieżkę kandydata $\hat{P}$. Możesz doprowadzić mistrza do optymalności lub jeśli używasz solwera obsługującego wywołania zwrotne, możesz po prostu przejść do pierwszego (lub następnego) rozwiązania kandydata. Ta ścieżka jest używana do konstruowania podproblemu, który jest rozwiązywany w celu uzyskania rzeczywistej najkrótszej fizycznej reprezentacji ścieżki wirtualnej. Jeśli zmienna zastępcza odpowiada długości fizycznej, zaakceptuj rozwiązanie (i, jeśli używasz wywołań zwrotnych, kontynuuj). Jeśli nie, dodajemy następujące cięcie Giętarki:$$w\ge\hat{f}\left(\sum_{(i,j)\in\hat{P}_{E}}y_{i,j}-\left|\hat{P}_{E}\right|+1\right),$$ gdzie $\hat{f}$ jest optymalną obiektywną wartością podproblemu (najkrótsza możliwa długość ścieżki fizycznej) i $\left|\hat{P}_{E}\right|$to liczba krawędzi ścieżki wirtualnej. Cięcie Bendera jest gwarantowane jako niewiążące, z wyjątkiem sytuacji, gdy wirtualna ścieżka zawiera wszystkie krawędzie, które ma bieżąca, więc nie jest to mocne cięcie w żaden sposób, ale jest prawidłowe.
Jednym ze sposobów rozwiązania tego problemu byłaby dyskretyzacja zbiorów $S_v$ dla każdego $v \in V$. To znaczy zdefiniuj skończoną liczbę punktów wewnątrz$S_v$i dla każdego z tych punktów zdefiniuj węzeł. Połącz te węzły ze wszystkimi sąsiadami węzła$v$, ale dostosuj odległość do rzeczywistej odległości euklidesowej.
Gdy masz już ten nowy wykres, uruchom klasyczny algorytm najkrótszej ścieżki.
Załóżmy na przykład, że na wykresie masz tylko jedną krawędź: $G=(\{u,v\},(u,v))$. Chcesz najkrótszej drogi od$u$ do $v$. Zdefiniuj węzły$u_1,...,u_n$ na pokrycie zestawu $S_u$i węzły $v_1,...,v_n$ dla $S_v$i dodaj krawędź z każdego wierzchołka $u_i$ do każdego wierzchołka $v_j$, z kosztami $d_{u_i,v_j}$, gdzie $d$oznacza odległość, której używasz. Możesz zdefiniować źródło i połączyć je z każdym węzłem$u_i$i zlewozmywak, który jest z nimi połączony $v_j$. Teraz najkrótsza ścieżka z$u$ do $v$ to najkrótsza ścieżka od źródła do zlewu.
Jeśli nierówność trójkąta zachodzi dla funkcji odległości, nie mogę wymyślić dobrego powodu, dla którego nie wystarczyłoby tylko zdyskretyzować granice zbiorów $S_v$. W takim przypadku zaoszczędzisz trochę miejsca i zmniejszysz złożoność. Jednak udowodnienie, że to wystarczy, nie zostało jeszcze zrobione.