انواع الگوریتم
انواع الگوریتم search
انواع الگوریتم search در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مساله را به عنوان ورودی میگیرد و بعد از ارزیابی کردن راه حلهای ممکن، یک راه حل برای آن مساله برمی گرداند.مجموعهٔ راه حلهای ممکن برای یک مساله را فضای جستجو مینامند.بعضی از الگوریتمها که با عنوان الگوریتمهای ناآگاهانه شناخته میشوند الگوریتمهایی هستند که از متدهای سادهای برای جستجوی فضای نمونه استفاده میکنند.در حالی که الگوریتمهای آگاهانه با استفاده روشهایی مبتنی بر دانش در بارهٔ ساختار فضای جستجو، میکوشند تا زمان جستجو را کاهش دهند. رده بندی در کتاب راسل این الگوریتمها به شکل زیر رده بندی شدهاند. · الگوریتمهای ناآگاهانه · الگوریتم نخست-پهنا · الگوریتم نخست-ژرفا · الگوریتمهای آگاهانه · الگوریتم نخست-بهترین · الگوریتم مکاشفهای جستجوی ناآگاهانه یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیت مساله کاری ندارد.از این رو میتوانند به طور عمومی طراحی شوند و از همان طراحی برای محدودهٔ عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتمهایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونههای کوچک) میباشد.از این رو برای بالا بردن سرعت پردازش غالبا از الگوریتمهای آگاهانه استفاده میکنند. جستجوی لیست الگوریتمهای جستجوی لیست شاید از ابتدایی ترین انواع الگوریتمهای جستجو باشند.هدف آن پیدا کردن یک عنصر از مجموعهای از کلید هاست(ممکن است شامل اطلاعات دیگری مرتبط با آن کلید نیز باشد). ساده ترین این الگوریتمها، الگوریتم جستجوی ترتیبی است که هر عنصر از لیست را با عنصر مورد نظر مقایسه میکند. جستجوی درختی الگوریتمهای جستجوی درختی، قلب شیوههای جستجو برای دادههای ساخت یافته هستند.مبنای اصلی جستجوی درختی، گرههایی است که از یک ساختمان داده گرفته شدهاند. هر عنصر که بخواهد اضافه شود با دادههای موجود در گرههای درخت مقایسه میشود و به ساختار درخت اضافه میشود.با تغییر ترتیب دادهها و قرار دادن آنها در درخت، درخت با شیوههای مختلفی جستجو میشود. برای مثال سطح به سطح (جستجوی نخست-پهنا) یا پیمایش معکوس درخت (جستجوی نخست-ژرفا).از مثالهای دیگر جستجوهای درختی میتوان به جستجوی عمقی تکرار شونده،جستجوی عمقی محدود شده، جستجوی دوطرفه، جستجوی هزینه یکنواخت اشاره کرد. جستجوی گراف بسیاری ...
انواع الگوریتم مسیریابی
بدیهی است که الگوریتمی بهتر است که صحت عملکرد بالایی داشته باشد و در عین حال ساده باشد، اما چه الگوریتمی قابلیت اتکای خوبی دارد؟ الگوریتمی مناسب است که در گذشت زمان، با تغییر نرمافزارها و سختافزارهای شبکه و تغییر پروتکلها، همچنان مسیریابی درستی ارائه دهد. همچنین مهم است که بعد از یک مدت زمان خاص، الگوریتم مسیریابی به حالتی پایدار برسد و همزمان با آن، مسیریابی بهینهای داشته باشد و در ارسال بستهها عدالت را رعایت کند. الگوریتم کوتاهترین مسیر سادهترین روش مسیریابی، روش کوتاهترین مسیر است. هدف اصلی از این الگوریتم، این است که گراف زیرشبکه را طوری تشکیل بدهیم که در آن هر گره را یک مسیریاب فرض کنیم و هر یال را یک خط ارتباطی میان دو مسیریاب. در این حالت، هر یال یک وزن خواهد داشت و با توجه به الگوریتم کوتاهترین مسیر دایجسترا(8) میتوان کوتاهترین مسیر ممکن را محاسبه کرد. الگوریتم سیلآسا در این روش، هر بسته ورودی که به یک مسیریاب میرسد، از تمام کانالهای خروجی مسیریاب خارج میشود. بدینترتیب تعداد زیادی بسته تکراری وجود خواهد داشت و عملا میزان آن بینهایت خواهد بود. بنابراین باید برای خاتمه این تعداد بستهها راهکاری اندیشید. راهکارهای پیشنهادی برای این روش، استفاده از یک شمارنده گام است. بدین صورت که در سرآیند(9) هر بسته یک شمارنده بگذاریم و در هر گام یک شماره از آن کم کنیم تا به صفر برسد و بسته حذف شود. در این صورت مبدا باید طول شبکه را بداند و در بدترین حالت، طول شبکه را طولانیترین فاصله در نظر بگیرد. یک روش دیگر، استفاده از حالتی نیمهمنطقی است. مسیریاب در این روش، بسته را به تمام کانالهای خروجی نمیفرستد. بلکه به کانالهایی میفرستد که احتمال رسیدن آنها به مقصد وجود دارند. در این صورت اگر بستهای به سمت غرب بخواهد برود، نبایستی از کانالهای شرقی مسیریاب استفاده کرد، مگر اینکه مسیریاب از ساختار شبکه مطلع باشد و بداند که این کانالها به کجا منتهی میشوند. الگوریتم سیلآسا به جز چند مورد خاص، از جمله سیستمهای توزیعی که عملکردهای موازی در آنها نیاز است، کاربرد علمی دیگری ندارد. الگوریتم بردار فاصله در این روش، مسیریابها در خود جدولی (برداری) ذخیره میکنند با عنوان بردار فاصله که در آن بهترین فاصله تا هر مسیریاب دیگر در شبکه را ذخیره میکنند. در این صورت، تصمیمگیری بهتری هنگام مسیریابی اتخاذ میشود. این جدولها با اطلاعات مسیریابهای همسایه بهروز میشود. هر یک از عناصر این جدولها یک درایه دوبخشی دارند که یکی از آنها نشانگر خط خروجی مناسب برای ...
مسیریابی شبکه های کامپیوتری
انواع مسیریابی الگوریتم های مسیریابی در شبکه ادهاک انواع پروتکل های مسیر یابی در شبکه های ad- hocانواع پروتکل های مسیر یابی در شبکه های ad- hoc در شبکه های Mobile Ad hoc عمل مسیر یابی به دلایلی همچون متحرک بودن و نبود سیستم کنترلی متمرکز از اهمیت بالایی بر خوردار بوده و مطالعه و بررسی بیشتری را می طلبد . قبل از بررسی این پروتکل ها باید توجه کنیم که هدف از الگوریتم ها و استراتژی های مسیریابی جدید کاهش سربار ناشی از مسیریابی در کل شبکه , یافتن مسیرهای کوتاه تر و انتقال صحیح داده ها و اطلاعات می باشد.تقسیم بندی های مختلفی در مورد پروتکل های مسیر یابی شبکه های Mobile ad hoc وجود دارد که از این میان می توان به 2 نوع زیر اشاره کرد:تقسیم بندی اول : Pro active(Table driven) Reactive(On demand) Hybrid(Table driven & On demand)هر کدام از این انواع خود شامل پروتکل هایی هستند که در زیر اشاره شده است:تقسیم بندی دوم: Flat routing protocols Hierarchal routing approaches GPS Augmented geographical routing approachesدر اینجا به توضیحاتی در مورد پروتکل های تقسیم بندی اول می پردازیم:1.Table driven Pro active - در پروتکلهای از این نوع , node ها مدام در حال جستجوی اطلاعات مسیر یابی جدید درون شبکه هستند به صورتی که حتی با تغییر مکان node ها در صورت نیاز به راحتی می توان مسیر مناسبی را یافته و برای ارسال و دریافت اطلاعات بین هر دو node ی استفاده کرد . به عبارت بهتر می توان گفت که در این شبکه ها مسیر ها از قبل موجود هستند.و به محض آنکه node ی اقدام به ارسال داده به node دیگری کند قادر خواهد بود مسیر موجود را از روی اطلاعات از قبل جمع آوری شده شناسایی کرده و مورد استفاده قرار دهد و لذا تاخیری در این مورد متوجه node نیست. DSDV این پروتکل بر مبنای الگوریتم کلاسیک Bellman-Ford بنا شده است.در این حالت هر node لیستی از تمام مقصد هاو نیز تعداد hop ها تا هر مقصد را تهیه می کند.هر مدخل لیست با یک عدد شماره گزاری شده است . برای کم کردن حجم ترافیک ناشی از به روز رسانی مسیر ها در شبکه از incremental packets استفاده می شود.تنها مزیت این پروتکل اجتناب از به وجود آمدن حلقه های مسیر یابی در شبکه های شامل مسیر یاب های متحرک است.بدین ترتیب اطلاعات مسیر ها همواره بدون توجه به این که آیا node در حال حاضر نیاز به استفاده از مسیر دارد یا نه فراهم هستند. معایب پروتکل DSDV نیازمند پارامترهایی از قبیل بازه ی زمانی به روز رسانی اطلاعات و تعداد به روز رسانی های مورد نیاز می باشد. WRP این پروتکل بر مبنای الگوریتم path-finding بنا شده با این استثنا که مشکل count-to-infinity این الگوریتم را برطرف کرده است. در این پروتکل هر node , 4 جدول تهیه می کند جدول فاصله , جدول مسیر یابی , جدول link-cost و جدولی در مورد پیامهایی که ...
انواع روش ها والگوریتم های مسیریابی درشبکه اینترنت
الگوریتم مسیریابی ایستا : هیچ اعتنایی به شرایط توپولوژیکی و ترافیک لحظه ای شبکه نمی شود و معمولاً هر مسیریاب برای هدایت بسته از جداولی استفاده می کند که در صورت وقوع هرگونه مشکل درزیر ساخت ارتباطی شبکه به صورت دستی تنظیم می گردند و در طول زمان ثابت می باشند که ترافیک لحظه ای هم به دلیل سریع بودن الگوریتم متغیر می باشد . الگوریتم مسیریابی پویا : مسیریابی براساس آخرین وضعییت توپولوژیکی و ترافیک شبکه انجام می شود و هرثانیه یکبار بروز می شوند،تصمیم گیری این الگوریتم براساس وضعییت فعلی شبکه می باشد ولی ممکن است به دلیل پیچیدگی بالای این الگوریتم زمان انتخاب بهترین مسیرطولانی شود و نهایتاً به ازدحام بینجامد که جهت رفع این مشکل از تکنیکهای چند پردازنده ای و پردازش موازی استفاده می گردد . الگوریتم متمرکز یا :Link State دراین الگوریتم هرمسیریاب باید5عمل زیر را انجام دهد: 1- آگاهی مسیریاب از اطلاعات کامل زیرساخت ارتباطی شبکه 2-شناسایی تمام مسیریابهای دیگر، ارتباطات بین آنها و هزینه ی هر خط توسط مسیریاب 3-جمع آوری اطلاعات کامل و تشکیل ساختمان داده ی مربوط به هرگراف زیرساخت ارتباطی 4-استفاده از الگوریتم کوتاهترین مسیر نظیر بهترین مسیر موجود بین دومسیریاب (دایجکسترا) 5-محاسبه مسیرهای جدید 1- شناسایی مسیریاب های مجاور : با شروع به کار مسیریاب، اولین کاری که مسیریاب انجام می دهد شناسایی مسیریاب هاي مجاور با ارسال یک بسته ی خاص به نام بسته ی سلام یا Hello Packet روی تمام خروجی های خود می باشد . مسیریاب ضمن پاسخ به این بسته آدرس جهانی خود را اعلام می نمایند و بعد از دریافت بسته های پاسخ ، این اطلاعات را در جدول خود درج می كنند . 2-اندازه گیری هزینه : * اندازه گیری تاخیر هریک از خطوط خروجی توسط هر مسیریاب با ارسال یک بسته ی خاص با نام Echo Packet بر روی تمام خطوط خروجی * پاسخ هر مسیریاب با بسته ی Echo Reply درصورت دریافت بسته ی Echo Packet * در صورت پاسخ دهی به بسته ی Echo یک زمان رفت و برگشت پیش می آید که تاخیر فیزیکی بین دو مسیریاب را به عنوان هزینه مشخص می کند که مسیریاب این زمان را با یک زمان سنج اندازه گیری نموده وبا تقسیم در جدولی درج می کند . * تشخیص مسیر بهینه همانند CF توسط مسیریاب ها و هدایت تمامی بسته ها از شبکه 1 و 2 * تبدیل شدن مسیر CF به بدترین مسیر با گزارش تاخیر و ترافیک بالا در عرض چند ثانیه * انتخاب مسیر بهینه EI با داشتن ترافیک و تاخیر کمتر و هدایت بسته ها از این مسیر * تبدیل دوباره این مسیر به بدترین مسیر با گزارش تاخیر و ترافیک بالا در عرض چند ثانیه ی دیگر * تکرار روند نوسان تا بی نهایت 3- تشکیل بسته Link State Packed هر ...
الگوریتم کلونی مورچگان
بهینهسازی گروه مورچهها یا ACO همانطور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز میتوان مطرح کرد. در این روش(ACo)، مورچههای مصنوعی بهوسیلهٔ حرکت بر روی نمودار مساله و با باقی گذاشتن نشانههایی بر روی نمودار، همچون مورچههای واقعی که در مسیر حرکت خود نشانههای باقی میگذارند، باعث میشوند که مورچههای مصنوعی بعدی بتوانند راهحلهای بهتری را برای مساله فراهم نمایند. همچنین در این روش میتوان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت. این روش که از رفتار مورچهها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد. مقدمه الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچهها حشراتی اجتماعی هستند که در کلونیها زندگی میکنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچهها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچهها دارای نوعی هوشمندی تودهای است که اخیرا مورد توجه دانشمندان قرار گرفته است در دنیای واقعی مورچهها ابتدا به طور تصادفی به این سو و آن سو میروند تا غذا بیابند. سپس به لانه بر میگردند و ردّی از فرومون (Pheromone) به جا میگذارند. چنین ردهایی پس از باران به رنگ سفید در میآیند و قابل رویت اند. مورچههای دیگر وقتی این مسیر را مییابند، گاه پرسه زدن را رها کرده و آن را دنبال میکنند. سپس اگر به غذا برسند به خانه بر میگردند و رد دیگری از خود در کنار رد قبل میگذارند؛ و به عبارتی مسیر قبل را تقویت میکنند. فرومون به مرور تبخیر میشود که از سه جهت مفید است: باعث میشود مسیر جذابیت کمتری برای مورچههای بعدی داشته باشد. از آنجا که یک مورچه در زمان دراز راههای کوتاهتر را بیش تر میپیماید و تقویت میکند هر راهی بین خانه و غذا که کوتاهتر (بهتر) باشد بیشتر تقویت میشود و آنکه دورتر است کمتر.اگر فرومون اصلاً تبخیر نمیشد، مسیرهایی که چند بار طی میشدند، چنان بیش از حد جذّاب میشدند که جستجوی تصادفی برای غذا را بسیار محدود میکردند.وقتی غذای انتهای یک مسیر جذاب تمام میشد رد باقی میماند. لذا وقتی یک مورچه مسیر کوتاهی (خوبی) را ...
دانلود پایان نامه: الگوریتم مسیریابی شبکه های بیسیم ادهاک
عنوان : الگوریتم مسیریابی شبکه های بیسیم ادهاکشرح مختصر : امروزه علم کامپیوتر به حدی پیشرفت کرده که بسیاری از علوم دیگر پیشرفتشان وابسته به علم کامپیوتر می باشد.شبکه های کامپیوتری به حدی پیشرفت کرده اند که توانسته اند جهان را به یک دهکده علمی کوچک تبدیل نمایند.برای برقراری ارتباط بین این شبکه ها نیازمند به یک ستون فقرات می باشیم٬ این شبکه زیر بنایی که از تعداد زیادی مسیریاب تشکیل شده است وظیفه انتقال اطلاعات را دارد. بر روی این مسیریاب ها باید الگوریتم هایی اجرا شوند تا بتوانند بهترین مسیر را برای انتقال اطلاعات در این دهکده را انتخاب کنند. مجموعه مطالبی که در اختیار شما خواننده گرامی است پژوهشی در رابطه با مسیریابی در شبکه های جهانی اینترنت و بررسی الگوریتم های مسیریابی متفاوت ٬تجزیه و تحلیل٬نحوه پیاده سازی این الگوریتم ها به صورت کاربردی می باشد. فهرست : فهرست مطالب عنوان صفحه پیشگفتار تقدیر و تشکّر چکیده مبانی شبکه های بی سیم مقدمه تشریح مقدماتی شبکه های بی سیم و کابلی مبانی شبکه های بیسیم انواع شبکه های بی سیم شبکه های بی سیم، کاربردها، مزایا و ابعاد روش های ارتباطی بی سیم عناصر فعال شبکه های محلی بی سیم مسیر یاب تفاوت یک سوییچ لایه با یک مسیریاب معمولی پروتکل های INTERIOR و EXTERIOR شبکه هایی که با مسیریاب BGP در ارتباطند دو دیدگاه الگوریتم های مسیریابی انواع پروتکل انواع پروتکل Routed انواع پروتکل Routing CLASSFUL ROUTING CLASSLESS ROUTING پروتکل های IP Distance Vector عملکرد پروتکل های Distance Vector پروتکل های IP Link State آگاهی از وضعیت شبکه نحوه ی مسیریابی بصورت استاتیک پروتکل OSPF مقایسه پروتکل OSPF با پروتکل RIP سلسله مراتب تعیین شده برای نواحی در پروتکل OSPF انواع Area وضعیت های اتصال خصوصیات یک شبکه OSPF ID مسیریاب OSPF همسایه یابی OSPF بررسی عملکرد OSPF تایمرهای OSPF انواع LSA در OSPF انواع شبکه های تعریف شده در OSPF برقراری رابطه مجاورت در شبکه های NBMA پیکربندی OSPF در شبکه های Frame Relay کاربرد OSPF در شبکه frame relay pointtomultipoint انواع روترهای OSPF انواع پیام در پروتکل OSPF کاربرد Ipv در پروتکل OSPF عملکرد OSPF در شبکه های IPv مقایسه OSPF V و OSPF V نحوه مسیریابی با پروتکل OSPF مسیر یابی مبتنی بر کیفیت سرویس اهداف مسیریابی کیفیت سرویس پروتکل LINK STATE و OSPF سیستم فازی پیشنهادی توابع عضویت و بانک قوانین شبیه سازی و ارزیابی عملکرد مسیر یابی چند منظوره انتخاب مسیر چند منظوره پروتکل IGMP پروتکل CGMP جستجوی IGMP پروتکل مستقل مسیریابی چند منظوره PIM سبک متراکم PIM سبک پراکنده AutoRP Anycast RP آدرس های چند منظوره ذخیره مسیریابی هوشمند نتیجه ...
الگوریتم و فلوچارت
دانلود کتاب الکترونیکی الگوریتم و فلوچارت مبحث الگوریتم و فلوچارت اساس و پایه برنامه نویسی است . الگوریتم و فلوچارت تنها چیزهایی هستند که به طور کامل میان تمامی زبانهای برنامه نویسی مشترک است . الگوریتم مجموعه ای از دستورالعمل های مشخصی است که مراحل انجام یک کار و یا مسئله را به زبانی دقیق و با جزئیات کافی که چگونگی ترتیب کامل عملیات و کارها را ذکر می کند این عکس تزئینی است برای دانلود بر روی لینک زیر کلیک راست کرده و گزینه save target as را بزنید دانلود کتاب الکترونیکی الگوریتم و فلوچارت
دانلود جزوه و نمونه سوالات طراحی الگوریتم ها
فصل اول: الگوریتم ها شامل : جستجوی ترتیبی-تفاوت شبه کد با c++ -جمع نمودن عناصر آرایه-مرتب سازی تعویضی- ضرب ماتریس ها-جستجوی دودویی- دنباله فیبوناچی کارایی، تحلیل و مرتبه اجرای الگوریتم های اشاره شدهفصل دوم: رهیافت تقسیم و حل رهیافت بالا به پایین- جستجوی دودویی –مرتب سازی ادغامی- مرتب سازی سریع- الگوریتم ضرب ماتریس به روش استراسن- ضرب اعداد صحیح بزرگ و پیچیدگی زمانی در الگوریتم های اشاره شدهفصل سوم:برنامه نویسی پویا الگوریتم فلوید برای محاسبه کوتاهترین مسیرها- برنامه نویسی پویا و مسائل بهینه سازی- ضرب زنجیره ای ماتریس ها- مساله فروشنده دوره گردفصل چهارم: رهیافت حریصانه باقیمانده پول- درخت های پوشای کمینه- الگوریتم پریم- الگوریتم کروسکال- الگوریتم دیکسترا- الگوریتم هافمن- رهیافت حریصانه برای مساله کوله پشتی- برنامه نویسی پویا برای مساله کوله پشتیفصل پنجم: عقب گرد جستجوی اول عمق- جستجوی عقبگرد برای ۴ وزیر- رنگ آمیزی گراف- الگوریتم عقبگرد برای مساله دورهای هامیلتونیدریافت یکجانمونه سوالات درس « طراحی الگوریتم ها »سال تحصیلینیمسال 1پاسخنامهنیمسال 2پاسخنامهتابستانپاسخنامه91-92دریافتدریافت90-91دریافتدریافت89-90دریافتدریافت88-89دریافتدریافت87-88دریافتدریافت86-87دریافتدریافتدریافت85-86دریافتدریافت84-85دریافتدریافت83-84سرفصل های این جزوه عبارتند از:فصل اول: الگوریتم ها شامل : جستجوی ترتیبی-تفاوت شبه کد با c++ -جمع نمودن عناصر آرایه-مرتب سازی تعویضی- ضرب ماتریس ها-جستجوی دودویی- دنباله فیبوناچی کارایی، تحلیل و مرتبه اجرای الگوریتم های اشاره شدهفصل دوم: رهیافت تقسیم و حل رهیافت بالا به پایین- جستجوی دودویی –مرتب سازی ادغامی- مرتب سازی سریع- الگوریتم ضرب ماتریس به روش استراسن- ضرب اعداد صحیح بزرگ و پیچیدگی زمانی در الگوریتم های اشاره شدهفصل سوم:برنامه نویسی پویا الگوریتم فلوید برای محاسبه کوتاهترین مسیرها- برنامه نویسی پویا و مسائل بهینه سازی- ضرب زنجیره ای ماتریس ها- مساله فروشنده دوره گردفصل چهارم: رهیافت حریصانه باقیمانده پول- درخت های پوشای کمینه- الگوریتم پریم- الگوریتم کروسکال- الگوریتم دیکسترا- الگوریتم هافمن- رهیافت حریصانه برای مساله کوله پشتی- برنامه نویسی پویا برای مساله کوله پشتیفصل پنجم: عقب گرد جستجوی اول عمق- جستجوی عقبگرد برای ۴ وزیر- رنگ آمیزی گراف- الگوریتم عقبگرد برای مساله دورهای هامیلتونیدانلود فایل :دانلود کتاب درس طراحی الگوریتم حمید رضا مقسمی به زبان فارسی در این پست با جزوه درس طراحی الگوریتم حمید رضا مقسمی در خدمت شما عزیزان هستیم. این کتاب شامل ۵ فصل است ومولف آن حمیدرضا ...