الگوریتم جستجو: تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
Yamaha5Bot (بحث | مشارکتها) جز تمیزکاری، + ماژول ابرابزار با استفاده از AWB |
|||
خط ۱:
{{یادکرد دقیق}}
در [[علوم کامپیوتر]] و [[ریاضیات]]، یک '''الگوریتم جستجو'''، الگوریتمی است که یک مسئله را به عنوان ورودی میگیرد و بعد از ارزیابی کردن راه حلهای ممکن، یک راه حل برای آن مسئله
==
در کتاب [[راسل]] این الگوریتمها به شکل زیر
* [[الگوریتمهای ناآگاهانه]]
** [[الگوریتم نخست-پهنا]]
خط ۱۲:
== جستجوی ناآگاهانه ==
یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیت مسئله کاری ندارد. از این رو میتوانند به طور عمومی طراحی شوند و از همان طراحی برای محدودهٔ عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتمهایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونههای کوچک) میباشد. از این رو برای بالا بردن سرعت پردازش
== جستجوی لیست ==
الگوریتمهای جستجوی لیست شاید از
[[الگوریتم graver]] الگوریتم پلهای است که برای لیستهای مرتب نشده استفاده میشود.
[[جدول درهمسازی]] نیز برای جستجوی لیست به کار میرود. به طور متوسط زمان اجرای ثابتی دارد. اما نیاز به فضای اضافه داشته و بدترین زمان اجرای آن از(O(n است.
== جستجوی درختی ==
الگوریتمهای جستجوی درختی، قلب شیوههای جستجو برای دادههای ساخت یافته هستند. مبنای اصلی جستجوی درختی، [[گره]]هایی است که از یک [[ساختمان داده]] گرفته شدهاند. هر عنصر که بخواهد اضافه شود با دادههای موجود در گرههای [[درخت]] مقایسه میشود و به ساختار درخت اضافه میشود. با تغییر ترتیب دادهها و قرار دادن آنها در درخت، درخت با شیوههای مختلفی جستجو میشود. برای مثال سطح به سطح ([[جستجوی نخست-پهنا]]) یا پیمایش معکوس درخت ([[جستجوی نخست-ژرفا]]). از مثالهای دیگر جستجوهای درختی میتوان به [[جستجوی عمقی تکرار شونده]]، [[جستجوی عمقی محدود شده]]، [[جستجوی دوطرفه]]، [[جستجوی هزینه یکنواخت]] اشاره کرد.
== جستجوی گراف ==
بسیاری از مسائل در [[نظریه گراف|نظریهٔ گراف]] میتواند با الگوریتمها ی [[پیمایش درخت]] حل شوند، مثل [[الگوریتم دیکسترا]]، [[الگوریتم کروسکال]]، [[الگوریتم
== جستجوی آگاهانه ==
در یک جستجوی آگاهانه، از نوع خاصی از مسائل به عنوان راهنما استفاده میشود. یک گونهٔ خوب یک جستجوی آگاهانه با کارایی قابل توجهی نسبت به جستجوی ناآگاهانه به وجود میآورد. الگوریتمهای برجستهٔ کمی از جستجوی آگاهانهٔ یک لیست وجود دارد. یکی از این الگوریتمها hash table
== جستجوی خصمانه ==
در یک بازی مثل شطرنج، یک درخت بازی شامل تمام حرکات ممکن توسط هر دو بازیکن و نتایج حاصل از ترکیب این حرکات وجود دارد، و ما میتوانیم این درخت را جستجو کرده و موثرترین استراتژی برای بازی را بیابیم. این چنین مسائلی دارای مشخصهٔ منحصر به فردی هستند. برنامههای بازیهای رایانهای، و همچنین فرمهای هوش مصنوعی مثل
== الگوریتم اف اسکن ==▼
(FSCAN)''' F-SCAN یک الگوریتم
=== تحلیل الگوریتم ===▼
▲==الگوریتم اف اسکن==
الگوریتم F-SCAN مطابق N-Step-SCAN از چسبانکی آرم جلوگیری میکند در صورتی که در الگوریتمهای دیگر مانند
▲(FSCAN)''' F-SCAN یک الگوریتم زمان بندی دیسک است که حرکت آرم و هد دیسک در سرویس دهی درخواستهای خواندن و نوشتن را تعیین میکند. طی روبش تمام درخواستها در صف اول دادهها ی اولیه هستند و تمام درخواستهای جدید در صف دادههای ثانویه قرار داده میشوند. بنا براین سرویس دهی به درخواستهای جدید به تاخیر میافتد تا زمانی که تمام درخواستهای قدیمی تحت پردازش قرار گیرد. هنگامی که روبش پایان مییابد آرم به تمام صف دادههای اولیه برده میشود و دوباره سرتاسر آن شروع میشود.
▲===تحلیل الگوریتم===
▲الگوریتم F-SCAN مطابق N-Step-SCAN از چسبانکی آرم جلوگیری میکند در صورتی که در الگوریتمهای دیگر مانند SSTF، SCAN و C-LOOK چنین امری اتفاق نمیافتد. چسبانکی آرم در الگوریتمهای دیگر وقتی رخ میدهد که هجمهای از درخواستها برای مسیر مشترک موجب میشود تا آرم دیسک توقف پردازش در آن مسیر گردد، از این رو ترجیح داده میشود که هیچ جستجوئی برای درخواستهای آن مسیری که در آن است مورد تایید واقع نشود، از آن جا که F-SCAN درخواستها را به دو صف دادهها جدا میکند، روبرو شدن با درخواستهای جدید به صف دادههای در حال انتظار برده میشود، آرم روبش خود را تا مسیر بیرونی ادامه میدهد و از این رو چسبانکی پیش روی الگوریتم نیست. یک معاوضه آشکار وجود دارد به طوری که درخواستها در صف دادههای در حال انتظار باید انتظار طولانی تر تا برای به اجرا درآوردن بکشند، اما در مبادله F-SCAN برای تمام درخواستهای رضایت بخش تر است.
دیگر متغیرها شامل موارد زیر میشود:
*
*
*
== منابع ==
* [//en.wikipedia.org/w/index.php?title=Search_algorithm الگوریتمهای جستجو] {{نشان زبان|en}}
* Donald Knuth. ''The Art of Computer Programming. Volume ۳: [[الگوریتم مرتبسازی|Sorting]] and Searching''. ISBN 0-201-89685-0.
* {{یادکرد-ویکی
|پیوند= http://en.wikipedia.org/w/index.php?title=FSCAN&oldid=538040925
|عنوان= FSCAN
سطر ۴۹ ⟵ ۵۱:
|بازیابی=}}
== پیوند به بیرون ==
* [http://www.gp-field-guide.org.uk/ A Field Guide to Genetic Programming] by Poli, Langdon, and McPhee. Available as a free PDF, or in printed form from Lulu.com.
* [[:v:en:Uninformed Search Project|Self-Guided Lesson on Uninformed Search]] Go to the Wikiversity and teach yourself to program an uninformed search solution.
|