Art gallery problem
آرٹ گیلری کا مسئلہ یا میوزیم کا مسئلہ کمپیوٹیشنل جیومیٹری میں اچھی طرح سے مطالعہ شدہ مرئیت کا مسئلہ ہے۔ یہ مندرجہ ذیل حقیقی دنیا کے مسئلے سے نکلتا ہے: "ایک آرٹ گیلری میں، محافظوں کی کم از کم تعداد کتنی ہوتی ہے جو مل کر پوری گیلری کا مشاہدہ کر سکتے ہیں؟" مسئلہ کے ہندسی ورژن میں، آرٹ گیلری کی ترتیب کی نمائندگی ایک سادہ کثیر الاضحی سے کی جاتی ہے اور ہر محافظ کی نمائندگی کثیر الاضحی میں ایک نقطہ سے کی جاتی ہے۔ پوائنٹس کے ایک سیٹ کو کثیر الاضحی کی حفاظت کرنے کے لیے کہا جاتا ہے اگر، کثیر الاضحی میں ہر نقطہ کے لیے، کچھ ایسا ہے کہ اور کے درمیان کی لکیر کا حصہ کثیر الاضحی کو نہیں چھوڑتا ہے۔ آرٹ گیلری کا مسئلہ کئی ڈومینز میں لاگو کیا جا سکتا ہے جیسے روبوٹکس میں، جب مصنوعی ذہانت (اے آئی) کو اپنے ارد گرد کے لحاظ سے حرکات انجام دینے کی ضرورت ہوتی ہے۔ دوسرے ڈومینز، جہاں اس مسئلے کا اطلاق ہوتا ہے، وہ امیج ایڈیٹنگ، کسی مرحلے کی روشنی کے مسائل یا قدرتی آفات کے انتباہ کے لیے انفراسٹرکچر کی تنصیب میں ہیں۔ دو جہتیں اصل مسئلے کے بے شمار تغیرات ہیں جنہیں آرٹ گیلری کا مسئلہ بھی کہا جاتا ہے۔ کچھ ورژنوں میں محافظوں کو دائرے، یا یہاں تک کہ کثیر الاضحی کے عمودی حصوں تک محدود رکھا جاتا ہے۔ کچھ ورژن کی حفاظت کے لیے صرف دائرے یا دائرے کے ذیلی سیٹ کی ضرورت ہوتی ہے۔ اس ورژن کو حل کرنا جس میں محافظوں کو چوٹیوں پر رکھا جانا چاہیے اور صرف چوٹیوں کو محفوظ رکھنے کی ضرورت ہے، کثیر الاضحی کے مرئیت گراف پر غالب سیٹ کے مسئلے کو حل کرنے کے مترادف ہے۔ چوتال کا آرٹ گیلری تھیوریم چوتال کا آرٹ گیلری تھیوریم، جس کا نام ویکلاو چوتال کے نام پر رکھا گیا ہے، محافظوں کی کم سے کم تعداد پر ایک اوپری حد دیتا ہے۔ اس میں کہا گیا ہے: "چوٹیوں کے ساتھ ایک سادہ کثیر الاضحی کی حفاظت کے لیے، محافظ ہمیشہ کافی ہوتے ہیں اور بعض اوقات ضروری بھی ہوتے ہیں۔" تاریخ یہ سوال کہ کتنے عمودی/چوکیدار/محافظوں کی ضرورت تھی، 1973 میں وکٹر کلی نے چوتال سے پوچھا تھا۔ اس کے فورا بعد چوتال نے اسے ثابت کر دیا۔ چوتال کے ثبوت کو بعد میں اسٹیو فسک نے 3 رنگوں کی دلیل کے ذریعے آسان بنایا۔ چوتال میں زیادہ ہندسی نقطہ نظر ہے، جبکہ فسک گراف تھیوری کے معروف نتائج کا استعمال کرتا ہے۔ فسک کا مختصر ثبوت اسٹیو فسک کا ثبوت اتنا مختصر اور خوبصورت ہے کہ اسے کتاب کے ثبوت میں شامل کرنے کے لیے منتخب کیا گیا تھا۔ ثبوت مندرجہ ذیل ہے: سب سے پہلے، کثیر الاضحی مثلث ہے (اضافی عمودی کو شامل کیے بغیر)، جو ممکن ہے، کیونکہ مثلث کا وجود بعض تصدیق شدہ حالات میں ثابت ہوتا ہے۔ نتیجے میں مثلث گراف کے عمودی حصے 3 رنگ کے ہو سکتے ہیں۔ واضح طور پر، 3 رنگ کے تحت، ہر مثلث میں تینوں رنگ ہونے چاہئیں۔ کسی بھی ایک رنگ کے عمودی حصے ایک درست محافظ سیٹ بناتے ہیں، کیونکہ کثیر الاضحی کا ہر مثلث اس رنگ کے ساتھ اس کے عمودی حصے سے محفوظ ہوتا ہے۔ چونکہ تین رنگ کثیر الاضحی کے n عمودی حصوں کو تقسیم کرتے ہیں، اس لیے سب سے کم عمودی رنگ زیادہ تر محافظوں کے ساتھ ایک درست محافظ سیٹ کی وضاحت کرتا ہے۔ ثبوت کی مثال ثبوت کی وضاحت کے لیے، ہم نیچے دیے گئے کثیر الاضحی پر غور کرتے ہیں۔ پہلا قدم کثیر الاضحی کو مثلث بنانا ہے (شکل 1 دیکھیں)۔ پھر، ایک مناسب رنگ (شکل 2) لگایا جاتا ہے اور مشاہدہ کیا جاتا ہے کہ سرخ، نیلے اور سبز عمودی ہیں۔ سب سے کم عمودی رنگ نیلا یا سرخ ہوتا ہے، اس طرح کثیر الاضحی کو محافظوں سے ڈھانپا جا سکتا ہے (شکل 3)۔ یہ آرٹ گیلری تھیوریم سے متفق ہے، کیونکہ کثیر الاضحی کے عمودی حصے ہوتے ہیں، اور۔ عام فہمیاں چوتال کی اوپری حد درست رہتی ہے اگر کونوں پر محافظوں کی پابندی کو کسی بھی مقام پر محافظوں کے لیے ڈھیلا کر دیا جائے جو کہ کثیر الاضحی سے باہر نہ ہو۔ اصل آرٹ گیلری تھیوریم کی کئی دیگر عمومی اور تخصصات ہیں۔ مثال کے طور پر، آرتھوگنل کثیر الاضلاعات کے لیے، جن کے کنارے/دیواریں صحیح زاویہ پر ملتی ہیں، صرف محافظوں کی ضرورت ہوتی ہے۔ اس نتیجے کے کم از کم تین الگ الگ ثبوت ہیں، ان میں سے کوئی بھی سادہ نہیں ہے: کان، کلا، اور کلیٹ مین کی طرف سے ؛ لبیو کی طرف سے ؛ اور ساک اور ٹاسسینٹ کی طرف سے۔ ایک متعلقہ مسئلہ کسی من مانی کثیر الاضحی ("قلعہ کا مسئلہ") کے بیرونی حصے کو ڈھانپنے کے لیے محافظوں کی تعداد کا مطالبہ کرتا ہے: بعض اوقات ضروری ہوتے ہیں اور ہمیشہ کافی ہوتے ہیں اگر محافظ کثیر الاضحی کی حد پر رکھے جاتے ہیں، جبکہ بعض اوقات ضروری ہوتے ہیں اور ہمیشہ کافی ہوتے ہیں اگر محافظ کثیر الاضحی کے بیرونی حصے میں کہیں بھی رکھے جاتے ہیں۔ دوسرے لفظوں میں، لامحدود بیرونی کا احاطہ کرنا محدود اندرونی سے زیادہ مشکل ہے۔ کمپیوٹیشنل پیچیدگی آرٹ گیلری کے مسئلے کے فیصلے کے مسئلے کے ورژن میں، ایک کو کثیر الاضحی اور ایک نمبر k دونوں کے ان پٹ کے طور پر دیا جاتا ہے، اور اس بات کا تعین کرنا ضروری ہے کہ آیا کثیر الاضحی کو k یا اس سے کم محافظوں سے محفوظ کیا جا سکتا ہے۔ یہ مسئلہ مکمل ہے، جیسا کہ وہ ورژن ہے جہاں محافظ کثیر الاضحی کے کناروں تک محدود ہیں۔ مزید برآں، زیادہ تر دیگر معیاری تغیرات (جیسے کہ گارڈ کے مقامات کو عمودی تک محدود کرنا) این پی سخت ہیں۔ گارڈز کی کم از کم تعداد کے لیے تخمینہ الگورتھم کے حوالے سے، اس مسئلے کو اے پی ایکس-سخت ثابت کیا، جس سے یہ ظاہر ہوتا ہے کہ اس بات کا امکان نہیں ہے کہ کسی مقررہ مستقل سے بہتر کوئی تخمینہ تناسب کثیر الجہتی وقت کے تخمینہ الگورتھم کے ذریعے حاصل کیا جا سکے۔ اس سے پتہ چلتا ہے کہ ان پٹ کثیر الاضحی کو کنویکس ذیلی خطوں میں الگ کرکے اور پھر مسئلے کو ایک سیٹ کور کے مسئلے تک کم کرکے ورٹیکس گارڈز کی کم از کم تعداد کے لیے لوگرتھمک تخمینہ حاصل کیا جا سکتا ہے۔ جیسا کہ دکھایا گیا ہے، آرٹ گیلری کے مسئلے سے اخذ کردہ سیٹ سسٹم نے وی سی طول و عرض کو محدود کیا ہے، جس سے ε-نیٹ پر مبنی سیٹ کور الگورتھم کے اطلاق کی اجازت ملتی ہے جس کا تخمینہ تناسب کثیر الاضحی عمودی کی تعداد کے بجائے محافظوں کی زیادہ سے زیادہ تعداد کا لوگارتھم ہوتا ہے۔ غیر محدود گارڈز کے لیے، ممکنہ گارڈ پوزیشنوں کی لامحدود تعداد مسئلے کو اور بھی مشکل بنا دیتی ہے۔ تاہم محافظوں کو باریک گرڈ پر لیٹنے تک محدود کر کے، کچھ ہلکے اضافی مفروضوں کے تحت ایک زیادہ پیچیدہ لوگرتھمک تخمینہ الگورتھم حاصل کیا جا سکتا ہے، جیسا کہ اس میں دکھایا گیا ہے۔ تاہم، موثر الگورتھم زیادہ تر ورٹیکس گارڈز کا ایک مجموعہ تلاش کرنے کے لیے جانا جاتا ہے، جو چوتال کی اوپری حد سے ملتا جلتا ہے۔ یہ ثابت کیا کہ ان گارڈز کے لیے پلیسمنٹ کا حساب O (n لاگ n) وقت میں بدترین صورت میں، تقسیم اور فتح الگورتھم کے ذریعے کیا جا سکتا ہے۔ فسک کے مختصر ثبوت اور برنارڈ چیزیل کے لکیری ٹائم پلین ٹرائینگولیشن الگورتھم کا استعمال کرتے ہوئے ایک لکیری ٹائم الگورتھم دیا۔ سادہ کثیر الاضلاعات کے لیے جن میں سوراخ نہیں ہوتے ہیں، ورٹیکس اور ایج گارڈز کے لیے ایک مستقل عنصر تخمینہ الگورتھم کے وجود کا قیاس گھوش نے کیا تھا۔ گھوش کا قیاس ابتدائی طور پر سادہ کثیر الاضحی کے دو خصوصی ذیلی زمروں میں ورٹیکس گارڈز کے لیے درست ثابت ہوا۔ مونوٹون کثیر الاضحی اور کثیر الاضحی ایک کنارے سے کمزور نظر آتے ہیں۔ ایک تخمینہ الگورتھم پیش کیا جو کثیر الجہتی وقت میں ایک مونوٹون کثیر الاضحی کے لیے ایک ورٹیکس گارڈ سیٹ کا حساب لگاتا ہے جیسے کہ گارڈ سیٹ کا سائز ورٹیکس گارڈز کی زیادہ سے زیادہ تعداد سے 30 گنا زیادہ ہو۔ ایک تخمینہ الگورتھم پیش کیا جو O (n2) وقت میں ایک سادہ کثیر الاضحی کے لیے ایک ورٹیکس گارڈ سیٹ کا حساب لگاتا ہے جو ایک کنارے سے کمزور نظر آتا ہے جیسے کہ گارڈ سیٹ کا سائز ورٹیکس گارڈز کی زیادہ سے زیادہ 6 گنا زیادہ ہو۔ اس کے بعد، انہوں نے ورٹیکس گارڈز اور ایج گارڈز کا استعمال کرتے ہوئے عام سادہ کثیر الاضلاعات کی حفاظت کے لیے مستقل عنصر تخمینہ الگورتھم پیش کر کے قیاس کو مکمل طور پر حل کرنے کا دعوی کیا۔ سادہ کثیر الاضلاعات کے ذیلی طبقے کی حفاظت کرنے والے ورٹیکس کے لیے جو کنارے سے کمزور نظر آتے ہیں، ایک کثیر الجہتی وقت کا تخمینہ اسکیم تجویز کی گئی تھی۔ ورٹیکس گارڈز کے لیے ایک عین مطابق الگورتھم تجویز کیا گیا تھا۔ مصنفین نے کثیر الاضلاعات کی کئی کلاسوں کے ساتھ وسیع کمپیوٹیشنل تجربات کیے جس سے یہ ظاہر ہوتا ہے کہ ہزاروں عمودی حصوں سے وابستہ مثالوں کے لیے بھی نسبتا چھوٹے کمپیوٹیشن اوقات میں بہترین حل تلاش کیے جا سکتے ہیں۔ ان مثالوں کے لیے ان پٹ ڈیٹا اور بہترین حل ڈاؤن لوڈ کے لیے دستیاب ہیں۔ تین جہتیں اگر کسی عجائب گھر کو تین جہتوں میں پولی ہیڈرون کے طور پر پیش کیا جاتا ہے، تو ہر سرے پر گارڈ لگانے سے یہ یقینی نہیں ہوگا کہ تمام عجائب گھر زیر مشاہدہ ہے۔ اگرچہ پولی ہیڈرون کی تمام سطح کا سروے کیا جائے گا، کچھ پولی ہیڈر کے لیے اندرونی حصے میں ایسے مقامات ہیں جو نگرانی میں نہیں ہو سکتے۔ آرٹ گیلری کے ممکنہ استعمال کے منظرنامے مسئلہ آرٹ گیلری کے مسئلے کو متعدد کیمروں کی پوزیشن کے لیے استعمال کیا جا سکتا ہے جب مقصد کم سے کم کیمروں کا استعمال کرتے ہوئے کیمروں کے پیش نظر ایک بڑے علاقے کا احاطہ کرنا ہو۔ اسٹار پولیگنز اسٹار کی شکل کے پولیگن کے ساتھ ایک مستطیل کثیر الاضحی کا احاطہ کرنا، کثیر الاضحی کی ایک کلاس جس کے لیے آرٹ گیلری کا مسئلہ ایک ہی گارڈ سے حل کیا جا سکتا ہے۔ روشنی کا مسئلہ: اگر دیواریں آئینہ دار ہوں تو کیا ایک ہی گارڈ کافی ہے؟ حوالہ جات کے ذرائع کو نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ کمپیوٹیشنل جیومیٹری ثبوتوں پر مشتمل مضامین مسائل کا احاطہ کرنے والے کثیر الاضحی