Page 11 - kahroba42

1402 ناتسمز - 42 هرامش ابرهک - رتویپماک و قرب یسدنهم یصصخت همانلصف

تفای زین هدنیآ رد ًلاامتحا و تهسا هدهشن ادیپ ناهشیارب ،یلوقعم نامز رد ماجنا لباق و عیرهس لح هار نونکات هک 5 NP لئاهسم

عیرس لح هار ل ئاس م ن یا زا ی ک ی ی ارب ط قف رگا ه ک ت س ا هد ش ت ابثا ه تبلا ه ک ،ت س ا رایس ب ی اهدربراک اب ف لتخ م ه لئس م رازه د نچ ل ماش ،د ش د هاوخ ن
یا هلمج دنچ هطبار ،عیرس لح هار زا روظنم ) دنرادن یعیرس لح هار و هدوب هدیچیپ ًلامع لئاسم نیا ؛ دش دهاوخ زین لئاسم هیقب لح ثعاب ،دوش ادیپ
[ 3 ] . )تسا هلئسم یاه یدورو هزادنا اب هلئسم نآ ماجنا نامز نیب
دایز ردق نآ هلئس م نیا نوگانوگ یاه هخس ن عونت ه ک تس ا 6 مات NP لئاس م نیرتدربراکرپ و نیرت مهم زا یکی VRP هیلقن هلیس و یبایریس م هلئس م
و نیققحم هجوت دروم رایسب هزورما هک تسا ریگ نامز و لکشم رایسب ،دهد یم خر نآ رد هک یفلتخم یاه تلاح نایب و اه نآ یدنب هتسد هک تسا
هک یتوافتم یاهدربراک ساسا رب نآ زا یرایسب یاه شرتسگ ،تفرگ رارق یسررب دروم 60 ههد رد هلئسم نیا هک ینامز زا .دریگ یم رارق نادنمشناد

[ 4 ] . دندش قتشم ،دنتشاد یعقاو یایند رد
لئاس م زا یکی .دش اب یم اه هنیزه شهاک و عیانص درکلمع دوبهب رد یس اس ا لماع ،نیمات هریجنز رد لااک لقنو لمح تایلمع و عبانم هنیهب تیریدم
یاه ناکم هلمج زا یددعتم یاهریغتم اب تیعقاو رد هلئسم نیا ؛دشاب یم لااک لقنو لمح یبایریسم هلئسم ،دوش یم حرطم هنیمز نیا رد هک یساسا

.تسا هجاوم لقنو لمح عبانم یاه تیدودحم و ریغتم یاهزاین ،اه نامز ،اه تفاسم ،فلتخم
،یراکتباارف یاه متیروگلا زا یریگ هرهب ا ب و دبای دوبهب نیمأت هریجنز رد لااک لقنو لمح یبایریههسم هک تههسا نیا ام یلههصا فده ،رههضاح شهوژپ رد
تردق و دنوش یم هتخانش هدیچیپ لئاسم یزاس هنیهب رد دربراکرپ یاه شور ناونع هب یراکتباارف یاه متیروگلا .دوش ماجنا تایلمع نیا یزاس هنیهب
،اه تکرش یروآدوس و یرو هر هب رب نآ ریثات و هلئسم نیا یگدیچیپ هب هجوت اب . دنراد تیدودحم و ریغتم دایز دادعت یاراد لئاسم اب ههجاوم رد یدایز
اب ات دنک یم شلات شهوژپ نیا ،نیاربانب ؛تههسا هدههش نیمأت هریجنز رد گرزب شلاچ کی هب لیدبت لااک لقنو لمح یبایریههسم یزاههس هنیهب و هعلاطم

. دیام ن هئارا هلئسم نیا یارب ار یزاس هنی هب یاهراکهار و دهد دوبهب ار لقنو لمح یاه هنیزه و یتایلمع درکلمع ،یراکتباارف یاه متیروگلا زا هدافتسا
هجوت دروم نیمأت هریجن ز و کیتسجل رد رایسب هزورما ،دیلوت هنیزه زا لااک عیزوت هنیزه هجوت لباق مهس تلع هب VRP هیلقن هلیسو یبایریسم هلئسم
دروم ار نآ سپههس و د رک لیدبت هلئههسم نیا یاه هخههسن زا یکی هب ناوت یم ار لااک عیزوت هزوح لئاههسم زا یرایههسب تفگ ناوتب دیاههش .دریگ یم رارق
ثعاب اهلااک لقنو لمح ر د ییاراک دوبهب اریز ،دراد یا هدرتسگ یاهدربراک تامدخ و تعنص یاه شخب رد رتشیب هلئسم نیا هولاع هب ؛داد رارق یسررب

یابقر ربارب رد تبا قر یارب یرتشیب تیلباق یتامدخ و ی تعنص یاه تکرش ددرگ یم ببس و دوش یم اه نآ هدش مامت تمیق رد هجوت لباق ییوج هفرص
دوههس و هداد شرتههس گ ار دوخ یلااک رازاب قیرط نیا زا و هدناههسر نارادیرخ تههسد هب ار دوخ یلااک یرتمک تمیق اب دنناوتب و دنههشاب هتههشاد دوخ
[ 5 ] . دریگب رارق هج وت دروم رایسب هرمزور یگدنز رد هلئسم نیا هک تسا هدش ببس یعقاو یایند رد هلئسم نیا تیمها .دنروآ تسد هب ار یرتشیب
اب قیقد ییاه متیروگلا و دوش یم یدنب ه تس د ت خ س ل ئاس م ءزج ه یلقن ه لیس و ی بایریس م ه لئس م ن وچ هد ش هداد ت اح یض وت رب انب ،رگ ید ف رط زا
شرتسگ هلئسم نیا ی ارب قیقد یاه شور رانک رد یرا کتباارف و یراکتبا یاه شور نتفای هب لیامت ،درادن دوجو هلئسم یارب یا هلمجدنچ یگدیچیپ

رایسب یاه شور ه ک یروط هب هدش ریگارف رایسب اه ش ور ن یا زا هدافتس ا ،ی ص خ ش ی اهرتویپماک ت عرس ش یازفا اب و ه تش ذ گ ه هد رد ص وص خ هب ؛تفای
[ 4 ] ، یرامعتسا تباق ر متیروگلا ، [ 7 ] یلینآ یزاس هیبش ، [ 6 ] هعونمم یوجتسج اه نآ نیرت مهم زا یضعب هک دندش داهنشیپ هلئسم نیا یارب یدایز
ه بش متیروگلا ] ، 11 [ هعونمم یوجتس ج اب هیاس مه نیرت کیدزن یبیکرت ، ] 10 [ هدنکارپ یوجتس ج ، [ 9 ] کیتمم متیروگلا [ 8 ] ، ناگچروم متیروگلا
.دنشاب یم ] 15 [ ریغتم هیاسمه متیروگلا و ] 14 [ یقباطت گرزب یگیاسمه یوجتسج ، ] 13 [ هیاسمه یاهریغتم هدنهاک متیروگلا ، ] 12 [ ییابرنهآ

هب ار اه متیروگلا نیا یلک روط هب ناوت یم هک دننک هئارا هلئسم نیا لح یارب یدایز ییاه متیروگلا ،نیققحم هک تسا هدش ثعاب هدش رکذ یاهدربراک
کی رد هلئسم هنیهب باوج ،دریگ یم رارق هدافتسا دروم کچوک داعبا اب لئاسم یارب هک لوا هتسد رد ؛درک یدنب میسقت ینیمخت و قیقد هتسد ود
یراکتباارف و یراکتبا یاه متیروگلا هتهههسد ود هب زین دوخ ینیمخت و یراکتبا یاه متیروگلا هک درک هجوت د یاب ؛دیآ یم تهههسد هب دایز رایهههسب نامز
ًابیرقت اه باوج ،تسا هتسباو ربراک میمصت هب ،یراکتبا یاه شور فلاخرب ،متیروگلا یارجا نازیم هک یراکتباارف یاه شور رد ؛دنوش یم یدنب میسقت
یاه باوج زا اه شور نیا یاه باوج ًلاومعم هچرگا ؛دنیآ یم تهههسد هب قیقد یاه شور زا رتمک و یراکتبا یاه متی روگلا زا رتهههشیب نامز کی رد

اما ،دنتفین ریگ یلحم یاه هنیهب رد نکمم دح ات هک دننک یم هدافتهههسا ییاهراکهار زا اه متیروگلا زا هنوگ نیا و تهههسا رتهب یراکتبا یاه شور

5 Non deterministic polynomial
6 NP-Complete Problems

www.kahrobaonline.ir