الگوریتم وارونگی در حلقه چند جمله ای کوتاه شده

توضیحات تصویر را اینجا وارد کنید

+ نوشته شده در جمعه بیست و یکم مرداد ۱۴۰۱ ساعت 10:35 توسط علی رضا نقش  | 

فلوچارت while

+ نوشته شده در جمعه بیست و یکم خرداد ۱۴۰۰ ساعت 22:9 توسط علی رضا نقش  | 

الگوریتم های حلقوی محدب

 

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

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

کامپیوتر ابزار بدنه محدب که یک غیر مبهم و کارآمد نمایندگی از شکل محدب مورد نیاز ساخته شده است. پیچیدگی الگوریتم های مربوطه معمولاً بر حسب n ، تعداد نقاط ورودی و گاهی اوقات نیز از نظر ساعت h ، تعداد نقاط موجود در پوسته محدب محاسبه می شود.

 

فهرست

مورد مسطح [ ویرایش ]

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

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

محدود به پیچیدگی محاسباتی [ ویرایش ]

برای مجموعه ای محدود از نقاط در هواپیما ، محدودیت پایین در پیچیدگی محاسباتی برای یافتن پوسته محدب نشان داده شده به عنوان چند ضلعی محدب به راحتی نشان داده شده است برای مرتب سازی با استفاده از کاهش زیر . برای مجموعهx_1 ، \ نقطه ، x_n شماره ها را برای مرتب کردن مجموعه امتیازها در نظر بگیرید 

(x_ {1} ، x_ {1} ^ {2}) ، \ نقطه ، (x_ {n} ، x_ {n} ^ {2})نقاط موجود در هواپیما از آنجا که آنها روی یک پارابولا قرار دارند که یک منحنی محدب است ، به راحتی می توان دریافت که رئوسهای قشر محدب هنگام عبور از مرز ، ترتیب مرتب سازی اعداد را تولید می کنند.

x_1 ، \ نقطه ، x_n. واضح است که برای تبدیل توصیف اعداد به نقاط و سپس استخراج ترتیب مرتب شده آنها ، زمان خطی لازم است. بنابراین ، در حالت کلی ، پوسته محدب از نقاط n نمی تواند سریعتر از مرتب سازی محاسبه شود.

حد استاندارد پایین ( n log n ) برای مرتب سازی در مدل درخت تصمیم گیری محاسبات اثبات شده است ، که در آن فقط مقایسه های عددی اما عملیات حسابی انجام نمی شود. با این حال ، در این مدل ، بدنه محدب به هیچ وجه قابل محاسبه نیست. مرتب سازی نیز نیاز به Ω ( N ورود N ) زمان در درخت تصمیم جبری مدل محاسبه، یک مدل است که بیشتر مناسب برای پوش محدب، و در این مدل پوش محدب نیز Ω نیاز ( N ورود N ) زمان. [1] با این حال، در مدل های ریاضی رایانه ای است که اجازه می دهد تعداد به سرعت بیش از مرتب O ( N ورود به سیستمn ) زمان ، به عنوان مثال با استفاده از الگوریتم های مرتب سازی عدد صحیح ، می توان سریع تر محورهای محدب محور محاسبه کرد: الگوریتم اسکن گراهام برای قشرهای محدب شامل یک مرحله مرتب سازی منفرد است که به دنبال آن مقدار خطی کار اضافی انجام می شود.

الگوریتم های حساس به خروجی بهینه [ ویرایش ]

همانطور که در بالا گفته شد ، پیچیدگی یافتن یک قشر محدب به عنوان تابعی از اندازه ورودی n با O ( n log n ) کمتر است. با این حال ، پیچیدگی برخی از الگوریتم های حلقوی محدب می تواند از نظر اندازه ورودی n و اندازه خروجی h (تعداد نقاط موجود در پوسته) مشخص شود. به این الگوریتم ها الگوریتم های حساس به خروجی گفته می شود . آنها ممکن است در مواردی که h = o ( n ) از نظر الگوریتم Θ ( n log n ) کارایی بیشتری داشته باشند از نظر غیرمتعارف کارایی بیشتری داشته باشند .

محدودیت پایین در بدترین حالت زمان اجرای الگوریتم های حلقوی محدب حساس به خروجی به صورت ω ( n log h ) در حالت مسطح تعیین شد. [1] چندین الگوریتم وجود دارد که به این پیچیدگی بهینه زمان دست می یابند . اولین مورد در سال 1986 توسط کرکپاتریک و سییدل معرفی شد (که آن را " الگوریتم نهایی بدنه محدب " نامیدند ). الگوریتم بسیار ساده تری در سال 1996 توسط Chan ساخته شد و الگوریتم Chan نامیده می شود .

الگوریتم ها [ ویرایش ]

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

  • بسته بندی هدایا ، با نام مستعار جارویس - O ( nh )
    یکی از ساده ترین (اگرچه در بدترین حالت کارآمدترین زمان نیست) الگوریتم های مسطح. ایجاد شده به طور مستقل توسط Chand & Kapur در سال 1970 و RA Jarvis در 1973. این دارای پیچیدگی زمانی O ( nh ) است که در آن n تعداد نقاط موجود در مجموعه است ، و h تعداد امتیازهای پوسته است. در بدترین حالت پیچیدگی Θ ( n 2 ) است.
  • اسکن Graham - O ( n log n )
    یک الگوریتم کمی پیچیده تر اما بسیار کارآمد تر ، منتشر شده توسط رونالد گراهام در سال 1972. اگر امتیاز از قبل توسط یکی از مختصات یا با زاویه به یک بردار ثابت طبقه بندی شده باشد ، الگوریتم زمان O ( n )طول می کشد.
  • Quickhull به
    طور مستقل در 1977 توسط W. Eddy و در 1978 توسط A. Bykat ساخته شد. درست مانندالگوریتم Quicksort ، پیچیدگی زمانی مورد انتظار O ( n log n ) را دارد ، اما ممکن استدر بدترین حالتبه O ( n 2 )منحرف شود.
  • تقسیم و تسخیر - الگوریتم O ( n log n )
    یکی دیگر ازالگوریتم هایO ( n log n ) ، که در سال 1977 توسط آماده سازی و هنگ منتشر شده است. این الگوریتم برای مورد سه بعدی نیز کاربرد دارد.
  • زنجیره یکتایی ، الگوریتم با نام مستعار اندرو - O ( n log n )
    منتشر شده در 1979 توسط AM اندرو. این الگوریتم می تواند به عنوان نوعی از اسکن گراهام مشاهده شود که نقاط مختلف را از طریق مختصات آنها مرتب سازی می کند. وقتی ورودی قبلاً مرتب شده باشد ، الگوریتم زمان O ( n ) را می گیرد.
  • الگوریتم حلقوی محدب افزایشی - O ( n log n )
    منتشر شده در سال 1984 توسط مایکل کالایی.
  • الگوریتم Kirkpatrick-Seidel - O ( n log h )
    اولین الگوریتم حساس به خروجی مطلوب. این الگوریتم تقسیم و تسخیر را با استفاده از تکنیک ازدواج-قبل از فتح و برنامه نویسی خطی کم بعدی اصلاح می کند . توسط کرکپاتریک و سییدل در سال 1986 منتشر شده است.
  • الگوریتم Chan - O ( n log h )
    یک الگوریتم حساس به خروجی ساده تر ایجاد شده توسط Chan در سال 1996. این بسته بندی هدیه را با اجرای یکالگوریتم O ( n log n ) (مانند اسکن گراهام) در زیر مجموعه های کوچک ورودی ترکیب می کند. .

اکتشافی اکلوزوسن [ ویرایش ]

اکتشافی ساده زیر اغلب به عنوان اولین گام در اجرای الگوریتم های حلقوی محدب برای بهبود عملکرد آنها استفاده می شود. این مبتنی بر الگوریتم کارآمد محدب محدب توسط Selim Akl و GT Toussaint ، 1978 است. ایده این است که به سرعت بسیاری از نکات را که به هر حال بخشی از پوسته محدب نمی شوند ، حذف کرد. این روش بر اساس ایده زیر است. دو نقطه را با کمترین و بالاترین مختصات x و دو نقطه با کمترین و بالاترین مختصات y را پیدا کنید. (هر یک از این عملیات O ( n ) را می گیرد.) این چهار نقطه چهار ضلعی محدب را تشکیل می دهند، و همه نکاتی که در این چهارگوشه نهفته است (به جز چهار راس که ابتدا انتخاب شده اند) جزئی از قشر محدب نیستند. یافتن همه این نکات که در این چهارگوشه نهفته است نیز O ( n ) است ، و بنابراین ، کل عملیات O ( n ) است. در صورت اختیاری ، نقاط با کمترین و بیشترین مقدار مختصات x- و y و همچنین مواردی که کوچکترین و بزرگترین تفاوت مختصات x- و y را دارند نیز می توانند به چهار ضلعی اضافه شوند و بدین ترتیب یک هشت ضلعی محدب نامنظم را تشکیل می دهند ، که طرفین آن می توانند با خیال راحت دور ریخته شود. اگر امتیاز متغیرهای تصادفی باشد ، برای یک کلاس باریک اما معمولاً با توابع تراکم احتمال ، این پرتاب استمرحله قبل از پردازش باعث می شود که یک الگوریتم حلقوی محدب در زمان مورد انتظار خطی اجرا شود ، حتی اگر بدترین حالت پیچیدگی الگوریتم محدب محدب هم درجه در n باشد. [2]

مشکلات پوسته محدب بر روی خط و پویا [ ویرایش ]

بحث بالا این مورد را در نظر می گیرد که همه نقاط ورودی از قبل شناخته شده باشند. ممکن است یکی دو تنظیم دیگر را در نظر بگیرد. [1]

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

درج یک نقطه ممکن است تعداد شاخک های یک محدب محدب را حداکثر با 1 افزایش دهد ، در حالی که حذف ممکن است یک پوسته محدب محور n را به یک n-1 معکوس تبدیل کند.

نسخه آنلاین ممکن است با O (log n ) در هر نقطه اداره شود ، که از نظر نامتقارن بهینه است. نسخه پویا ممکن است با O (log 2 n ) در هر عملیات اداره شود. [1]

چند ضلعی ساده [ ویرایش ]

مقاله اصلی: پوسته محدب از چند ضلعی ساده

پوسته محدب یک چند ضلعی ساده توسط چند ضلعی به قطعات تقسیم می شود که یکی از آنها چند ضلعی است و بقیه جیب هایی هستند که توسط یک قطعه از مرز چند ضلعی و یک لبه تک شاخ محدود می شوند. اگرچه بسیاری از الگوریتم ها برای مشکل ساخت بدنه محدب یک چند ضلعی ساده منتشر شده اند ، اما اکثر آنها نادرست بوده اند. [3] مک کالوم و آویس اولین الگوریتم صحیح را ارائه دادند. [4] ساده سازی بعدی توسط گراهام و یائو (1983) و لی (1983) تنها از یک ساختار داده پشته استفاده می کند.. الگوریتم آنها چند ضلعی را در جهت عقربه های ساعت طی می کند ، و از سمت چپ ترین محور آن شروع می کند. همانطور که اتفاق می افتد ، یک توالی محدب از مهره ها را روی پشته ذخیره می کند ، مواردی که هنوز مشخص نشده اند که در جیب هستند. در هر مرحله ، الگوریتم مسیری را در امتداد چند ضلعی از بالای پشته تا راس بعدی دنبال می کند که در یکی از دو جیب مجاور بالای پشته قرار ندارد. سپس ، در حالی که دو راس برتر روی پشته به همراه این راس جدید در موقعیت محدب قرار ندارند ، پشته را باز می کند ، قبل از این که در نهایت رأس جدید راس را روی پشته فشار دهید. هنگامی که چرخش در جهت عقربه های ساعت به نقطه شروع می رسد ، الگوریتم ترتیب توالی های پشته را به عنوان بدنه باز می گرداند. [5] [6]

ابعاد بالاتر [ ویرایش ]

تعدادی از الگوریتم ها برای پرونده سه بعدی و همچنین برای ابعاد دلخواه شناخته شده اند. [7] الگوریتم چان برای ابعاد 2 و 3 استفاده می شود و از Quickhull برای محاسبه پوسته محدب در ابعاد بالاتر استفاده می شود. [8]

برای مجموعه های محدودی از نقاط ، پوسته محدب یک چند ضلعی محدب در سه بعد یا به طور کلی یک پلی استوپ محدب برای هر یک از ابعاد است که رئوس های آن برخی از نکات در مجموعه ورودی است. نمایندگی آن به همان اندازه در مورد مسطح ساده نیست. در ابعاد بالاتر ، حتی اگر از رئوس های پلی یپورت محدب نیز مشخص باشد ، ساختن چهره های آن یک کار غیر مهم است ، همانطور که مشکل دوتایی ساخت راس ها با توجه به صورت ها وجود دارد. اندازه اطلاعات صورت خروجی ممکن است از نظر ابعادی بزرگتر از اندازه راس ورودی باشد و حتی در مواردی که ورودی و خروجی هر دو با یک اندازه قابل مقایسه باشند ، الگوریتم های شناخته شده برای بدنه های محدب با ابعاد بالا حساس به خروجی نیستندبه دلیل مشکلاتی با ورودی های انحطاطی و همچنین نتایج میانی پیچیدگی بالا. [9]

منبع

https://en.wikipedia.org/wiki/Convex_hull_algorithms

 

+ نوشته شده در یکشنبه دوازدهم مرداد ۱۳۹۹ ساعت 2:21 توسط علی رضا نقش  | 

وعده زنجیر زدن

 

بیایید به مسئله ذکر شده در فصل مقدمه: تماس های برگشتی : ما یک توالی از کارهای ناهمزمان داریم که یکی پس از دیگری انجام می شوند - به عنوان مثال بارگذاری اسکریپت ها. چگونه می توانیم آن را به خوبی کدگذاری کنیم؟

وعده ها برای انجام این کار چند دستور العمل ارائه می دهند.

در این فصل ما زنجیره وعده را پوشش می دهیم.

به نظر می رسد مانند این:

new Promise(function(resolve, reject) {

  setTimeout(() => resolve(1), 1000); // (*)

}).then(function(result) { // (**)

  alert(result); // 1
  return result * 2;

}).then(function(result) { // (***)

  alert(result); // 2
  return result * 2;

}).then(function(result) {

  alert(result); // 4
  return result * 2;

});

ایده این است که نتیجه از طریق زنجیره .thenدستیاران منتقل می شود.

در اینجا جریان است:

  1. قول اولیه در 1 ثانیه برطرف می شود (*)،
  2. سپس .thenدستگیرنده نامیده می شود (**).
  3. مقدار بازگشتی آن به .thenدسترنج بعدی منتقل می شود(***)
  4. ... و غیره

در نتیجه در امتداد زنجیره ای از گرداننده گذشت، ما می توانیم یک دنباله از دیدن alertتماس: 1→ 2→ 4.

همه چیز کار می کند ، زیرا یک تماس برای promise.thenبازگشت یک وعده ، به طوری که ما می توانیم مورد بعدی را .thenبر روی آن بنامیم.

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

یک خطای کلاسیک Newbie: از لحاظ فنی نیز می توان بسیاری را .thenبه یک قول واحد اضافه کرد. این زنجیر نیست.

مثلا:

let promise = new Promise(function(resolve, reject) {
  setTimeout(() => resolve(1), 1000);
});

promise.then(function(result) {
  alert(result); // 1
  return result * 2;
});

promise.then(function(result) {
  alert(result); // 1
  return result * 2;
});

promise.then(function(result) {
  alert(result); // 1
  return result * 2;
});

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

در اینجا تصویر (آن را با زنجیر بالا مقایسه کنید):

نتیجه همه .thenوعده ها - نتیجه همان وعده است. بنابراین در کد بالا همه alertیکسان را نشان می دهد 1:.

در عمل ، ما به ندرت برای یک وعده به چندین دستکار نیاز داریم. زنجیر زدن بیشتر اوقات استفاده می شود.

بازگشت وعده ها

یک کنترل کننده ، که در آن استفاده می شود ، .then(handler)ممکن است یک وعده را ایجاد کند و برگرداند

در این حالت ، دست اندرکاران دیگر صبر می کنند تا زمان حل و فصل آن ، نتیجه خود را بدست آورند.

برای مثال:




new Promise(function(resolve, reject) {

  setTimeout(() => resolve(1), 1000);

}).then(function(result) {

  alert(result); // 1

  return new Promise((resolve, reject) => { // (*)
    setTimeout(() => resolve(result * 2), 1000);
  });

}).then(function(result) { // (**)

  alert(result); // 2

  return new Promise((resolve, reject) => {
    setTimeout(() => resolve(result * 2), 1000);
  });

}).then(function(result) {

  alert(result); // 4

});

در اینجا اولین .thenنمایش ها 1و بازگشت new Promise(…)در خط (*). پس از یک ثانیه حل می شود ، و نتیجه (استدلال resolve، در اینجا آن است result * 2) به کنترل کننده دوم منتقل می شود .then. آن هندلر در خط است (**)، همین کار را نشان می دهد 2و انجام می دهد.

بنابراین خروجی همانند مثال قبلی است: 1 → 2 4 اما اکنون با 1 ثانیه تأخیر بین alertتماسها.

بازگشت وعده ها به ما امکان می دهد زنجیره ای از اقدامات ناهمزمان ایجاد کنیم.

مثال: loadScript

بیایید از این ویژگی با قول مصور loadScriptتعریف شده در فصل قبل استفاده کنیم تا اسکریپت ها را یک به یک بار بارگیری کنیم ، به ترتیب:

loadScript("/article/promise-chaining/one.js")
  .then(function(script) {
    return loadScript("/article/promise-chaining/two.js");
  })
  .then(function(script) {
    return loadScript("/article/promise-chaining/three.js");
  })
  .then(function(script) {
    // use functions declared in scripts
    // to show that they indeed loaded
    one();
    two();
    three();
  });

این کد را می توان با عملکردهای فلش کمی کوتاه تر کرد:

loadScript("/article/promise-chaining/one.js")
  .then(script => loadScript("/article/promise-chaining/two.js"))
  .then(script => loadScript("/article/promise-chaining/three.js"))
  .then(script => {
    // scripts are loaded, we can use functions declared there
    one();
    two();
    three();
  });

در اینجا هر loadScriptتماس یک وعده را برمی گرداند و .thenوقتی حل می شود بعدی اجرا می شود. سپس بارگذاری فیلمنامه بعدی را آغاز می کند. بنابراین اسکریپت ها یکی پس از دیگری بارگیری می شوند.

ما می توانیم اقدامات ناهمزمان بیشتری را به زنجیره اضافه کنیم. لطفاً توجه داشته باشید که کد هنوز "صاف" است - نه به سمت راست ، رشد می کند. هیچ نشانه ای از "هرم عذاب" وجود ندارد.

از نظر فنی می توانیم .thenمستقیماً به هریک اضافه کنیم loadScript، مانند این:

loadScript("/article/promise-chaining/one.js").then(script1 => {
  loadScript("/article/promise-chaining/two.js").then(script2 => {
    loadScript("/article/promise-chaining/three.js").then(script3 => {
      // this function has access to variables script1, script2 and script3
      one();
      two();
      three();
    });
  });
});

این کد همین کار را انجام می دهد: 3 اسکریپت را به ترتیب دنبال می کند. اما "به راست" رشد می کند. بنابراین ما همان مشکلی را که در رابطه با تماس با ما وجود دارد ، داریم.

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

بعضی اوقات نوشتن .thenمستقیم اشکالی ندارد ، زیرا تابع تو در تو به فضای بیرونی دسترسی دارد. در مثال بالا ترین پاسخ به تماس های تو در تو دسترسی به تمام متغیرهای دارد script1، script2، script3. اما این یک استثناء است نه یک قاعده.

موارد قابل استفاده

به طور دقیق ، ممکن است یک کنترل کننده دقیقاً قول داده نشود ، بلکه یک شیء به اصطلاح "قابل جابجایی" باشد - یک شیء دلخواه که دارای روشی است .then. با همان وعده رفتار خواهد شد.

ایده این است که کتابخانه های شخص ثالث ممکن است اشیاء "سازگار با وعده" را به کار گیرند. آنها می توانند مجموعه گسترده ای از روش ها را داشته باشند ، اما همچنین با وعده های بومی سازگار باشند ، زیرا آنها عملی می شوند .then.

در اینجا نمونه ای از یک شی قابل استفاده وجود دارد:



class Thenable {
  constructor(num) {
    this.num = num;
  }
  then(resolve, reject) {
    alert(resolve); // function() { native code }
    // resolve with this.num*2 after the 1 second
    setTimeout(() => resolve(this.num * 2), 1000); // (**)
  }
}

new Promise(resolve => resolve(1))
  .then(result => {
    return new Thenable(result); // (*)
  })
  .then(alert); // shows 2 after 1000ms

جاوا اسکریپت شیء برگشت داده شده توسط .thenدستگیره را بررسی می کند (*): اگر روشی فراخوانی شده به نام خود داشته باشد then، آنگاه آن متد را برای ارائه توابع بومی resolve، rejectبه عنوان آرگومان (شبیه به مجری) می نامد و منتظر می ماند تا یکی از آنها فراخوانی شود. در مثال بالا resolve(2)بعد از 1 ثانیه گفته می شود (**). سپس نتیجه به پایین زنجیره منتقل می شود.

این ویژگی به ما امکان می دهد بدون نیاز به ارث بردن ، اشیاء سفارشی را با زنجیره های وعده ادغام کنیم Promise.

مثال بزرگتر: واکشی

در برنامه های مقدماتی وعده های برنامه نویسی اغلب برای درخواست های شبکه استفاده می شود. بنابراین بیایید یک مثال گسترده از آن را ببینیم.

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

let promise = fetch(url);

این باعث می شود یک درخواست شبکه به urlوعده داده شود. responseوقتی سرور از راه دور با هدر پاسخ می دهد ، وعده با یک شیء حل می شود ، اما قبل از بارگیری کامل پاسخ .

برای خواندن پاسخ کامل ، باید از این روش استفاده کنیم response.text(): این نوید را برمی گرداند که هنگام بارگیری متن کامل از سرور از راه دور ، با نتیجه آن متن برطرف می شود.

کد زیر درخواستی را وارد کرده user.jsonو متن آن را از سرور بارگیری می کند:

fetch('/article/promise-chaining/user.json')
  // .then below runs when the remote server responds
  .then(function(response) {
    // response.text() returns a new promise that resolves with the full response text
    // when it loads
    return response.text();
  })
  .then(function(text) {
    // ...and here's the content of the remote file
    alert(text); // {"name": "iliakan", "isAdmin": true}
  });

responseشئ بازگشتی fetchهمچنین شامل روش response.json()است که می خواند داده از راه دور و آن را تجزیه به صورت JSON. در مورد ما که این حتی راحت تر است ، بنابراین اجازه دهید به آن تغییر دهید.

ما همچنین برای توابع کوتاه از توابع فلش استفاده خواهیم کرد:

// same as above, but response.json() parses the remote content as JSON
fetch('/article/promise-chaining/user.json')
  .then(response => response.json())
  .then(user => alert(user.name)); // iliakan, got user name

حالا بیایید با کاربر لود شده کاری انجام دهیم.

به عنوان مثال ، می توانیم یک درخواست دیگر به GitHub ارسال کنیم ، نمایه کاربر را بارگذاری کنیم و نماد را نشان دهیم:

// Make a request for user.json
fetch('/article/promise-chaining/user.json')
  // Load it as json
  .then(response => response.json())
  // Make a request to GitHub
  .then(user => fetch(`https://api.github.com/users/${user.name}`))
  // Load the response as json
  .then(response => response.json())
  // Show the avatar image (githubUser.avatar_url) for 3 seconds (maybe animate it)
  .then(githubUser => {
    let img = document.createElement('img');
    img.src = githubUser.avatar_url;
    img.className = "promise-avatar-example";
    document.body.append(img);

    setTimeout(() => img.remove(), 3000); // (*)
  });

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

به خط نگاه کنید (*): چگونه می توانیم کاری کنیم که بعد از اتمام نمایش و حذف شدن نماد ، کاری انجام دهیم ؟ به عنوان مثال ، ما می خواهیم یک فرم برای ویرایش آن کاربر یا چیز دیگری نشان دهیم. در حال حاضر ، هیچ راهی وجود ندارد.

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

مثل این:



fetch('/article/promise-chaining/user.json')
  .then(response => response.json())
  .then(user => fetch(`https://api.github.com/users/${user.name}`))
  .then(response => response.json())
  .then(githubUser => new Promise(function(resolve, reject) { // (*)
    let img = document.createElement('img');
    img.src = githubUser.avatar_url;
    img.className = "promise-avatar-example";
    document.body.append(img);

    setTimeout(() => {
      img.remove();
      resolve(githubUser); // (**)
    }, 3000);
  }))
  // triggers after 3 seconds
  .then(githubUser => alert(`Finished showing ${githubUser.name}`));

این است که، .thenکنترل در خط (*)در حال حاضر بازده new Promise، که می شود تنها پس از تماس از حل و فصل resolve(githubUser)در setTimeout (**). مورد بعدی .thenدر زنجیره منتظر آن است.

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

در آخر ، ما می توانیم کد را به توابع قابل استفاده مجدد تقسیم کنیم:

function loadJson(url) {
  return fetch(url)
    .then(response => response.json());
}

function loadGithubUser(name) {
  return fetch(`https://api.github.com/users/${name}`)
    .then(response => response.json());
}

function showAvatar(githubUser) {
  return new Promise(function(resolve, reject) {
    let img = document.createElement('img');
    img.src = githubUser.avatar_url;
    img.className = "promise-avatar-example";
    document.body.append(img);

    setTimeout(() => {
      img.remove();
      resolve(githubUser);
    }, 3000);
  });
}

// Use them:
loadJson('/article/promise-chaining/user.json')
  .then(user => loadGithubUser(user.name))
  .then(showAvatar)
  .then(githubUser => alert(`Finished showing ${githubUser.name}`));
  // ...

خلاصه

اگر یک دستگیرنده .then(یا catch/finallyمهم نیست) یک قول را برمی گرداند ، بقیه زنجیره تا زمان حل و فصل منتظر می ماند. وقتی این کار را انجام داد ، نتیجه (یا خطای) آن منتقل می شود.

در اینجا یک تصویر کامل وجود دارد:

وظایف

قول: سپس در مقابل گرفتن

آیا این قطعات کد برابر هستند؟ به عبارت دیگر ، آیا آنها در هر شرایطی ، برای هر کارکرد کنترل کننده رفتار می کنند؟

promise.then(f1).catch(f2);

در مقابل:

promise.then(f1, f2);

راه حل

منبع

https://javascript.info/promise-chaining

+ نوشته شده در سه شنبه دهم تیر ۱۳۹۹ ساعت 19:39 توسط علی رضا نقش  | 

ادامه الگوریتم های بهینه سازی کلونی مورچه ها

همگرایی [ ویرایش ]

برای برخی از نسخه های الگوریتم ، می توان اثبات کرد که همگرا است (یعنی می تواند در زمان محدود بهینه جهانی را پیدا کند). اولین شواهد همگرایی برای یک الگوریتم کلونی مورچه ها در سال 2000 ساخته شد ، الگوریتم سیستم مورچه های گرافیکی و بعداً برای الگوریتم های ACS و MMAS. تخمین سرعت نظری همگرایی ، مانند اکثر فراشناختی ، بسیار دشوار است. تجزیه و تحلیل عملکرد یک الگوریتم مستمر کلونی مورچه با توجه به پارامترهای مختلف آن (استراتژی انتخاب لبه ، اندازه گیری فاصله و سرعت تبخیر فرمون) نشان داد که عملکرد و میزان همگرایی آن نسبت به مقادیر پارامتر انتخاب شده و به ویژه به مقدار حساس است. میزان تبخیر فرمون [31] در سال 2004 ، Zlochin و همکارانش[32] نشان داد که الگوریتم های نوع COAC می توانند از روش های نزولی شیب تصادفی ، در سطح انتروپی و برآورد الگوریتم توزیع استفاده کنند . آنها این استعاره ها را به عنوان " الگوی مبتنی بر تحقیق " پیشنهاد دادند.

برنامه ها [ ویرایش ]

مشکل کوله پشتی : مورچه ها قطره کوچکتر عسل را نسبت به قند فراوان تر اما مغذی تر ترجیح می دهند

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

اولین الگوریتم ACO با نام سیستم مورچه ها [25] نامگذاری شده است و هدف آن حل مسئله فروشنده فروشنده مسافر بود که در آن هدف پیدا کردن کوتاهترین سفر دور جهت پیوند یک سری شهرها است. الگوریتم کلی نسبتاً ساده است و براساس مجموعه مورچه ها ساخته شده است که هر یک یکی از سفرهای دور برگشت ممکن را در سطح شهرها ایجاد می کند. در هر مرحله ، مورچه ها طبق برخی قوانین حرکت از یک شهر به شهر دیگر را انتخاب می کنند:

  1. باید دقیقاً یکبار از هر شهر بازدید کند.
  2. یک شهر دوردست شانس کمتری برای انتخاب دارد (دید).
  3. هرچه دنباله فرمون در حاشیه بین دو شهر پررنگ تر باشد ، احتمال انتخاب آن لبه بیشتر خواهد شد.
  4. مورچه ها پس از اتمام سفر خود ، در صورت کوتاه بودن سفره ، فرمون های بیشتری را در تمام لبه های طی شده خود قرار می دهند.
  5. پس از هر تکرار ، مسیرهای فرومون ها تبخیر می شوند.

Aco TSP.svg

برنامه زمانبندی [ ویرایش ]

مشکل مسیریابی وسایل نقلیه [ ویرایش ]

  • مشکل مسیریابی وسایل نقلیه خازنی (CVRP) [46] [47] [48]
  • مشکل مسیریابی وسایل نقلیه چند انبار (MDVRP) [49]
  • مشکل مسیریابی دوره ای خودرو (PVRP) [50]
  • مشکل مسیریابی وسیله نقلیه تحویل تقسیم (SDVRP) [51]
  • مشکل مسیریابی تصادفی وسیله نقلیه (SVRP) [52]
  • مشکل مسیریابی وسایل نقلیه در وانت و تحویل (VRPPD) [53] [54]
  • مشکل مسیریابی خودرو با ویندوز زمان (VRPTW) [55] [56] [57] [58]
  • مشکل مسیریابی وسیله نقلیه وابسته به زمان با ویندوز زمان (TDVRPTW) [59]
  • مشکل مسیریابی وسایل نقلیه با ویندوز زمان و چندین کارگر سرویس (VRPTWMS)

مشکل تکلیف [ ویرایش ]

تنظیم مشکل [ ویرایش ]

مشکل اندازه دستگاه در طراحی فیزیکی نانوالکترونیک [ ویرایش ]

  • بهینه سازی کلونی مورچه (ACO) بهینه سازی مبتنی بر 45 آمپلی فایر تقویت کننده حس مبتنی بر CMOS ، می تواند در زمان بسیار حداقل به راه حلهای بهینه همگرا شود. [72]
  • سنتز مدار برگشت پذیر مبتنی بر بهینه سازی کلونی مورچه (ACO) می تواند بهره وری را به طور قابل توجهی بهبود بخشد. [73]

بهینه سازی و سنتز آنتن ها [ ویرایش ]

ویبراتورهای حلقه برگشت 10 × 10 ، با استفاده از الگوریتم ACO سنتز می شوند [74]

ویبراتورهای Unloopback 10 × 10 ، ساخته شده با استفاده از الگوریتم ACO [74]

برای بهینه سازی شکل آنتن ها می توان از الگوریتم های مورچه استفاده کرد. به عنوان نمونه می توان برچسب های RFID آنتن بر اساس الگوریتم های کلونی مورچه ها (ACO) در نظر گرفت. ، [75] حلقه بازگرداندن حلقه و باز کردن قفل و بازشدن از 10 × 10 [74]

پردازش تصویر [ ویرایش ]

الگوریتم ACO در پردازش تصویر برای تشخیص لبه تصویر و اتصال لبه استفاده می شود. [76] [77]

  • تشخیص لبه:

نمودار در اینجا تصویر 2 بعدی است و مورچه ها از فرمون سپرده شده در یک پیکسل عبور می کنند. حرکت مورچه ها از یک پیکسل به نقطه دیگر با تغییر محلی مقادیر شدت تصویر هدایت می شود. این حرکت باعث می شود بیشترین تراکم فرمون در لبه ها رسوب شود.

موارد زیر مراحل شناسایی لبه با استفاده از ACO است: [78] [79] [80]

مرحله 1: اولیه سازی:
به طور تصادفی جای دهیدک مورچه ها بر روی تصویرI_ {M_ {1} M_ {2} جایی کهK = (M_ {1} * M_ {2}) ^ {\ tfrac {1} {2}. ماتریس فرمون\ tau _ {(من ، ج)با یک مقدار تصادفی اولیه سازی می شوند. چالش اصلی در فرایند اولیه سازی تعیین ماتریس اکتشافی است.

روشهای مختلفی برای تعیین ماتریس اکتشافی وجود دارد. برای مثال زیر ماتریس اکتشافی بر اساس آمار محلی محاسبه شد: آمار محلی در موقعیت پیکسل (i ، j).

\ eta _ {(i، j)} = {\ tfrac {1} {Z}} * Vc * I _ {(i، j)

جایی که من تصویر اندازه است M_ {1} * M_ {2}
Z = \ sum _ {i = 1: M_ {1}} \ sum _ {j = 1: M_ {2}} Vc (I_ {i، j})که یک عامل عادی سازی است

{\ displaystyle {\ fill {تراز شده} Vc (I_ {i، j}) = & f \ left (\ left \ vert I _ {(i-2، j-1)} - I _ {(i + 2، j + 1 )} \ Right \ vert + \ left \ vert I _ {(i-2، j + 1)} - I _ {(i + 2، j-1) \ Right \ vert \ Right. \\ & + \ left \ vert I _ {(i-1، j-2)} - I _ {(i + 1، j + 2)} \ Right \ vert + \ left \ vert I _ {(i-1، j-1)} - I_ (i + 1 ، j + 1) \ Right \ vert \\ & + \ left \ vert I _ {(i-1، j)} - I _ {(i + 1، j) \ Right \ vert + \ left \ vert I _ {(i-1، j + 1)} - I _ {(i-1، j-1)} \ Right \ vert \\ & + \ left. \ left \ vert I _ {(i-1، j +2)} - I _ {(i-1، j-2)} \ Right \ vert + \ left \ vert I _ {(i، j-1)} - I _ {(i، j + 1)} \ Right \ vert \ Right) \ end {تراز شده}}}

f (\ cdot) با استفاده از توابع زیر قابل محاسبه است:
f (x) = \ lambda x، \ quad {\ text {برای x ≥ 0؛ (1)}
f (x) = \ lambda x ^ {2} ، \ quad {\ text {برای x ≥ 0؛ (2)}
f (x) = {\ شروع {موارد} \ sin ({\ frac {\ pi x} {2 \ lambda}}) ، و & {متن {برای ≤ x ≤}} \ lambda {\ متن {؛ (3)}} \\ 0 ، و {\ متن {other}} \ end {موارد}}
f (x) = begin \ شروع {موارد} \ pi x \ sin ({\ frac {\ pi x} {2 \ lambda}}) ، & {\ متن {برای ≤ x ≤}} \ lambda {\ متن ؛ (4)}} \\ 0 ، و {\ متن {other}} \ end {موارد}}
پارامتر\ لامبدا در هر یک از توابع فوق اشکال مربوط به توابع را تنظیم می کند.
مرحله 2 روند ساخت و ساز:
جنبش مورچه بر اساس 4-متصل پیکسل یا 8-متصل پیکسل . احتمال حرکت مورچه با معادله احتمال داده می شودP _ {{x ، y}
مرحله 3 و مرحله 5 فرایند بروزرسانی:
ماتریس فرمون دو بار به روز می شود. در مرحله 3 دنباله مورچه (داده شده توسط\ tau _ {(x ، y) ) به روز شده که در مرحله 5 میزان تبخیر دنباله به روز شده است که توسط معادله زیر آورده شده است.
\ tau _ {new} \ leftarrow (1- \ psi) \ tau _ {old} + \ psi \ tau _ {0، جایی که \ psi  ضریب فروپاشی فرمون است 0 <\ tau <1

مرحله 7 فرآیند تصمیم گیری:
هنگامی که مورچه ها K مسافت ثابت L را برای تکرار N جابجا می کنند ، تصمیم گیری در مورد لبه بودن یا نبودن آن براساس آستانه T بر روی ماتریس فرمون است. آستانه مثال زیر بر اساس روش اوتسو محاسبه می شود .

تصویر Edge با استفاده از ACO شناسایی شده است:
تصاویر زیر با استفاده از توابع مختلف داده شده توسط معادله (1) تا (4) تولید می شوند. [81]

(الف) تصویر اصلی (ب) تصویر با استفاده از معادله (1) (ج) تولید شده با استفاده از معادله (2) (د) تصویر تولید شده با استفاده از معادله (3) (ه) تصویر تولید شده با استفاده از معادله (4) .jpg

  • اتصال لبه: [82] ACO همچنین در الگوریتم های اتصال لبه نیز اثبات شده است.

برنامه های دیگر [ ویرایش ]

مشکل در تعریف [ ویرایش ]

Aco shortpath.svg

با یک الگوریتم ACO ، کوتاه ترین مسیر در یک نمودار ، بین دو نقطه A و B ، از ترکیبی از چندین مسیر ساخته شده است. [104] ارائه دقیق دقیق اینکه الگوریتم چیست یا یک مستعمره مورچه نیست ، کار ساده ای نیست ، زیرا این تعریف ممکن است با توجه به نویسندگان و کاربردها متفاوت باشد. به طور کلی، الگوریتم کلونی مورچه ها به عنوان در نظر گرفته پرجمعیت الگوریتمهای فراابتکاری با هر راه حل ارائه شده توسط یک حرکت مورچه در فضای جستجو. [105] مورچه ها بهترین راه حل ها را علامت گذاری می کنند و مارک های قبلی را برای بهینه سازی جستجوی خود در نظر می گیرند. آنها را می توان به عنوان دیده احتمالاتی چند عامل الگوریتم با استفاده از یک توزیع احتمال به انتقال بین هر تکرار. [106] در نسخه های خود برای مشکلات ترکیبی ، از راه حل های تکراری استفاده می کنند. [107]به گفته برخی از نویسندگان ، چیزی که الگوریتم های ACO را از سایر اقوام متمایز می کند (مانند الگوریتم ها برای برآورد توزیع یا بهینه سازی ذرات ذره) دقیقاً جنبه سازنده آنهاست. در مشکلات ترکیبی ، ممکن است که در نهایت بهترین راه حل پیدا شود ، حتی اگر هیچ مورچه ای اثربخش نباشد. بنابراین ، در مثال مشکل فروشنده مسافرتی ، لازم نیست که مورچه واقعاً کوتاهترین مسیر را طی کند: کوتاهترین مسیر را می توان از قوی ترین بخش بهترین راه حل ها ساخت. با این حال ، این تعریف می تواند در مورد مشکلات در متغیرهای واقعی مشکل ساز باشد ، جایی که هیچ ساختار "همسایگان" وجود ندارد. رفتار جمعی حشرات اجتماعیمنبع الهام محققان است. طیف گسترده ای از الگوریتم ها (برای بهینه سازی یا عدم) به دنبال خود سازماندهی در سیستم های بیولوژیکی منجر به مفهوم " هوش swarm " شده است ، [10] که یک چارچوب کاملاً کلی است که در آن الگوریتم های مورچه ها قرار می گیرند.

الگوریتم های Stigmergy [ ویرایش ]

در عمل تعداد زیادی الگوریتم وجود دارد که ادعا می کنند "مستعمرات مورچه ها" هستند ، بدون اینکه همیشه چارچوب کلی بهینه سازی توسط مستعمرات مورچه های متعارف را به اشتراک بگذارند. [108] در عمل ، استفاده از تبادل اطلاعات بین مورچه ها از طریق محیط (اصولی به نام " تنگی ") به اندازه کافی در نظر گرفته می شود که یک الگوریتم متعلق به کلاس الگوریتم های کلونی مورچه ها باشد. این اصل باعث شده است تا برخی از نویسندگان با ایجاد اصطلاح "ارزش" ، سازماندهی روش ها و رفتارهای مبتنی بر جستجوی غذا ، مرتب سازی لاروها ، تقسیم کار و حمل و نقل تعاونی انجام دهند. [109]

روشهای مرتبط [ ویرایش ]

  • الگوریتم های ژنتیکی (GA) مجموعه ای از راه حل ها را به جای فقط یکی حفظ می کنند. فرایند یافتن راه حلهای برتر از تحولات تقلید می کند ، در حالی که راه حلها در ترکیب یا جهش یافته برای تغییر مجموعه راه حل ها هستند و راه حل هایی با کیفیت پایین تر دور ریخته می شوند.
  • برآورد الگوریتم توزیع (EDA) یک است الگوریتم تکاملی است که جایگزین اپراتورهای تولید مثل سنتی توسط اپراتورهای مدل هدایت می شود. چنین مدل هایی با استفاده از تکنیک های یادگیری ماشینی از جمعیت آموخته شده و به عنوان مدل های گرافیکی احتمالی معرفی می شوند ، که از آنها می توان نمونه های جدیدی را [110] [111] نمونه برداری کرد یا از متقاطع هدایت شده تولید کرد. [112] [113]
  • Annealing شبیه سازی (SA) یک روش بهینه سازی جهانی مرتبط است که با تولید راه حل های همسایه از راه حل فعلی ، فضای جستجو را مرور می کند. همسایه برتر همیشه پذیرفته می شود. یک همسایه فرومایه بر اساس تفاوت کیفیت و یک پارامتر دما احتمالاً پذیرفته می شود. پارامتر دما با پیشرفت الگوریتم برای تغییر ماهیت جستجو اصلاح می شود.
  • بهینه سازی جستجوی واکنشی در ترکیب یادگیری ماشین با بهینه سازی ، با اضافه کردن یک حلقه بازخورد داخلی برای تنظیم دقیق پارامترهای رایگان یک الگوریتم به ویژگی های مسئله ، به عنوان مثال ، و وضعیت محلی پیرامون راه حل فعلی.
  • جستجوی تابو (TS) شبیه به بازپخت شبیه سازی شده در آن است که هر دو با آزمایش جهش های یک راه حل فردی ، فضای محلول را عبور می کنند. در حالی که بازپخت شبیه سازی شده تنها یک راه حل جهش یافته ایجاد می کند ، جستجوی تابو بسیاری از راه حل های جهش یافته را ایجاد می کند و با کمترین تناسب اندام از تولید شده به سمت محلول حرکت می کند. برای جلوگیری از دوچرخه سواری و تشویق حرکت بیشتر از طریق فضای راه حل ، یک لیست تبو از راه حل های جزئی یا کامل نگهداری می شود. حرکت به راه حلی که حاوی عناصر لیست تابو باشد ، ممنوع است که همزمان با طی کردن راه حل ، فضای راه حل به روز می شود.
  • الگوریتم های سیستم ایمنی مصنوعی (AIS) در سیستم ایمنی مهره داران مدل سازی شده اند.
  • بهینه سازی ازدحام ذرات (PSO)، یک هوش گروهی روش
  • قطره آب هوشمند (IWD) ، الگوریتم بهینه سازی مبتنی بر ازدحام مبتنی بر قطرات آب طبیعی که در رودخانه ها جاری است
  • الگوریتم جستجوی گرانشی (GSA)، یک هوش گروهی روش
  • روش خوشه بندی مورچه ها (ACCM) ، روشی که از روش خوشه بندی استفاده می کند و ACO را گسترش می دهد.
  • جستجوی انتشار تصادفی (SDS) ، یک تکنیک جستجوی جهانی و بهینه سازی جهانی احتمالی مبتنی بر عامل است که به بهترین وجه مناسب برای مشکلاتی است که می تواند عملکرد هدف را به چندین عملکرد جزئی جزئی مستقل تجزیه کند

تاریخچه [ ویرایش ]

مخترعین Frans Mysson و Bernard Manderick هستند . پیشگامان این رشته عبارتند از مارکو دوریگو ، لوکا ماریا گامبراردلا . [114]

وقایع الگوریتم های COA

وقایع الگوریتم بهینه سازی کلونی مورچه ها.

  • 1959، پیر پل گراس اختراع نظریه نشانهورزی به توضیح رفتار ساختمان لانه در موریانه ؛ [115]
  • 1983، Deneubourg و همکارانش مورد مطالعه رفتار جمعی از مورچه ها ؛ [116]
  • 1988 ، و میسون ماندریک مقاله ای در مورد خود سازماندهی در بین مورچه ها دارند. [117]
  • 1989 ، کار گاس ، آرون ، دنوبورگ و پاستیل در مورد رفتار جمعی مورچه های آرژانتین ، که ایده الگوریتم های بهینه سازی کلونی مورچه ها را ارائه می دهد. [118]
  • 1989 ، اجرای الگوی رفتاری برای غذا توسط ابلینگ و همکارانش. [119]
  • در سال 1991 ، M. Dorigo سیستم مورچه ها را در پایان نامه دکتری خود پیشنهاد داد (که در سال 1992 منتشر شد [6] ). یک گزارش فنی استخراج شده از پایان نامه و همزمان با تألیف V. Maniezzo و A. Colorni [120] پنج سال بعد منتشر شد. [25]
  • 1994 ، Appleby و Steward از British Telecommunications Plc اولین برنامه را برای شبکه های ارتباطی منتشر کردند [121]
  • 1995 ، گامباردلا و دوریگو مورچه را پیشنهاد کردند ، [122] نسخه اولیه سیستم کلونی مورچه ها به عنوان اولین ارزیابی از سیستم مورچه ها. [25] .
  • 1996 ، گامباردلا و دوریگو سیستم کلونی مورچه ها را پیشنهاد کردند [123]
  • 1996 ، انتشار مقاله درباره سیستم مورچه ها؛ [25]
  • 1996 ، Hoos و Stützle سیستم مورچه های حداکثر دقیقه را اختراع می کنند . [27]
  • 1997 ، Dorigo و Gambardella سیستم کلونی مورچه را که با جستجوی محلی ترکیبی شده بودند ، پیشنهاد کردند. [26]
  • در سال 1997 ، شوودرووود و همكارانش برنامه بهبود يافته را در شبكه هاي ارتباط از راه دور منتشر كردند . [124]
  • در سال 1998 ، Dorigo اولین کنفرانس را به الگوریتم های ACO اختصاص داده است. [125]
  • 1998 ، St ،tzle اجرای موازی اولیه را پیشنهاد می کند . [126]
  • سال 1999 ، گامباردلا ، تایلارد و آگزی پیشنهاد كردند كه نخستین سیستم كلونی چند مورچه برای مشكلات مسیریابی وسایل نقلیه با ویندوز زمان استفاده می شود. [127]
  • 1999 ، Bonabeau ، Dorigo و Theraulaz کتابی را منتشر می کنند که عمدتاً با مورچه های مصنوعی سروکار دارد [128]
  • 2000 ، شماره ویژه مجله سیستم های رایانه ای نسل آینده در الگوریتم های مورچه ها [129]
  • 2000 ، اولین برنامه ها برای برنامه ریزی ، دنباله برنامه ریزی و رضایت از محدودیت ها .
  • سال 2000 ، گوتهار اولین شواهد همگرایی را برای الگوریتم مستعمرات مورچه ها ارائه می دهد [130]
  • 2001 ، اولین استفاده از الگوریتم های COA توسط شرکت ها ( Eurobios و AntOptima ).
  • 2001 ، Iredi و همکارانش اولین الگوریتم چند هدف را منتشر کردند [131]
  • 2002 ، اولین برنامه ها در طراحی برنامه ، شبکه های بیزی؛
  • 2002 ، Bianchi و همکارانش اولین الگوریتم را برای مشکل تصادفی پیشنهاد کردند . [132]
  • 2004 ، Dorigo و Stützle کتاب بهینه سازی مورچه ها را با MIT Press منتشر می کنند [133]
  • 2004 ، Zlochin و Dorigo نشان می دهند که برخی از الگوریتم ها معادل نزول شیب تصادفی ، روش متقابل آنتروپی و الگوریتم ها برای برآورد توزیع هستند [32]
  • 2005 ، اولین بار برای مشکلات تاشو پروتئین .
  • 2012 ، Prabhakar و همکارانش تحقیقات خود را در رابطه با عملکرد مورچه های فردی که به طور پشت سر هم در ارتباط هستند و بدون فرومون ارتباط برقرار می کنند ، منتشر می کنند ، با استفاده از اصول سازمان شبکه های رایانه ای. مدل ارتباط با پروتکل کنترل انتقال مقایسه شده است . [134]
  • 2016 ، اولین برنامه برای طراحی توالی پپتید. [96]
  • 2017 ، ادغام موفقیت آمیز روش تصمیم گیری چند معیاره PROMETHEE در الگوریتم ACO ( الگوریتم HUMANT ). [135]

منبع

https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

+ نوشته شده در یکشنبه بیست و پنجم خرداد ۱۳۹۹ ساعت 19:42 توسط علی رضا نقش  | 

الگوریتم های بهینه سازی کلونی مورچه ها

 

این مقاله لیستی از منابع را شامل می شود ، اما منابع آن ناشناخته مانده اند زیرا استنادهای داخلی کافی ندارند . ( آگوست 2018 )

رفتار مورچه الهام بخش تکنیک بهینه سازی فراتحوری بود

هنگامی که یک مستعمره مورچه ها با انتخاب مسیر رسیدن به غذای خود از طریق دو مسیر مختلف روبرو می شوند که یکی از آنها بسیار کوتاه تر از دیگری است ، انتخاب آنها کاملاً تصادفی است. اما ، كسانی كه از مسیری كوتاه تر استفاده می كنند ، سریعتر به غذا می رسند و بنابراین بیشتر و بیشتر بین مایع مایع آنتیل و غذا می روند. [1]

در تحقیقات علوم رایانه و عملیات رایانه ، الگوریتم بهینه سازی کلونی مورچه ها ( ACO ) یک روش احتمالی برای حل مشکلات محاسباتی است که می توان از طریق نمودارها مسیرهای خوبی را پیدا کرد . مورچه های مصنوعی برای روش های چند عامل الهام گرفته از رفتار مورچه های واقعی هستند. ارتباطات مبتنی بر فرمون از مورچه های بیولوژیکی ، اغلب الگوی غالب مورد استفاده است. [2] ترکیبی از مورچه های مصنوعی و الگوریتم های جستجوی محلی به روش انتخابی برای کارهای بهینه سازی بی شماری تبدیل شده اند که شامل نوعی مواردنمودار ، به عنوان مثال ، مسیریابی وسایل نقلیه و مسیریابی اینترنت . فعالیت های گسترده در این زمینه منجر به کنفرانس هایی شده است که صرفاً به مورچه های مصنوعی و برنامه های تجاری متعددی توسط شرکتهای تخصصی مانند AntOptima اختصاص یافته است .

به عنوان نمونه ، بهینه سازی کلونی مورچه ها [3] کلاس الگوریتم های بهینه سازی است که در مورد اقدامات یک مستعمره مورچه ها مدل شده است . مورچه های مصنوعی (به عنوان مثال عوامل شبیه سازی) با حرکت در فضای پارامتری که تمام راه حل های ممکن را نشان می دهد ، راه حلهای بهینه را پیدا می کنند. مورچه های واقعی فرمون هایی را تعیین می کنند که ضمن کاوش در محیطشان ، یکدیگر را به سمت منابع هدایت می کنند. مورچه ها شبیه سازی شده به طور مشابه موقعیت و کیفیت راه حل های خود را نیز ثبت می کنند ، به طوری که در تکرارهای شبیه سازی بعدی مورچه ها بیشتر راه حل های بهتری پیدا می کنند. [4] یکی از تغییرات این روش الگوریتم زنبورها است که بیشتر شبیه به الگوهای علوفه ایزنبور عسل ، یکی دیگر از حشرات اجتماعی.

این الگوریتم در روش های هوش swarm عضو خانواده الگوریتم های مورچه ها است و برخی از بهینه سازی های فرااگرایی را تشکیل می دهد . در ابتدا که توسط مارکو دوریگو در سال 1992 در پایان نامه دکترا ارائه شده بود ، [5] [6] اولین الگوریتم با هدف جستجوی یک مسیر بهینه در یک نمودار ، بر اساس رفتار مورچه ها که به دنبال مسیری بین مستعمره خود و یک منبع غذایی بودند. . ایده اصلی از زمان متنوع برای حل یک طبقه گسترده تر از مشکلات عددی متنوع است ، و در نتیجه ، چندین مشکل پدید آمده است که جنبه های مختلفی از رفتار مورچه ها را ترسیم می کند. از یک دیدگاه گسترده تر ، ACO یک جستجوی مبتنی بر مدل را انجام می دهد [7]و برخی از شباهت ها را با برآورد الگوریتم های توزیع به اشتراک می گذارد .

منبع

https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

+ نوشته شده در یکشنبه بیست و پنجم خرداد ۱۳۹۹ ساعت 19:32 توسط علی رضا نقش  | 

رنگ آمیزی نمودار

 

با رنگ آمیزی Edge اشتباه گرفته نشود .

یک رنگ آمیزی مناسب از ورق پیترسن با 3 رنگ ، حداقل تعداد ممکن.

در تئوری نمودار ، رنگ آمیزی نمودار یک مورد خاص از برچسب زدن نمودار است . این یک واگذاری برچسب هایی است که به طور سنتی "رنگ" به عناصر یک نمودار در معرض محدودیت های خاص گفته می شود. در ساده ترین شکل آن ، راهی برای رنگ آمیزی رئوس های یک گراف است به گونه ای که هیچ دو راس مجاور از یک رنگ برخوردار نیستند. به این رنگ آمیزی vertex گفته می شود . به طور مشابه ، یک لبه رنگ آمیزی به هر لبه یک رنگ اختصاص می دهد به طوری که هیچ دو لبه مجاور از یک رنگ برخوردار نیستند ، و رنگ آمیزی صورت از یک نمودار مسطح یک رنگ را به هر صورت یا منطقه اختصاص می دهد به طوری که هیچ دو صورت که دارای یک مرز مشترک هستند. همان رنگ

رنگ آمیزی عمودی معمولاً برای معرفی مشکلات مربوط به رنگ آمیزی نمودار استفاده می شود زیرا سایر مشکلات رنگ آمیزی را می توان به عنوان نمونه رنگ آمیزی راس تبدیل کرد. به عنوان مثال ، رنگ آمیزی یک لبه یک نمودار فقط یک نقوش محور از نمودار خط آن است ، و رنگ آمیزی صورت یک نمودار هواپیما فقط یک نقوش محوری از دوتایی آن است . با این حال ، مشکلات رنگ آمیزی غیر vertex اغلب گفته می شود و مورد مطالعه قرار می گیرد . این تا حدی آموزشی است و بخشی نیز به دلیل اینکه بعضی از مشکلات به بهترین شکل در شکل غیر vertex آنها ، مانند مورد رنگ آمیزی لبه ها مورد بررسی قرار می گیرد.

کنوانسیون استفاده از رنگها از رنگ آمیزی کشورها در یک نقشه سرچشمه می گیرد ، جایی که هر صورت به معنای واقعی کلمه رنگی است. این به رنگ آمیزی چهره های گرافیکی تعبیه شده در هواپیما تعمیم یافته است. با دوگانگی مسطح ، رنگ آمیزی راسها به دست می آید و در این شکل به کلیه نمودارها تعمیم می یابد. در بازنمودهای ریاضی و رایانه معمولی است که از چند عدد صحیح مثبت یا غیر منفی به عنوان "رنگ" استفاده کنید. به طور کلی ، می توان از هر مجموعه متناهی به عنوان "مجموعه رنگ" استفاده کرد. ماهیت مشکل رنگ آمیزی بستگی به تعداد رنگ دارد اما نه به آنچه که هستند بستگی دارد.

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

توجه: بسیاری از اصطلاحات به کار رفته در این مقاله در واژه نامه تئوری نمودار تعریف شده است .

 

فهرست

تاریخچه [ ویرایش ]

همچنین ببینید: تاریخچه قضیه چهار رنگ و تاریخ نظریه نمودار

اولین نتایج در مورد رنگ آمیزی نمودار تقریباً منحصراً با نمودارهای مسطح به شکل رنگ آمیزی نقشه ها سروکار دارد . در حالی که تلاش به رنگ یک نقشه از شهرستان از انگلستان، فرانسیس Guthrie بدیهی شمرده حدس چهار رنگ و اشاره کرد که چهار رنگ به رنگ در نقشه به طوری که هیچ مناطق به اشتراک گذاری مرز مشترک همان رنگ دریافت کافی بود. برادر گاتری این سؤال را به معلم ریاضیات خود آگوستوس د مورگان در کالج دانشگاه منتقل کرد ، که در نامه ای به ویلیام همیلتون در سال 1852 اشاره کرد. آرتور کیلی در جلسه انجمن ریاضی لندن این مشکل را مطرح کرد.در سال 1879. در همان سال ، آلفرد کمپ مقاله ای را منتشر کرد که ادعا می کند نتیجه را می گیرد و برای یک دهه مشکل چهار رنگ حل کرد. برای موفقیت خود کمپه عضو انجمن سلطنتی و بعداً رئیس انجمن ریاضی لندن انتخاب شد. [1]

در سال 1890 ، هووود اظهار داشت كه استدلال كمپ اشتباه بوده است. با این حال ، او در این مقاله ، قضیه پنج رنگ را اثبات کرد و گفت که هر نقشه مسطح با استفاده از ایده های کمپ می تواند بیش از پنج رنگ باشد. در قرن بعد ، تعداد زیادی کار و تئوری برای کاهش تعداد رنگها به چهار نفر تدوین شد ، تا اینکه قضیه چهار رنگ بالاخره در سال 1976 توسط کنت اپل و ولفگانگ هاکن ثابت شد . اثبات به عقاید هووود و کمپ برمی گردد و تا حدود زیادی از تحولات مداخله گرانه صرف نظر می کرد. [2] اثبات قضیه چهار رنگ نیز به دلیل اولین اثبات مهم رایانه ای قابل توجه است.

در سال 1912، جورج دیوید Birkhoff معرفی چند جمله ای رنگی به مطالعه مشکلات رنگ آمیزی، که به تعمیم داده شد چند جمله ای Tutte توسط Tutte ، سازه مهم در نظریه گراف جبری . کمپ قبلاً توجه خود را به مورد کلی و غیر مسطح در سال 1879 جلب کرده بود ، [3] و نتایج بسیاری راجع به کلیات رنگ آمیزی نمودارهای مسطح به سطحی با مرتبه بالاتر که در اوایل قرن بیستم دنبال شد.

در سال 1960 ، Claude Berge حدس دیگری را در مورد رنگ آمیزی نمودار ، حدس گرافیکی عالی و کامل ، که در اصل با یک مفهوم اطلاعات نظری به نام ظرفیت خطای صفر گراف ارائه شده توسط شانون ایجاد می شد ، فرموله کرد . این حدس به مدت 40 سال حل نشده باقی ماند ، تا اینکه در سال 2002 به عنوان قضیه نمودار قدرتمند برجسته مشهور توسط چودنوفسکی ، رابرتسون ، سیمور و توماس تاسیس شد.

رنگ آمیزی نمودار از اوایل دهه 1970 به عنوان یک مسئله الگوریتمی مورد مطالعه قرار گرفته است: مشکل شماره کروماتیک یکی از مشکلات 21 NP-کامل کارپ از سال 1972 است ، و تقریباً در همان زمان ، الگوریتم های مختلف نمایی مختلفی مبتنی بر بازگشت به عقب و حذف حذف شد. عود كنترل انقباض زيكوف (1949) . یکی از کاربردهای مهم رنگ آمیزی نمودار ، تخصیص ثبت در کامپایلرها ، در سال 1981 معرفی شد.

منبع

https://en.wikipedia.org/wiki/Graph_coloring

+ نوشته شده در یکشنبه هجدهم خرداد ۱۳۹۹ ساعت 6:54 توسط علی رضا نقش  | 

ادامه لیست الگوریتم ها


مهندسی نرم افزار [ ویرایش ]

اطلاعات بیشتر: مهندسی نرم افزار

الگوریتم های پایگاه داده [ ویرایش ]

اطلاعات بیشتر: بانک اطلاعاتی

الگوریتم های سیستم توزیع شده [ ویرایش ]

اطلاعات بیشتر: الگوریتم توزیع و سیستم های توزیع شده

تخصیص حافظه و الگوریتم های تفکیک جابجایی [ ویرایش ]

شبکه [ ویرایش ]

اطلاعات بیشتر: برنامه ریز شبکه

الگوریتم های سیستم عامل [ ویرایش ]

اطلاعات بیشتر: سیستم های عامل

هماهنگ سازی فرآیند [ ویرایش ]

اطلاعات بیشتر: هماهنگ سازی فرآیند

اطلاعات بیشتر: برنامه ریز فرآیند

برنامه ریزی [ ویرایش ]

اطلاعات بیشتر: برنامه ریزی (محاسبات)

برنامه ریزی I / O [ ویرایش ]

اطلاعات بیشتر: برنامه ریزی I / O

[آیکون]

این بخش به گسترش نیاز دارد . با افزودن به آن می توانید کمک کنید . ( جولای 2017 )

برنامه ریزی دیسک [ ویرایش ]

منبع

https://en.wikipedia.org/wiki/List_of_algorithms#Statistics

+ نوشته شده در یکشنبه یازدهم خرداد ۱۳۹۹ ساعت 22:30 توسط علی رضا نقش  | 

ادامه لیست الگوریتم ها

نظریه اطلاعات و پردازش سیگنال [ ویرایش ]

مقالات اصلی: نظریه اطلاعات و پردازش سیگنال

نظریه کدگذاری [ ویرایش ]

اطلاعات بیشتر: نظریه کدگذاری

تشخیص و تصحیح خطا [ ویرایش ]

اطلاعات بیشتر: تشخیص و تصحیح خطا

الگوریتم های فشرده سازی بدون ضرر [ ویرایش ]

صفحه اصلی: الگوریتم های فشرده سازی بدون ضرر

الگوریتم های فشرده سازی از دست رفته [ ویرایش ]

صفحه اصلی: الگوریتم های فشرده سازی از دست رفته

پردازش سیگنال دیجیتال [ ویرایش ]

اطلاعات بیشتر: پردازش سیگنال دیجیتال

پردازش تصویر [ ویرایش ]

اطلاعات بیشتر: پردازش تصویر دیجیتال

منبع

https://en.wikipedia.org/wiki/List_of_algorithms#Statistics

+ نوشته شده در یکشنبه یازدهم خرداد ۱۳۹۹ ساعت 22:28 توسط علی رضا نقش  | 

ادامه لیست الگوریتم ها

منطق دیجیتال [ ویرایش ]

یادگیری ماشین و طبقه بندی آماری [ ویرایش ]

مقاله اصلی: لیست الگوریتم های یادگیری ماشین

اطلاعات بیشتر: یادگیری ماشین و طبقه بندی آماری

تئوری زبان برنامه نویسی [ ویرایش ]

اطلاعات بیشتر: تئوری زبان برنامه نویسی

تجزیه [ ویرایش ]

اطلاعات بیشتر: تجزیه

الگوریتم های کوانتومی [ ویرایش ]

اطلاعات بیشتر: الگوریتم کوانتومی

  • الگوریتم Deutsch-Jozsa : معیار تعادل برای عملکرد بولی
  • الگوریتم Grover : فراهم می کند سرعت درجه دوم برای بسیاری از مشکلات جستجو
  • الگوریتم Shor : فراهم می کند سرعت نمایی (نسبت به الگوریتم های غیر کوانتومی شناخته شده در حال حاضر شناخته شده) برای تعیین تعداد
  • الگوریتم Simon : یک سرعت شفاف نمایی (نسبت به هر الگوریتم غیر کوانتومی) برای یک مشکل جعبه سیاه فراهم می کند

تئوری محاسبه و خودکار [ ویرایش ]

اطلاعات بیشتر: تئوری محاسبه

منبع

https://en.wikipedia.org/wiki/List_of_algorithms#Statistics

+ نوشته شده در یکشنبه یازدهم خرداد ۱۳۹۹ ساعت 22:28 توسط علی رضا نقش  | 

ادامه لیست الگوریتم ها

آمار [ ویرایش ]

اطلاعات بیشتر: آمار محاسباتی

علم کامپیوتر [ ویرایش ]

اطلاعات بیشتر: علوم کامپیوتر

معماری رایانه [ ویرایش ]

اطلاعات بیشتر: معماری رایانه

  • الگوریتم Tomasulo : اجازه می دهد تا دستورالعمل های پی در پی که به دلیل وابستگی های خاص متوقف می شوند برای اجرای غیر متوالی

گرافیک رایانه [ ویرایش ]

اطلاعات بیشتر: گرافیک رایانه

رمزنگاری [ ویرایش ]

اطلاعات بیشتر: رمزنگاری و مباحث مربوط به رمزنگاری

منبع

https://en.wikipedia.org/wiki/List_of_algorithms#Statistics

+ نوشته شده در یکشنبه یازدهم خرداد ۱۳۹۹ ساعت 22:27 توسط علی رضا نقش  | 

ادامه لیست الگوریتم ها

دنباله جستجو [ ویرایش ]

ادغام دنباله [ ویرایش ]

مقاله اصلی: الگوریتم ادغام

  • الگوریتم ادغام ساده
  • الگوریتم ادغام k-way
  • اتحاد (ادغام با عناصر موجود در خروجی تکرار نشده است)

جایگشت های دنباله ای [ ویرایش ]

اطلاعات بیشتر: Permutation

تراز دنباله [ ویرایش ]

مرتب سازی ترتیب [ ویرایش ]

مقاله اصلی: الگوریتم مرتب سازی

اختلاف صحت

به نظر می رسد این مقاله با مقاله Sorting_algorithm # Comparison_of_algorithms متناقض است . لطفاً بحث را در صفحه بحث و گفتگو مرتبط مشاهده کنید . ( مارس 2011 ) ( یاد بگیرید که چگونه و چه زمانی این پیام الگوی را حذف کنید )

پیامدهای [ ویرایش ]

اطلاعات بیشتر: پیامد

بسترها [ ویرایش ]

اطلاعات بیشتر: بستر

ریاضیات محاسباتی [ ویرایش ]

اطلاعات بیشتر: ریاضیات محاسباتی

همچنین ببینید: الگوریتم های ترکیبی و علوم محاسباتی

جبر چکیده [ ویرایش ]

اطلاعات بیشتر: جبر چکیده

جبر رایانه [ ویرایش ]

اطلاعات بیشتر: جبر رایانه

منبع

https://en.wikipedia.org/wiki/List_of_algorithms#Statistics

+ نوشته شده در یکشنبه یازدهم خرداد ۱۳۹۹ ساعت 22:25 توسط علی رضا نقش  | 

لیست الگوریتم ها

در زیر لیستی از الگوریتم ها به همراه توضیحات تک خط برای هرکدام قرار گرفته است.

 

فهرست

برنامه ریزی خودکار [ ویرایش ]

اطلاعات بیشتر: لیست الگوریتم های برنامه ریزی خودکار

الگوریتم های ترکیبی [ ویرایش ]

اطلاعات بیشتر: Combinatorics

الگوریتم های ترکیبی عمومی [ ویرایش ]

الگوریتم های نمودار [ ویرایش ]

اطلاعات بیشتر: تئوری نمودار و رده: الگوریتم های نمودار

رسم نمودار [ ویرایش ]

اطلاعات بیشتر: طراحی نمودار

نظریه شبکه [ ویرایش ]

اطلاعات بیشتر: نظریه شبکه

مسیریابی نمودارها [ ویرایش ]

جستجوی نمودار [ ویرایش ]

اطلاعات بیشتر: الگوریتم جستجوی فضای دولتی و نمودار جستجو

زیرگرافها [ ویرایش ]

الگوریتم های دنباله [ ویرایش ]

اطلاعات بیشتر: توالی

تطبیق توالی تقریبی [ ویرایش ]

الگوریتم های انتخاب [ ویرایش ]

مقاله اصلی: الگوریتم انتخاب

منبع

https://en.wikipedia.org/wiki/List_of_algorithms#Statistics

+ نوشته شده در یکشنبه یازدهم خرداد ۱۳۹۹ ساعت 22:24 توسط علی رضا نقش  |