نمودار Voronoi یک مفهوم ساده و بر اساس حداقل مسافت مورد نیاز برای رسیدن به یک نقطه یا مکان خاص است. اگر نیاز به رفتن به یک ایستگاه مترو دارید ، یافتن نزدیکترین ایستگاه اولین راه حلی است که به ذهنتان می رسد. ساده است ، نه؟
بهتر است بخوانید : الگوریتم Naive Bayes در یادگیری ماشین
شهری را تصور کنید که در آن آتش سوزی شده است. سرویس های اضطراری باید یک ماشین آتش نشانی به این مکان بفرستند. اگر N ایستگاه آتش نشانی وجود داشته باشد ، چه ماشین آتش نشانی باید به نقطه مورد نظر ارسال شود؟
همانطور که در شکل بالا به خوبی نشان داده شده است ،آتش‌سوزی در منطقه ای که با رنگ سبز روشن علامت گذاری شده، اتفاق افتاده است . نزدیکترین ایستگاه به مکان آتش‌سوزی ایستگاهی است که در همین ناحیه ورونوی قرار گرفته است. هیچ کامیونی سریعتر از این کامیون نمی تواند به نقطه آتش سوزی در ناحیه سبز روشن برسد.
Voronoi Diagram را به صورت کلی می توان به صورت زیر تعمیم داد:
نمودار Voronoi: در صفحه ، برای مجموعه ای از سایت‌ها (نقاطی در آن فضای ۲ بعدی با خصوصیات مشابه) نمودار Voronoi فضا را براساس حداقل فاصله تا هر سایت تقسیم می کند.
نمودار ورونوی در شبه کد به صورت زیر می‌تواند باشد :
for each (point in plane){
voronoi[point] = null; // Clear site owner of the point
for each (site in list_sites){
double tempdist = distance(point,site);
if (voronoi[point] == null || tempdist < distance(point, voronoi[point]) )
voronoi[point] = site; // Update site owner if it’s nearest.
}
}
این کد یک اجرای Naive یا ساده است.
کاربرد Voronoi Diagram در AI
در تئوری بازی، نمودارهای ورونویی به طور گسترده ای استفاده می شوند. وقتی بازیکن های N برای منابع یکسانی رقابت می کنند، بسیار مهم است که دستورات بازی نه تنها با فاصله، بلکه احتمال دستیابی سریع تر آن‌ها به این منابع نسبت به دشمنان، در الویت قرار بگیرند.
در بازی بازیکنان B و C بعد از مشاهده‌ی بسته ۴ ممکن است به سمت آن هجوم برند. اما باتوجه به نمودار Voronoi ، بازیکن D سریعتر به آن می رسد. اگر این سه بازیکن بسته‌ی ۴ را مورد هدف قرار دهند ، با اطمینان بالا می‌توان پیش‌بینی کرد که بازیکن D آن را از آن خود می کند. در این صورت ، هوش مصنوعی بازی باید تصمیم بگیرد که آیا هدفی را انتخاب کند که خارج از Voronoi Area قرار داردو یا ایمن بازی کرده و بسته هایی را انتخاب کند که در همان منطقه Voroni قرار دارند.
علاوه بر این، از نمودارهای Voronoi برای به حداکثر رساندن مناطق کنترل استفاده می شود. در بازی متا که در مورد به حداکثر رساندن منطقه کنترل شده است ، شما می توانید در چهار جهت حرکت کنید ، می توان با بررسی دقیق حرکتی را در هر ۴ جهت شبیه سازی کرد و نمودار Voronoi را محاسبه کرد. حرکتی که بزرگترین منطقه Voronoi را ایجاد می کند احتمالاً بهترین حرکت است. در مورد Tron Google AI Challenge post-mortem درباره این ابتکار بیشتر بدانید.
