ڊيگراف الگورتھم ۽ ان تي عمل درآمد

رياضياتي سائنس ۽ ڪمپيوٽر سائنس ۾ اتي الڳ الڳ هدايت آهي، گرافڪس جو نظريو سڏيو ويندو آهي. ان جي فريم ورڪ ۾، مختلف ڪمن کي جوڙ ۽ حل ڪيا ويا آهن، مثال طور، عمودي جي وچ ۾ ننڍڙو رستو ڳولڻ بابت. رياضي پسندن جي وچ ۾ هن مسئلي کي حل ڪرڻ لاء تمام عام طريقن جو هڪ ڊگهو ڊجسٽر الورورٿم آهي.

ھڪڙو رياضياتي گراف آھي

اهو يقين آهي ته گراف جو تصور اٺين صدي عيسوي ۾ لونٽور ايولي پاران متعارف ڪرايو ويو هو. اهو اهو هو جو ڪير هن نظريي جي طبقياتي مسئلن جي حل ۽ حل جو آواز ڏنو - ڪوينگزبرگ جي ست پلن بابت. هن نظريي جي اعتراض کي بيان ڪرڻ لاء، اڪثر ڪري مختلف طرحن جي وچ ۾ حرڪت جي حيثيت ۾ اهڙي ريت هڪ قياس استعمال ڪندا آهن. پوء جهاز تي گراف روڊن جي سڄي منصوبي جي نمائندگي ڪندو، جتي عمارتون خاص نقطا آهن (مثال طور، شهرن)، ۽ ڪنج هڪ ڪنڊن واري رستي کان ٻئي (رستي جي شهرن جي وچ ۾ ٺهيل) آهن. ڊجسٽر جي الورورٿم، ٻين طريقن سان، هن سوال جو حل ڪري سگهي ٿو.

مختصر ترين رستو ڳولڻ

گرافڪس جي اصولن جي معيار مان هڪ هڪ آهي جنهن ۾ ٻن پوائنٽن جي وچ ۾ قيمت جي گهٽتائي جو اندازو لڳائڻ ضروري آهي. اهو گراف جي حل لاء جهاز تي گهٽجي سگهجي ٿو، جنهن ۾ عمارتون - شهرن - ربن طرفان منسلڪ آهن، جيڪي ممڪن روڊن جي نمائندگي ڪن ٿا. ۽ هر روڊ کي پنهنجي ڊيگهه آهي، تنهن ڪري سفر ڪرڻ لاء ڪجهه پئسي خرچ ڪرڻو پوندو. هي رقم گراف تي هڪ کنڊ جي وزن سان برابر آهي. پوء اهو مسئلو هن طريقي سان ترتيب ڪري سگهجي ٿو: طريقي سان هڪ شهر کان ٻئي طريقي سان چڪر ڪرڻ، گهٽ ۾ گهٽ پئسي تي خرچ ڪرڻ.

حل

هن مسئلي کي حل ڪرڻ لاء، ڪجهه الورگراف ٿيل ايجاد ڪئي وئي، جيڪا سائنسي دنيا ۾ گهڻو مشهور ٿي چڪي هئي. مثال طور، Floyd-Warshell एल्गोरिथ्म، फोर्ड-बेल्ल्मन एल्गोरिथ्म. ڊيجيسٽرا الورورجيم حل ڳولڻ جو هڪ طريقو آهي. اهو پڻ وزن جي لاء (هر ڪنڊ جي ڄاڻ واري وزن) گراف، ۽ اسپري لاء پڻ استعمال ڪري سگهجي ٿو. آخري رستو ڳولڻ لاء، توهان کي ڪجھ قدم ڪرڻو پوندو.

ڊيجيٽر جي الورورٿم

ھن طريقي جو مطلب اھو آھي ته سڀ عمارتون باطل ٿيل آھن، ھڪڙي شروعاتي سان گڏ، ھڪڙي خاص قيمت سان ھڪ ليبل ڏنو وڃي. ان کان پوء نتيجن ۾ اهي عمارتون شامل ٿيندا جن جي ليبل گهٽ هونديون آهن. پهرين قدم ۾، اصلي عمودي 0. جي قيمت سان گڏ هڪ ليبل لڳايو ويو آهي. پوء اهي سڀئي هيٺيون عمارتون سمجهي وينديون آهن اھي لکيل لڳل آھن جن جي قدر سرچ جي رقم ۽ واٽ جو وزن بيان ڪيو ويندو آھي. ايندڙ مرحلن جي عمارتون کان، هڪ چونڊيو آهي ته ليبل جو ننڍڙو قدر آهي، ۽ سڀني عمارتون جن کي وچ ۾ ڦوٽو استعمال ڪرڻ کان بغير وڃي سگهجي ٿو. ليبل جي نئين قيمت بيان ڪئي وئي آهي، ذريعن جي عمار جي برابر ۽ رستي جي وزن جي برابر. جيڪڏهن نتيجو ڪندڙ قيمت عمودي ليبل کان گهٽ ناهي، پوء اهو ليٽ تبديل ٿي وڃي. ٻي صورت ۾، اصلي قيمت رهي ٿي. انهي صورت ۾، هڪ الڳ صف ۾، جنهن جو طول گراف جي عمودي جي تعداد سان برابر هوندو آهي، بهتر ڪرڻ جو نتيجو محفوظ آهي، جنهن سان اهو رستو رستو طئي ڪيو ويو آهي. Dijkstra الورجٿم وانگر اهڙي طريقي تي عمل ڪرڻ، Pascal تمام آسان سهولتون مهيا ڪن ٿا. الورورٿيمم اهو فائدو حاصل ڪيو آهي ته اهو اسان کي پروگرام جي بنياد جي طور تي استعمال ڪري سگهجي ٿو جيڪا ننڍڙي سائيز آهي. اهڙي سافٽويئر مصنوعات جي مثال انٽرنيٽ تي ڳولڻ آسان آهي.

ايٽميلي رستو کي ڳولڻ جي مسئلي کي حل ڪرڻ لاء مختلف وسيلا استعمال ڪيا وڃن. هڪ حل لاء ڊيجيسٽرا جي الورورٿم، ڊيلمي اصل معلومات کي ڪڍڻ ۽ آخري نتيجو ڪڍڻ لاء هڪ بصري آسان روپ ٺاهي سگهندو.