Art gallery problem
আর্ট গ্যালারি সমস্যা বা জাদুঘর সমস্যা গণনামূলক জ্যামিতিতে একটি সু-অধ্যয়নরত দৃশ্যমানতা সমস্যা। এটি নিম্নলিখিত বাস্তব-জগতের সমস্যা থেকে উদ্ভূত হয়েছেঃ "একটি আর্ট গ্যালারিতে, ন্যূনতম কতজন রক্ষী রয়েছে যারা একসঙ্গে পুরো গ্যালারিটি পর্যবেক্ষণ করতে পারে?" সমস্যার জ্যামিতিক সংস্করণে, আর্ট গ্যালারির বিন্যাস একটি সাধারণ বহুভুজ দ্বারা প্রতিনিধিত্ব করা হয় এবং প্রতিটি গার্ড বহুভুজের একটি বিন্দু দ্বারা প্রতিনিধিত্ব করা হয়। একটি বিন্দুর সেটকে একটি বহুভুজকে রক্ষা করার জন্য বলা হয়, যদি বহুভুজের প্রতিটি বিন্দুর জন্য এমন কিছু থাকে যে এবং এর মধ্যবর্তী রেখাটি বহুভুজটি ছেড়ে না যায়। আর্ট গ্যালারির সমস্যাটি রোবোটিক্সের মতো বিভিন্ন ক্ষেত্রে প্রয়োগ করা যেতে পারে, যখন কৃত্রিম বুদ্ধিমত্তার (এআই) তাদের আশেপাশের উপর নির্ভর করে গতিবিধি কার্যকর করার প্রয়োজন হয়। অন্যান্য ক্ষেত্রে, যেখানে এই সমস্যাটি প্রয়োগ করা হয়, সেগুলি হল চিত্র সম্পাদনা, কোনও পর্যায়ের আলোর সমস্যা বা প্রাকৃতিক দুর্যোগের সতর্কতার জন্য পরিকাঠামো স্থাপন। মূল সমস্যার অসংখ্য বৈচিত্র রয়েছে যা আর্ট গ্যালারি সমস্যা হিসাবেও উল্লেখ করা হয়। কিছু সংস্করণে রক্ষীরা পরিধির মধ্যে বা এমনকি বহুভুজের শীর্ষে সীমাবদ্ধ থাকে। কিছু সংস্করণে শুধুমাত্র পরিসীমা বা পরিসীমার একটি উপসেট রক্ষা করার প্রয়োজন হয়। যে সংস্করণে রক্ষীদের অবশ্যই শীর্ষে স্থাপন করতে হবে এবং শুধুমাত্র শীর্ষগুলি রক্ষা করতে হবে তা সমাধান করা বহুভুজের দৃশ্যমানতা গ্রাফের উপর প্রভাবশালী সেট সমস্যা সমাধানের সমতুল্য। চাভাতালের আর্ট গ্যালারি উপপাদ্য চাভাতালের আর্ট গ্যালারি উপপাদ্য, যা ভাক্লাভ চাভাতালের নামে নামকরণ করা হয়েছে, ন্যূনতম সংখ্যক রক্ষীদের উপর একটি ঊর্ধ্বসীমা প্রদান করে। এতে বলা হয়েছেঃ "শীর্ষ সহ একটি সাধারণ বহুভুজকে রক্ষা করার জন্য, রক্ষীরা সর্বদা যথেষ্ট এবং কখনও কখনও প্রয়োজনীয়।" কতজন শীর্ষ/প্রহরী/রক্ষী প্রয়োজন ছিল সেই প্রশ্নটি 1973 সালে ভিক্টর ক্লি চাভাতালের কাছে উত্থাপন করেছিলেন। এর পরেই খুব শীঘ্রই চাভাতাল তা প্রমাণ করেন। চৌতালের প্রমাণটি পরে স্টিভ ফিস্ক দ্বারা 3-রঙের যুক্তির মাধ্যমে সরলীকৃত করা হয়েছিল। চাভাতালের আরও জ্যামিতিক পদ্ধতি রয়েছে, যেখানে ফিস্ক গ্রাফ তত্ত্ব থেকে সুপরিচিত ফলাফল ব্যবহার করে। ফিস্কের সংক্ষিপ্ত প্রমাণ স্টিভ ফিস্কের প্রমাণ এতটাই সংক্ষিপ্ত এবং মার্জিত যে এটিকে প্রুফস ফ্রম দ্য বুক-এ অন্তর্ভুক্ত করার জন্য বেছে নেওয়া হয়েছিল। প্রমাণটি নিম্নরূপঃ প্রথমত, বহুভুজটি ত্রিভুজাকার (অতিরিক্ত শীর্ষ যোগ না করে), যা সম্ভব, কারণ ত্রিভুজের অস্তিত্ব নির্দিষ্ট যাচাইকৃত অবস্থার অধীনে প্রমাণিত হয়। ফলস্বরূপ ত্রিভুজ গ্রাফের শীর্ষগুলি 3-রঙের হতে পারে। স্পষ্টতই, একটি 3-রঙের অধীনে, প্রতিটি ত্রিভুজের অবশ্যই তিনটি রঙ থাকতে হবে। যে কোনও একটি রঙের শীর্ষগুলি একটি বৈধ গার্ড সেট গঠন করে, কারণ বহুভুজের প্রতিটি ত্রিভুজ সেই রঙের সাথে তার শীর্ষ দ্বারা সুরক্ষিত থাকে। যেহেতু তিনটি রঙ বহুভুজের এন শীর্ষকে বিভক্ত করে, তাই সবচেয়ে কম শীর্ষযুক্ত রঙটি বেশিরভাগ গার্ডের সাথে একটি বৈধ গার্ড সেটকে সংজ্ঞায়িত করে। প্রমাণের দৃষ্টান্ত প্রমাণটি ব্যাখ্যা করার জন্য, আমরা নীচের বহুভুজটি বিবেচনা করি। প্রথম ধাপ হল বহুভুজকে ত্রিভুজ করা (চিত্র 1 দেখুন)। তারপর, একটি সঠিক রঙ প্রয়োগ করা হয় (চিত্র 2) এবং লক্ষ্য করা যায় যে লাল, নীল এবং সবুজ শীর্ষ রয়েছে। সবচেয়ে কম শীর্ষযুক্ত রঙ নীল বা লাল, তাই বহুভুজটি রক্ষী দ্বারা আবৃত করা যেতে পারে (চিত্র 3)। এটি আর্ট গ্যালারি উপপাদ্যের সাথে একমত, কারণ বহুভুজের শীর্ষ রয়েছে, এবং। সাধারণীকরণ চৌতালের উপরের সীমাটি বৈধ থাকে যদি বহুভুজের বাইরে নয় এমন যে কোনও সময়ে কোণে রক্ষীদের উপর নিষেধাজ্ঞা শিথিল করা হয়। মূল শিল্প-গ্যালারি উপপাদ্যের আরও বেশ কয়েকটি সাধারণীকরণ এবং বিশেষীকরণ রয়েছে। উদাহরণস্বরূপ, অর্থোগোনাল বহুভুজের জন্য, যার প্রান্ত/দেয়াল সমকোণে মিলিত হয়, শুধুমাত্র রক্ষীদের প্রয়োজন হয়। এই ফলাফলের কমপক্ষে তিনটি স্বতন্ত্র প্রমাণ রয়েছে, যার কোনওটিই সহজ নয়ঃ কান, ক্লাউ এবং ক্লেইটম্যান দ্বারা; লুবিউ দ্বারা; এবং স্যাক এবং টাউসসেন্ট দ্বারা। একটি সম্পর্কিত সমস্যা একটি নির্বিচারে বহুভুজের ("দুর্গ সমস্যা") বাইরের অংশকে ঢেকে রাখার জন্য রক্ষীদের সংখ্যা জিজ্ঞাসা করেঃ কখনও কখনও প্রয়োজনীয় এবং সর্বদা যথেষ্ট যদি রক্ষীদের বহুভুজের সীমানায় স্থাপন করা হয়, তবে কখনও কখনও প্রয়োজনীয় এবং সর্বদা যথেষ্ট যদি রক্ষীদের বহুভুজের বাইরের যে কোনও জায়গায় স্থাপন করা হয়। অন্য কথায়, অসীম বাহ্যিক অংশটি সীমাবদ্ধ অভ্যন্তরের তুলনায় আচ্ছাদন করা আরও চ্যালেঞ্জিং। গণনামূলক জটিলতা আর্ট গ্যালারি সমস্যার সিদ্ধান্ত সমস্যা সংস্করণগুলিতে, একটি বহুভুজ এবং একটি সংখ্যা কে উভয়ই ইনপুট হিসাবে দেওয়া হয় এবং বহুভুজটিকে কে বা তার কম গার্ড দিয়ে রক্ষা করা যেতে পারে কিনা তা নির্ধারণ করতে হবে। এই সমস্যাটি-সম্পূর্ণ, যেমন সংস্করণটি যেখানে রক্ষীরা বহুভুজের প্রান্তে সীমাবদ্ধ। উপরন্তু, অন্যান্য স্ট্যান্ডার্ড বৈচিত্রগুলির বেশিরভাগই (যেমন গার্ডের অবস্থানগুলিকে শীর্ষে সীমাবদ্ধ করা) এনপি-হার্ড। ন্যূনতম সংখ্যক গার্ডের জন্য আনুমানিক অ্যালগরিদম সম্পর্কে, সমস্যাটি এ. পি. এক্স-হার্ড হিসাবে প্রমাণিত হয়েছে, যা বোঝায় যে কোনও নির্দিষ্ট ধ্রুবকের চেয়ে ভাল কোনও আনুমানিক অনুপাত একটি বহুপদী সময় আনুমানিক অ্যালগরিদম দ্বারা অর্জন করা সম্ভব নয়। দেখিয়েছেন যে ইনপুট বহুভুজকে উত্তল উপ-অঞ্চলে বিভক্ত করে এবং তারপরে সমস্যাটিকে একটি নির্দিষ্ট আবরণ সমস্যায় হ্রাস করে সর্বনিম্ন সংখ্যক শীর্ষ রক্ষীর জন্য একটি লগারিদমিক অনুমান অর্জন করা যেতে পারে। যেমন দেখানো হয়েছে, একটি আর্ট গ্যালারি সমস্যা থেকে উদ্ভূত সেট সিস্টেমটি ভি. সি মাত্রাকে সীমাবদ্ধ করেছে, যা ε-নেটের উপর ভিত্তি করে সেট কভার অ্যালগরিদম প্রয়োগের অনুমতি দেয় যার আনুমানিক অনুপাত বহুভুজ শীর্ষের সংখ্যার পরিবর্তে সর্বোত্তম সংখ্যক গার্ডের লগারিদম। অনিয়ন্ত্রিত রক্ষীদের জন্য, অসীম সংখ্যক সম্ভাব্য রক্ষী অবস্থান সমস্যাটিকে আরও কঠিন করে তোলে। তবে রক্ষীদের একটি সূক্ষ্ম গ্রিডে শুয়ে থাকতে সীমাবদ্ধ করে, একটি আরও জটিল লগারিদমিক আনুমানিক অ্যালগরিদম কিছু হালকা অতিরিক্ত অনুমানের অধীনে প্রাপ্ত করা যেতে পারে, যেমনটি দেখানো হয়েছে। যাইহোক, দক্ষ অ্যালগরিদমগুলি বেশিরভাগ ভার্টেক্স গার্ডের একটি সেট খুঁজে বের করার জন্য পরিচিত, যা চাভাতালের উপরের সীমানার সাথে মেলে। প্রমাণ করে যে এই রক্ষীদের জন্য একটি স্থান নির্ধারণ করা যেতে পারে ও (এন লগ এন) সময়ে সবচেয়ে খারাপ ক্ষেত্রে, একটি বিভাজন এবং জয় অ্যালগরিদমের মাধ্যমে। ফিস্কের সংক্ষিপ্ত প্রমাণ এবং বার্নার্ড চেজেলের রৈখিক সময় সমতল ত্রিভুজ অ্যালগরিদম ব্যবহার করে একটি রৈখিক সময় অ্যালগরিদম দিয়েছেন। যে সাধারণ বহুভুজগুলিতে ছিদ্র থাকে না, সেগুলির জন্য শীর্ষ এবং প্রান্ত রক্ষীদের জন্য একটি ধ্রুবক ফ্যাক্টর আনুমানিক অ্যালগরিদমের অস্তিত্ব ঘোষ অনুমান করেছিলেন। ঘোষের অনুমান প্রাথমিকভাবে সরল বহুভুজের দুটি বিশেষ উপ-শ্রেণীর ভার্টেক্স গার্ডের ক্ষেত্রে সত্য বলে প্রমাণিত হয়েছিল। মনোটোন বহুভুজ এবং বহুভুজ একটি প্রান্ত থেকে দুর্বলভাবে দৃশ্যমান। একটি আনুমানিক অ্যালগরিদম উপস্থাপন করা হয়েছে যা বহুপদী সময়ে একটি একক স্বর বহুভুজের জন্য একটি ভার্টেক্স গার্ড সেট গণনা করে যাতে গার্ড সেটের আকার ভার্টেক্স গার্ডের সর্বোত্তম সংখ্যার সর্বাধিক 30 গুণ হয়। একটি আনুমানিক অ্যালগরিদম উপস্থাপন করা হয়েছে যা O (n2) সময়ে একটি সাধারণ বহুভুজের জন্য একটি ভার্টেক্স গার্ড সেট গণনা করে যা একটি প্রান্ত থেকে দুর্বলভাবে দৃশ্যমান হয় যাতে গার্ড সেটের আকার সর্বাধিক 6 গুণ বেশি সংখ্যক ভার্টেক্স গার্ড হয়। পরবর্তীকালে, ভার্টেক্স গার্ড এবং এজ গার্ড ব্যবহার করে সাধারণ সাধারণ বহুভুজ রক্ষার জন্য ধ্রুবক ফ্যাক্টর আনুমানিক অ্যালগরিদম উপস্থাপন করে অনুমানটি সম্পূর্ণরূপে নিষ্পত্তি করার দাবি করা হয়। একটি প্রান্ত থেকে দুর্বলভাবে দৃশ্যমান সাধারণ বহুভুজগুলির উপশ্রেণীকে রক্ষা করার জন্য, একটি বহুপদী-সময় আনুমানিক পরিকল্পনা দ্বারা প্রস্তাবিত হয়েছিল। ভার্টেক্স গার্ডের জন্য একটি সঠিক অ্যালগরিদম প্রস্তাব করা হয়েছিল। লেখকরা বিভিন্ন শ্রেণীর বহুভুজ নিয়ে ব্যাপক গণনামূলক পরীক্ষা-নিরীক্ষা করেছেন যা দেখায় যে হাজার হাজার শীর্ষের সাথে সম্পর্কিত দৃষ্টান্তের ক্ষেত্রেও তুলনামূলকভাবে ছোট গণনার সময়ে সর্বোত্তম সমাধান পাওয়া যেতে পারে। এই উদাহরণগুলির জন্য ইনপুট ডেটা এবং সর্বোত্তম সমাধানগুলি ডাউনলোডের জন্য উপলব্ধ। যদি কোনও জাদুঘরকে পলিহেড্রন হিসাবে তিনটি মাত্রায় উপস্থাপন করা হয়, তবে প্রতিটি শীর্ষে একটি গার্ড স্থাপন করা নিশ্চিত করবে না যে সমস্ত জাদুঘর পর্যবেক্ষণে রয়েছে। যদিও পলিহেড্রনের সমস্ত পৃষ্ঠ জরিপ করা হবে, কিছু পলিহেড্রার জন্য অভ্যন্তরে এমন পয়েন্ট রয়েছে যা নজরদারির অধীনে নাও থাকতে পারে। আর্ট গ্যালারির সম্ভাব্য ব্যবহার সমস্যা আর্ট গ্যালারির সমস্যাটি একাধিক ক্যামেরা স্থাপন করতে ব্যবহার করা যেতে পারে যখন ক্যামেরার দৃষ্টিতে একটি বড় এলাকা জুড়ে ন্যূনতম সংখ্যক ক্যামেরা ব্যবহার করা হয়। আরও দেখুন একটি আয়তাকার বহুভুজকে তারা-আকৃতির বহুভুজ দিয়ে আচ্ছাদন করা, বহুভুজের একটি শ্রেণী যার জন্য আর্ট গ্যালারির সমস্যাটি একক গার্ড দিয়ে সমাধান করা যেতে পারে। আলোকসজ্জার সমস্যাঃ দেওয়ালে আয়না দেওয়া থাকলে একটি গার্ডই কি যথেষ্ট? তথ্যসূত্রের উৎস উল্লেখ করুন। । । । । । । । । । । । । । । । । । । । । । । । গণনামূলক জ্যামিতি বহুভুজ সংক্রান্ত সমস্যার প্রমাণ সম্বলিত নিবন্ধ