تحقیق کاربرد گراف در هوش مصنوعی

تعداد صفحات: ۳۱ | قابل ویرایش

مقدمه

نظریه گراف شاخه ای از ریاضیات است که درباره ی اشیاء خاصی درریاضی به نام گراف بحث می کند. به صورت شهودی گراف نمودار یا دیاگرافی است شامل تعدادی راس که با یالهایی به هم متصل شده اند. تعریف دقیق تر گراف به این صورت است که گراف مجموعه ای از راس هاست که توسط خانواده ای از زوج های مرتب که همان یالهاست به هم مرتبط شده اند.

یالها بر دو نوع ساده و جهت دار هستند که هر کدام در جای خود کاربرد بسیاری دارد. مثلا اگر صرفا اتصال دو نقطه مانند اتصال تهران و زنجان با کمک آزاد راه مد نظر شما باشد کافیست آن دو شهر را با دو نقطه نمایش داده و اتوبان مزبور را یالی ساده نمایش دهید. اما اگر بین دو شهر جاده ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.

آغاز نظریه ی گراف به سده ی هجدهم بر می گردد. اویلر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله ی پل های کونیگسربگ ابداع کرد، اما رشد و پویایی این نظریه عمدتا مربوط به نیم سده ی اخیر و با رشد علم داده ورزی (انفورماتیک) بوده است.

مهمترین کاربرد گراف مدل سازی پدیده های گوناگون و بررسی بر روی آنهاست. با گراف می توان به راحتی یک نقشه بسیار بزرگ یا شبکه ای عظیم را درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتم های مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و…. را برروی آن اعمال نمود.

نظریه ی گراف یکی از پرکاربرد ترین نظریه ها در شاخه های مختلف علوم مهندسی (مانند عمران)، باستانشناسی (کشف محدوده ی یک تمدن) و هوش مصنوعی و…. است.

تاریخچه

نظریه مجموعه‌ها در اواخر قرن نوزدهم به طور عمده توسط جرج کانتور بنیان گذاشته شد. زمانی که کانتور مفاهیم و استدلالهای جدید و متهورانه خود را منتشر کرد، اهمیت آنها تنها توسط تعداد کمی از ریاضیدانان بزرگ درک شد. اما این نظریه در توسعه بعدی‌اش، تقریباً در تمام شاخه‌های ریاضیات نفوذ کرد و تأثیری عمیق بر گسترش آنها داشت.

بطوری که حتی باعث تغییر نظریه‌های تثبیت شده گردید و ریاضیدانان سعی کردند مفاهیم ریاضی را بر اساس نظریه مجموعه‌ها تعریف کنند. به عنوان مثال می‌توان از تعریف اعداد طبیعی توسط پئانو اشاره کرد.

همچنین توسعه بعضی از نظامهای ریاضی، از قبیل توپولوژی، اساساً به ابزار نظریه مجموعه‌ها وابسته است. از اینها مهم‌تر، نظریه مجموعه‌ها نیرویی متحد کننده بدست داد که به تمام شاخه‌های ریاضیات مبنای مشترک و مفاهیم آنها،وضوح ودقتی تازه بخشیده است.

هنگامی که می‌خواهیم با مجموعه‌ای آشنا شویم می‌توانیم آنها را به سه صورت مورد بررسی قرار دهیم. مطالعه مجموعه‌ها به طور کلی نیاز به آشنایی عمومی با آنها دارد که هر کس که می‌خواهد علوم پایه را مورد مطالعه قرار دهد باید این آشنایی را کسب کند، مطالعه مجموعه‌ها به طور طبیعی و مطالعه مجموعه‌ها به صورت اصل موضوعی. در نظریه مجموعه‌ها دو واژه طبیعی و اصل موضوعی دو واژه متضاد هم می‌باشند.

زمینه های کاری و تحقیقاتی رشته مهندسی کامپیوتر

سخت افزار و معماری کامپیوتر (Hardware & Computer Architecture)

طراحی و ساخت مدارهای منطقی و دیجیتال (Design & Implementation of Digital Logic Circuits)به عنوان مثالهایی از سیستم هایی که شامل مدارهای منطقی می باشند، می توان از سیستم های دیجیتال مانند ساعت های دیجیتال، برد های تبلیغاتی، سیستم های کنترل دیجیتال در اکثر وسایل امروزی، موبایل ها و … نام برد. مسلما بارزترین نوع این سیستم ها کامپیوتر ها هستند.

معماری کامپیوتر (Computer Architecture)

نحوه طراحی و ساخت کامپیوترها و مدارهای کامپیوتری بوسیله اجزای ساده منطقی.

 طراحی و ساخت مدارهای واسط (Design & Implementation of Interface Circuits)نحوه ساخت مدارهایی که بتوانند به کامپیوترها، میکروپروسسورهاو میکروکنترلر ها متصل گردند و وظیفه ای خاص را انجام دهند. (برای مثال کارت صوتی یا کارت مودم)

 طراحی و ساخت سیستم های بلادرنگ (Design & Implementation of Real-time Systems)سیستم های کامپیوتری که در حین انجام چند عمل مختلف، ضمانت می کنند اعمال خاصی در زمانهای مشخص یا به تعداد مشخصی انجام خواهند شد.

هوش مصنوعی  (Artificial Intelligence)

یادگیری ماشین (Machine Learning)

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

شبکه های عصبی (Neural Networks)

روش جدید حل مسایل در هوش مصنوعی بوسیله شبکه ای از واحد های متصل به هم (نورون ها) که هر کدام قابلیت پردازش داده ها، ارتباط با نورون های دیگر و همچنین ایجاد تغییرات در مشخصات شبکه را دارند و این اعمال را در جهت بهینه سازی عملکرد شبکه انجام می دهند. شبکه های عصبی معمولا در مسایلی نظیر بهینه سازی، تخمین توابع، کنترل و… کاربرد دارند.

 پردازش تکاملی ( Processing)

شاخه ای جدید از هوش مصنوعی که با در نظر گرفتن یک یا چند جواب اولیه برای یک مساله، بوجود آوردن جوابهای جدید از جوابهای موجود و انتخاب جوابهای بهتر سعی می کند یک جوابی نسبتا بهینه برای مساله بدست آورد. (برای مثال پیدا کردن ماکزیمم یک تابع چند متغیره که بدست آوردن ماکزیمم آن با روشهای معمولی مانند مشتق گیری بسیار سخت است.)