Witam,
Za zadanie mam zaprojektować algorytm tworzący plan rozłącznych ścieżek, doprowadzających wieże do dowolnej krawędzi szachownicy, dla K wież rozmieszczonych na szachownicy losowo. Plan powinien optymalizować ilość ruchów (ruchów 'szachowych', tj. dozwolonych dla wieży w szachach).
Pomysłów mam wiele. Z wykorzystaniem rang punktów w przestrzeni 2D, bądź z szukaniem optymalnej osi projekcji regularnej w celu wyznaczenia kierunków ruchów. Ale tak na prawdę nie jestem w stanie udowodnić, że którykolwiek z moich pomysłów w ogóle znajdzie plan ścieżek dla każdego układu, dla którego taki plan istnieje.
Złożoność algorytmu powinna mieścić się w asymptotyce wielomianowej.
Ma ktoś może pomysł jak zaprojektować algorytm dla tego problemu, albo do jakiego problemu, zbioru podproblemów go sprowadzić?
Pozdrawiam,
Paweł