Witam, przeszukałem całe forum, ale nie znalazłem podobnego problemu, dostałem taki oto projekt:
Na płaszczyźnie dany jest zbiór punktów o współrzędnych całkowitych. Przez ścieżkę pomiędzy parą punktów tego zbioru rozumiemy sekwencję odcinków równoległych do osi układu współrzędnych. Długość ścieżki to suma odległości odcinków wchodzących w jej skład. Ścieżka jest minimalna, jeżeli nie istnieje inna krótsza ścieżka łącząca tę parę punktów (może być wiele ścieżek minimalnych). Minimalną ortogonalną siecią połączeń dla zadanego zbioru punktów płaszczyzny nazywamy taki zbiór odcinków spinających zadane punkty, w którym każda para punktów ma połączenie minimalne i koszt całego zbioru (suma wszystkich odcinków) jest minimalny. Opracować algorytm znajdujący minimalną ortogonalną sieć połączeń.
Czy ktoś z was ma jakiś pomysł na algorytm który rozwiązywałby to zadanie? (najlepiej o złożoności wielomianowej, ale niekoniecznie).
Byłbym bardzo wdzięczny za pomoc.</quote>