1-مقدمه
سيستمهاي پيچيده اجتماعي تعداد زيادي از مسائل داراي طبيعت تركيباتي1 را پيش روي ما قرار ميدهند. مسير كاميونهاي حمل و نقل بايد تعيين شود، انبارها يا نقاط فروش محصولات بايد جايابي شوند، شبكههاي ارتباطي بايد طراحي شوند، كانتينرها بايد بارگيري شوند، رابطهاي راديويي ميبايست داراي فركانس مناسب باشند، مواد اوليه چوب، فلز، شيشه و چرم بايد به اندازههاي لازم بريده شوند؛ از اين دست مسائل بيشمارند. تئوري پيچيدگي به ما مي گويد كه مسائل تركيباتي اغلب پلينوميال2 نيستند. اين مسائل در اندازههاي كاربردي و عملي خود به قدري بزرگ هستند كه نميتوان جواب بهينه آنها را در مدت زمان قابل پذيرش به دست آورد. با اين وجود، اين مسائل بايد حل شوند و بنابراين چارهاي نيست كه به جوابهاي زير بهينه3 بسنده نمود به گونهاي كه داراي كيفيت قابل پذيرش بوده و در مدت زمان قابل پذيرش به دست آيند.
چندين رويكرد براي طراحي جوابهاي با كيفيت قابل پذيرش تحت محدوديت زماني قابل پذيرش پيشنهاد شده است. الگوريتمهايي هستند كه ميتوانند يافتن جوابهاي خوب در فاصله مشخصي از جواب بهينه را تضمين كنند كه به آنها الگوريتمهاي تقريبي ميگويند. الگوريتمهاي ديگري هستند كه تضمين ميدهند با احتمال بالا جواب نزديك بهينه توليد كنند كه به آنها الگوريتمهاي احتمالي گفته ميشود. جداي از اين دو دسته، ميتوان الگوريتمهايي را پذيرفت كه هيچ تضميني در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتايج آنها، به طور متوسط بهترين تقابل كيفيت و زمان حل براي مسئله مورد بررسي را به همراه داشتهاند. به اين الگوريتمها، الگوريتمهاي هيوريستيك گفته ميشود.
سيستمهاي پيچيده اجتماعي تعداد زيادي از مسائل داراي طبيعت تركيباتي1 را پيش روي ما قرار ميدهند. مسير كاميونهاي حمل و نقل بايد تعيين شود، انبارها يا نقاط فروش محصولات بايد جايابي شوند، شبكههاي ارتباطي بايد طراحي شوند، كانتينرها بايد بارگيري شوند، رابطهاي راديويي ميبايست داراي فركانس مناسب باشند، مواد اوليه چوب، فلز، شيشه و چرم بايد به اندازههاي لازم بريده شوند؛ از اين دست مسائل بيشمارند. تئوري پيچيدگي به ما مي گويد كه مسائل تركيباتي اغلب پلينوميال2 نيستند. اين مسائل در اندازههاي كاربردي و عملي خود به قدري بزرگ هستند كه نميتوان جواب بهينه آنها را در مدت زمان قابل پذيرش به دست آورد. با اين وجود، اين مسائل بايد حل شوند و بنابراين چارهاي نيست كه به جوابهاي زير بهينه3 بسنده نمود به گونهاي كه داراي كيفيت قابل پذيرش بوده و در مدت زمان قابل پذيرش به دست آيند.
چندين رويكرد براي طراحي جوابهاي با كيفيت قابل پذيرش تحت محدوديت زماني قابل پذيرش پيشنهاد شده است. الگوريتمهايي هستند كه ميتوانند يافتن جوابهاي خوب در فاصله مشخصي از جواب بهينه را تضمين كنند كه به آنها الگوريتمهاي تقريبي ميگويند. الگوريتمهاي ديگري هستند كه تضمين ميدهند با احتمال بالا جواب نزديك بهينه توليد كنند كه به آنها الگوريتمهاي احتمالي گفته ميشود. جداي از اين دو دسته، ميتوان الگوريتمهايي را پذيرفت كه هيچ تضميني در ارائه جواب ندارند اما بر اساس شواهد و سوابق نتايج آنها، به طور متوسط بهترين تقابل كيفيت و زمان حل براي مسئله مورد بررسي را به همراه داشتهاند. به اين الگوريتمها، الگوريتمهاي هيوريستيك گفته ميشود.