الگوریتمی جدید، مشکل گراف را در هم شکست

لازلو بابایی (Laszlo Babai) در ۱۰ نوامبر ۲۰۱۵ در دانشگاه شیکاگو به معرفی الگوریتم جدیدش پرداخت. الگوریتمی که مشکل فریبنده­ی گراف­های هم­ شکل را سریعتر از روش­های دیگر حل می­کند.
گراف­های همسان یک پازل به شدت به هم ریخته است که کامپیوترها و دانشمندانی که به آن برنامه می­دهند به طور ناگهانی از کنترل و مدیریت آن باز می مانند.
الگوریتم جدید، به شکلی مؤثر مشکل گراف­های همسان را حل می­کند. دانشمند علوم کامپیوتر لازلو بابایی در سمینار ترکیبات و نظریات علوم کامپیوتر در۱۰ نوامبر در دانشگاه شیکاگو اعلام کرد: این مشکل نیازمند آن است که مشخص شود دو گروه مجزا از نقاط به هم پیوسته، که به عنوان گراف می­شناسیم، به یک شکل به هم متصل شده­اند، حتی اگر گراف­ها خیلی متفاوت به نظر برسند.
در عمل، الگوریتم­های موجود می­توانند در زمان معقولی کار خود را به انجام برسانند اما این احتمال وجود دارد که گراف­های بسیار پیچیده، مسئله را غیر قابل حل کنند.
رایان ویلیامز (Ryan Williams) دانشمند علوم کامپیوتر در دانشگاه استنفورد می­گوید ایده­ی اولیه من یک جوک به نظر می­رسید . من می­خواستم با الگوریتمی خاص که در حل گراف­های همسان استفاده می­شود، نام ماه جاری را چک کنم تا مطمئن شوم نام آن آپریل نباشد. این در واقع یک جهش عظیم در فهم ما از مشکل است. این دستاورد مهمترین دستاورد نظری علوم کامپیوتر در دهه اخیر است.
الگوریتم لازلو بابایی هنوز نیاز به بررسی دارد اما تخصص او به همکارانش در بررسی نتایج اعتماد به نفس می­دهد. او حتی قبل از اینکه این مسئله را موضوع رساله­ی دکتری خود در ۱۹۸۴ قرار دهد با این مسئله درگیر بود، زمانی که این مسئله یک مسئله کاملاً انتزاعی به نظر می­رسید. این یک مثال برجسته از مدلی عجیب و غریب از پازل هاست که کامپیوتر در حل آن مشکل دارد درحالی­که اگر یک شکل را به رایانه ارائه دهیم به سرعت میتواند راه حل را نشانمان دهد. البته نتیجه ممکن است در ماورای علوم کامپیوتر معکوس باشد، مثلاً اجازه دادن به شیمیدان¬ها که مولکول¬های پیچیده را دارای ساختار پیوندی یکسان در نظر بگیرند.

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

منبع:علمنا

No tags for this post.