Łączenie punktów + najkrótsza droga

[Dasio11]

Inkwizytor, ten rysunek to nie był sposób rozwiązania, tylko argument dla monomiana, że dodanie węzła czasami skróci drogę, a nie wydłuży.
xiikzodz, czy to, że problem jest NP-trudny oznacza, że nie istnieje na to algorytm ogólny?

[xiikzodz]

Problemy NP-trudne póki co nie mają algorytmów wielomianowych. Przy czym ten problem może być gorszy niż SAT. Mam coś w rodzaju argumentu, że SAT jest niełatwiejszy.

W praktyce oznacza to, że rozwiązanie tego problemu wymaga (póki co) wykładniczego (lub jeszcze gorzej), czyli nawet przy kilkunastu węzłach program się może nie skończyć w sensownym czasie.

Rozwiązanie numeryczne (siatka sześciokątów + graf pełny + drzewo minimalne) jest stuprocentowo dobre o ile dopuścimy jakiś mały błąd. Może się np. okazać, że minimalna łączna długość wynosi powiedzmy 100, zaś ten algorytm da wynik 100,001 i w ogólności nie ma nawet powodu, żeby otrzymane w ten sposób drzewo było podobne do minimalnego (które wiadomo, że istnieje). Dokładność ustalamy sami i może być dowolnie dobra kosztem sześciennego wzrostu działania programu, co jest akceptowalne. Przyczyna jest prosta. Przy 50 punktach i algorytmie wykładniczym, mamy koszt czasowy rzędu \(\displaystyle{ 2^{50}\simeq 10^{120}}\), zaś dodając nawet milion węzłów wynikających z pokrycia sześciokątami otrzymujemy złożoność rzędu \(\displaystyle{ (10^6)^3=10^{18}}\), czyli liczbę w zasięgu komputerów.

[Dasio11]

Nie rozumiem tej metody sześciokątów, możesz wytłumaczyć?
I co oznacza zapis \(\displaystyle{ 2^{50} \simeq 10^{120}}\)?
Dokładność oczywiście nie musi być duża, byle rozsądna.

[xiikzodz]

Mój błąd. Ta metoda z sześciokątami daje jedynie redukcję do problemu NP-zupełnego. To znaczy oryginalne zagadnienie jest NP-zupełne, o ile dopuścimy jakiś ustalony błąd (bez tego trudno w ogóle mówić o złożoności). Opiszę, o co mi chodzi:

Powiedzmy, że chcemy połączyć trzy punkty:

\(\displaystyle{ \psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(0.64,1.54)(5.84,4.98)
\psdots[linecolor=blue](1.42,2.78)
\psdots[linecolor=blue](4,2)
\psdots[linecolor=blue](4.98,4.56)
\end{pspicture*}}\)

Dorysowujemy sześciokąty, im mniejsze, tym będzie dokładniej:

\(\displaystyle{ \newrgbcolor{zzttqq}{0.6 0.2 0}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(0.86,1.16)(6.04,5.36)
\psline[linecolor=zzttqq](1.24,2.98)(1.26,2.48)
\psline[linecolor=zzttqq](1.26,2.48)(1.7,2.25)
\psline[linecolor=zzttqq](1.7,2.25)(2.13,2.51)
\psline[linecolor=zzttqq](2.13,2.51)(2.11,3.01)
\psline[linecolor=zzttqq](2.11,3.01)(1.66,3.25)
\psline[linecolor=zzttqq](1.66,3.25)(1.24,2.98)
\psline[linecolor=zzttqq](2.97,3.05)(2.99,2.55)
\psline[linecolor=zzttqq](2.99,2.55)(2.57,2.28)
\psline[linecolor=zzttqq](2.57,2.28)(2.13,2.51)
\psline[linecolor=zzttqq](2.13,2.51)(2.11,3.01)
\psline[linecolor=zzttqq](2.11,3.01)(2.53,3.28)
\psline[linecolor=zzttqq](2.53,3.28)(2.97,3.05)
\psline[linecolor=zzttqq](3.44,2.32)(2.99,2.55)
\psline[linecolor=zzttqq](2.99,2.55)(2.57,2.28)
\psline[linecolor=zzttqq](2.57,2.28)(2.59,1.78)
\psline[linecolor=zzttqq](2.59,1.78)(3.03,1.55)
\psline[linecolor=zzttqq](3.03,1.55)(3.46,1.82)
\psline[linecolor=zzttqq](3.46,1.82)(3.44,2.32)
\psline[linecolor=zzttqq](3.44,2.32)(3.86,2.58)
\psline[linecolor=zzttqq](3.86,2.58)(4.3,2.35)
\psline[linecolor=zzttqq](4.3,2.35)(4.32,1.85)
\psline[linecolor=zzttqq](4.32,1.85)(3.9,1.58)
\psline[linecolor=zzttqq](3.9,1.58)(3.46,1.82)
\psline[linecolor=zzttqq](3.46,1.82)(3.44,2.32)
\psline[linecolor=zzttqq](3.84,3.08)(3.86,2.58)
\psline[linecolor=zzttqq](3.86,2.58)(4.3,2.35)
\psline[linecolor=zzttqq](4.3,2.35)(4.72,2.62)
\psline[linecolor=zzttqq](4.72,2.62)(4.7,3.12)
\psline[linecolor=zzttqq](4.7,3.12)(4.26,3.35)
\psline[linecolor=zzttqq](4.26,3.35)(3.84,3.08)
\psline[linecolor=zzttqq](4.24,3.85)(4.66,4.12)
\psline[linecolor=zzttqq](4.66,4.12)(5.11,3.89)
\psline[linecolor=zzttqq](5.11,3.89)(5.13,3.39)
\psline[linecolor=zzttqq](5.13,3.39)(4.7,3.12)
\psline[linecolor=zzttqq](4.7,3.12)(4.26,3.35)
\psline[linecolor=zzttqq](4.26,3.35)(4.24,3.85)
\psline[linecolor=zzttqq](4.64,4.62)(4.66,4.12)
\psline[linecolor=zzttqq](4.66,4.12)(5.11,3.89)
\psline[linecolor=zzttqq](5.11,3.89)(5.53,4.15)
\psline[linecolor=zzttqq](5.53,4.15)(5.51,4.65)
\psline[linecolor=zzttqq](5.51,4.65)(5.07,4.89)
\psline[linecolor=zzttqq](5.07,4.89)(4.64,4.62)
\psline[linecolor=zzttqq](4.64,4.62)(4.66,4.12)
\psline[linecolor=zzttqq](4.66,4.12)(4.24,3.85)
\psline[linecolor=zzttqq](4.24,3.85)(3.8,4.08)
\psline[linecolor=zzttqq](3.8,4.08)(3.78,4.58)
\psline[linecolor=zzttqq](3.78,4.58)(4.2,4.85)
\psline[linecolor=zzttqq](4.2,4.85)(4.64,4.62)
\psline[linecolor=zzttqq](3.84,3.08)(4.26,3.35)
\psline[linecolor=zzttqq](4.26,3.35)(4.24,3.85)
\psline[linecolor=zzttqq](4.24,3.85)(3.8,4.08)
\psline[linecolor=zzttqq](3.8,4.08)(3.38,3.82)
\psline[linecolor=zzttqq](3.38,3.82)(3.4,3.32)
\psline[linecolor=zzttqq](3.4,3.32)(3.84,3.08)
\psline[linecolor=zzttqq](3.84,3.08)(3.86,2.58)
\psline[linecolor=zzttqq](3.86,2.58)(3.44,2.32)
\psline[linecolor=zzttqq](3.44,2.32)(2.99,2.55)
\psline[linecolor=zzttqq](2.99,2.55)(2.97,3.05)
\psline[linecolor=zzttqq](2.97,3.05)(3.4,3.32)
\psline[linecolor=zzttqq](3.4,3.32)(3.84,3.08)
\psline[linecolor=zzttqq](2.97,3.05)(2.53,3.28)
\psline[linecolor=zzttqq](2.53,3.28)(2.51,3.78)
\psline[linecolor=zzttqq](2.51,3.78)(2.93,4.05)
\psline[linecolor=zzttqq](2.93,4.05)(3.38,3.82)
\psline[linecolor=zzttqq](3.38,3.82)(3.4,3.32)
\psline[linecolor=zzttqq](3.4,3.32)(2.97,3.05)
\psline[linecolor=zzttqq](3.78,4.58)(3.34,4.82)
\psline[linecolor=zzttqq](3.34,4.82)(2.91,4.55)
\psline[linecolor=zzttqq](2.91,4.55)(2.93,4.05)
\psline[linecolor=zzttqq](2.93,4.05)(3.38,3.82)
\psline[linecolor=zzttqq](3.38,3.82)(3.8,4.08)
\psline[linecolor=zzttqq](3.8,4.08)(3.78,4.58)
\psline[linecolor=zzttqq](2.11,3.01)(2.53,3.28)
\psline[linecolor=zzttqq](2.53,3.28)(2.51,3.78)
\psline[linecolor=zzttqq](2.51,3.78)(2.07,4.01)
\psline[linecolor=zzttqq](2.07,4.01)(1.64,3.75)
\psline[linecolor=zzttqq](1.64,3.75)(1.66,3.25)
\psline[linecolor=zzttqq](1.66,3.25)(2.11,3.01)
\psline[linecolor=zzttqq](2.17,1.51)(1.72,1.75)
\psline[linecolor=zzttqq](1.72,1.75)(1.7,2.25)
\psline[linecolor=zzttqq](1.7,2.25)(2.13,2.51)
\psline[linecolor=zzttqq](2.13,2.51)(2.57,2.28)
\psline[linecolor=zzttqq](2.57,2.28)(2.59,1.78)
\psline[linecolor=zzttqq](2.59,1.78)(2.17,1.51)
\psdots[linecolor=blue](1.42,2.78)
\psdots[linecolor=blue](4,2)
\psdots[linecolor=blue](4.98,4.56)
\end{pspicture*}}\)

Zamiast łączyć te trzy punkty z dorysowywaniem węzłów, traktujemy (np.) środki tych sześciokątów jako punkty

\(\displaystyle{ \newrgbcolor{ccccff}{0.8 0.8 1}
\newrgbcolor{zzttqq}{0.6 0.2 0}
\newrgbcolor{ffqqtt}{1 0 0.2}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-4.3,-4.46)(8.48,6.3)
\psline[linecolor=zzttqq](1.24,2.98)(1.26,2.48)
\psline[linecolor=zzttqq](1.26,2.48)(1.7,2.25)
\psline[linecolor=zzttqq](1.7,2.25)(2.13,2.51)
\psline[linecolor=zzttqq](2.13,2.51)(2.11,3.01)
\psline[linecolor=zzttqq](2.11,3.01)(1.66,3.25)
\psline[linecolor=zzttqq](1.66,3.25)(1.24,2.98)
\psline[linecolor=zzttqq](2.97,3.05)(2.99,2.55)
\psline[linecolor=zzttqq](2.99,2.55)(2.57,2.28)
\psline[linecolor=zzttqq](2.57,2.28)(2.13,2.51)
\psline[linecolor=zzttqq](2.13,2.51)(2.11,3.01)
\psline[linecolor=zzttqq](2.11,3.01)(2.53,3.28)
\psline[linecolor=zzttqq](2.53,3.28)(2.97,3.05)
\psline[linecolor=zzttqq](3.44,2.32)(2.99,2.55)
\psline[linecolor=zzttqq](2.99,2.55)(2.57,2.28)
\psline[linecolor=zzttqq](2.57,2.28)(2.59,1.78)
\psline[linecolor=zzttqq](2.59,1.78)(3.03,1.55)
\psline[linecolor=zzttqq](3.03,1.55)(3.46,1.82)
\psline[linecolor=zzttqq](3.46,1.82)(3.44,2.32)
\psline[linecolor=zzttqq](3.44,2.32)(3.86,2.58)
\psline[linecolor=zzttqq](3.86,2.58)(4.3,2.35)
\psline[linecolor=zzttqq](4.3,2.35)(4.32,1.85)
\psline[linecolor=zzttqq](4.32,1.85)(3.9,1.58)
\psline[linecolor=zzttqq](3.9,1.58)(3.46,1.82)
\psline[linecolor=zzttqq](3.46,1.82)(3.44,2.32)
\psline[linecolor=zzttqq](3.84,3.08)(3.86,2.58)
\psline[linecolor=zzttqq](3.86,2.58)(4.3,2.35)
\psline[linecolor=zzttqq](4.3,2.35)(4.72,2.62)
\psline[linecolor=zzttqq](4.72,2.62)(4.7,3.12)
\psline[linecolor=zzttqq](4.7,3.12)(4.26,3.35)
\psline[linecolor=zzttqq](4.26,3.35)(3.84,3.08)
\psline[linecolor=zzttqq](4.24,3.85)(4.66,4.12)
\psline[linecolor=zzttqq](4.66,4.12)(5.11,3.89)
\psline[linecolor=zzttqq](5.11,3.89)(5.13,3.39)
\psline[linecolor=zzttqq](5.13,3.39)(4.7,3.12)
\psline[linecolor=zzttqq](4.7,3.12)(4.26,3.35)
\psline[linecolor=zzttqq](4.26,3.35)(4.24,3.85)
\psline[linecolor=zzttqq](4.64,4.62)(4.66,4.12)
\psline[linecolor=zzttqq](4.66,4.12)(5.11,3.89)
\psline[linecolor=zzttqq](5.11,3.89)(5.53,4.15)
\psline[linecolor=zzttqq](5.53,4.15)(5.51,4.65)
\psline[linecolor=zzttqq](5.51,4.65)(5.07,4.89)
\psline[linecolor=zzttqq](5.07,4.89)(4.64,4.62)
\psline[linecolor=zzttqq](4.64,4.62)(4.66,4.12)
\psline[linecolor=zzttqq](4.66,4.12)(4.24,3.85)
\psline[linecolor=zzttqq](4.24,3.85)(3.8,4.08)
\psline[linecolor=zzttqq](3.8,4.08)(3.78,4.58)
\psline[linecolor=zzttqq](3.78,4.58)(4.2,4.85)
\psline[linecolor=zzttqq](4.2,4.85)(4.64,4.62)
\psline[linecolor=zzttqq](3.84,3.08)(4.26,3.35)
\psline[linecolor=zzttqq](4.26,3.35)(4.24,3.85)
\psline[linecolor=zzttqq](4.24,3.85)(3.8,4.08)
\psline[linecolor=zzttqq](3.8,4.08)(3.38,3.82)
\psline[linecolor=zzttqq](3.38,3.82)(3.4,3.32)
\psline[linecolor=zzttqq](3.4,3.32)(3.84,3.08)
\psline[linecolor=zzttqq](3.84,3.08)(3.86,2.58)
\psline[linecolor=zzttqq](3.86,2.58)(3.44,2.32)
\psline[linecolor=zzttqq](3.44,2.32)(2.99,2.55)
\psline[linecolor=zzttqq](2.99,2.55)(2.97,3.05)
\psline[linecolor=zzttqq](2.97,3.05)(3.4,3.32)
\psline[linecolor=zzttqq](3.4,3.32)(3.84,3.08)
\psline[linecolor=zzttqq](2.97,3.05)(2.53,3.28)
\psline[linecolor=zzttqq](2.53,3.28)(2.51,3.78)
\psline[linecolor=zzttqq](2.51,3.78)(2.93,4.05)
\psline[linecolor=zzttqq](2.93,4.05)(3.38,3.82)
\psline[linecolor=zzttqq](3.38,3.82)(3.4,3.32)
\psline[linecolor=zzttqq](3.4,3.32)(2.97,3.05)
\psline[linecolor=zzttqq](3.78,4.58)(3.34,4.82)
\psline[linecolor=zzttqq](3.34,4.82)(2.91,4.55)
\psline[linecolor=zzttqq](2.91,4.55)(2.93,4.05)
\psline[linecolor=zzttqq](2.93,4.05)(3.38,3.82)
\psline[linecolor=zzttqq](3.38,3.82)(3.8,4.08)
\psline[linecolor=zzttqq](3.8,4.08)(3.78,4.58)
\psline[linecolor=zzttqq](2.11,3.01)(2.53,3.28)
\psline[linecolor=zzttqq](2.53,3.28)(2.51,3.78)
\psline[linecolor=zzttqq](2.51,3.78)(2.07,4.01)
\psline[linecolor=zzttqq](2.07,4.01)(1.64,3.75)
\psline[linecolor=zzttqq](1.64,3.75)(1.66,3.25)
\psline[linecolor=zzttqq](1.66,3.25)(2.11,3.01)
\psline[linecolor=zzttqq](2.17,1.51)(1.72,1.75)
\psline[linecolor=zzttqq](1.72,1.75)(1.7,2.25)
\psline[linecolor=zzttqq](1.7,2.25)(2.13,2.51)
\psline[linecolor=zzttqq](2.13,2.51)(2.57,2.28)
\psline[linecolor=zzttqq](2.57,2.28)(2.59,1.78)
\psline[linecolor=zzttqq](2.59,1.78)(2.17,1.51)
\psdots[linecolor=ccccff](1.42,2.78)
\psdots[linecolor=ccccff](4,2)
\psdots[linecolor=ccccff](4.98,4.56)
\psdots[linecolor=ffqqtt](1.68,2.75)
\psdots[linecolor=ffqqtt](2.15,2.01)
\psdots[linecolor=ffqqtt](2.09,3.51)
\psdots[linecolor=ffqqtt](2.55,2.78)
\psdots[linecolor=ffqqtt](3.01,2.05)
\psdots[linecolor=ffqqtt](2.95,3.55)
\psdots[linecolor=ffqqtt](3.42,2.82)
\psdots[linecolor=ffqqtt](3.88,2.08)
\psdots[linecolor=ffqqtt](3.36,4.32)
\psdots[linecolor=ffqqtt](3.82,3.58)
\psdots[linecolor=ffqqtt](4.28,2.85)
\psdots[linecolor=ffqqtt](4.22,4.35)
\psdots[linecolor=ffqqtt](4.68,3.62)
\psdots[linecolor=ffqqtt](5.09,4.39)
\end{pspicture*}}\)

Pozostaje znaleźć mninimalne drzewo zawierające sześciokąty, w których leżały wyjściowe punkty w grafie pełnym rozpiętym na środkach tych sześciokątów, czyli o wierzchołkach w punktach poniżej:

\(\displaystyle{ \newrgbcolor{qqwwqq}{0 0.4 0}
\newrgbcolor{ffqqtt}{1 0 0.2}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-4.3,-4.46)(8.48,6.3)
\psdots[linecolor=qqwwqq](1.68,2.75)
\psdots[linecolor=ffqqtt](2.15,2.01)
\psdots[linecolor=ffqqtt](2.09,3.51)
\psdots[linecolor=ffqqtt](2.55,2.78)
\psdots[linecolor=ffqqtt](3.01,2.05)
\psdots[linecolor=ffqqtt](2.95,3.55)
\psdots[linecolor=ffqqtt](3.42,2.82)
\psdots[linecolor=qqwwqq](3.88,2.08)
\psdots[linecolor=ffqqtt](3.36,4.32)
\psdots[linecolor=ffqqtt](3.82,3.58)
\psdots[linecolor=ffqqtt](4.28,2.85)
\psdots[linecolor=ffqqtt](4.22,4.35)
\psdots[linecolor=ffqqtt](4.68,3.62)
\psdots[linecolor=qqwwqq](5.09,4.39)
\end{pspicture*}}\)

czyli np. coś takiego:

\(\displaystyle{ \newrgbcolor{qqwwqq}{0 0.4 0}
\newrgbcolor{ffqqtt}{1 0 0.2}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dotstyle=*,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-4.3,-4.46)(8.48,6.3)
\psline(1.68,2.75)(3.42,2.82)
\psline(3.42,2.82)(5.09,4.39)
\psline(3.42,2.82)(3.88,2.08)
\psdots[linecolor=qqwwqq](1.68,2.75)
\psdots[linecolor=ffqqtt](2.15,2.01)
\psdots[linecolor=ffqqtt](2.09,3.51)
\psdots[linecolor=ffqqtt](2.55,2.78)
\psdots[linecolor=ffqqtt](3.01,2.05)
\psdots[linecolor=ffqqtt](2.95,3.55)
\psdots[linecolor=ffqqtt](3.42,2.82)
\psdots[linecolor=qqwwqq](3.88,2.08)
\psdots[linecolor=ffqqtt](3.36,4.32)
\psdots[linecolor=ffqqtt](3.82,3.58)
\psdots[linecolor=ffqqtt](4.28,2.85)
\psdots[linecolor=ffqqtt](4.22,4.35)
\psdots[linecolor=ffqqtt](4.68,3.62)
\psdots[linecolor=qqwwqq](5.09,4.39)
\end{pspicture*}}\)

Niestety, w odróżnieniu od zagadnienia szukania minimalnego drzewa (MST) rozpinającego całego grafu, w którym to przypadku działa metoda zachłanna, problem minimalnego drzewa zawierającego podzbiór wierzchołków (zwany Steiner MST) jest NP-zupełny. Pożytek z pomysłu z sześciokątami jest więc tylko taki, że wiemy, że oryginalny problem jest NP-zupełny i argument jest prostszy od tego mojego redukowania do SAT.

Podsumowując, zgodnie z aktualnym stanem wiedzy i intuicji na temat "P=NP"nie da się wymyślić nic istotnie lepszego od systematycznego przejścia przez wszystkie możliwe położenia dodanych węzłów.