پروفایل اشتراکی opedia

این وبگاه شامل مطالب آموزشی، المپیاد بایگانی سوالات و اطلاعات مربوط بـه مراحل مختلف المپیـاد کامپیوتر ایران است.

فهرست مندرجات

الگوریتم دایکسترا راه‌کاری به منظور پیدا کم‌وزن مسیر از رأس مشخص آغاز بـه بقیـه رئوس درون گراف جهت‌دار و وزن‌دار (با وزن‌های مثبت) مـی‌دهد. الگوریتم وزن وزن یک مسیر درون گراف وزن‌دار برابر مجموع وزن یـال‌های آن است. الگوریتم وزن جهت‌دار نبودن یـال‌ها هم مشکلی ایجاد نمـی‌کند و مـی‌توان به منظور یـال‌های غیر جهت‌دار دو یـال فرض کرد.

فرض کنید $1 \le ‌s \le n$ کـه در آن رأس ‌$s$ رأس آغاز هست و فرض کنید: الگوریتم وزن $$dist(s) = 0$$ و به ازای هر $v\neq s$: $$dist(v) = \infty$$ فرض کنید مجموعه‌ی $T$ برابر رئوسی باشد کـه تا کنون کم وزن‌ترین مسیر آن‌ها را پیدا کرده‌ایم. این الگوریتم درون هر مرحله نزدیک‌ترین رأس بـه $s$ را کـه تا کنون بـه مجموعه‌ی ‌$T$ اضافه نشده را انتخاب مـی‌کند (مثلا ‌$x$) و آن را بـه مجموعه‌ی $T$ اضافه مـی‌کند و فاصله‌ی دیگر رأس‌ها را با توجه بـه فاصله‌‌ی $x$ بروز مـی‌کند. بـه ازای هر رأس $v$ خارج $T$: $$dist(v) = min\Big(dist(v), dist(x) + w(x, v)\Big)$$ کـه در آن $w(x, v)$ برابر وزن یـال بین $x$ و $v$ است. این الگوریتم درون هر مرحله رأسی را کـه کوتاه‌ترین فاصله‌ی آن که تا $s$ پیدا شده‌ هست را بـه $T$ اضافه مـی‌کند. زیرا کوتاه ترین مسیر این رأس از یکی از رأس‌های $T$ مـی‌گذرد کـه در مراحل قبلی فاصله آن‌ها بدست آمده و دیگر رئوس را بروز کرده‌اند.

در گراف زیر، الگوریتم وزن روند اجرای این الگوریتم را مـی‌توانید مشاهده کنید

در صورت منفی بودن یـال‌ها فرض اینکه درون هر مرحله رأسی کـه کوتاه‌ترین مسیر آن پیدا شده اضافه مـی‌شود زیر سوال مـی‌رود. زیرا این رأس مـی‌تواند بدون استفاده از رأس‌های $T$ و یـال‌های منفی مسیری کوتاه‌تر بـه ‌$s$ پیدا کند.

به ازای هر رأس حتما روند بالا را طی کنیم. یعنی دنبال آن بگردیم و همـه‌ی همسایـه‌های آن را پیمایش کنیم. بعد پیچیدگی زمانی برنامـه از $O(n \times n) = O(n^2)$ است. هر چند مـی‌توان با استفاده از داده ساختار هرم پیـاده‌سازی از $O\Big(e \times lg(n)\Big)$ ارائه داد.

شبه کد:

function Dijkstra(s): dist[s] = 0 for each vertex v in Graph: // Initializations if v ≠ s dist[v] = infinity end if end for while Size(T) ≠ n : // The main loop u := vertex not in T with min dist[u] add u to T for each neighbor v of u: dist[v] = min(dist[v], dist[u]+w[u][v]) end for end while end function

Dijkstra.cpp #include <iostream> using namespace std; const int MAXN = 1000 + 10; const int INF = 1000*1000*1000; int n, m; int adj[MAXN][MAXN]; int w[MAXN][MAXN]; int dist[MAXN]; int mark[MAXN]; void readInput(){ cin >> n >> m; for(int i=0; i<m; ++i){ int v, u, z; cin >> u >> v >> z; adj[u][v] = 1; w[u][v] = z; } } void dijkstra(int s){ dist[s] = 0; for(int i=0; i<n; ++i) if(i!=s) dist[i] = INF; for(int rep=0; rep<n; ++rep) { int u = -1; int du = INF; for(int i=0; i<n; ++i) if(!mark[i] && dist[i] <= du){ u = i; du = dist[i]; } mark[u] = 1; for(int v=0; v<n; ++v) if(adj[u][v]) dist[v] = min(dist[v], dist[u]+w[u][v]); } } void writeOutput(){ for(int i=0; i<n; ++i) cout << dist[i] << " "; cout << endl; } int main(){ readInput(); dijkstra(0); writeOutput(); return 0; }

مـی‌توان یـافتن نزدیک‌ترین رأس درون هر مرحله را بـه کمک این داده ساختار انجام داد. درون این صورت حتما گراف را بـه صورت لیست مجاورت نگه داریم. کـه در $C++$ به منظور راحتی کار از $Set$ استفاده مـی کنیم.

Dijkstra.cpp #include <iostream> #include <vector> #include <set> using namespace std; const int MAXN = 1000*100 + 10; const int INF = 1000*1000*1000; typedef pair<int, int> pii; int n, m; vector<int> adj[MAXN]; vector<int> w[MAXN]; set<pii> q; int dist[MAXN]; void readInput(){ cin >> n >> m; for(int i=0; i<m; ++i){ int v, u, z; cin >> u >> v >> z; adj[u].push_back(v); w[u].push_back(z); } } void dijkstra(int s){ dist[s] = 0; for(int i=0; i<n; ++i) if(i!=s) dist[i] = INF; for(int i=0; i<n; ++i) q.insert(pii(dist[i], i)); while(!q.empty()) { set<pii> :: iterator it = q.begin(); int u = it->second; q.erase(it); for(int i=0; i<adj[u].size(); ++i){ int v = adj[u][i]; q.erase(pii(dist[v], v)); dist[v] = min(dist[v], dist[u]+w[u][i]); q.insert(pii(dist[v], v)); } } } void writeOutput(){ for(int i=0; i<n; ++i) cout << dist[i] << " "; cout << endl; } int main(){ readInput(); dijkstra(0); writeOutput(); return 0; }

فهرست مندرجات

الگوریتم کروسکال، الگوریتم وزن الگوریتم به منظور پیدا درخت پوشای کمـینـه یک گراف وزن‌دار است. الگوریتم وزن این الگوریتم بر خلاف الگوریتم پریم لزوما اجزایی کـه در حین اجرا جزء درخت پوشای کمـینـه تشخیص مـی‌دهد همبند نیستند و تنـها تضمـین مـی‌کند کـه در پایـان این شرط برقرار است.

درون این الگوریتم، یـال‌ها را بر اساس وزن بـه صورت صعودی مرتب مـی‌کنیم. الگوریتم وزن سپس از اولین یـال شروع مـی‌کنیم و هر یـالی کـه با یـال‌هایی کـه قبلا انتخاب کردیم دور نمـی‌سازد را انتخاب مـی‌کنیم. که تا جایی کـه درخت تشکیل شود.

اما چگونـه متوجه شویم کـه یـال جدید با یـال‌های انتخابی قبلی دور نمـی‌سازد؟ کافیست گرافی کـه تا کنون از یـال‌های انتخابی تشکیل شده را بـه مؤلفه‌های همبندی تقسیم کنیم و اگر یـال جدید هر دو سر آن درون یک مؤلفه بود، یـال جدید دور ایجاد مـی‌کند و در غیر اینصورت اضافه یـال جدید مشکلی ندارد.

هر راس متغیری همراه خود دارد کـه شماره مولفه‌ی همبندیش را نشان مـی‌دهد. درون ابتدا هر راس، خود یک مؤلفه‌ی همبندیست. و وقتی یک یـال بین دو مؤلفه ارتباط ایجاد مـی‌کند حتما شماره مولفه‌ی همبندی هر دو گروه یکی شود.

در شکل یک مثال به منظور اجرای این الگوریتم را مـی‌بینید. توجه کنید یـال‌های انتخاب شده تنـها درون آخر کار یک مجموعه‌ی همبند تشکیل مـی‌دهند ولی درون الگوریتم پریم همـیشـه درون طول ساخت درخت، مجموعه ما همبند بود.

فرض خلف: الگوریتم وزن فرض کنید درخت پوشای کمـینـه‌ی $T$ وجود دارد کـه مجموع‌ وزن یـال‌های ساخته شده توسط آن کمتر از درخت تولید شده توسط الگوریتم کروسکال بـه نام $G$ باشد. کم‌ورن‌ترین یـالی درون که عضو $T$ هست ولی عضو $G$ نیست را انتخاب کنید. این یـال حتما توسط الگوریتم کروسکال انتخاب مـی‌شد مگر اینکه با یـال‌های قبلی دور بسازد و چون تمام یـال های سبک تر از این یـال درون هر دو درخت وجود دارد بـه معنی آن هست که درون درخت $T$ دور وجود دارد کـه تناقض است.

تمام یـال‌ها را بـه ترتیب صعودی وزن مرتب کن

برای هر راس v یک مجموعه بساز.

یـال (u,v) را انتخاب کن.

اگر مجموعه‌ی u و v یکی نیستند. کارهای زیر را انجام بده.

مجموعه‌ی آنـها را ادغام کن.

یـال (u,v) را بـه عنوان یـالی از درخت پوشای کمـینـه بردار.

اگر هنوز n-1 یـال انتخاب نشده بـه شماره ۳ برو.

پایـان

مرتب یـال ها و بررسی یـال‌ها از $O(m+m log n)$ هست که برابر $O(m log n)$ هست و هر‌بار اتصال دو مولفه از $O(n)$ هست که چون اتصال $n-1$ بار انجام مـی‌شود پیچیدگی الگوریتم $O(m log n + n^2)$ مـی‌شود

همانطور کـه گفته شده پیچیدگی این پیـاده‌سازی از $O(m log n + n^2)$ است.

Kruskal.cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=1000; // حداکثر تعداد راس ها int n,m; vector <pair <int, pair <int, int> > > g; // پشته شامل یـال و وزن ‌انـها vector <pair <int, int> > MST; // پشته‌ای کـه درون آن درخت پوشای کمـینـه را خواهیم ریخت int tree_ID [N]; // شماره مولفه‌همبندی هر راس void find_mst(){ sort (g.begin (), g.end ()); MST.clear(); for(int i=0; i<n; i++) tree_ID[i]=i; for(int i=0; i<m; i++){ int f=g[i].second.first; int t=g[i].second.second; if(tree_ID[f]!=tree_ID[t]){ MST.push_back(g[i].second); int old_ID = tree_ID [t], new_ID = tree_ID [f]; for(int j=0; j<n; j++) // یکی شماره‌مولفه همبندی ها به منظور ادغام دو مجموعه if (tree_ID [j] == old_ID) tree_ID [j] = new_ID; } } } int main() { cin >> n>>m; g.clear(); for(int i=0; i<m; i++){ int f,t,w; cin >>f>>t>>w; g.push_back(make_pair (w, make_pair (--f, --t))); /* * هست n هست ولی بازه معتبر راس ها درون ورودی ۱ که تا n-۱ بازه معتبر راس ها به منظور ما صفر که تا * بعد ما حتما قبل از ذخیره یکی از آنـها کم کنیم */ } find_mst(); }

درخت پوشای کمـینـه درون پشته MST ریخنـه مـی‌شود. مـی‌توانید بر حسب نیـاز بـه جای اینکار مجموع وزن یـال‌های درخت را نگه دارید یـا همراه با یـال‌ها وزنشان را هم نگه دارید.

مـی‌توان از داده‌ساختار مجموعه‌های مجزا به منظور مولفه‌های همبندی استفده کرد، درون این صورت پیچیدگی الگوریتم بـه $O(m log n + n)$ کـه برابر $O(m log n)$ هست کاهش پیدا مـی‌کند.

efficient_Kruskal.cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int N=1000; int n,m; vector <pair <int, pair <int, int>>> g; // پشته شامل یـال و وزن ‌انـها vector <pair <int, int>> MST; // پشته‌ای کـه درون آن درخت پوشای کمـینـه را خواهیم ریخت int parent [N]; int root (int a){ // هر مولفه‌ یک ریشـه دارد کـه نماد آن است if(parent[a] ==a) return a; parent[a]=root(parent[a]); return root(parent[a]); } void Union (int a,int b){ // تابع ادغام parent[root(a)]=root(b); } void find_mst(){ sort (g.begin (), g.end ()); MST.clear(); for(int i=0; i<n; i++) parent[i]=i; for(int i=0; i<m; i++){ int f=g[i].second.first; int t=g[i].second.second; if(root(f)!=root(t)){ MST.push_back(g[i].second); Union(f,t); } } } int main() { cin >> n>>m; g.clear(); for(int i=0; i<m; i++){ int f,t,w; cin >>f>>t>>w; g.push_back(make_pair (w, make_pair (--f, --t))); /* * هست n هست ولی بازه معتبر راس ها درون ورودی ۱ که تا n-۱ بازه معتبر راس ها به منظور ما صفر که تا * بعد ما حتما قبل از ذخیره یکی از آنـها کم کنیم */ } find_mst(); }

درباره‌ی المپیـاد:دانش‌پژوهان:۱۳۹۶

روش‌های محاسبه ب.م.م

روش تجزیـه بـه عوامل اول

روش اقلیدسی (تقسیم متوالی)

پیـاده سازی

پیچیدگی زمانی