close

Вход

Забыли?

вход по аккаунту

?

Kursovaya (4)

код для вставкиСкачать
???????????? ??????????? ? ????? ?????????? ?????????
??????????? ??????????????? ????????? ??????????????? ?????????? ??????? ????????????????? ??????????? "?????? ??????????????? ??????????? ???????????"
??????? "?????????? ?????????? ? ??????????????? ???????????"
010500.62 "?????????????? ??????????? ? ????????????????? ?????????????? ??????" ?? ??????? "?????????????? ??????? ? ???? ??????"
???????? ??????
?? ???? ???????? ?????-??????????
?? ?????????? ????????????????
??????? ???????? ?????? ?????? ??-211
????????????? ???????
???? ??????? ?? - 206899 - 56 - 15 - 00.00.000.??
???????????? ???????
???? ?.?.
____________________
(???????, ????)
??????????????????????? ???????
______________________ _____________________(???????, ????)
???? 2012
???????
????????????? ??????? ? ???????? ??????: 18?., 5 ???., 0 ????., 3 ????????, 2 ??????????.
????????, ????, ?????, ???????, ???????????? ?????, ????????????, ?????????, ?????????, ??????????
?????? ????????????: ???????? ?????-??????????
???? ??????: ??????????? ?????? ? ??????, ?????????? ? ???????? ?????????????? ????????.
????? ??????: ??????????? ????????????? ?????? ? ??????? ?????????? ?????????, ??????????? ?????? ????????.
??????????
????????4
1 ?????5
1.1???????? ?????????????? ??????5
1.2 ???? ? ????????5
2. ???????? ?????-??????????6
2.1 ??????? ???????? ?????????6
2.2 ?????? ????????? ?????????8
2.3 ?????????8
3 ???????????????? ??????? ?????????9
3.1 ?????????? omp.h9
3.2 ??????? ???????? ????????????????? ?????????9
??????????11
?????? ?????????????? ??????????12
?????????? ? ????? ???????? ?????????13
?????????? ? ????? ??????????? ?????14
????????
???????? ???????????? ???????? ?????? ????? ?????????? ????????? ?????-??????????. ?????? ?????? ????????:
1) ???????????? ? ?????????? ?????-??????????, ??? ????????;
2) ?????????? ?????????, ??? ?????????? ?????????? ????????????? ?????? ????;
3) ?????? ???????????? ?????????;
4) ???????????? ?????????.
? ?????? ?????? ???????????? ???? - ??????????????? ????, ? ??????? ?????? ????? ????? ??????????????? ?????????? ??????????? ? ????? . ?????????? ??? ???????: ???????? ? ???? ?????, ??? ????? ?????? ??????? ???? ????? ?? ???? ?? ????????? ? ????. ???????????? ???? ????? ???? ???????????? ??? ?????????????, ????????, ????????? ???????. ????????????? ???????????? ???? - ???????????? ????, ??? ?????????? ??????????? ????? ??????? - ????? ?????.
????? - ??????? ?? ?????????? ?????????? ??? ????? ??????:
1) ??????????? ?????????? ???????????; 2) ????? ?? ????? ????????? ?????????? ???????????;
3) ????? ?? ??????? ? ?????? ?????? ???? ??????????????? ? ?????? ???????????;
4) ?????????? ??????. ??? ???? , ????? ????????? ? ?????.
?????? ????? "???????????? ????? ? ????" ?????????? 19 ?????? 1954 ????. ?????? ?????? - ???? ? ?????????, ???????? ??????? ? ???????????? ?????? ? ??????????? ??????? ??? ????????????????? ??????: ???????? ????????????? ?????? ? ???? ????? ??????????? ?????????? ??????????? ???????. (???????? ? ???? ?????????? ????????? ????????? ?? ?????? ?? ??? ???????????????? ??????, ????? ??? ???????? ? ???? ????? ? ?????? ???????. ?????????? ???????????? ??????? ?????????? ????? ?????????? ???????????? ?????, ????? ??????? ????? ? ?????? ???????.) ? 1955 ???? ? ?????? ???????? ???? ?????????, ??? ??????? ??? ??????? ??????? ?????????.
???? ????? ???????? ??????????? ??????, ?????? ????? ?????? ?????? ??????? - ??????? ????? ???????? ?????????. ??? ?? ?????, ???? ?????? ???????? ????????????? ??? ????? ?????, ??????? ????? ????????? ?????????? ???????????? ?????? ????? ?????. ???????? ?????? ??????????? ? ????? ?????????, ??? ???? ????? ????? ??????????? ???????? ????????? ??????. ????? ??????? ?????????? ?? ??????? ? ???????????? ???????????, ???????????????? ?????, ????????????? ?????.
???? ????????????????? ????????? ??????????? ? ?????????? ??????? ?????? ? ???????? ???????? ??????? ??????. ????? ????????, ??? ????????? ? ???????????? ????????? ???????? ??????? ?? ??????? ??????????. ?????? ????????? ? ???????, ???????? ??? ?????? ????????? ?????? ????? ? ??????. ???? ???????? ????? ??? ????, ????? ?????? ???? ? ???????? ????? ?? ????????? ? ????.
1 ?????
1.1???????? ?????????????? ??????
???? G - ??? ?????????????? ??????, ????????? ?? ????????? ?????? X = {x1,x2,...,xn} ? ????????? ????? A={a1, a2,..., am}. ????? ???????, ???? ????????? ???????????? ????????????? ???????? X, A ? ???????????? G(X, A).
???? ?????? ????? ??????? ??????????? ?? ????? ??????? ? ??????, ?? ????? ???? ?????????? ???????????????. ????? ???????????????? ????? ?????????? ??????. ??????????????? ??????? ???????????????? ????? ???????? ??????? ? ??????. ???? ??????????? ????? ?? ???????????, ?? ???? ?????????? ????????????????? (??? ?????? ??????).????, ??????? ??? ???????????????, ??? ? ????????????????? ?????, ?????????? ?????????.????????????????? ????? ????? ???????????? ???? ?????????????? ???????????? ?????, ??????????? ?? ?? ????? ???????.
????????? ????? ????? ????? ???? ??????. ????????? ?????? ????? ?? ????? ???? ??????. ???? G (X, A)- ??????, ???? ??? ????? ???? ?????? xi? xj?????????? ????? (xi, xj).
1.2 ???? ? ????????
????????? ??? ????? ? ????????????????? ?????G ?????????? ????? ?????????????????? (???????? ??? ???????????) ????? a1, a2,...,an,..., ??? ?????? ???????? ??? ????? ai ? ai+1????? ????? ??????????? ???????. ???? ? ?? ?? ????? ????? ??????????? ? ???????? ????????? ???. ? ???????? ???????? (a1,a2,...,an) ??????? ?????? ????? a1? ????????? ????? an. ??????? x1, ??????????? ????? a1, ?? ?? ??????????? ????? a2, ?????????? ??????? ????????, ? ??????? xn, ??????????? ????? an, ?? ?? ??????????? ????? an-1, ?????????? ?????? ????????.
?????? (??? ?????????) ???????? ?????????? ????? ?????, ???????? ? ???????, ?????? ?????? ????? ????????? ??????? ???, ??????? ??? ?????? ? ?????? ???????.
????????? ??????? ?????????? ??????. ??????? (????), ? ??????? ??? ????? ????????, ?????????? ??????? ????????? ??? ??????? ????? (??????). ??????? (????), ? ??????? ??? ???????, (????? ?????? ? ?????????), ????????, ?????????? ???????????? ????????? ??????????????? ????? (??????). ????? ???????????????? ????? ?????????? ?????????????????? ???, ? ??????? ???????? ??????? ?????? ????, ???????? ?? ?????????, ???????? ????????? ???????? ????????? ????. ????? ??? ???? ?????????? ?????? ????.
???? ?????????? ????????, ???? ??? ????????? ??????? ????????? ? ???????? ????????.
???? (??????), ? ??????? ??? ???? ????????, ?????????? ???????. ???? (??????), ? ??????? ??? ???????, ????? ?????? ? ?????????, ????????, ?????????? ????????????.
?????? ????? ????? ?????????????? ????? ?????????? ?????, ??? ?????? ????. ????? ???? ?????????? ?????? ?? ??????????? ??????. ?????? ???? ????????????? ???????? ?????, ? ????? ?????????? ???? ? ??????????? ?????????. ???? ? ????? ???? ????????? ? ?????, ? ????????, ?? ?? ?????????? ?????? ??????????. ??? ???? ? ????? ???????????? ??? ????? ????? ????? ????? ????. ?????????? ????? ????? ????? ????????? ?????????? ???? ??????????? ????, ??????????? ??? ???????.
2. ???????? ?????-??????????
2.1 ??????? ???????? ?????????
???? ????????? ??????????? ? ?????????. ???????? ????? ???? ?? ????????? ? ? ?????, ????? ??? ??????? ????? ?????????? ?????????? ??????????? ???? ?????? ?????? ????. ??? ???? ????? ?? ?????? ???? ????? ??????????? ??? ? ??????, ??? ? ? ???????? ???????????. ???????? ??????????? ???????? ????? ?????????? ?????????? ???????????? ????? ??????? ????. ??????????? ????? ?? ?????? ?? ????? ??????? ???? ?? ????????? ??????????? ????????. ????? ???? ????????? ??????????? ????.
?????? ????????? ???????????? ?? ??? ???, ???? ??????? ???????? ?????? ????.
????? ???????, ??? ?????? ???????? ????????? ? ?????? ???????????????????, ?.?. ?????? ????????? ??? ????????? ????????? ????????????. ? ????? ?????? (?????????? ?????) ????????? ??????? ?? ????, ??? ????? ?????????? ????. ???????????? ???????? ?????????:
* ???????? ??? ??????. ?????????? ???? ?????????? ????????? ? ???????? ?????;
* ? ?????????? ???? ??????? ????? ???? ?? ????????? ? ????. ???? ?????? ???? ???, ???????????????;
* ??????? ????? ????????? ???? (?? ?????????? ????????????? ????? ??? ????????????? ?????) ??????????? ????????? ?????;
* ?? ????????? ???? ? ?????????? ???? ???? ????? ? ??????????? ?????????? ???????????? ;
* ??? ??????? ????? ?? ????????? ???? ??????????? ????? ?? , ? ? ??????????????? ??? - ????????? ?? ;
* ???????????? ?????????? ????. ??? ???? ????? ?? ????????? ????, ? ????? ??? ??????????????? ?? ?????, ????????? ????? ?????????? ???????????. ???? ??? ????? ?????????, ????????? ????? ? ?????????? ????, ? ???? ??????????, ??????? ???;
* ???????????? ?? ??? 2.
?????, ??? ???????? ?? ??????????????, ????? ?????? ???? ?? ???? ?? ???? 2 ??? ??? ?? ??? ??????. ?? ???? ??????? ???????? ?????????????? ???????? ?????? ??? ????? ?????????? ????????????, ?? ???? ??? ??? ??? ??????? ????????? ?????????? ???????????? ?? ????? ???????? ????? ?????. ???? ?????????? ??????????? ???????????, ???????? ????? ???????? ?????????? ?????, ?? ??????? ? ???????????? ???????. ?? ??????? 1 ???????????? ????? ????? ?????? ?????????.
????? ?????????, ?? ????? ??????????????? ???? G = (V; E), ?? ?????????? ?????? V ? ?????????? ????? E. ?? ????????? V ???????? ??? ???????: s - ???????? ? t - ????. ??? ????, ? ??????? s ???? ????????????? ?????, ? ??????? t ???? ?????? ???????? ?????.
???? ????? ????? ???????????? ?????????? ??????????? x ? ?????y, ?? ?????????? ?????????? ???????????? ????? ?????????? ????? xy. ????? ?????????? ?????????? ??????????? ??????????? ? ???, ?? ??????? ??? ????? ????????? ????? ?? ?????? ?????.
??????? 1 - ????? ?????
????????? ?????? ?????????? ????????? ???????? ?????????? ????????? ? ?????. ????? ????????? ??????????? ? ??????? ????????? ?????? ????? ? ??????. ?? ??????? 2 ???????????? ????-????? ????????? ?????? ????? ? ??????.
???????? ?????-?????????? ???????? ???? ????? ????? ???? ?? ???? ???? ?? ????????? ? ????, ?????????? ?????????? ????? ?? ??????????? ????????. ?? ??????? 3 ???????????? ????-????? ????????? ?????-??????????. ??????? 2 - ????-????? ????????? ?????? ? ?????? ??????? 3 - ???????? ?????-??????????
2.2 ?????? ????????? ?????????
?? ?????? ???? ???????? ????????? ????? ?????????????? ???? ? ??? ?????????? ??????. ???? ?????????? ??????????? ???? ????? - ????? ?????, ????? ???????? ?? ????????, ??? ? ?????? ????? ??? ????? ?????? ????? ??????. ?????????????, ?? ?????? ???? ???????? ??????????? ????? ?? ??????? ???? ?? ???????, ?????????????, ?? ???????? ?? ????? ??? ?? O(f) ?????, ??? f - ???????????? ????? ? ?????. ????? ????????? ?????? ??? ?? ????? O(E), ??? E - ????? ????? ? ?????, ????? ????? ????? ?????? ????????? ?????????? O(Ef). ???? ???????? ?????????? ??????????? ???? ?? ?????? ?? ????? - ?????????????? ?????, ?? ???????? ????? ???????? ??????????, ???? ?? ??????????? ??????? ? ??????????? ???????. ?? ??????? 4 ??????????? ????????? ????????? ?????-??????????.
2.3 ?????????
Ford_Fulkerson(G, s, t)
1 for ??????? ????? (u, v) ? E[G]
2 do f[u,v] "-0
3 f[v,u] "- 0
4 while ?????????? ???? p ?? s ? t ? ?????????? ???? Gf
5 do ?f(?) "- min {cf(u, v) : (u, v) ??????????? ?}
6 for ??????? ????? (u, v) in p
7 do f[u,v] "- f[u] + cf(p)
8 f[v,u] "- -f[u,v]
??????? 4 - ????????? ????????? ?????-??????????
3 ???????????????? ??????? ?????????
3.1 ?????????? omp.h
???????????? OpenMP ?????? ???????????? ??????? ?????? ???????? ??????? ? ???????????, ?? ?????? ?? ???????????? ?????? ? ????????, ????????????? ? ??????????? ???????, ? ????? ????????????? ???????????, ??????? ??????? ??????? ???????. ??? ????? ???????????? OpenMP ??????? ??????????? ?? ????????? ????? ?????, ????????, ??????? ??????? ? ?????????? ?????, ??????? ????? ??????? ????????? ???????????, ??? ? ??? ?????? ??????? ???????? ?????? ? ??????????. ??????????? ?????? ????? ??????????????, ??????? ????? ???? ?????? ??????????????? ????? ??????. ????? ????, ??????? ?????????? ???????? ??????? ??????????? ? OpenMP, ?? ?????? ?????? ??????? ??????? ??????????? ????, ????? ????? ??????? ??????????????, ? ??? ????????? ??????? ???????? ????????? ?????????? ??? ?????????? ???????????? ??????????????????. ???????????? ?????????????????? OpenMP ??????????? ??? ????????????? ????? ??????????? ??? ????????????????? "??????? ?????", - ???????? ?????????? ?????? ? ??????????.
????????? ????????????? ???????? ???????? ? ????????? ?????. ?????? - ??? ????????? ?????????????, ???????????? ?????????????, ??????? ?? ???????????? ?????? ??????????. ?? ???? ?????????, ?????????? ? ??????????? ?????? ??????????, ????? ???? ?????????????? ??? ????????????????, ??? ??? ????? ?????????? ?? ?????? ??????? ??????. ?????? ????????, ?????????????? ? ?????? ??????:
1) #pragma omp parallel - ????????? ????? ?????? ??? ????????????????? ?????????? ??????????. ????????? ??????? ?? ??????, ????? ??????? ????? ??????? ? ??????? ??????? omp_num_threads(int n), ??? n - ????? ???????.
2) #pragma omp for - ??????????? ??? ????????????????? ???????????? ??????????? ????????. ?? ????, ????????? ???????? ??????????? ??????????? ?? ?????????? ???????????. ??? ??? ?????? ????????? ???? ???????? ???????????, ?? ??????????? ???? ?????? ????? ? ?????? ?????, ??????? ?????? ??????? ????????????????? ????? ?????????? ??? ????????????? ?? ??????? ?????? P = NP. 3.2 ??????? ???????? ????????????????? ?????????
??????? ????????????????? ????????? ?????-?????????? ???????? ? ????????????????? ?????? ????? ? ??????. ???? ?? ??? ?????????? ?????????, ??? ?????? ????? ? ????? ????????????, ????????, ???????? ?????? ? ??????? - ????????????????? ?? ?????????????? ?????????. ??? ????????????????? ???????????? ?????????? omp.h, ???????????? ??????????? OpenMP ??????????. ???????? ??????? ?? ????????? ???????, ? ?? ?????? ?? ??????? ?????????? ???? ????? ?????????. ??????????? ??????????? ?? ???? ????????? ????? ? ??????????????? ?????????? ????. ?? ??????? 5 ??????????? ???????? ????, ? ?????????????? ????????????? ?????. ?????? ??????? ??????????? ? ?????????? ?.
???????? ????? ????????????????? ??? ?????? ????????? ?????? ?????????. ?? ????????, ????????? ??????? ?????? ?? ????? ??????? ??????? ??????, ?? ?????? ??????????????. ????????? ?????????, ??????????? ?? ??????? ??????, ??? 25% ???????? ??????????? ??????????? ?? 2 ??????????? ?????????? 300% ?? ????????????????? ??????????, ?????? ?? ???????? ?????? ????????? ?????????? ?? ????, ? ???? ?????? ???? ????????, ???????? ?? ???????? ?????????? ????????.
??????? 5 - ???????? ????????????????? ???? ?????????
??????????
? ???????? ???????? ??????? ??????? ???? ??????????? ?????? ?????? ? ?????, ??????? ??????? ????? ? ?????????. ??????????? ?????????, ??????????? ???????? ?????-?????????? ? MicrosoftVisualStudio 2010.???????? ????? ????? ???? ?????????? ? ?????????? ??? ???????????? ? ???????????????? ?????, ????? ??? ?????????? ??????????????? ?????? ? Internet, ??? ??????? - ???????, ? ????? ??? ????? ????? ?????????. ????? ???????, ??? ?????? ????? ????, ??? ??????? ????? ????????? ?????? ?????????? ? ?????? ????? ?????????????? ??????.
????? ???? ????????? ??????, ?????????? ? ???????? ?????????? ???????????? ????? ?? ???????? "????????????????".
?????? ?????????????? ??????????
1. ???? 7.32-2001. ????? ? ??????-????????????????? ??????. ????????? ? ??????? ?????????? [?????]. - ?????? ???? 7.32-91 ;????. 2001-07-01. - ????? :??????. ????? ?? ??????????????, ?????????? ? ???????????? ; ?. : ???-?? ??????????, 2001. - 16 ?. - (??????? ?????????? ?? ??????????, ????????????? ? ????????????? ????).
2. ???? 7.1-2003. ????????????????? ??????. ????????????????? ????????. ????? ?????????? ? ??????? ??????????? [?????]. - ?????? ???? 7.1-84, ???? 7.16-79, ???? 7.18-79, ???? 7.34-81, ???? 7.40-82 ;????. 2004-07-01. - ?. : ???-?? ??????????, 2004. - 116 ?. - (??????? ?????????? ?? ??????????, ????????????? ? ????????????? ????).
3. ??????, ????? ??????????. ?????????? ?????????? [?????] : ????.??????? / ?. ?. ??????, 2009. - 87 ?.
4. ?????, ?. ??????????? ?????? ?? ?????????? ? ???????? ? ???????[?????]: ????. ??????? / ?. ????? -?.: "????????", 2007?. - 644?.
5. ???????? ?????-?????????? [??????????? ??????]: ???????????? ????? ???????????? ????. - http://habrahabr.ru/- ????. ? ??????.
6. ???????? ????????????????? ?????? ? ????? [??????????? ??????]: ??????????? ??????????. -http://neerc.ifmo.ru/mediawiki/index.php?title.redirect=no/- ????. ? ??????.
?????????? ?
(????????????)
????? ????????? ?????
#include"ff_alg.h"
int main()
{
clock_t time = clock();
read_input_file();
printf("%d\n",max_flow(0,n-1));
time = clock() - time;
cout<<time<<endl;
system("pause");
return 0;
}
?????????? ?
(????????????)
????? ??????????? ?????
#include<stdio.h>
#include<iostream>
#include<time.h>
using namespace std;
#ifdef _DEBUG
#undef _DEBUG
#include <omp.h>
#define _DEBUG
#else
#include <omp.h>
#endif
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX_NODES 100
#define INFINITY 10000
int min (int x, int y);
void enqueue (int x);
int dequeue () ;
int bfs (int start, int target) ;
int max_flow (int source, int sink);
int n; int e; int capacity[MAX_NODES][MAX_NODES]; int flow[MAX_NODES][MAX_NODES]; int color[MAX_NODES]; int pred[MAX_NODES]; int head,tail;
int q[MAX_NODES+2];
int min (int x, int y) {return x<y ? x : y;}
void enqueue (int x)
{
q[tail] = x;
tail++;
color[x] = GRAY;
}
int dequeue () {
int x = q[head];
head++;
color[x] = BLACK;
return x;
}
int bfs (int start, int target) {
int u,v;
for (u=0; u<n; u++) {
color[u] = WHITE;
} head = tail = 0;
enqueue(start);
pred[start] = -1;
omp_set_num_threads(32);
#pragma omp parallel while (head!=tail) {
u = dequeue();
//#pragma omp for for (v=0; v<n; v++) {
if (color[v]==WHITE && capacity[u][v]-flow[u][v]>0) {
enqueue(v);
pred[v] = u;
}
}
}
return color[target]==BLACK;
}
int max_flow (int source, int sink) {
int u;
int max_flow = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
flow[i][j] = 0;
}
}
omp_set_num_threads(32);
//#pragma omp parallel while (bfs(source,sink)) {
int increment = INFINITY;
//#pragma omp for for (u=n-1; pred[u]>=0; u=pred[u]) {
increment = min(increment,capacity[pred[u]][u]-flow[pred[u]][u]);
}
#pragma omp for for (u=n-1; pred[u]>=0; u=pred[u]) {
flow[pred[u]][u] += increment;
flow[u][pred[u]] -= increment;
}
max_flow += increment;
}
return max_flow;
}
void read_input_file() {
int a,b,c;
FILE* input = fopen("C:\\data.txt","r");
fscanf_s(input,"%d %d",&n,&e);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
capacity[i][j] = 0;
}
}
for (int i = 0; i < e; i++) {
fscanf_s(input,"%d %d %d",&a,&b,&c);
capacity[a][b] = c;
}
fclose(input);
}
2
Документ
Категория
Без категории
Просмотров
42
Размер файла
139 Кб
Теги
kursovaya
1/--страниц
Пожаловаться на содержимое документа