گسترش ساختمان دادهی خط زمانی برای الگوریتم پالایش نه اولین انه آخرین در محدودیت گسسته

چکیده مقاله

برنامه سازی محدودیتی ابزاری برای حل سریع مسائل ارضای محدودیت مطرح در حوزهی هوش مصنوعی است یک مساله زمانبندی مقید به منبع را می توان به بیان مساله ارضای محدودیت تعبیر نمود نتیجتا از برنامه سازی محدودیتی می توان برای حل مسائل زمانبندی استفاده نمود زمانبندی گسسته حالتی خاص از مسائل زمانبندیست که در آن بیش از یک فعالیت به طور همزمان نمی توانند بر روی یک منبع اجرا شوند حذف تمامی مقادیری از دامنه که منجر به یک راه حل با لحاظ محدودیت گسسته در مساله ارضای محدودیت نمی شوند در حالت کلی NP کامل است با این وجود جهت هرس کردن فضای جستجو الگوریتم های پالایش متنوعی در زمان چندجمله ای معرفی گردیده اند استفاده از درخت دودویی متوازنی به نام tree Θ و پس از آن ساختمان دادهی خط زمان نقش مفیدی در ارایهی الگوریتم های پالایش کارا ایفا نموده اند به علاوه ساختمان دادهی خط زمان با بهره گیری از ویژگی های ساختار اجتماع یافت کارایی زمانی چند نوع الگوریتم پالایش متفاوت برای محدودیت گسسته را که از tree Θ استفاده می نموده اند برای n فعالیت از Θ nlog n به n Θکاهش داده است یکی از الگوریتم های پالایشی محدودیت گسسته که ساختمان دادهی خط زمان بر آن تطبیق نشده است الگوریتم نه اولین انه آخرین می باشد این الگوریتم شرایطی را در نظر می گیرد که امکان پذیر نیست یک فعالیت به عنوان اولین یا آخرین فعالیت نسبت به مجموعه ای از فعالیت ها اجرا شود در این مقاله با استفاده از ساختمان دادهی خط زمان فرایندی خطی برای الگوریتم پالایش نه اولین نه آخرین ارایه می دهیم

کلیدواژه‌ها

نویسندگان

حامد فهیمی

استادیاردانشکده علوم ریاضی و کامپیوتر دانشگاه شهید چمران اهواز،

فهیمی، حامد،1399،گسترش ساختمان دادهی خط زمانی برای الگوریتم پالایش نه اولین انه آخرین در محدودیت گسسته،چهارمین کنفرانس ملی کامپیوتر، فناوری اطلاعات و کاربردهای هوش مصنوعی،اهواز

ارائه‌شده در

مجموعه مقالات پنجمین کنفرانس ملی کامپیوتر، فناوری اطلاعات و کاربردهای هوش مصنوعی15 اسفند 1400 · اهواز