Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > محاسبات نرم > الگوریتم ژنتیک(Genetic Algorithm)


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۳-۲۹-۱۳۸۹, ۰۴:۵۶ بعد از ظهر   #1 (لینک دائم)
عضو جدید
 
آواتار gkhazayeni
 
تاريخ عضويت: اسفند ۱۳۸۸
محل سكونت: تهران
پست ها: 2
تشكرها: 1
0 تشكر در 0 پست
پيش فرض اثبات np-hard

سلام، لطفا کسی می تونه به من راه حلی بدهد که اثبات کنم یک مساله NP-HARD است و برای حل ان نیاز به روشهای Meta hurestic است؟
gkhazayeni آفلاين است   پاسخ با نقل قول

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۳-۳۰-۱۳۸۹, ۰۲:۴۱ قبل از ظهر   #2 (لینک دائم)
Super Moderator
 
آواتار alijy
 
تاريخ عضويت: خرداد ۱۳۸۹
محل سكونت: ارض الله الواسعة
پست ها: 78
تشكرها: 23
250 تشكر در 77 پست
My Mood: Khonsard
پيش فرض

سلام
یکی از معمول ترین روشها برای اثبات NP-hard بودن یک مسئله استفاده از reduction in polynomial time to another np-hard problem هست. این به این معنیه که شما کافیه ثابت کنید که اون مسئله با استفاده از یه الگوریتم دلخواه در زمان polynomial به یکی از مسائل NP-hard شناخته شده تبدیل میشه. بعنوان مثال مسئله برای اثبات NP-hard بودن مسئله کوله پشتی (knapsack problem) کافیه که به هر کدوم از آیتمها یک متغیر boolean اختصاص بدین که فقط میتونه مقدار 0 یا 1 رو بگیره(X1,X2,...). بعد حجم کوله پشتی رو بصورت ثابت C در نظر میگیرید که بنابراین میتونید شرط کوله پشتی رو بصورت X1 + X2 + ... + Xn =< C بنویسید. حالا این دقیقا یه مسئله برنامه ریزی خطی هست که NP-hard بودن اون برای نمونه های دارای متغیرهای باینری (مثل همین مسئله) قبلا اثبات شده.
امیدوارم مفید بوده باشه.
alijy آفلاين است   پاسخ با نقل قول
از alijy تشكر كرده اند:
Astaraki (۰۳-۳۰-۱۳۸۹), neda2 (۰۳-۳۰-۱۳۸۹)
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۹:۴۰ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design