عدد التعديلات للمستخدم (user_editcount) | null |
اسم حساب المستخدم (user_name) | '51.36.63.6' |
عمر حساب المستخدم (user_age) | 0 |
المجموعات (متضمنة غير المباشرة) التي المستخدم فيها (user_groups) | [
0 => '*'
] |
ما إذا كان المستخدم يعدل من تطبيق المحمول (user_app) | false |
ما إذا كان المستخدم يعدل عبر واجهة المحمول (user_mobile) | false |
المجموعات العامة التي ينتمي إليها الحساب (global_user_groups) | [] |
هوية الصفحة (page_id) | 5946811 |
نطاق الصفحة (page_namespace) | 0 |
عنوان الصفحة (بدون نطاق) (page_title) | 'مسألة الإسناد' |
عنوان الصفحة الكامل (page_prefixedtitle) | 'مسألة الإسناد' |
آخر عشرة مساهمين في الصفحة (page_recent_contributors) | [
0 => 'مصعب العبود',
1 => 'JarBot',
2 => 'Pr.mtb',
3 => 'AlaaBot',
4 => 'ASammourBot',
5 => 'Mr.Ibrahembot'
] |
عمر الصفحة (بالثواني) (page_age) | 88707220 |
أول مستخدم ساهم في الصفحة (page_first_contributor) | 'Pr.mtb' |
فعل (action) | 'edit' |
ملخص التعديل/السبب (summary) | '' |
نموذج المحتوى القديم (old_content_model) | 'wikitext' |
نموذج المحتوى الجديد (new_content_model) | 'wikitext' |
نص الويكي القديم للصفحة، قبل التعديل (old_wikitext) | ''''مشكلة الاسناد''' أو '''مشكلة الاسناد الأمثل''' عرفت منذ بداية علم [[بحوث العمليات]] و لها تطبيقات عملية جد مطلوبة.
== مثال ابتدائي ==
شركة تتشغل '''n''' أشخاص لوظائف مختلفة عددها الكلي '''n'''. نحدد متغيرًا الربحية '''r<sub>ij</sub> ≥ 0''' بالنسبة لأي شخص '''i''' مأهل للمنصب '''j''' ، على سبيل المثال '''r<sub>ij</sub>''' تمثل الربح الذي يمكن أن تحققه المؤسسة إذا أسند الشخص '''i''' إلى الوظيفة '''j''' ،
تكمن المشكلة في تحديد تعيين الأشخاص لمحطات العمل بالكيفية التي تزيد من قيمة الربحية الإجمالية.
== نماذج الثمثيل ==
[[ملف:Optimal assignment.jpg|تصغير]]
=== الثمثيل ببيان ثنائي ===
يمكن تمثيل هذه المشكلة بواسطة [[مخطط ثنائي|بيان ثنائي]] '''(G(U,V,E'''، تكون فيه مجموعة الرؤوس '''U''' هي الأشخاص ومجموعة الرؤوس '''V''' هي مناصب الشغل ، أما ثقل كل ضلع ('''w(u<sub>i</sub>,v<sub>j</sub>''' فيمثل الربحية.
تتمثل المهمة هنا في العثور على [[المطابقة (نظرية الرسوم البيانية)|الإقتران]] في البيان الثنائي ذا أقصى مجموع أثقال الأضلاع.
=== الثمثيل بمصفوفة ===
يمكن كذلك تمثيل المشكلة بواسطة مصفوفة حدوث '''R''' حيث يمثل كل سطر شخصًا ويمثل كل عمود منصبا ، عناصر المصفوفة تساوي '''r<sub>ij</sub>'''
الحل الأمثل هنا يتمثل في العثور على مجموعة من العناصر '''r<sub>ij</sub>''' ليس لها أي خط ولا عمود مشترك في المصفوفة '''R''' ومجموعهم المتراكم له أكبر قيمة ممكنة ، و هذا يتناسب مع الطرح الشكلي لمسألة [[برمجة خطية]]
== خوارزميات الحل الأمثل ==
يمكن الحصول على الحل الأمثل بواسطة تخصيص أيّ خوارزميات [[برمجة خطية|البرمجة الخطي]]ة ، لكن أول طريقة تستغرق زمنا [[تعقيد الوقت|كثير الحدود قطعي]] لحل هذه المسألة هي طريقة [[هارولد دبليو كوهن|كوهن]] المعروفة باسم [[الخوارزمية المجرية]]<ref>KUHN, Harold W. The Hungarian method for the assignment problem. [https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109 Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97] {{Webarchive|url=https://web.archive.org/web/20190326192011/https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109 |date=26 مارس 2019}}</ref>
== صنف التعقيد ==
لم تذكر مشكلة الانساد الأمثل تحت صيغتها الخام ضمن القائمة الأساسية لمايكل غاري و [[دايفيد جونسون (عالم)|دايفيد جونسون]] للمسائل من صنف التعقيد الحسابي NP-كامل<ref>Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979</ref> ، و نظرا بأن الخوارزمية المجرية تسمح حلّها خلال زمن كثير الحدود قإن هذه المسألة تنتمي إلى [[كثير حدود|صنف التعقيد P]]
== مراجع ==
{{مراجع}}
{{شريط بوابات|علم الحاسوب|رياضيات}}
[[تصنيف:استمثال توافقي]]
[[تصنيف:برمجة خطية]]{{ضبط استنادي}}' |
نص الويكي الجديد للصفحة، بعد التعديل (new_wikitext) | ''''مشكلة الاسناد''' أو '''مشكلة الاسناد الأمثل''' عرفت منذ بداية علم [[بحوث العمليات]] و لها تطبيقات عملية جد مطلوبة.
== مثال ابتدائي ==
شركة تتشغل '''n''' أشخاص لوظائف مختلفة عددها الكلي '''n'''. نحدد متغيرًا الربحية '''r<sub>ij</sub> ≥ 0''' بالنسبة لأي شخص '''i''' مأهل للمنصب '''j''' ، على سبيل المثال '''r<sub>ij</sub>''' تمثل الربح الذي يمكن أن تحققه المؤسسة إذا أسند الشخص '''i''' إلى الوظيفة '''j''' ،
تكمن المشكلة في تحديد تعيين الأشخاص لمحطات العمل بالكيفية التي تزيد من قيمة الربحية الإجمالية.
== نماذج الثمثيل ==
[[ملف:Optimal assignment.jpg|تصغير]]
=== الثمثيل ببيان ثنائي ===
يمكن تمثيل هذه المشكلة بواسطة [[مخطط ثنائي|بيان ثنائي]] '''(G(U,V,E'''، تكون فيه مجموعة الرؤوس '''U''' هي الأشخاص ومجموعة الرؤوس '''V''' هي مناصب الشغل ، أما ثقل كل ضلع ('''w(u<sub>i</sub>,v<sub>j</sub>''' فيمثل الربحية.
تتمثل المهمة هنا في العثور على [[المطابقة (نظرية الرسوم البيانية)|الإقتران]] في البيان الثنائي ذا أقصى مجموع أثقال الأضلاع.
=== الثمثيل بمصفوفة ===
يمكن كذلك تمثيل المشكلة بواسطة مصفوفة حدوث '''R''' حيث يمثل كل سطر شخصًا ويمثل كل عمود منصبا ، عناصر المصفوفة تساوي '''r<sub>ij</sub>'''
الحل الأمثل هنا يتمثل في العثور على مجموعة من العناصر '''r<sub>ij</sub>''' ليس لها أي خط ولا عمود مشترك في المصفوفة '''R''' ومجموعهم المتراكم له أكبر قيمة ممكنة ، و هذا يتناسب مع الطرح الشكلي لمسألة [[برمجة خطية]]
== خوارزميات الحل الأمثل ==
يمكن الحصول على الحل الأمثل بواسطة تخصيص أيّ خوارزميات [[برمجة خطية|البرمجة الخطي]]ة ، لكن أول طريقة تستغرق زمنا [[تعقيد الوقت|كثير الحدود قطعي]] لحل هذه المسألة هي طريقة [[هارولد دبليو كوهن|كوهن]] المعروفة باسم [[الخوارزمية المجرية]]<ref>KUHN, Harold W. The Hungarian method for the assignment problem. [https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109 Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97] {{Webarchive|url=https://web.archive.org/web/20190326192011/https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109 |date=26 مارس 2019}}</ref>
== صنف التعقيد ==
لم تذكر مشكلة الانساد الأمثل تحت صيغتها الخام ضمن القائمة الأساسية لمايكل غاري و [[دايفيد جونسون (عالم)|دايفيد جونسون]] للمسائل من صنف التعقيد الحسابي NP-كامل<ref>Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979</ref> ، و نظرا بأن الخوارزمية المجرية تسمح حلّها خلال زمن كثير الحدود قإن هذه المسألة تنتمي إلى [[كثير حدود|صنف التعقيد P]]
== مراجع ==
{{مراجع}}
{{شريط بوابات|علم الحاسوب|رياضيات}}
{{شريط مختارة}}
[[تصنيف:استمثال توافقي]]
[[تصنيف:برمجة خطية]]{{ضبط استنادي}}' |
فرق موحد للتغييرات المصنوعة بواسطة التعديل (edit_diff) | '@@ -24,4 +24,5 @@
{{مراجع}}
{{شريط بوابات|علم الحاسوب|رياضيات}}
+{{شريط مختارة}}
[[تصنيف:استمثال توافقي]]
[[تصنيف:برمجة خطية]]{{ضبط استنادي}}
' |
حجم الصفحة الجديد (new_size) | 3853 |
حجم الصفحة القديم (old_size) | 3827 |
الحجم المتغير في التعديل (edit_delta) | 26 |
السطور المضافة في التعديل (added_lines) | [
0 => '{{شريط مختارة}}'
] |
السطور المزالة في التعديل (removed_lines) | [] |
نص الصفحة الجديد، مجردا من أية تهيئة (new_text) | 'مشكلة الاسناد أو مشكلة الاسناد الأمثل عرفت منذ بداية علم بحوث العمليات و لها تطبيقات عملية جد مطلوبة.
محتويات
1 مثال ابتدائي
2 نماذج الثمثيل
2.1 الثمثيل ببيان ثنائي
2.2 الثمثيل بمصفوفة
3 خوارزميات الحل الأمثل
4 صنف التعقيد
5 مراجع
مثال ابتدائي[عدل المصدر]
شركة تتشغل n أشخاص لوظائف مختلفة عددها الكلي n. نحدد متغيرًا الربحية rij ≥ 0 بالنسبة لأي شخص i مأهل للمنصب j ، على سبيل المثال rij تمثل الربح الذي يمكن أن تحققه المؤسسة إذا أسند الشخص i إلى الوظيفة j ،
تكمن المشكلة في تحديد تعيين الأشخاص لمحطات العمل بالكيفية التي تزيد من قيمة الربحية الإجمالية.
نماذج الثمثيل[عدل المصدر]
الثمثيل ببيان ثنائي[عدل المصدر]
يمكن تمثيل هذه المشكلة بواسطة بيان ثنائي (G(U,V,E، تكون فيه مجموعة الرؤوس U هي الأشخاص ومجموعة الرؤوس V هي مناصب الشغل ، أما ثقل كل ضلع (w(ui,vj فيمثل الربحية.
تتمثل المهمة هنا في العثور على الإقتران في البيان الثنائي ذا أقصى مجموع أثقال الأضلاع.
الثمثيل بمصفوفة[عدل المصدر]
يمكن كذلك تمثيل المشكلة بواسطة مصفوفة حدوث R حيث يمثل كل سطر شخصًا ويمثل كل عمود منصبا ، عناصر المصفوفة تساوي rij
الحل الأمثل هنا يتمثل في العثور على مجموعة من العناصر rij ليس لها أي خط ولا عمود مشترك في المصفوفة R ومجموعهم المتراكم له أكبر قيمة ممكنة ، و هذا يتناسب مع الطرح الشكلي لمسألة برمجة خطية
خوارزميات الحل الأمثل[عدل المصدر]
يمكن الحصول على الحل الأمثل بواسطة تخصيص أيّ خوارزميات البرمجة الخطية ، لكن أول طريقة تستغرق زمنا كثير الحدود قطعي لحل هذه المسألة هي طريقة كوهن المعروفة باسم الخوارزمية المجرية[1]
صنف التعقيد[عدل المصدر]
لم تذكر مشكلة الانساد الأمثل تحت صيغتها الخام ضمن القائمة الأساسية لمايكل غاري و دايفيد جونسون للمسائل من صنف التعقيد الحسابي NP-كامل[2] ، و نظرا بأن الخوارزمية المجرية تسمح حلّها خلال زمن كثير الحدود قإن هذه المسألة تنتمي إلى صنف التعقيد P
مراجع[عدل المصدر]
.mw-parser-output .reflist{font-size:90%;margin-bottom:0.5em;list-style-type:decimal;overflow-y:auto;max-height:300px}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}@media print{.mw-parser-output .reflist{overflow-y:visible!important;max-height:none!important}}
^ KUHN, Harold W. The Hungarian method for the assignment problem. Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97 نسخة محفوظة 26 مارس 2019 على موقع واي باك مشين.
^ Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979
بوابة علم الحاسوب
بوابة رياضيات
هذه الصفحة مقالة مختارة اعتبارا من نسخة (قارن بالنسخة الحالية · انظر صفحة النقاش والتصويت)ضبط استنادي
LCCN: sh00004835' |
مصدر HTML المعروض للمراجعة الجديدة (new_html) | '<div class="mw-parser-output"><p><b>مشكلة الاسناد</b> أو <b>مشكلة الاسناد الأمثل</b> عرفت منذ بداية علم <a href="/wiki/%D8%A8%D8%AD%D9%88%D8%AB_%D8%A7%D9%84%D8%B9%D9%85%D9%84%D9%8A%D8%A7%D8%AA" title="بحوث العمليات">بحوث العمليات</a> و لها تطبيقات عملية جد مطلوبة.
</p>
<div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="ar" dir="rtl"><h2 id="mw-toc-heading">محتويات</h2><span class="toctogglespan"><label class="toctogglelabel" for="toctogglecheckbox"></label></span></div>
<ul>
<li class="toclevel-1 tocsection-1"><a href="#مثال_ابتدائي"><span class="tocnumber">1</span> <span class="toctext">مثال ابتدائي</span></a></li>
<li class="toclevel-1 tocsection-2"><a href="#نماذج_الثمثيل"><span class="tocnumber">2</span> <span class="toctext">نماذج الثمثيل</span></a>
<ul>
<li class="toclevel-2 tocsection-3"><a href="#الثمثيل_ببيان_ثنائي"><span class="tocnumber">2.1</span> <span class="toctext">الثمثيل ببيان ثنائي</span></a></li>
<li class="toclevel-2 tocsection-4"><a href="#الثمثيل_بمصفوفة"><span class="tocnumber">2.2</span> <span class="toctext">الثمثيل بمصفوفة</span></a></li>
</ul>
</li>
<li class="toclevel-1 tocsection-5"><a href="#خوارزميات_الحل_الأمثل"><span class="tocnumber">3</span> <span class="toctext">خوارزميات الحل الأمثل</span></a></li>
<li class="toclevel-1 tocsection-6"><a href="#صنف_التعقيد"><span class="tocnumber">4</span> <span class="toctext">صنف التعقيد</span></a></li>
<li class="toclevel-1 tocsection-7"><a href="#مراجع"><span class="tocnumber">5</span> <span class="toctext">مراجع</span></a></li>
</ul>
</div>
<h2><span id=".D9.85.D8.AB.D8.A7.D9.84_.D8.A7.D8.A8.D8.AA.D8.AF.D8.A7.D8.A6.D9.8A"></span><span class="mw-headline" id="مثال_ابتدائي">مثال ابتدائي</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=1" title="عدل القسم: مثال ابتدائي">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h2>
<p>شركة تتشغل <b>n</b> أشخاص لوظائف مختلفة عددها الكلي <b>n</b>. نحدد متغيرًا الربحية <b>r<sub>ij</sub> ≥ 0</b> بالنسبة لأي شخص <b>i</b> مأهل للمنصب <b>j</b> ، على سبيل المثال <b>r<sub>ij</sub></b> تمثل الربح الذي يمكن أن تحققه المؤسسة إذا أسند الشخص <b>i</b> إلى الوظيفة <b>j</b> ،
تكمن المشكلة في تحديد تعيين الأشخاص لمحطات العمل بالكيفية التي تزيد من قيمة الربحية الإجمالية.
</p>
<h2><span id=".D9.86.D9.85.D8.A7.D8.B0.D8.AC_.D8.A7.D9.84.D8.AB.D9.85.D8.AB.D9.8A.D9.84"></span><span class="mw-headline" id="نماذج_الثمثيل">نماذج الثمثيل</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=2" title="عدل القسم: نماذج الثمثيل">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h2>
<div class="thumb tleft"><div class="thumbinner" style="width:222px;"><a href="/wiki/%D9%85%D9%84%D9%81:Optimal_assignment.jpg" class="image"><img alt="Optimal assignment.jpg" src="//upload.wikimedia.org/wikipedia/commons/thumb/8/89/Optimal_assignment.jpg/220px-Optimal_assignment.jpg" decoding="async" width="220" height="266" class="thumbimage" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/89/Optimal_assignment.jpg/330px-Optimal_assignment.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/89/Optimal_assignment.jpg/440px-Optimal_assignment.jpg 2x" data-file-width="448" data-file-height="542" /></a> <div class="thumbcaption"><div class="magnify"><a href="/wiki/%D9%85%D9%84%D9%81:Optimal_assignment.jpg" class="internal" title="كبّر"></a></div></div></div></div>
<h3><span id=".D8.A7.D9.84.D8.AB.D9.85.D8.AB.D9.8A.D9.84_.D8.A8.D8.A8.D9.8A.D8.A7.D9.86_.D8.AB.D9.86.D8.A7.D8.A6.D9.8A"></span><span class="mw-headline" id="الثمثيل_ببيان_ثنائي">الثمثيل ببيان ثنائي</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=3" title="عدل القسم: الثمثيل ببيان ثنائي">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h3>
<p>يمكن تمثيل هذه المشكلة بواسطة <a href="/wiki/%D9%85%D8%AE%D8%B7%D8%B7_%D8%AB%D9%86%D8%A7%D8%A6%D9%8A" title="مخطط ثنائي">بيان ثنائي</a> <b>(G(U,V,E</b>، تكون فيه مجموعة الرؤوس <b>U</b> هي الأشخاص ومجموعة الرؤوس <b>V</b> هي مناصب الشغل ، أما ثقل كل ضلع (<b>w(u<sub>i</sub>,v<sub>j</sub></b> فيمثل الربحية.
</p><p>تتمثل المهمة هنا في العثور على <a href="/wiki/%D8%A7%D9%84%D9%85%D8%B7%D8%A7%D8%A8%D9%82%D8%A9_(%D9%86%D8%B8%D8%B1%D9%8A%D8%A9_%D8%A7%D9%84%D8%B1%D8%B3%D9%88%D9%85_%D8%A7%D9%84%D8%A8%D9%8A%D8%A7%D9%86%D9%8A%D8%A9)" title="المطابقة (نظرية الرسوم البيانية)">الإقتران</a> في البيان الثنائي ذا أقصى مجموع أثقال الأضلاع.
</p>
<h3><span id=".D8.A7.D9.84.D8.AB.D9.85.D8.AB.D9.8A.D9.84_.D8.A8.D9.85.D8.B5.D9.81.D9.88.D9.81.D8.A9"></span><span class="mw-headline" id="الثمثيل_بمصفوفة">الثمثيل بمصفوفة</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=4" title="عدل القسم: الثمثيل بمصفوفة">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h3>
<pre>يمكن كذلك تمثيل المشكلة بواسطة مصفوفة حدوث <b>R</b> حيث يمثل كل سطر شخصًا ويمثل كل عمود منصبا ، عناصر المصفوفة تساوي <b>r<sub>ij</sub></b>
</pre>
<p>الحل الأمثل هنا يتمثل في العثور على مجموعة من العناصر <b>r<sub>ij</sub></b> ليس لها أي خط ولا عمود مشترك في المصفوفة <b>R</b> ومجموعهم المتراكم له أكبر قيمة ممكنة ، و هذا يتناسب مع الطرح الشكلي لمسألة <a href="/wiki/%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%AE%D8%B7%D9%8A%D8%A9" title="برمجة خطية">برمجة خطية</a>
</p>
<h2><span id=".D8.AE.D9.88.D8.A7.D8.B1.D8.B2.D9.85.D9.8A.D8.A7.D8.AA_.D8.A7.D9.84.D8.AD.D9.84_.D8.A7.D9.84.D8.A3.D9.85.D8.AB.D9.84"></span><span class="mw-headline" id="خوارزميات_الحل_الأمثل">خوارزميات الحل الأمثل</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=5" title="عدل القسم: خوارزميات الحل الأمثل">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h2>
<p>يمكن الحصول على الحل الأمثل بواسطة تخصيص أيّ خوارزميات <a href="/wiki/%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%AE%D8%B7%D9%8A%D8%A9" title="برمجة خطية">البرمجة الخطية</a> ، لكن أول طريقة تستغرق زمنا <a href="/wiki/%D8%AA%D8%B9%D9%82%D9%8A%D8%AF_%D8%A7%D9%84%D9%88%D9%82%D8%AA" title="تعقيد الوقت">كثير الحدود قطعي</a> لحل هذه المسألة هي طريقة <a href="/wiki/%D9%87%D8%A7%D8%B1%D9%88%D9%84%D8%AF_%D8%AF%D8%A8%D9%84%D9%8A%D9%88_%D9%83%D9%88%D9%87%D9%86" title="هارولد دبليو كوهن">كوهن</a> المعروفة باسم <a href="/wiki/%D8%A7%D9%84%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A7%D9%84%D9%85%D8%AC%D8%B1%D9%8A%D8%A9" title="الخوارزمية المجرية">الخوارزمية المجرية</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1">[1]</a></sup>
</p>
<h2><span id=".D8.B5.D9.86.D9.81_.D8.A7.D9.84.D8.AA.D8.B9.D9.82.D9.8A.D8.AF"></span><span class="mw-headline" id="صنف_التعقيد">صنف التعقيد</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=6" title="عدل القسم: صنف التعقيد">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h2>
<p>لم تذكر مشكلة الانساد الأمثل تحت صيغتها الخام ضمن القائمة الأساسية لمايكل غاري و <a href="/wiki/%D8%AF%D8%A7%D9%8A%D9%81%D9%8A%D8%AF_%D8%AC%D9%88%D9%86%D8%B3%D9%88%D9%86_(%D8%B9%D8%A7%D9%84%D9%85)" title="دايفيد جونسون (عالم)">دايفيد جونسون</a> للمسائل من صنف التعقيد الحسابي NP-كامل<sup id="cite_ref-2" class="reference"><a href="#cite_note-2">[2]</a></sup> ، و نظرا بأن الخوارزمية المجرية تسمح حلّها خلال زمن كثير الحدود قإن هذه المسألة تنتمي إلى <a href="/wiki/%D9%83%D8%AB%D9%8A%D8%B1_%D8%AD%D8%AF%D9%88%D8%AF" class="mw-redirect" title="كثير حدود">صنف التعقيد P</a>
</p>
<h2><span id=".D9.85.D8.B1.D8.A7.D8.AC.D8.B9"></span><span class="mw-headline" id="مراجع">مراجع</span><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&section=7" title="عدل القسم: مراجع">عدل المصدر</a><span class="mw-editsection-bracket">]</span></span></h2>
<style data-mw-deduplicate="TemplateStyles:r56810696">.mw-parser-output .reflist{font-size:90%;margin-bottom:0.5em;list-style-type:decimal;overflow-y:auto;max-height:300px}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}@media print{.mw-parser-output .reflist{overflow-y:visible!important;max-height:none!important}}</style><div class="reflist">
<div class="mw-references-wrap"><ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">KUHN, Harold W. The Hungarian method for the assignment problem. <a rel="nofollow" class="external text" href="https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109">Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190326192011/https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800020109">نسخة محفوظة</a> 26 مارس 2019 على موقع <a href="/wiki/%D9%88%D8%A7%D9%8A_%D8%A8%D8%A7%D9%83_%D9%85%D8%B4%D9%8A%D9%86" title="واي باك مشين">واي باك مشين</a>.</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman ed 1979</span>
</li>
</ol></div></div>
<ul class="bandeau-portail إعلام" id="bandeau-portail">
<li class="bandeau-portail-element"><span class="bandeau-portail-icone" style="margin-right:1em"><a href="/wiki/%D8%A8%D9%88%D8%A7%D8%A8%D8%A9:%D8%B9%D9%84%D9%85_%D8%A7%D9%84%D8%AD%D8%A7%D8%B3%D9%88%D8%A8" title="بوابة:علم الحاسوب"><img alt="أيقونة بوابة" src="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Desktop_computer_clipart_-_Yellow_theme.svg/32px-Desktop_computer_clipart_-_Yellow_theme.svg.png" decoding="async" width="32" height="23" class="noviewer" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Desktop_computer_clipart_-_Yellow_theme.svg/48px-Desktop_computer_clipart_-_Yellow_theme.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/d7/Desktop_computer_clipart_-_Yellow_theme.svg/64px-Desktop_computer_clipart_-_Yellow_theme.svg.png 2x" data-file-width="281" data-file-height="203" /></a></span><span class="bandeau-portail-texte"><a href="/wiki/%D8%A8%D9%88%D8%A7%D8%A8%D8%A9:%D8%B9%D9%84%D9%85_%D8%A7%D9%84%D8%AD%D8%A7%D8%B3%D9%88%D8%A8" title="بوابة:علم الحاسوب">بوابة علم الحاسوب</a></span></li>
<li class="bandeau-portail-element"><span class="bandeau-portail-icone" style="margin-right:1em"><a href="/wiki/%D8%A8%D9%88%D8%A7%D8%A8%D8%A9:%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A7%D8%AA" title="بوابة:رياضيات"><img alt="أيقونة بوابة" src="//upload.wikimedia.org/wikipedia/commons/thumb/2/26/Nuvola_apps_edu_mathematics-ar.svg/32px-Nuvola_apps_edu_mathematics-ar.svg.png" decoding="async" width="32" height="21" class="noviewer" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/26/Nuvola_apps_edu_mathematics-ar.svg/48px-Nuvola_apps_edu_mathematics-ar.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/26/Nuvola_apps_edu_mathematics-ar.svg/64px-Nuvola_apps_edu_mathematics-ar.svg.png 2x" data-file-width="190" data-file-height="124" /></a></span><span class="bandeau-portail-texte"><a href="/wiki/%D8%A8%D9%88%D8%A7%D8%A8%D8%A9:%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A7%D8%AA" title="بوابة:رياضيات">بوابة رياضيات</a></span></li></ul>
<div id="FC-editnotice"></div>
<div class="إعلام plainlinks noprint" id="fa-box" style="text-align:center;margin:5px auto;padding:.3em;"><div class="صورة" style="display:inline"><img alt="Symbol star gold.svg" src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Symbol_star_gold.svg/25px-Symbol_star_gold.svg.png" decoding="async" width="25" height="26" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Symbol_star_gold.svg/38px-Symbol_star_gold.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Symbol_star_gold.svg/50px-Symbol_star_gold.svg.png 2x" data-file-width="180" data-file-height="185" /></div> <div style="display:inline">هذه الصفحة <a href="/wiki/%D9%88%D9%8A%D9%83%D9%8A%D8%A8%D9%8A%D8%AF%D9%8A%D8%A7:%D9%85%D9%82%D8%A7%D9%84%D8%A7%D8%AA_%D9%85%D8%AE%D8%AA%D8%A7%D8%B1%D8%A9" title="ويكيبيديا:مقالات مختارة">مقالة مختارة</a> اعتبارا من <a class="external text" href="https://ar.wikipedia.org/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&oldid=">نسخة </a> <span style="font-size:80%">(<a class="external text" href="https://ar.wikipedia.org/w/index.php?title=%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&oldid={{{نسخة}}}&diff=cur">قارن بالنسخة الحالية</a> <b>·</b> انظر <a href="/wiki/%D9%86%D9%82%D8%A7%D8%B4:%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF" title="نقاش:مسألة الإسناد">صفحة النقاش</a> <a href="/w/index.php?title=%D9%88%D9%8A%D9%83%D9%8A%D8%A8%D9%8A%D8%AF%D9%8A%D8%A7:%D8%AA%D8%B1%D8%B4%D9%8A%D8%AD%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D9%82%D8%A7%D9%84%D8%A7%D8%AA_%D8%A7%D9%84%D9%85%D8%AE%D8%AA%D8%A7%D8%B1%D8%A9/%D9%85%D8%B3%D8%A3%D9%84%D8%A9_%D8%A7%D9%84%D8%A5%D8%B3%D9%86%D8%A7%D8%AF&action=edit&redlink=1" class="new" title="ويكيبيديا:ترشيحات المقالات المختارة/مسألة الإسناد (الصفحة غير موجودة)">والتصويت</a>)</span></div></div><div role="navigation" class="navbox authority-control" aria-labelledby="ضبط_استنادي" style="padding:1px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th id="ضبط_استنادي" scope="row" class="navbox-group" style="width:1%"><a href="/wiki/%D8%B6%D8%A8%D8%B7_%D8%A7%D8%B3%D8%AA%D9%86%D8%A7%D8%AF%D9%8A" title="ضبط استنادي">ضبط استنادي</a></th><td class="navbox-list navbox-odd" style="text-align:right;border-right-width:2px;border-right-style:solid;width:100%;padding:0px;text-align:left;"><div style="padding:0em 0.25em">
<ul><li><a href="/wiki/%D8%B1%D9%82%D9%85_%D8%A7%D9%84%D8%B6%D8%A8%D8%B7_%D9%81%D9%8A_%D9%85%D9%83%D8%AA%D8%A8%D8%A9_%D8%A7%D9%84%D9%83%D9%88%D9%86%D8%BA%D8%B1%D8%B3" title="رقم الضبط في مكتبة الكونغرس">LCCN</a>: <span class="uid"><a rel="nofollow" class="external text" href="http://id.loc.gov/authorities/subjects/sh00004835">sh00004835</a></span></li></ul>
</div></td></tr></tbody></table></div></div>' |
ما إذا كان التعديل قد تم عمله من خلال عقدة خروج تور (tor_exit_node) | false |
طابع زمن التغيير ليونكس (timestamp) | 1648719081 |
