INFOMAN брой 17
{ This is the input data: N, M; weight[1..N]; v1, v2, dist_v1_v2 :
12 16
7 9 5 1 1 2 4 2 5 3 8 8
1 2 17
1 4 4
1 9 3
1 12 9
2 6 20
2 4 1
3 6 4
3 7 9
4 6 1
4 7 11
4 8 3
5 9 8
7 8 5
8 12 2
9 11 6
10 12 5
--------------------
4 НАЙ-БЛИЗКИ ВЪРХА
--------------------
Даден е неориентиран граф с тегла по ребрата и по върховете. Път между
два върха в графа наричаме последователност от върхове,започваща в началния
връх и завършваща в крайния. Дължина на път наричаме сумата от дължините на
съставящите го ребра и тежестите на междинните върхове.Разстояние между два
върха наричаме дължината на най-късия път между тях. Да се намерят 4-те най-
близки един до друг върха на графа. Под най-близки разбираме 4-те върха, за
които сумата от 6-те разстояния между тях е минимална. Гарантира се че има
път между всеки два върха, т.е. графът е свързан. Входът е описан като две
числа N и M - брой върхове и брой ребра, N числа - тежести по върховете и M
тройки числа описващи ребрата във вид начало, край, дължина.
РЕШЕНИЕ: Първо трябва да намерим разстоянията между всеки два върха на
графа. Използваме класическия алгоритъм на Флойд. Нека G[1..N,1..N] е матри-
цата на графа, т.е. за всяко ребро (v1,v2,len) G[v1,v2]=len и G[i,i]=0 и не-
ка G[i,j]=безкрайност ако няма ребро между върховете i, j. Трябва да отбеле-
жим, че алгоритъмът на Флойд, понеже се основава на последователни подобре-
ния в матрицата на разстоянията, трябва малко да се измени, за да работи в
граф с тежести по върховете. Понеже на всяка итерация подобравяме пътя меж-
ду два върха v1 и v2 през някой друг връх t, то ако пътя от v1 до v2 през t
е по-къс от намеряния за момента най-къс път между v1 и v2 точно когато:
G[v1,t]+W[t]+G[t,v2] > G[v1,v2].
Това ни дава основание д ареализираме алгоритъма на Флойд по следния начин:
for t = 1 ... N
for v1 = 1 ... N
for v2 = 1 ... N
if G[v1,v2] = min ( G[v1,v2], G[v1,t]+W[t]+G[t,v2] )
Сложността на алгоритъма е от порядъка на N*N*N.
Втората част от задачата е по-трудна ако трябва да я направим доволно
бърза. Един очевиден алгоритъм е пълното изчерпване на всички четворки вър-
хове:
MinR = безкрайност
for v1 = 1 ... N
for v2 = 1 ... N
for v3 = 1 ... N
for v4 = 1 ... N
MinR = min ( MinR,
G[v1,v2]+G[v1,v3]+G[v1,v4]+G[v2,v3]+G[v2,v4]+G[v3,v4] )
Проблемът обаче е, че този алгоритъм е много бавен (от порядъка на N*N*N*N).
Как бихме могли да го ускорим. Да поразсъждаваме логично Щом търсим четири-
те най-близки върха, то винаги болшинството от върховете ще е много далеко
от тази четворка. Ето защо не е необходимо да правим пълно изчерпване, а мо-
жем да правим пълно изчерпване в рамките на една достатъчно голяма околност
на всеки връх. И за да сме сигурни, че няма да изтървем решението, най-лес-
но можем да ускорим алгоритъма така. Въртим първия цикъл и втория в него и
преди да започнем третия, проверяваме дали текущата сума не е надвишила ми-
нималната за момента. Ако е така, няма смисъл да търсим по-нататък. Идеята
е във всеки момент от бавния посочен по-горе алгоритъм с четирите цикъла да
следим текущата сума и ако тя надвиши минималната за момента, да продължава-
ме съответния цикъл от следващия връх, т.е.да прескачаме проверката на всич-
ки четворки върхове, за които предварително знаем, че не са подходящи.
Ще посоча и още 3 алгоритъма, които не винаги дават верния резултат, но
работят достатъчно бързо - GREEDY алгоритми. Първият от тях е следният: За
всеки връх взимаме 3-те върха, които са най-близко до него и проверяваме по-
лучената четворка върхове дали не е по-добра от текущата. Този алгоритъм ра-
боти в повечето случаи, но не винаги. Той е по-бърз, защото проверява само
N четворки числа вместо всичките N!*(N-4)!/4!. Друг по идея алчен алгоритъм
се основава на следните разсъждения. Ако имаме N върха, то програмата ни ще
е работи бавно при N > 100 и ще е достатъчно бърза при N <= 100.Идеята е да
премахнем някои от върховете на графа, които не могат да участват в решение-
то. Как обаче да ги разпознаем. Ако един връх е много далек от всички други
върхове, то той, с които и други 3 върха да се комбинира, няма да се получи
добра четворка. Ето защо можем да премахнем върховете, за които най-близкия
връх е най-далеко. Като премахнем по този критерий толкова върхове,че да ос-
танат най-много 100, можем да пуснам бавния алгоритъм и да намерим решение.
Тестовете показват, че този алгоритъм дава по-лошо приближение до верния ре-
зултат отколкото предния (с 3-те най-близки върха). Ето защо предлагаме още
един алчен алгоритъм за тази задача. Взимаме връх. Взимаме 10-те върха кои-
то са най-близки до него (сортираме N-те върха по разстояния от въпросния и
взимаме 10-те, които застават на първите 10 позиции). Измежду избрания връх
и 10-те му най-близки генерираме всички четворки и проверяваме всяка от тях.
Скоростта е задоволителна (по-голяма от скоростта на Флойд-а за голямо N) и
резултатите са почти верни, но не съвсем. Все пак този алгоритъм е алчна ап-
роксимация.
Да се върнем на нашия алгоритъм с пълното изчерпване с граница. Понеже
ни трябва граница, т.е. възможно най-малко число, за което има решение, най-
добре е да пуснем първо един алчен алгоритъм, например този с 3-те най-близ-
ки върха (понеже се пише най-лесно) и да получим едно добро приближение на
оптималното решение. Когато вече имаме една ниска горна граница, пълното из-
черпване ще върви много добре, защото ще отрязва безперспективните двойки и
тройки върхове, ако сумата им надвишава границата, без да се генерират чет-
ворките върхове съдържащи безперспективан двойка или тройка. Хубавото е че
за разлика от алчните алгоритми,този с границата гарантира, че решението ко-
ето намира е правилно, а освен това го намира в средния случай за много мал-
ко време (обикновено по-малко отколкото за алгоритъма на Флойд, който е не-
изибежен). Да разгледаме още един случай. Нека всички ребра на графа имат
дължини между 100 и 150, а решението е 700. Тогава нашата граница няма да
подобри съществено скоростта, понеже като вземем 2 върха, почти никога няма
частичната да я надвиши. Ако вземем три върха, частичната сума отново няма
е достатъчно голяма, че да отрежем безперспективната тройка.Ето защо трябва
да изчислим границата по-точно. Първо да дефинираме ясно какво наричаме гра-
ниаца. Граница на 2 върха ще наричаме най-малката сума, която може да се по-
лучи в най-идеалния случай ако допълним 2-та върха до 4 върха. Граница на 3
върха аналогично е най-малката сума, която може да се получи, като допълним
тези 3 върха до 4, т.е. най-оптимистичната прогноза за сумата която ще полу-
чим като включим в решението избраните 3 върха. Понеже в нашия граф всички
върхове са със стойности между 100 и 150, то спокойно можем да кажем,че гра-
ницата на върховете v1 и v2 е най-малко G[v1,v2] + 5*100, защото решението
се състои от сумата на 6 ребра, всяко от които е на по-късо от 100,а едното
от тях е дълго G[v1,v2]. Аналогично границата на върховете v1, v2 и v3 вина-
ги е по-голяма или равна на G[v1,v2]+G[v1,v3]+G[v2,v3]+3*100.Тези две грани-
ци са значително по-ниски и по-близки до реалната стойност и затова са мно-
гократно по-ефективни. Всеобщ принцип в изчерпващите алгоритми с граници е
че колкото по-точна е границата, толкова по-малко варианти се изчерпват. То-
ва разбира се води до значително ускорение, стига изчисляването на по-точна-
та границата да не отнема прекалено много време. В нашия случай ще означим
с T[1..6] дължините на 6-те най-къси ребра в матрицата на разстоянията.Тога-
ва можем да дадем точна граница,при това без да допускаме нищо за дължините
на ребрата. За два върха тя е G[v1,v2]+T[1]+T[2]+T[3]+T[4]+T[5], а за 3 вър-
ха е G[v1,v2]+G[v1,v3]+G[v2,v3]+T[1]+T[2]+T[3].Разбира се сумите T[1]..T[5]
и T[1]..T[3] са константи по време на изпълняване на алгоритъма и могат да
се изчислят предварително. С новите граници изчерпващият алгоритъм наистина
е достатъчно бърз и решава правилно задачата.
22.03.2000
Светлин Наков
(автор на задачата)
}
{$R-,Q-,S-}
CONST InFileName = '4VURHA.PAS';
OutFileName = '';
MaxN = 175;
EndLess = 30000;
TYPE TGraph = array[1..MaxN,1..MaxN] of word;
VAR G: TGraph; { The distance matrix of the graph }
N,M: integer;
W: array[1..MaxN] of byte;
BestSum: longint;
Procedure ReadData; { Read the input data - N, M, W[1..N], G[1..N,1..N] }
Var F: Text;
v1,v2,r: integer;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,N,M);
for v1:=1 to N do
for v2:=1 to N do
if v1=v2 then G[v1,v2]:=0
else G[v1,v2]:=EndLess;
for N:= 1 to N do
Read(F,W[N]);
for M:= 1 to M do
begin
ReadLn(F,v1,v2,r);
G[v1,v2]:=r; G[v2,v1]:=r;
end;
Close(F);
End;
Procedure Floyd; { Apply Floyd's algorithm to find distances in G[][] }
Var t,v1,v2: integer;
Begin
for t:= 1 to N do
for v1:=1 to N do
for v2:= 1 to N do
if G[v1,t]+W[t]+G[t,v2] < G[v1,v2] then
G[v1,v2] := G[v1,t]+W[t]+G[t,v2];
End;
Procedure Approximate4Nearest; { Greedy approximation of BestSum }
Type TR = record v,d:word; end;
Var R: array[1..MaxN] of TR;
v,i,v1,v2,v3,v4: integer;
Sum: longint;
Procedure SortR;
Var i,j,Min: integer;
Tmp: TR;
Begin
for i:= 1 to N-1 do
begin
Min:=i;
for j:= i+1 to N do
if R[j].d < R[Min].d then
Min:=j;
Tmp:=R[i]; R[i]:=R[Min]; R[Min]:=Tmp;
end;
End;
Begin
BestSum:=MaxLongInt;
for v:= 1 to N do
begin
for i:=1 to N do
begin R[i].v:=i; R[i].d:=G[v,i]; end;
SortR;
v1:=v; v2:=R[2].v; v3:=R[3].v; v4:=R[4].v;
Sum:=G[v1,v2]+G[v1,v3]+G[v1,v4]+G[v2,v3]+G[v2,v4]+G[v3,v4];
if Sum < BestSum then
BestSum:=Sum;
end;
End;
Procedure Find4Nearest; { The fast algorithm with the bounds }
Var T: array[1..MaxN] of integer;
Procedure FindMin6Dist;
Var D: ^TGraph;
i,v1,v2,bestv1,bestv2: integer;
Begin
New(D); D^:=G;
for i:= 1 to 6 do
begin
bestv1:=1; bestv2:=2;
for v1:= 1 to N do
for v2:= v1+1 to N do
if D^[v1,v2] < D^[bestv1,bestv2] then
begin bestv1:=v1; bestv2:=v2; end;
T[i]:=D^[bestv1,bestv2];
D^[bestv1,bestv2]:=MaxInt;
end;
for i:= 2 to 6 do
T[i]:=T[i]+T[i-1];
Dispose(D);
End;
Var Sum1,Sum2,Sum3,Sum4,T3,T5: longint;
v1,v2,v3,v4: integer;
Begin
FindMin6Dist; T5:=T[5]; T3:=T[3];
for v1:= 1 to N do
begin
Sum1:=0;
for v2:= v1+1 to N do
begin
Sum2:=Sum1+G[v1,v2];
if Sum2 + T5 < BestSum then
for v3:= v2+1 to N do
begin
Sum3:=Sum2+G[v1,v3]+G[v2,v3];
if Sum3 + T3 < BestSum then
for v4:= v3+1 to N do
begin
Sum4:=Sum3+G[v1,v4]+G[v2,v4]+G[v3,v4];
if Sum4 < BestSum then
BestSum:=Sum4;
end;
end;
end;
end;
End;
Procedure PrintSolution; { Print the found solution - BestSum }
Var OutF: Text;
Begin
Assign(OutF,OutFileName); Rewrite(OutF);
WriteLn(OutF,BestSum);
Close(OutF);
End;
BEGIN
ReadData;
Floyd;
Approximate4Nearest;
Find4Nearest;
PrintSolution;
END.