گسترش ساختمان دادهی خط زمانی برای الگوریتم پالایش نه اولین/نه آخرین در محدودیت گسسته
|
|
|
DOR
|
20.1001.2.9920064087.1399.4.1.3.7
|
نویسنده
|
فهیمی حامد
|
منبع
|
كنفرانس ملي كامپيوتر، فناوري اطلاعات و كاربردهاي هوش مصنوعي - 1399 - دوره : 4 - چهارمین کنفرانس ملی کامپیوتر، فناوری اطلاعات و کاربردهای هوش مصنوعی - کد همایش: 99200-64087
|
|
|
چکیده
|
برنامه سازی محدودیتی ابزاری برای حل سریع مسائل ارضای محدودیت مطرح در حوزهی هوش مصنوعی است. یک مساله زمانبندی مقید به منبع را می توان به بیان مساله ارضای محدودیت تعبیر نمود. نتیجتا از برنامه سازی محدودیتی می توان برای حل مسائل زمانبندی استفاده نمود. زمانبندی گسسته حالتی خاص از مسائل زمانبندیست که در آن بیش از یک فعالیت به طور همزمان نمی توانند بر روی یک منبع اجرا شوند. حذف تمامی مقادیری از دامنه که منجر به یک راه حل با لحاظ محدودیت گسسته در مساله ارضای محدودیت نمی شوند در حالت کلی np-کامل است. با این وجود جهت هرس کردن فضای جستجو الگوریتم های پالایش متنوعی در زمان چندجمله ای معرفی گردیده اند. استفاده از درخت دودویی متوازنی به نام -tree و پس از آن ساختمان دادهی خط زمان نقش مفیدی در ارایهی الگوریتم های پالایش کارا ایفا نموده اند. به علاوه ساختمان دادهی خط زمان با بهره گیری از ویژگی های ساختار اجتماع-یافت کارایی زمانی چند نوع الگوریتم پالایش متفاوت برای محدودیت گسسته را که از -tree استفاده می نموده اند برای n فعالیت از (nlog(n)) به (n) کاهش داده است. یکی از الگوریتم های پالایشی محدودیت گسسته که ساختمان دادهی خط زمان بر آن تطبیق نشده است الگوریتم نه اولین/نه آخرین می باشد. این الگوریتم شرایطی را در نظر می گیرد که امکان پذیر نیست یک فعالیت به عنوان اولین یا آخرین فعالیت نسبت به مجموعه ای از فعالیت ها اجرا شود. در این مقاله با استفاده از ساختمان دادهی خط زمان فرایندی خطی برای الگوریتم پالایش نه اولین/ نه آخرین ارایه می دهیم.
|
کلیدواژه
|
مساله ارضای محدودیت ,برنامه سازی محدودیتی ,زمانبندی، محدودیت گسسته ,ساختمان داده خط زمان ,الگوریتم های پالایش
|
آدرس
|
دانشگاه شهید چمران اهواز،, ایران
|
|
|
|
|
|
|