Fréchet distance
ریاضی میں، فریشیٹ فاصلہ منحنی خطوط کے درمیان مماثلت کی ایک پیمائش ہے جو منحنی خطوط کے ساتھ پوائنٹس کے مقام اور ترتیب کو مدنظر رکھتی ہے۔ اس کا نام مورس فریشیٹ کے نام پر رکھا گیا ہے۔ بدیہی تعریف تصور کریں کہ ایک شخص اپنے کتے کو پٹے پر چلتے ہوئے ایک محدود مڑے ہوئے راستے سے گزر رہا ہے، جس میں کتا ایک علیحدہ محدود مڑے ہوئے راستے سے گزر رہا ہے۔ ہر ایک پٹے میں سست رہنے کے لیے اپنی رفتار تبدیل کر سکتا ہے، لیکن نہ ہی پیچھے کی طرف بڑھ سکتا ہے۔ دونوں منحنی خطوط کے درمیان فریشیٹ کا فاصلہ مختصر ترین پٹے کی لمبائی ہے جو دونوں کے لیے شروع سے آخر تک اپنے الگ الگ راستوں کو عبور کرنے کے لیے کافی ہے۔ نوٹ کریں کہ تعریف دو منحنی خطوط کے حوالے سے ہم آہنگ ہے-فریشیٹ کا فاصلہ یکساں ہوگا اگر کتا اپنے مالک کے ساتھ چل رہا ہو۔ رسمی تعریف ایک میٹرک اسپیس ہونے دیں۔ ایک وکر یونٹ کے وقفے سے ایک مسلسل نقشہ ہے، یعنی۔ ریپرامیٹرائزیشن ایک مسلسل، غیر کم ہونے والا، سرجیکشن ہے۔ دو منحنی خطوط کو اندر آنے دیں۔ پھر، اور کے درمیان فریشیٹ فاصلے کو تمام ریپرمیٹرائزیشنز پر لامحدود اور اور کے درمیان تمام فاصلے پر زیادہ سے زیادہ کے طور پر بیان کیا جاتا ہے۔ ریاضیاتی اشارے میں، فریشیٹ فاصلہ ہے جہاں کا فاصلہ فنکشن ہے۔ غیر رسمی طور پر، ہم پیرامیٹر کو "وقت" کے طور پر سوچ سکتے ہیں۔ پھر، کتے کی پوزیشن ہے اور وقت پر کتے کے مالک کی پوزیشن ہے (یا اس کے برعکس)۔ وقت پر ان کے درمیان پٹے کی لمبائی اور کے درمیان کا فاصلہ ہے۔ تمام ممکنہ ریپرامیٹریزشن پر لامحدود لے جانا دیئے گئے راستوں کے ساتھ چلنے کا انتخاب کرنے سے مطابقت رکھتا ہے جہاں پٹے کی زیادہ سے زیادہ لمبائی کم سے کم ہوتی ہے۔ پابندی اور غیر کم ہونے کا مطلب یہ ہے کہ نہ تو کتا اور نہ ہی اس کا مالک پیچھے ہٹ سکتا ہے۔ فریشیٹ میٹرک دو منحنی خطوط کے بہاؤ کو مدنظر رکھتا ہے کیونکہ ان پوائنٹس کے جوڑے جن کا فاصلہ فریشیٹ کے فاصلے کو ان کے متعلقہ منحنی خطوط کے ساتھ مسلسل جھاڑنے میں معاون ہوتا ہے۔ اس سے فریشیٹ کا فاصلہ منحنی خطوط کے لیے مماثلت کا ایک بہتر پیمانہ بن جاتا ہے، جیسے کہ صوابدیدی پوائنٹ سیٹوں کے لیے ہاؤزڈورف کا فاصلہ۔ دو منحنی خطوط کے لیے یہ ممکن ہے کہ ہاؤز ڈورف کا فاصلہ چھوٹا ہو لیکن فریشیٹ کا فاصلہ بڑا ہو۔ فریشیٹ کا فاصلہ اور اس کی مختلف شکلیں مورفنگ اور تحریر کی شناخت سے لے کر پروٹین کی ساخت کی صف بندی تک کئی مسائل میں استعمال ہوتی ہیں۔ آلٹ اور گوڈاؤ سب سے پہلے تھے جنہوں نے پیرامیٹرک سرچ کے اصول کی بنیاد پر یوکلڈین اسپیس میں دو کثیر الاضحی منحنی خطوط کے درمیان فریشیٹ فاصلے کا حساب لگانے کے لیے کثیر الجہتی وقت کے الگورتھم کو بیان کیا۔ ان کے الگورتھم کا چلنے کا وقت m اور n حصوں کے ساتھ دو کثیر الاضحی منحنی خطوط کے لیے ہے۔ فری اسپیس خاکہ دو منحنی خطوط کے فریشیٹ فاصلے کا حساب لگانے کا ایک اہم ذریعہ فری اسپیس خاکہ ہے، جسے آلٹ اور گوڈاؤ نے متعارف کرایا تھا۔ دی گئی فاصلے کی حد ε کے لیے دو منحنی خطوط کے درمیان فری اسپیس خاکہ پیرامیٹر اسپیس میں ایک دو جہتی خطہ ہے جو زیادہ سے زیادہ ε فاصلے پر دو منحنی خطوط پر تمام پوائنٹ جوڑوں پر مشتمل ہوتا ہے: فریشیٹ کا فاصلہ زیادہ سے زیادہ ε ہوتا ہے اگر اور صرف اس صورت میں جب فری اسپیس خاکہ نچلے بائیں کونے سے اوپری دائیں کونے تک کا راستہ رکھتا ہو، جو افقی اور عمودی دونوں سمتوں میں مونوٹون ہو۔ امکان کی تقسیم کے درمیان فاصلے کے طور پر (ایف آئی ڈی سکور) منحنی خطوط کے درمیان فاصلے کی پیمائش کے علاوہ، فریشیٹ فاصلے کو امکان کی تقسیم کے درمیان فرق کی پیمائش کے لیے بھی استعمال کیا جا سکتا ہے۔ ذرائع اور کوویرینس میٹرکس کے ساتھ دو ملٹی ویریٹ گوسیئن ڈسٹری بیوشن کے لیے، ان ڈسٹری بیوشن کے درمیان فریشیٹ کا فاصلہ ہے۔ یہ فاصلہ فریچیٹ کے آغاز کے فاصلے (ایف آئی ڈی) کی بنیاد ہے جو ایک جنریٹو مخالف نیٹ ورک کے ذریعہ تیار کردہ تصاویر کا ان حقیقی تصاویر سے موازنہ کرنے کے لیے استعمال ہوتا ہے جو تربیت کے لیے استعمال ہوتی تھیں۔ متغیرات کمزور فریشیٹ فاصلہ کلاسیکی فریشیٹ فاصلے کی ایک قسم ہے جس میں اس ضرورت کے بغیر کہ اختتامی نکات اپنے متعلقہ منحنی خطوط کے ساتھ یکسوئی سے حرکت کریں-کتے اور اس کے مالک کو ان کے درمیان پٹے کو چھوٹا رکھنے کے لیے پیچھے ہٹنے کی اجازت ہے۔ آلٹ اور گوڈاؤ ایک منسلک گرڈ گراف میں منی میکس راستوں کی کمپیوٹنگ پر مبنی کثیر الاضحی منحنی خطوط کے درمیان کمزور فریشیٹ فاصلے کا حساب لگانے کے لیے ایک آسان الگورتھم بیان کرتے ہیں۔ مجرد فریشیٹ فاصلہ، جسے جوڑی کا فاصلہ بھی کہا جاتا ہے، کثیر الاضحی منحنی خطوط کے لیے فریشیٹ میٹرک کا ایک تخمینہ ہے، جس کی تعریف ایٹر اور منیلا نے کی ہے۔ مجرد فریشیٹ فاصلہ صرف پٹے کی پوزیشنوں پر غور کرتا ہے جہاں اس کے اختتامی نکات دو کثیر الاضحی منحنی خطوط کے عمودی حصوں پر واقع ہوتے ہیں اور کسی کنارے کے اندرونی حصے میں نہیں۔ یہ خاص ڈھانچہ ایک آسان متحرک پروگرامنگ الگورتھم کے ذریعے کثیر الجہتی وقت میں مجرد فریشیٹ فاصلے کا حساب لگانے کی اجازت دیتا ہے۔ جب دونوں منحنی خطوط کو یوکلڈین خلا کے علاوہ کسی اور میٹرک جگہ میں سرایت کیا جاتا ہے، جیسے کہ پولی ہیڈرل خطہ یا رکاوٹوں کے ساتھ کچھ یوکلڈین جگہ، تو منحنی خطوط پر دو نکات کے درمیان فاصلے کو قدرتی طور پر ان کے درمیان مختصر ترین راستے کی لمبائی کے طور پر بیان کیا جاتا ہے۔ پٹے کو اس کے اختتامی نکات میں شامل ہونے والا جیوڈیسیک ہونا ضروری ہے۔ منحنی خطوط کے درمیان نتیجے میں آنے والے میٹرک کو جیوڈیسیک فریشیٹ فاصلہ کہا جاتا ہے۔ کک اور وینک ایک سادہ کثیر الاضحی میں دو کثیر الاضحی منحنی خطوط کے درمیان جیوڈیسیک فریشیٹ فاصلے کا حساب لگانے کے لیے کثیر الجہتی وقت کے الگورتھم کی وضاحت کرتے ہیں۔ اگر ہمیں مزید ضرورت ہو کہ پٹا ماحول کی میٹرک جگہ میں مسلسل حرکت کرے، تو ہم دو منحنی خطوط کے درمیان ہوموٹوپک فریشیٹ فاصلے کا تصور حاصل کرتے ہیں۔ پٹا ایک جگہ سے دوسری جگہ مسلسل تبدیل نہیں ہو سکتا-خاص طور پر، پٹا رکاوٹوں پر چھلانگ نہیں لگا سکتا، اور صرف اس صورت میں کسی علاقے پر پہاڑ پر جھاڑ سکتا ہے جب وہ کافی لمبا ہو۔ پٹے کی حرکت دونوں منحنی خطوط کے درمیان ہوموٹوپی کو بیان کرتی ہے۔ چیمبرز اور دیگر۔ یوکلڈین سطح میں کثیر الجہتی منحنی خطوط کے درمیان ہوموٹوپک فریشیٹ فاصلے کو رکاوٹوں کے ساتھ شمار کرنے کے لیے کثیر الجہتی وقت کے الگورتھم کی وضاحت کریں۔ مثالیں رداس اور بالترتیب دو متمرکز حلقوں کے درمیان فریشیٹ کا فاصلہ سب سے طویل پٹا اس وقت درکار ہوتا ہے جب مالک خاموش کھڑا ہوتا ہے اور کتا دائرے () کے مخالف سمت میں سفر کرتا ہے، اور سب سے مختصر پٹا جب مالک اور کتا دونوں دائرے () کے ارد گرد مستقل کونیی رفتار سے چلتے ہیں۔ ایپلی کیشنز فریچیٹ فاصلہ بصری درجہ بندی کا مطالعہ کرنے کے لیے استعمال کیا گیا ہے، جو کہ گرافک ڈیزائن کا اصول ہے۔ یہ بھی دیکھیں کہ فریشیٹ کے آغاز کا فاصلہ فریشیٹ کا مطلب حوالہ جات مزید پڑھنا ہے۔ ۔ ۔ میٹرک جیومیٹری ڈسٹنس ٹوپولوجی جیومیٹرک الگورتھم