Pyton, 1 291 1 271 1,225 bajtów
Jak zauważył Martin, problem ten można w dużej mierze zredukować do jego doskonałego wyzwania dla gumki . Używając terminologii tego wyzwania, możemy przyjąć jako drugi zestaw gwoździ punkty przecięcia okręgów na granicy zamkniętego obszaru:
Jako gumka możemy obrać dowolną ścieżkę P między dwoma punktami końcowymi, która biegnie wewnątrz zamkniętego obszaru. Możemy następnie przywołać rozwiązanie problemu gumki, aby stworzyć (lokalnie) minimalną ścieżkę. Wyzwanie polega oczywiście na znalezieniu takiej ścieżki P , a dokładniej, znalezieniu wystarczającej liczby ścieżek, aby co najmniej jedna z nich tworzyła globalnie minimalną ścieżkę (zauważ, że w pierwszym przypadku testowym potrzebujemy co najmniej jednej ścieżki do obejmują wszystkie możliwości, aw drugim przypadku co najmniej dwa).
Naiwnym podejściem byłoby po prostu wypróbowanie wszystkich możliwych ścieżek: dla każdej sekwencji sąsiednich (tj. Przecinających się) okręgów, które łączą dwa punkty końcowe, poprowadź ścieżkę wzdłuż ich środków (gdy dwa koła się przecinają, segment między ich środkami zawsze znajduje się w obrębie ich związku .) Chociaż takie podejście jest technicznie poprawne, może prowadzić do absurdalnie dużej liczby ścieżek. Podczas gdy byłem w stanie rozwiązać pierwszy przypadek testowy przy użyciu tego podejścia w ciągu kilku sekund, drugi trwał wieczność. Mimo to możemy potraktować tę metodę jako punkt wyjścia i spróbować zminimalizować liczbę ścieżek, które musimy przetestować. Oto co następuje.
Nasze ścieżki budujemy w zasadzie, przeprowadzając najpierw głębokość wyszukiwania na wykresie okręgów. Szukamy sposobu na wyeliminowanie potencjalnych kierunków wyszukiwania na każdym etapie wyszukiwania.
Załóżmy, że w pewnym momencie jesteśmy w kręgu A , który ma dwa sąsiednie koła B i C , które również sąsiadują ze sobą. Możemy dostać się od A do C , odwiedzając B (i odwrotnie), więc możemy pomyśleć, że odwiedzanie zarówno B, jak i C bezpośrednio z A jest niepotrzebne. Niestety jest to błędne, jak pokazuje ta ilustracja:
Jeśli punkty na ilustracji są dwoma punktami końcowymi, możemy zobaczyć, że przechodząc od A do C przez B , otrzymujemy dłuższą ścieżkę.
Co powiesz na to: jeśli testujemy oba ruchy A → B i A → C , to nie jest konieczne testowanie A → B → C lub A → C → B , ponieważ nie mogą one skutkować krótszymi ścieżkami. Znowu źle:
Chodzi o to, że użycie argumentów opartych wyłącznie na przyleganiu nie ma zamiaru go wyciąć; musimy również użyć geometrii problemu. To, co łączy dwa powyższe przykłady (podobnie jak drugi przypadek testowy na większą skalę), polega na tym, że w zamkniętym obszarze znajduje się „dziura”. Przejawia się to w tym, że niektóre punkty przecięcia na granicy - nasze „gwoździe” - znajdują się w trójkącie △ ABC, którego wierzchołki są środkami okręgów:
Kiedy tak się stanie, istnieje szansa, że przejście z A do B i z A do C spowoduje różne ścieżki. Co ważniejsze, jeśli tak się nie stanie (tj. Jeśli nie będzie przerwy między A , B i C ), to gwarantuje się, że wszystkie ścieżki zaczynające się od A → B → C i A → C, które w przeciwnym razie są równoważne, będą skutkować w tym samym lokalnie minimalnej ścieżki, stąd jeśli odwiedzimy B nie trzeba również odwiedzić C bezpośrednio z A .
To prowadzi nas do naszej metody eliminacji: kiedy jesteśmy w kręgu A , trzymamy listę H sąsiednich kręgów, które odwiedziliśmy. Ta lista jest początkowo pusta. Odwiedzimy sąsiedniego okręgu B , jeśli istnieją jakieś „paznokcie” w każdym z trójkątów utworzonych przez centra A , B i każdy z kręgów H przylegających do B . Ta metoda dramatycznie obniża liczbę ścieżek, które musimy przetestować, do zaledwie 1 w pierwszym przypadku testowym i 10 w drugim.
Jeszcze kilka notatek:
Można jeszcze bardziej zmniejszyć liczbę testowanych ścieżek, ale ta metoda jest wystarczająca dla skali tego problemu.
Użyłem algorytmu od mojego rozwiązania do wyzwania gumki. Ponieważ ten algorytm ma charakter przyrostowy, można go dość łatwo zintegrować z procesem znajdowania ścieżki, aby zminimalizować ścieżkę w miarę postępów. Ponieważ wiele ścieżek ma wspólny segment początkowy, może to znacznie poprawić wydajność, gdy mamy wiele ścieżek. Może również zaszkodzić wydajności, jeśli jest znacznie więcej ślepych uliczek niż prawidłowe ścieżki. Tak czy inaczej, dla danych przypadków testowych wykonanie algorytmu dla każdej ścieżki osobno jest wystarczające.
Jest jeden przypadek krawędzi, w którym to rozwiązanie może się nie powieść: jeśli którykolwiek z punktów na granicy jest punktem przecięcia dwóch stycznych okręgów, to w pewnych warunkach wynik może być błędny. Wynika to ze sposobu działania algorytmu gumki. Z pewnymi modyfikacjami można również obsługiwać te przypadki, ale do diabła, to już wystarczająco długo.
# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
# Second test case
#I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.),((180.,230.),39.),((162.,231.),39.),((157.,281.),23.),((189.,301.),53.),((216.,308.),27.),((213.,317.),35.),((219.,362.),61.),((242.,365.),42.),((288.,374.),64.),((314.,390.),53.),((378.,377.),30.),((393.,386.),34.)}
from numpy import*
V=array;X=lambda u,v:u[0]*v[1]-u[1]*v[0];L=lambda v:dot(v,v)
e=V([511]*2)
N=set()
for c,r in I:
for C,R in I:
v=V(C)-c;d=L(v)
if d:
a=(r*r-R*R+d)/2/d;q=r*r/d-a*a
if q>=0:w=V(c)+a*v;W=V([-v[1],v[0]])*q**.5;N|={tuple(t)for t in[w+W,w-W]if all([L(t-T)>=s**2-1e-9 for T,s in I])}
N=map(V,N)
def T(a,b,c,p):H=[X(p-a,b-a),X(p-b,c-b),X(p-c,a-c)];return min(H)*max(H)>=0
def E(a,c,b):
try:d=max((X(n-a,b-a)**2,id(n),n)for n in N if T(a,b,c,n)*X(n-b,c-b)*X(n-c,a-c))[2];A=E(a,c,d);B=E(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(X(c-a,b-c))]+B[1]]
except:return[[]]*2
def P(I,c,r,A):
H=[];M=[""]
if L(c-e)>r*r:
for C,R in I:
if L(C-c)<=L(r+R)and all([L(h-C)>L(R+s)or any([T(c,C,h,p)for p in N])for h,s in H]):v=V(C);H+=[(v,R)];M=min(M,P(I-{(C,R)},v,R,A+[v]))
return M
A+=[e]*2;W=[.5]*len(A)
try:
while 1:
i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=A[i:i+5];A[i+2:i+3],W[i+2:i+3]=t,_=E(a,c,b);t=[a]+t+[b]
for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=X(q-p,c-q);y=X(q-p,t[j]-q);z=X(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
except:return[sum(L(A[i+1]-A[i])**.5for i in range(len(A)-1)),id(A),A]
print V(P(I,e*0,0,[e*0]*2)[2][1:-1])
Dane wejściowe są podawane przez zmienną Ijako zbiór krotek, w ((x, y), r)których (x, y)znajduje się środek okręgu i rjego promień. Wartości muszą być floats, inta nie s. Wynik zostanie wydrukowany do STDOUT.
Przykład
# First test case
I={((32.,42.),64.),((112.,99.),59.),((141.,171.),34.),((157.,191.),28.),((177.,187.),35.),((244.,168.),57.),((289.,119.),20.),((299.,112.),27.),((354.,59.),58.),((402.,98.),23.),((429.,96.),29.),((424.,145.),34.),((435.,146.),20.),((455.,204.),57.),((430.,283.),37.),((432.,306.),48.),((445.,349.),52.),((424.,409.),59.),((507.,468.),64.)}
[[ 0. 0. ]
[ 154.58723733 139.8329183 ]
[ 169.69950891 152.76985495]
[ 188.7391093 154.02738541]
[ 325.90536774 109.74141936]
[ 382.19108518 109.68789517]
[ 400.00362897 120.91319495]
[ 511. 511. ]]
