АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Практическое задание N 2. 26

Читайте также:
  1. Window(x1, y1, x2, y2); Задание окна на экране.
  2. В основной части решается практическое задание.
  3. Глава 1. Первое практическое занятие по методу ПМТ
  4. Домашнее задание
  5. Домашнее задание
  6. Домашнее задание
  7. Домашнее задание
  8. Домашнее задание
  9. Домашнее задание
  10. Домашнее задание
  11. Домашнее задание
  12. Домашнее задание

 

1. Построить траекторию движения мяча, подвешенного на упругой нити в вязкой среде, рассчитанную разностным моделированием. Сопротивление среды пропорционально скорости движения мяча: kc=0. 01, с-1. Нить закреплена в центре квадрата со стороной 2*Lm, длина нити L=1, м, коэффициент упругости Kn=5, н/м. Масса мяча M=0. 2, кг. Мяч начинает движение из точки с координатами x1=-0. 5*L, y1=0, со скоростью V1=10, м/с, под углом 450.

2. Построить траекторию движения мяча, подвешенного на упругой нити в квадратной коробке, рассчитанную разностным моделированием, с учетом уменьшения нормальной составляющей скорости на 20% при отражении мяча от стенки. Сопротивление среды пропорционально скорости движения мяча: kc=0. 05, с-1. Нить длиной L=1, м, закреплена в центре квадрата со стороной a=1. 5*L. Коэффициент упругости Kn=5, н/м, масса мяча M=0. 1, кг. Мяч начинает движение из точки с координатами x1=-L, y1=0, со скоростью V1x=1, м/с, V1y=5, м/с.

 

2. 4. Моделирование многовариантных задач с использованием графов

 
 


А

           
   
     
 
 

 


1 4 2

       
   
 


3

В

 

 

Рассмотрим "классический" пример многовариантной задачи. Пусть пункты A и B связаны между собой дорогами, могущими проходить также через пункты 1, 2, 3,..., N. В общем случае каждый пункт связан дорогами со всеми остальными. В частном случае некоторые связи (дороги) отсутствуют. Схематически эти пункты и связи можно изобразить в виде графа.

Графом называется совокупность узлов (пункты A, B, 1, 2,..., N) и связывающих их ребер (дорог). Маршрутом движения называется последовательность связанных ребрами узлов. В дальнейшем будем рассматривать те маршруты движения, которые всегда начинаются из пункта A и заканчиваются в пункте B. Причем пункты A и B на маршруте повторяться не могут. Например: А-1-4-В.

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

Пусть узел A имеет номер "0", а узел B - номер "N+1". Рассмотрим общий случай: каждый пункт связан со всеми остальными. Обозначим M - число промежуточных узлов на маршруте.

При М = 0 маршрут может проходить только из узла "0" в узел "N+ 1".

При М = 1 маршрут проходит через один из узлов: j1= 1, либо j1= 2,.., либо j1= N.

При М = 2 маршрут проходит через два узла, причем первый из них может иметь номер: j1=1, либо j1=2,... либо j1=N, а второй - номер: j2=1, либо j2=2,... либо j2=N, т. е. возможно N2 маршрутов. Графически все маршруты можно представить в виде:

A M=1 A M=2

           
   
   
 


1... j1... N

                                                                       
     
     
             
                                   
 
 
 

 


1 2 3... j1... N 1 2 3... j2. N 1 2 3... j2... N 1 2 3... j2.. N

       
   
 

 


B B

 

Таким образом, число маршрутов равно NM и время перебора маршрутов при больших значениях N и M очень быстро растет.

При постановке задачи нахождения маршрутов указывается значение M - наименьшее число узлов на маршруте, M1 - наибольшее число узлов на маршруте. Причем 1<=M<=M1. Например, пусть на графе имеется три узла N=3 и необходимо составить маршруты, проходящие через два узла, т. е. M=2, M1=2. Тогда в общем случае имеются маршруты:

A

0-1-1-4; 0-2-1-4; 0-3-1-4; односторонняя связь

0-1-2-4; 0-2-2-4; 0-3-2-4; 1 2 3

0-1-3-4; 0-2-3-4; 0-3-3-4; двусторонняя связь

B

 

Постановка задачи нахождения маршрутов включает определение матрицы коэффициентов aij, характеризующих связи между узлами i и j. Связь узла A задается коэффициентами a0j, узла В - коэффициентами aiN+ 1. Матрица имеет вид:

a11 a12 a13... a1N Если aij = aji = 0, то связь

a21 a22 a23... a2N между узлами i и j отсутствует.

a31 a32 a33... a3N Если aij=0 и aji<>0, то связь

............................ между узлами i и j односторонняя.

aN1 aN2 aN3... aNN Если aij<>0 и aji<>0, то связь

между узлами i и j двусторонняя.

Если aij = aji при i =1, 2,.., N; j = 1, 2,.., N, то матрица симметричная.

Если aij = 0 при j =1, 2,.., N; i > j, то матрица треугольная.

Значение aij может содержать значение ребра, связывающего узлы i и j (например, стоимость проезда), либо значение, содержащееся в узле i или j, либо любое значение, указывающее на существование связи между узлами i и j.

Введем линейный массив "Y", коэффициенты которого обозначают номера узлов графа через которые проходит маршрут, а индексы показывают номер пункта по порядку следования на маршруте. Операторы по перебору маршрутов имеют вид:

Y[0]:=0; {номер узла "А" графа}

repeat {цикл по числу узлов на маршруте}

for j:= 1 to M do Y[j]:=1; {начальные номера узлов на маршруте}

Y[M+1]:=N+1; {номер узла "B" графа}

repeat {цикл по перебору номеров узлов на маршруте}

for j:=1 to M+1 do if a[y[j-1],y[j]]=0 then goto METKA; {проверка}

{связей}

{****** здесь ставятся операторы фильтра ************}

{******............................... ************}

for j:=0 to M+1 do write('-', Y[j]); writeln; {вывод маршрута}

METKA: Y[1]:=Y[1]+1; {изменение номера узла первого пункта на маршруте}

for j:=1 to M-1 do {определяем номера узлов на маршруте}

if Y[j]>N then begin Y[j]:=1; Y[j+1]:=Y[j+1]+1 end else Break;

until Y[M]=N+1;

M:=M+1

until M>M1;

В начале программы задается возможный маршрут 0-1-1-1-... -1-N+1 для заданного значения M>0. Проверяется наличие связей и ставятся фильтры для определения маршрута. Затем увеличивается номер узла первого пункта по порядку следования на маршруте: 0-2-1-1-... -1-N+1 и т. д. до 0-N-1-1-... -1-N+1. При превышении номера узла значения N, номер узла сбрасывается до единицы, а номер следующего узла увеличивается на единицу: 0-1-2-1-... -1-N+1 и снова увеличивается номер узла первого пункта до значения N: 0-N-2-1-... -1-N+1 и далее сбрасывается до единицы с увеличением номера следующего узла: 0-1-3-1-... -1-N+1. После (N-1)-го сброса и увеличения значения узла первого пункта до N получим маршрут: 0-N-N-1-... -1-N+1 и далее: 0-1-1-2-... -1-N+1. Таким образом, происходит перебор всех возможных маршрутов до 0-N-N-N-... -N-N+1. После этого рассматриваются маршруты для M=M+1 включая M=M1. Отметим, что при необходимости маршрут 0-N+1 для M=0 нужно рассмотреть отдельно.

При решении конкретных задач необходимо определить значение коэффициентов aij матрицы связи и установить необходимые фильтры.

Рассмотрим задачу определения стоимости маршрутов из A в B.

 

 

1.) Зададим стоимость проезда из узла i в узел j:

for i:=0 to N+1 do for j:=i to N+1 do a[i,j]:=Random(X); {X-дано}

for i:=0 to N+1 do a[i,i]:=0; { движение внутри узла запрещено}

for i:=0 to N+1 do for j:=i to N+1 do a[j,i]:=a[i,j]; {связи }

{двусторонние и равнозначные}

2). Матрицу связей можно вывести на экран для проверки. При выводе маршрута на экран или в файл можно выводить также значение стоимости маршрута.

S:=0; for m:=1 to M1+1 do S:=S+a[y[m-1],y[m]]; {стоимость маршрута}

1 2 3   4 5 6   7 8 9

Рассмотрим задачу расстановки мин на прямоугольном поле размером Nx*Ny. При этом M=M1=N=Nx*Ny и все узлы должны быть пройдены без повторений. Расстановка начинается из узла с заданным номером NH и может закончиться в узлах на верхней границе.

1) Определим матрицу связей:

for i:=0 to N+1 do for j:=1 to N+1 do a[i,j]:=0;

for i:=1 to N-1 do begin a[i,i+1]:=1; a[i+1,i]:=1 end; {связи по гориз}

for j:=1 to Ny-1 do begin k:=Nx*j; a[k,k+1]:=0; a[k+1,k]:=0 end;

for i:=1 to Nx do for j:=1 to Ny-1 do {связи по вертикали}

begin k:=Nx*(j-1)+i; a[k,k+Nx]:=1; a[k+Nx,k]:=1 end;

a[0,NH]:=2; { NH - узел связи c узлом 0}

for i:=1 to Nx do a[i,N+1]:=3; { 1,.., Nx - узлы связи c узлом N+1}

2). Установим фильтр, запрещающий возврат в узел на маршруте:

for k:=1 to M do c[y[k]]:=0; for k:=1 to M do

begin c[y[k]]:=c[y[k]]+1; if c[y[k]]=1 then goto METKA end;

Здесь производится суммирование повторяющихся номеров узлов на маршруте. При совпадении номера узла значение счетчика c[y[k]]=1 -маршрут не рассматривается.

Рассмотрим задачу загрузки N - видов коробок в машину. Задается число коробок каждого вида: Ki, их вес Mi и объем Vi, где i=1, 2,.., N. Ограничения могут быть по общему весу и объему. Число узлов графа равно N. Число узлов на маршруте M=1, М1=K1+K2+... +KN. Интервал М-М1 можно уменьшить просчитав наибольшее допустимое по весу и объему число коробок KMi каждого вида загружаемых в машину (KMi<=Ki). Тогда М = min(KMi), а М1 = max(KMi). Поскольку порядок загрузки не имеет значения, то все связи односторонние. 0

1 2... k... N N+1

1) Определим матрицу связей:

 

for i:=0 to N+1 do for j:=i to N+1 do a[j,i]:=0; {нижний треугольник}

for i:=0 to N+1 do for j:=i to N+1 do a[i,j]:=1; {верхний треугольник}

2) Определение числа коробок каждого вида аналогично суммированию повторяющихся номеров узлов на маршруте.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.014 сек.)