INFOMAN брой 18
{ Това са входните данни: (N; N вериги - всяка на отделен ред)
6
1 5 9 8 3 7
3 4 11 12 17
6 7 17
6 15 20 30
10 21 31
10 7
ЗАДАЧА ЗА ТУРИСТИЧЕСКАТА АГЕНЦИЯ
--------------------------------
Туристическа агенция организира N екскурзии по N различни маршрута. Всеки
маршрут представлява последователност от града, като всеки град си има но-
мер (цяло положително число) Агенцията трябва да избере няколко града в
да си направи туристическо бюро.Необходимо е агенцията да има бюро в поне
един град от всеки маршрут. За да спести пари, агенцията трябва да напра-
ви възможно най-малко бюра и същевременно всеки маршрут да минава през по-
не един град, в който има бюро. При даден текстов файл с N-те маршрута да
се напише програма която намира списък от минимален брой градове, така че
във всеки маршрут да участва поне един от тези градове. Математически ка-
зано имаме N множества. Трябва да намерим множество от минимален брой еле-
менти, такова, че то да съдържа поне един елемент от всяко едно от дадени-
те множества.
РЕШЕНИЕ:
--------
Ще използваме лаком алгоритъм, за да решим задачата. За всеки един град
намираме в колко маршрута участва - VKolko. На всяка стъпка от алгоритъма
вземаме този град Grad, който участва в най-много маршрути. За всеки един
маршрут,в който този град участва ако този маршрут все още няма свой град
представител просто намаляваме с единица стойността в масива VKolko за
всички градове от този маршрут.Така в масива VKolko винаги имаме за всеки
град в колко маршрута без туристическо бюро участва. Ако на някоя стъпка
от алгоритъма се получи да има няколко града, които участват в най-много
маршрути без база, се взема този град, който участва в най-много маршрути
изобщо (за целта се използва масива OldVKolko).Намереният на всяка стъпка
град се добавя в масива Used. Алгоритъмът се повтаря докато има маршрути
без град с туристуческо бюро. След като не остане нито един такъв маршрут
се преминава към втората фаза - оптимизация на решението. Понеже алгоритъ-
мът е лаком, той винаги взема града който участва в най-много маршрути,но
не винаги това води до правилно решение. За това се прави проверка на все-
ки един град от решението дали е нужен. Ако след премахването на град, се
окаже, че условието на задачата всеки маршрут да има поне един град с ту-
ристическо бюро е изпълнено, то този град се премахва - защото не е нужен.
За да стане по-ефективен алгоритъма, понеже номерата на градовете може да
са много големи и различни, а градовете да са много по-малко от най-голе-
мия номер, се прави преномерирване на градовете,като се запазва стария им
номер.
}
CONST MaxN = 100; {Максимален брой множества}
MaxVerigaLen = 30; {Максимален брой градове в едно множество}
MaxBroiGradove = 255; {Максимален брой градове общо}
VAR V: array[1..MaxN] of
record
Br: byte;
Gr: array[1..MaxVerigaLen] of integer;
end;
OldValue: array[1..MaxBroiGradove] of integer;
NewValue: array[1..MaxInt] of byte;
N,BrGr: integer;
Procedure ReadData;
Var F: Text;
Begin
FillChar(V,SizeOf(V),0);
Assign(F,'TURIST.PAS'); Reset(F); ReadLn(F);
ReadLn(F,N);
for N:= 1 to N do
with V[N] do
begin
while not EoLn(F) do
begin Inc(Br); Read(F,Gr[Br]); end;
ReadLn(F);
end;
Close(F);
End;
Procedure Prenomerirai;
Var g: byte;
Begin
FillChar(NewValue,SizeOf(NewValue),0);
for N:= 1 to N do with V[N] do
for g:= 1 to Br do
begin
if NewValue[Gr[g]] = 0 then
begin Inc(BrGr); OldValue[BrGr]:=Gr[g]; NewValue[Gr[g]]:=BrGr; end;
Gr[g]:=NewValue[Gr[g]];
end;
End;
Procedure Izbor;
Var VKolko,OldVKolko: array[1..MaxBroiGradove] of integer;
I,j,g,Grad,Max,MaxOld: integer;
ImaGrad,MojeDaSeMahne: boolean;
Used: array[1..MaxBroiGradove] of boolean;
BroiPredstaviteli: array[1..MaxN] of byte;
Begin
FillChar(Used,SizeOf(Used),false);
FillChar(Vkolko,SizeOf(VKolko),0);
for I:= 1 to N do with V[I] do
for g:= 1 to Br do
Inc(Vkolko[Gr[g]]);
OldVKolko:=VKolko;
{ намираме решение по Greedy алгоритъма - всеки път вземаме града, който }
repeat {е представител на максимален брой множества и актуализираме VKolko}
Max:=0; MaxOld:=0;
for I:= 1 to BrGr do
if (VKolko[I] > Max) or ((VKolko[I]=Max)and(OldVKolko[I]>MaxOld)) then
begin MaxOld:=OldVKolko[I]; Max:=VKolko[I]; Grad:=I; end;
if Max = 0 then Break;
Used[Grad]:=true;
for I:= 1 to N do with V[I] do
begin
ImaGrad:=false;
for g:= 1 to Br do
if Gr[g] = Grad then
ImaGrad:=true
else if Used[Gr[g]] then
begin ImaGrad:=false; Break; end;
if ImaGrad then
for g:= 1 to Br do
Dec(Vkolko[Gr[g]]);
end;
until false;
{ фаза на оптимизация на решението - махат се излишните градове }
for g:= 1 to BrGr do
if Used[g] then {Пробваме да махнем всеки един град g от избраните}
begin {градове Used и ако всяко множество си има представител, го}
Used[g]:=false; {махаме окончателно, защото е излишен}
FillChar(BroiPredstaviteli,SizeOf(BroiPredstaviteli),0);
for I:= 1 to N do
with V[I] do
for j:= 1 to Br do
if Used[Gr[j]] then
Inc(BroiPredstaviteli[I]);
for I:= 1 to N do
if BroiPredstaviteli[I] = 0 then
begin Used[g]:=true; Break; end;
end;
{ отпечатване на решението (масива Used) }
for I:= 1 to BrGr do
if Used[I] then
Write(OldValue[I],' ');
WriteLn;
End;
BEGIN
ReadData;
Prenomerirai;
Izbor;
END.