Некоторое время сомневался, где разместить этот материал — в техническом или методическом разделах. Потом все-таки решил размесить его здесь — любое моделирование увеличивает меру понимания тех или иных технико-тактических действий, а значит их управляемость, что в конечном счете ведет к улучшению качества и росту спортивных результатов. Этой статье 12 лет!

 

Самарский областной центр технического творчества учащихся

Самарская городская общественная организация Детско-молодежный спортивно-технический клуб «Контур»

Моделирование процесса принятия решения об оптимальном варианте поиска передатчиков в соревнованиях по спортивной радиопеленгации.

Творческое задание для учащихся 4–5 годов обучения по направлению «Радиоспорт»

   

 

Дистанция в спортивной радиопеленгации состоит из 7 объектов:

 

 

 

Количество вариантов поиска, в случае, если поиск начинается со старта и заканчивается на финише соответствует числу перестановок для 5 объектов, т. е. 5! = 120;

Если координаты всех лис известны заранее, можно определить длины дистанций для всех 120 возможных вариантов поиска и определить минимальную.

Расстояния между объектами дистанции рассчитываются по формуле, вытекающей из теоремы Пифагора:

R²=(X_к-X_н)²+(Y_к-Y_н)²

Где X и Y координаты начального и конечного объекта отрезка дистанции.

Складывая полученные отрезки, можно получить длину дистанции.

Ниже приведен фрагмент программы LipWin – тренажера по «Охоте на «лис»», где рассчитывается оптимальный вариант путем полного перебора.

 

  

type         TVariantDistance = array[1..120] of Integer;

                TVariant = array[1..5] of Integer;

                TFoxStack = array[1..5] of TPoint;

Var                  Start: TPoint;

                               Finish: TPoint;

                               Foxs: TFoxStack;

                function DistanceP (One,Two:TPoint):LongInt;

Begin

{проверим на совпадение}

                if (One.X=Two.X)and (One.Y=Two.Y) then

                                DistanceP:= 0

                else

                                DistanceP:= Round (SQRT (SQR (One.X-Two.X)+SQR (One.Y-Two.Y)));

End;{Distance}

procedure VariantCount;

var

                varD                                       :              TVariantDistance;

                VVar        :              array[1..120] of TVariant;

                i,j,count,k: integer;

                P: TVariant;

                TmpDist,MinNum: Integer;

                Hour,Min,Sec,MSec: Word;

                StrToAdd: String;

  Ac: POneAct;

  R: LongInt; {пройденный путь в пикселах}

  TempPoint: TPoint;

  AvSpeed: real;

                procedure Change (var i,j: Integer);

                               var n: Integer;

                begin

                               n:= i;

                               i:= j;

                               j:= n;

                end;

                procedure Reverse (m: integer);

                {обращает последовательность длиной m задом наперед}

                               var i,j: integer;

                begin

                               i:= 1;

                               j:= m;

                               while i<j do

                               begin

                                               Change (P[i],P[j]);

                                               i:= i + 1;

                                               j:= j — 1;

                               end;

                end;

                {Внимание, рекурсия!!

Эта процедура генерирует перестановки для 5!}

                procedure Generate (m: integer);

                               var i: Integer;

                begin

                               if m = 1 then

                               begin

                               {новая перестановка}

                                               for i:= 1 to 5 do

                                                               VVar[Count][i]:= P[i];

                                               Count:= Count + 1;

                               end else

                                               for i:= 1 to m do

                                               begin

                                                               Generate (m-1);

                                                               if i < m then

                                                               begin

                                                                              Change (P[i],P[m]);

                                                                              Reverse (m-1);

                                                               end;

                                               end;

                end;

begin

                {расчет оптимального варианта}

                {генерация вариантов}

                Count:= 1;

                for i:= 1 to 5 do

                               P[i]:= i;

                Generate (5);

                {расчет расстояний и поиск минимума}

             { DistanceP  - рассчитывает расстояние между точками}

                varD[1]:= DistanceP (Start,Foxs[VVar[1][1]]);

                for j:= 1 to 4 do

                begin

                               varD[1]:= varD[1] + DistanceP (Foxs[VVar[1][j]],Foxs[VVar[1][j+1]]);

                end;

                varD[1]:= varD[1] + DistanceP (Foxs[VVar[1][5]],Finish);

                TmpDist:= varD[1];

                for i:= 2 to 120 do

                begin

                               varD[i]:= DistanceP (Start,Foxs[VVar[i][1]]);

                               for j:= 1 to 4 do

                               begin

                                               varD[i]:= varD[i] + DistanceP (Foxs[VVar[i][j]],Foxs[VVar[i][j+1]]);

                               end;

                               varD[i]:= varD[i] + DistanceP (Foxs[VVar[i][5]],Finish);

                               if varD[i] < TmpDist then

                               begin

                                TmpDist:= varD[i];

                                MinNum:= i;

                               end;

                end;

                 for i:= 1 to 120 do

                 begin

                               if varD[i] ≤ varD[MinNum] then

                               begin

                                               StrToAdd:= 'S-';

                                               for j:= 1 to 5 do

                                                               StrToAdd:= StrToAdd + IntToStr (VVar[i][j]) + '-';

                                               StrToAdd:= StrToAdd + 'F:'                                              

                               end;

                 end;

end;

Предлагаемый алгоритм работает вполне приемлемое время, но при увеличении числа объектов (например при расчете оптимального варианта в соревнованиях по спортивному ориентированию «по выбору») время вычислений будет слишком велико.

Предлагается использовать эвристический подход.

Будем рассчитывать оптимальный вариант исходя из следующего предположения: «Нужно обнаруживать передатчик, который ближе всего к нашей точке стояния,но при этом наиболее удален от финиша».

Таким образом, для каждого объекта нужно рассчитать значение эвристической функции.

F₁ = R_f-R₀

F₂ = R_f/R₀

где R_f  и R₀ – расстояния от передатчика до финиша и точки стояния соответственно.

Очередной обнаруживаемый передатчик должен иметь максимальное значение эвристической функции.

Количество итераций будет равно: 5+4+3+2 = 15, а не 120, как в первом примере.

ЗАДАНИЯ: 

1. Реализуйте алгоритм полного перебора и эвристические алгоритмы с двумя видами функций. Проведите серию экспериментов и исследуйте точность время вычислений  эвристического алгоритма в сравнении с алгоритмом полного перебора.

2. Попробуйте подобрать другие эвристические функции, сравните их работу с предложенными и полным перебором.

3. (*)Подумайте над алгоритмом, позволяющим при равенстве значений эвристических функций для двух и более передатчиков, произвести выбор, считая на один или несколько ходов вперед (Пусть лиса 1 и лиса 2 имеют одинаковое значение F. Предположим сначала, что мы выбираем лису 1 и проведем расчеты. Затем аналогичные вычисления проведем для лисы 2. На основе полученных данных сделаем выбор.

Успехов!

Абрамов А. В.

Самара – 1999.