عنوان پایان‌نامه
بررسی حل مسئله ماز با استفاده از الگوریتم های کار آمد به همراه شبیه سازی ربات میکروموس و اثبات N P کامل بودن آن
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 107.;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79822;کتابخانه پردیس یک فنی شماره ثبت: 107.;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79822
- تاریخ دفاع
- ۰۶ دی ۱۳۹۵
- دانشجو
- خاطره الوندی کوشا
- استاد راهنما
- محمود شعبان خواه
- چکیده
- ماز یک سرگرمی و بازی دوست داشتنی در جهان است. این بازی کاربردهای زیادی در علم دارد ، معمولا برای سنجش توانایی یادگیری موجودات زنده و یا سیستم های هوشمند از مازها استفاده می‌شود. مثلا وقتی موش را برای اولین بار در یک ماز قرار دهیم تا غذای خود را پیدا کند، زمان نسبتا زیادی را صرف این کار خواهد کرد. اما در دفعات بعدی با مرور خاطرات خود شکل ماز را به یاد می‌آورد و سریعتر به مقصد می‌رسد. از طریق اندازه گیری زمان یافتن مسیر در شرایط مختلف، دانشمندان می‌توانند توان یادگیری موش را ارزیابی کنند. پیدا کردن بهترین مسیر یک ماز یکی از موضوعات مورد علاقه ریاضی دانان است. با یافتن کوتاهترین مسیر بین دو نقطه می‌توان هزینه کابل کشی خطوط تلفن، ایجاد راه های ارتباطی بین شهرها و یا حتی تولید مدارهای الکترونیکی را کاهش داد و درک مسایل پیرامون خود را بهبود بخشید. بنابراین حل بهینه ماز مسئله ای مهم و کاربردی است، در این تحقیق الگوریتم های حل ماز و میزان بهینگی الگوریتم ها را بررسی کرده و روش های تولید مسیر ماز را توضیح داده و NP کامل بودن تولید مسیر ماز را اثبات می کنیم.
- Abstract
- The maze is a hobby and interesting game in the world. This game has many application in science, is often used to measure learning ability of living organisms or intelligent systems. For example, when we put a mouse in a maze to find his food, first time it spend a relatively long time for this work. But the next time by navigating the maze recalls his memories and faster to its destination. By measuring the time to find path in different conditions, scientists can assess the learning mouse. Find the best path of a maze is one of the topics of interest to mathematicians. Shortest path between two place can help phone lines and cabling costs, create connections between cities or even the production of electronic circuits. We can improve our understanding of the issues By findingoptimized algorithm. So optimal solution Maze important and practical issue, in this research we review maze solving algorithm and the optimality algorithms and explanation maze generation algorithm and we prove the maze generation algorithm is NP complete.
