Łączenie punktów + najkrótsza droga

MATEK126 · Post autor: **MATEK126** » 5 wrz 2009, o 00:16

Działa i dla trójkąta równobocznego też.

Post autor: **Dasio11** » 5 wrz 2009, o 08:11

No tak, powstaje wielokąt, ale jakby punktów było \(\displaystyle{ 2000}\) - nie odróżnisz od okręgu
Oddzielić \(\displaystyle{ n=3}\) punkty od reszty wydaje się być dobrym pomysłem, ale pamiętając, że początkowe zagadnienie miało \(\displaystyle{ n=4}\) punkty. Odpowiedź dla 3 może być podpowiedzią, ale nie rozwiązaniem ;P
Trudne zadanie...
P.S. Skoro mamy już parę ładnych kontrprzykładów, to proszę każdego, aby przed zamieszczeniem rozwiązania sprawdził, czy pasuje ono dla trójkąta równobocznego oraz wielokąta foremnego o dowolnie dużej liczbie wierzchołków. Chyba że przypadek szczególny. Albo jakaś uwaga nie będąca rozwiązaniem, ale ograniczająca możliwe odpowiedzi ;]

monomian · Post autor: **monomian** » 5 wrz 2009, o 08:47

A czy ktoś mógłby się wypowiedzieć na temat mojego rozwiązania dla pojedynczego węzła? (bo rozumiem, że to drugie, dla wielu węzłów, jest dość mało ścisłe)

Post autor: **Dasio11** » 5 wrz 2009, o 09:47

monomian, przypuśćmy, że znaleźliśmy taką funkcję. Jak teraz udowodnić, że nie można dodać następnego węzła i przez to skrócić sumę dróg - zamiast literki V zrobi się literka Y ?

Twoja odpowiedź jest dobra, gdy mamy jeden rozgałęźnik o \(\displaystyle{ n}\) wyjściach do dyspozycji. A mamy dowolną ilość.

Chciałbym w tym temacie zobaczyć zdanie jeszcze paru ludzi na forum, jednak nie wymienię ich nicków

monomian · Post autor: **monomian** » 5 wrz 2009, o 11:31

Dasio11 pisze:monomian, przypuśćmy, że znaleźliśmy taką funkcję. Jak teraz udowodnić, że nie można dodać następnego węzła i przez to skrócić sumę dróg - zamiast literki V zrobi się literka Y ?

Twoja odpowiedź jest dobra, gdy mamy jeden rozgałęźnik o \(\displaystyle{ n}\) wyjściach do dyspozycji. A mamy dowolną ilość.

Chciałbym w tym temacie zobaczyć zdanie jeszcze paru ludzi na forum, jednak nie wymienię ich nicków

Ale przecież z definicji funkcji wynika, że jest sumą długości od danego punktu - jeśli masz jej minimum, to to musi być punkt od którego biegnie najkrótsza droga. Jeśli dodasz nowy węzeł to jeśli nie leży on na już istniejącej drodze, to może ją tylko wydłużyć.

Post autor: **Dasio11** » 5 wrz 2009, o 11:37

Punkt na środku został stworzony sztucznie i został wyznaczony jako minimum Twojej funkcji. Krótsza jest droga czerwona czy zielona?

Może pokombinować z wektorami?

monomian · Post autor: **monomian** » 5 wrz 2009, o 12:08

Mógłbym poprosić o konkretne liczby, za pomocą których wyznaczyłeś ten punkt?

Inkwizytor · Post autor: **Inkwizytor** » 5 wrz 2009, o 12:14

Zadanie da sie sprowadzić do następującego problemu z teorii grafów. Niestety nie wiem na ile ten problem jest rozwiązany, gdyż trochę czasu minęło gdy ostatnio zajmowałem się grafami.

Część banalna
- Mamy n wierzchołków grafu nieskierowanego prostego (bez pętli i krawędzi wielokrotnych).
- Krawędzie z wagami. Waga krawędzi to odległość między parą wierzchołków
- Tworzymy graf pełny
- Istnieje algorytm Kruskala znajdujący minimalne drzewo rozpięte na tym grafie

Część problematyczna
Problem: Dodajemy k nowych wierzchołków i wespół z istniejącymi już n wierzchołkami rozpinamy nowe drzewo z n+k wierzchołkami takie że suma wag nowego drzewa jest mniejsza od sumy wag pierwotnego n-wierzchołkowego drzewa.

Czy istnieje dowód na to że problem jest ZAWSZE rozwiązywalny (albo dowód na "nie")?
Czy jeśli zawsze istnieje rozwiązanie to można oszacować/znaleźć dokładną liczbę k dla danego grafu?
Na pewno samo k nie zależy tylko od n ale i od wzajemnego położenia punktów.
Nawet jeśli znajdziemy k to czy możliwe jest znalezienie położenia tych k wierzchołków?

Dla zobrazowania w przypadku trójkąta równobocznego k=1 bo będzie to sztuczny węzeł wstawiony na "środku" trójkąta. Ale przykładowo dla n punktów współliniowych k=0
Dla osób analizujących wielokąty foremne zwracam uwagę na magiczną granicę n=6 (porównanie długości boku z promieniem okręgu opisanego w trójkacie, kwadracie, pięciokącie i sześciokącie oraz wielokąty o większej liczbie boków)

abc666 · Post autor: **abc666** » 5 wrz 2009, o 13:26

Z braku pomysłów na rozmieszczenie punktów do analizowania zrobiłem sobie mały skrypcik, który losowo ustawia punkty. Ilość punktów podajemy w adresie . Może komuś pomoże.

Post autor: **Dasio11** » 5 wrz 2009, o 13:46

monomian, mój rysunek w ogóle nie jest dokładny i nie bawiłem się w wyznaczanie tego punktu w środku - to jest rysunek poglądowy, na którym wyraźnie widać, że czasami dodanie węzła może skrócić sumę długości wszystkich krawędzi.
abc666 - genialne :] Na pewno bardzo się przyda w poszukiwaniu kontrprzykładów Albo, jeśli komuś się uda rozwiązać - będą to przykłady potwierdzające poprawność z algorytmem i im więcej "testów" on zaliczy tym większa szansa z teorii wielkich liczb

Inkwizytor · Post autor: **Inkwizytor** » 5 wrz 2009, o 14:23

MATEK126 pisze:Działa i dla trójkąta równobocznego też.

Tu pozwolę się nie zgodzić.

MATEK126 pisze:ponumeruj punkty w kolejności odleglości od żódła poczynając od najbliższego. Pierwszy łączymy ze źódłem, drugi z powstałą linią lub ze źródłem w zależnośći gdzie jest bliżej, trzeci z najbliższą z linii lub ze źódłem, itd. Suma linii będzie najkrótsza.

1. Mamy wierzchołki tworzące trójkąt równoboczny.
2. Źródło jest w jednym z wierzchołków.
3. Wybieramy jeden wierzchołek i podłączamy go do źródła. Czyli de facto rysujemy bok trójkąta.
4. Bierzemy trzeci wierzchołek. Albo podłączamy do któregoś wierzchołka (pokrywa sie z kolejnym bokiem) albo podłączamy do narysowanej wcześniej linii (czyli rysujemy wysokość w tym trójkącie). Oczywiście wybieramy tę drugą opcje.
5. Mamy konstrukcję bok i wysokość w trójkącie równobocznym

A porównaj to z rozwiązaniem Zordona

Ciekawe obserwacje dla pięciokąta foremnego. Nie jestem przekonany czy łamana idąca po 4 kolejnych bokach jest optymalnym rozwiązaniem.

monomian · Post autor: **monomian** » 5 wrz 2009, o 14:35

EDIT: Pomyłka, nie warto marnować czasu na rozważanie.

Inkwizytor · Post autor: **Inkwizytor** » 5 wrz 2009, o 14:42

Dasio11
Też w ten sposób próbuję ale doszedłem do wniosku że rozważanie trójek punktów (co można by później powiązać z traingularyzacją) i tego co narysowałeś CHYBA zależeć będzie od rodzaju rozważanego trójkąta pod względem długości boków (czy równoboczny) i pod względem kątów (ostrokątny, rozwartokątny)

abc666 · Post autor: **abc666** » 5 wrz 2009, o 14:46

Też trochę myślałem nad trójkami punktów. Poza tymi własnościami, które wymienił Inkwizytor, ważne jest jeszcze czy we wnętrzu trójkąta są inne punkty. Ale nadal nic konkretnego.

xiikzodz · Post autor: **xiikzodz** » 5 wrz 2009, o 14:47

Gdybyśmy przypadkiem znali te węzły konieczne do zrealizowania minimalnej połączenia rurami, zagadnienie byłoby niegorzej niż sześcienne (czas działania algorytmu) względem liczby węzłów - wystarczyłoby, jak to zauważył Inkwizytor, zbudować na nich graf pełny z wagami będącymi odległościami, następnie znaleźć jedno z minimalnych drzew rozpinających.

Nie ma więc problemu z numerycznym rozwiązaniem:

Pookrywamy otoczkę wypukłą tego zbioru punktów sześciokątami foremnymi - im mniejsze, tym lepsza dokładność - każdy sześciokąt traktujemy jako potencjalny węzeł, następnie stosujemy algorytm opisany powyżej. Jego złożoność obliczeniowa jest sensowna, więc nawet dla dużych sieci wodnych komputery się doliczą.

Jeśli chodzi o skonstruowanie punktów (nie chodzi o cyrkiel i linijkę, lecz o liczby) to wydaje mi się (mam argument, ale długi, skomplikowany i nieprzemyślany do końca) że zagadnienie jest NP-trudne. Te szukane węzły są bowiem rozwiązaniami układów równań liniowych zależnych od danych punktów, ale możliwych układów równań jest wykładniczo dużo. Argument wygląda z grubsza tak, że układając poszczególne równania dokonujemy arbitrarnego wyboru odpowiadającego wyborowi pomiędzy "V" a "Y". Te operacje naturalnie się zagnieżdżają - mając trzy (na przykład optymalnie) połączone grupy ich wzajemne połączenie oznacza kolejny wybór pomiędzy "V" a "Y". Wygląda mi więc na to, że przypisując spójniki \(\displaystyle{ \vee}\) \(\displaystyle{ \wedge}\) wyborom pomiędzy "V" a "Y" zaś nawiasy zagnieżdżeniom otrzymamy zagadnienie niełatwiejsze niż SAT. Tak mi to wygląda, ale pociąć się nie dam...