ভূমিকা
অ্যালগরিদমে, জীবনের মতো, নেতিবাচকতা একটি টেনে আনতে পারে।
একটি গ্রাফে দুটি বিন্দুর মধ্যে সংক্ষিপ্ততম পথ খুঁজে পাওয়ার সমস্যাটি বিবেচনা করুন — লিঙ্ক বা প্রান্ত দ্বারা সংযুক্ত নোডগুলির একটি নেটওয়ার্ক৷ প্রায়শই, এই প্রান্তগুলি বিনিময়যোগ্য নয়: একটি গ্রাফ একটি রাস্তার মানচিত্র উপস্থাপন করতে পারে যেখানে কিছু রাস্তা অন্যদের তুলনায় ধীর বা উচ্চ টোল রয়েছে। কম্পিউটার বিজ্ঞানীরা প্রতিটি প্রান্তকে একটি "ওজন" দিয়ে যুক্ত করে এই পার্থক্যগুলির জন্য হিসাব করেন যা সেই অংশ জুড়ে চলার খরচের পরিমাণ নির্ধারণ করে - সেই খরচটি সময়, অর্থ বা অন্য কিছুর প্রতিনিধিত্ব করে। 1950-এর দশক থেকে, তারা জেনেছে কিভাবে ছোটতম পাথগুলিকে মূলত যত দ্রুত সম্ভব তাত্ত্বিকভাবে খুঁজে বের করা যায়, ধরে নিই যে সমস্ত ওজন ইতিবাচক সংখ্যা।
কিন্তু কিছু গ্রাফে ওজন নেতিবাচক হতে পারে — একটি অংশ বরাবর ভ্রমণ অন্যটি অতিক্রম করার খরচ অফসেট করতে পারে। উদাহরণ স্বরূপ, একজন ডেলিভারি ড্রাইভারকে বিবেচনা করুন যাকে অবশ্যই প্যাকেজ পরিবহন থেকে আয়ের বিপরীতে গ্যাস এবং টোলের (ধনাত্মক ওজন দ্বারা উপস্থাপিত) ভারসাম্য রাখতে হবে (নেতিবাচক ওজন দ্বারা প্রতিনিধিত্ব করা)। এই ধরনের ক্ষেত্রে, দ্রুততম পরিচিত সংক্ষিপ্ততম-পাথ অ্যালগরিদম কাজ করে না। কয়েক দশক ধরে, নেতিবাচক-ওজন গ্রাফগুলিতে সংক্ষিপ্ততম পথ খুঁজে পাওয়ার জন্য দ্রুত অ্যালগরিদমগুলি অধরা রয়ে গেছে।
এখন কম্পিউটার বিজ্ঞানীদের একটি ত্রয়ী এই দীর্ঘস্থায়ী সমস্যার সমাধান করেছেন। তাদের নতুন অ্যালগরিদম, যা একটি প্রদত্ত "উৎস" নোড থেকে অন্য প্রতিটি নোডের গ্রাফের মাধ্যমে সংক্ষিপ্ততম পথগুলি খুঁজে বের করে, প্রায় সেই গতির সাথে মেলে যা ইতিবাচক-ওজন অ্যালগরিদমগুলি এতদিন আগে অর্জন করেছিল৷
আরও কী, নতুন পদ্ধতিটি কয়েক দশক-পুরাতন গাণিতিক কৌশল ব্যবহার করে, আধুনিক গ্রাফ তত্ত্ব গবেষণায় আধিপত্য বিস্তারকারী আরও পরিশীলিত পদ্ধতিগুলিকে এড়িয়ে যায়।
"আমি শুধু বিশ্বাস করতে পারিনি যে এই ধরনের একটি সহজ অ্যালগরিদম বিদ্যমান," বলেন ম্যাক্সিমিলিয়ান প্রবস্ট গুটেনবার্গ, সুইস ফেডারেল ইনস্টিটিউট অফ টেকনোলজি জুরিখের একজন কম্পিউটার বিজ্ঞানী। “এটা সবই 40 বছর ধরে আছে। কাউকে সত্যিকারের চতুর হতে এবং এটি সব কাজ করার জন্য দৃঢ়প্রতিজ্ঞ হতে লাগে।"
লোভের সীমা
গল্পটি শুরু হয় 1956 সালে, যখন ডাচ কম্পিউটার বিজ্ঞানী Edsger Dijkstra শুধুমাত্র ইতিবাচক ওজন সহ একটি গ্রাফে সংক্ষিপ্ততম পথগুলি খুঁজে বের করার জন্য একটি দ্রুত অ্যালগরিদম তৈরি করেছিলেন। এটি বোঝার জন্য, উত্স থেকে শুরু করে কল্পনা করুন এবং একবারে একটি গ্রাফ একটি নোড অন্বেষণ করুন, আপনি যেতে যেতে নতুন আবিষ্কৃত প্রান্তগুলির ওজন লিখুন। প্রতিবার যখন আপনি একটি নোড পরিদর্শন করেন, উত্স থেকে নতুন নোডের প্রতিটি প্রতিবেশীর কাছে সংক্ষিপ্ততম পথের প্রাথমিক অনুমান করুন, যদি আপনি একটি নতুন ছোট পথ খুঁজে পান তবে বিদ্যমান অনুমানগুলি আপডেট করুন৷ পরবর্তীতে কোন অনাবিষ্কৃত নোডটি পরিদর্শন করতে হবে তা স্থির করতে, একটি লোভনীয় কৌশল বলা হয় তা ব্যবহার করুন: আপনার বর্তমান অনুমান অনুসারে উত্সের নিকটতম যেটি যায় সেখানে যান৷
ইতিবাচক ওজনের সাথে, ডিজকস্ট্রার অ্যালগরিদম প্রথমবার প্রতিটি নোড পরিদর্শন করার জন্য যে পথটি নেয় তা সত্যিই সবচেয়ে ছোট। এটি দেখতে সবচেয়ে সহজ যে এটি প্রথম ধাপের জন্য সত্য। কল্পনা করুন যে দুটি নোড A এবং B ওজন 2 সহ একটি প্রান্ত দ্বারা সংযুক্ত। A যদি উৎস নোড হয় এবং এটিকে স্পর্শ করা অন্য প্রতিটি প্রান্তের ওজন বেশি থাকে, তাহলে A থেকে B পর্যন্ত সরাসরি পথটি অবশ্যই সেই দুটি বিন্দুকে সংযুক্ত করার জন্য সবচেয়ে ছোট সম্ভাব্য পথ হতে হবে। , যেহেতু অন্য কোনো পথের প্রথম অংশটি ইতিমধ্যেই দীর্ঘ হবে। অনুরূপ যুক্তি প্রতিটি ধাপে কাজ করে। অ্যালগরিদমকে কখনই পিছনে ফিরে তাকাতে হয় না, তাই একবার গ্রাফের মধ্য দিয়ে চলার পরে এটি শেষ হওয়ার গ্যারান্টিযুক্ত — এটাই এটিকে এত দ্রুত করে তোলে।
কিন্তু নেতিবাচক ওজন ডিজকস্ট্রার লোভী কৌশলের জন্য সমস্যা তৈরি করে। আবার আমাদের ডেলিভারি ড্রাইভার বিবেচনা করুন. A থেকে B পর্যন্ত একটি সরাসরি রুট যা একটি ছোট মুনাফা নেট করে এমন একটি সার্কিটাস পথের তুলনায় কম অর্থ উপার্জন করতে পারে যেখানে কোথাও একটি বড় লাভ আছে। "আপনি শুধুমাত্র স্থানীয় তথ্যের উপর ভিত্তি করে সিদ্ধান্ত নিতে পারবেন না," বলেছেন সঞ্জীব খান্না, পেনসিলভানিয়া বিশ্ববিদ্যালয়ের একজন কম্পিউটার বিজ্ঞানী। "অবশেষে একটি সত্যিকারের পুরষ্কার পেতে আপনাকে বেশ কয়েকটি আপাতদৃষ্টিতে সাবঅপ্টিমাল পদক্ষেপগুলি করতে হতে পারে।"
কয়েক দশক ধরে, কম্পিউটার বিজ্ঞানীরা নেতিবাচক-ওজন গ্রাফের উপর কাজ করে ডিজকস্ট্রার অ্যালগরিদমের গতির সাথে অনুরূপ "কম্বিনেটরিয়াল" অ্যালগরিদমের সাথে মেলানোর চেষ্টা করেছিলেন। এর মধ্যে বিচ্ছিন্ন ক্রিয়াকলাপ জড়িত - যেমন সম্ভাবনা গণনা করা, ওজন পরিবর্তন করা এবং প্রান্তগুলি বেছে নেওয়া - যা অন্তর্নিহিত গ্রাফের পৃথক কাঠামোকে প্রতিফলিত করে। তবে 1990 এর দশকে অগ্রগতি ধীর হয়ে যায়। অতি সম্প্রতি, গবেষকরা "নিরবচ্ছিন্ন অপ্টিমাইজেশান" অ্যালগরিদম ব্যবহার করেছেন, যা ক্যালকুলাস থেকে কৌশল ধার করে। দুর্ভাগ্যবশত, ফলস্বরূপ গতি সীমিত করা হয়েছে, এবং প্রায়শই সরলতার খরচে এসেছে।
চক্রটি ভেঙে দিন
2021 সালের গ্রীষ্মে, দুই কম্পিউটার বিজ্ঞানী যারা কোপেনহেগেন বিশ্ববিদ্যালয়ের সহকর্মী হয়ে উঠবেন — দানুপন নানংকাই এবং ক্রিশ্চিয়ান উলফ-নিলসেন - একটি যৌথ গবেষণা প্রকল্পের জন্য একটি বিষয় খুঁজছেন. "খ্রিস্টান বলেছিলেন, 'ওহ, যাইহোক, আমি ছুটিতে ছিলাম, এবং এর কারণে আমি খুব উচ্চাভিলাষী কিছু ভাবার চেষ্টা করছিলাম,'" স্মরণ করিয়ে দিলেন নানংকাই, যিনি এখন জার্মানির সারব্রুকেনের ম্যাক্স প্ল্যাঙ্ক ইনস্টিটিউট ফর ইনফরমেটিক্সে আছেন৷ তারা নেতিবাচক-ওজন সংক্ষিপ্ততম-পাথের সমস্যার সমাধান করেছে এবং আমন্ত্রণ জানিয়েছে হারুন বার্নস্টেইন তাদের যোগদানের জন্য Rutgers বিশ্ববিদ্যালয়ের.
তিনজন গবেষকই অন্যান্য সমস্যার জন্য কম্বিনেটরিয়াল গ্রাফ অ্যালগরিদমের বিশেষজ্ঞ ছিলেন, এবং তারা দেখতে চেয়েছিলেন যে এই তুলনামূলকভাবে প্রাচীন পদ্ধতিগুলি তাদের কতদূর পেতে পারে। বার্নস্টেইন বলেন, "আসলে উচ্চাভিলাষী এবং দীর্ঘদিন ধরে খোলা আছে এমন সমস্যা নিয়ে কাজ করার ক্ষেত্রে একটি নির্দিষ্ট স্বাধীনতা আছে।"
ত্রয়ীটি সাময়িকভাবে সম্ভাব্য গ্রাফগুলির একটি উপসেট উপেক্ষা করে শুরু করেছিল: যেগুলি নেতিবাচক চক্র রয়েছে৷ এগুলি এমন পথ যেগুলি প্রান্তগুলির একটি সিরিজের মধ্য দিয়ে যাওয়ার পরে যেখানে শুরু হয়েছিল সেখানে ফিরে যায় যার ওজন একটি ঋণাত্মক সংখ্যা পর্যন্ত যোগ করে। প্রারম্ভিক বিন্দু থেকে প্রাপ্ত ঋণাত্মক চক্র সহ একটি গ্রাফে, একটি সংক্ষিপ্ততম পথের ধারণা ভেঙ্গে যায়, যেহেতু আপনি নেতিবাচক চক্রের চারপাশে বারবার ল্যাপ করে আপনার পছন্দ মতো যে কোনও নোডের দূরত্বকে নেতিবাচক (বা লাভজনক) হিসাবে তৈরি করতে পারেন। আপনার গন্তব্যের দিকে যাচ্ছে।
গবেষকরা সন্দেহ করেছিলেন যে দীর্ঘ নেতিবাচক পথগুলি প্রধানত সমস্যাটিকে কঠিন করার জন্য দায়ী। তাই তারা কাছাকাছি নোডগুলির আঁটসাঁট ক্লাস্টারগুলিতে ফোকাস করতে শুরু করে, যেগুলিতে কোনও দীর্ঘ নেতিবাচক পথ থাকতে পারে না: এর কারণ যদি দুটি বিন্দু একটি ছোট ইতিবাচক পথ দ্বারা সংযুক্ত থাকে, তাদের মধ্যে একটি দীর্ঘ নেতিবাচক পথ যোগ করা একটি নেতিবাচক চক্র তৈরি করবে। একটি আঁটসাঁট ক্লাস্টারের মধ্যে, "সত্যিই যে ইতিবাচক অর্থে সবাই একসাথে কাছাকাছি থাকে তা আসলে আপনাকে নেতিবাচক প্রান্তগুলি সম্পর্কেও দরকারী তথ্য দেয়," বার্নস্টেইন বলেছিলেন। "এটি আপনাকে বলে যে জিনিসগুলি খুব নেতিবাচক হতে পারে না।"
বেশিরভাগ গ্রাফে এমন অনেকগুলি আঁট-নিট ক্লাস্টার থাকে যা একে অপরের সাথে দুর্বলভাবে সংযুক্ত থাকে। গবেষকরা যদি সমস্ত ক্লাস্টারগুলিকে চিহ্নিত করতে পারে তবে তারা সন্দেহ করেছিল যে তারা প্রতিটির মধ্যে দ্রুততম পথগুলি খুঁজে বের করার একটি উপায় বিকাশ করতে পারে। সেখান থেকে, তাদের পৃথক ক্লাস্টারগুলিকে সংযুক্ত করতে এবং মূল গ্রাফে সংক্ষিপ্ততম পথগুলি খুঁজে পেতে আরও সহজ সময় থাকতে পারে। কিন্তু এর জন্য যেকোন গ্রাফের অঞ্চলগুলিকে দ্রুত খুঁজে বের করতে হবে যেখানে নোডগুলি একত্রে কাছাকাছি রয়েছে - এমন কিছু যা তারা কীভাবে করতে হয় তা জানত না। চাবিটি এমন একটি কৌশল হিসাবে পরিণত হয়েছিল যা গ্রাফ তত্ত্বের সম্পূর্ণ ভিন্ন শাখায় উদ্ভূত হয়েছিল।
গ্রাফ আপ কাটা
1980-এর দশকে, কম্পিউটার বিজ্ঞানীরা একটি গ্রাফে আঁটসাঁট ক্লাস্টারগুলি বাছাই করার জন্য এবং সেই ক্লাস্টারগুলিকে আলাদা করার জন্য মুছে ফেলার জন্য প্রান্তগুলি সনাক্ত করতে কম-ব্যাসের পচন নামে একটি কৌশল তৈরি করেছিলেন। এই কৌশলটি গ্রাফগুলিকে স্বাধীন বিভাগে বিভক্ত করার একটি উপায় প্রদান করে। এটি "ডিস্ট্রিবিউটেড" অ্যালগরিদমগুলির সুবিধার্থে উদ্ভাবিত হয়েছিল, যেখানে গণনাগুলি একটি গ্রাফের বিভিন্ন অংশে সমান্তরালভাবে চলে, তাই এটি স্বল্পতম-পাথের অ্যালগরিদমগুলির জন্য কম স্পষ্টতই কার্যকর ছিল, যার এই বৈশিষ্ট্য নেই৷
Bernstein, Nanongkai এবং Wulff-Nilsen বুঝতে পেরেছিলেন যে কম-ব্যাসের পচন তাদের খুব বেশি ঘনীভূত নেতিবাচকতা ছাড়াই ক্লাস্টার সনাক্ত করতে সাহায্য করতে পারে। দুর্ভাগ্যবশত, স্ট্যান্ডার্ড লো-ব্যাসের পচনশীল অ্যালগরিদমগুলি শুধুমাত্র অনির্দেশিত গ্রাফগুলিতে কাজ করে — যেগুলির প্রতিটি প্রান্ত উভয় দিক দিয়ে অতিক্রম করা যেতে পারে। নেতিবাচক-ওজন সংক্ষিপ্ততম-পাথ সমস্যা, এদিকে, শুধুমাত্র নির্দেশিত গ্রাফগুলিতে বোঝা যায়, যেখানে প্রতিটি প্রান্ত একটি একমুখী রাস্তা। (অন্যথায়, একটি একক অনির্দেশিত ঋণাত্মক প্রান্তটি সেই প্রান্ত জুড়ে বারবার হপসের সমন্বয়ে একটি ঋণাত্মক চক্র তৈরি করবে।) গবেষকরা যদি কম-ব্যাসের পচন ব্যবহার করতে চান তবে তাদের এটি মানিয়ে নিতে হবে।
তারা তাদের নতুন কাগজে তাই করেছে। দ্বারা অনুপ্রাণিত গত কাজ যেখানে বার্নস্টেইন এবং উলফ-নিলসেন প্রোবস্ট গুটেনবার্গের সাথে সহযোগিতা করেছিলেন, তারা নিম্ন-ব্যাসের পচনের অনুরূপ নির্দেশিত গ্রাফগুলির জন্য একটি ফ্র্যাকচারিং পদ্ধতি তৈরি করেছিলেন। পদ্ধতিটি একটি নির্বিচারে নির্দেশিত গ্রাফকে একটি ক্রমশ টাইট-নিট ক্লাস্টারে বিভক্ত করে একটি এলোমেলো প্রক্রিয়া ব্যবহার করে মাত্র কয়েকটি প্রান্ত মুছে দেয়। পরবর্তীতে, এই ক্লাস্টারগুলি একটি স্পার্সার নেটওয়ার্ক দ্বারা সংযুক্ত থাকে যেখানে সমস্ত প্রান্ত একই দিকে নির্দেশ করে। এই ধরনের নেটওয়ার্ককে বলা হয় নির্দেশিত অ্যাসাইক্লিক গ্রাফ বা ডিএজি।
একটি ডিএজিকে একটি স্রোতের মতো ভাবুন যাতে জল বিভিন্ন পথে প্রবাহিত হতে পারে: কিছু পথ বিভিন্ন উত্স থেকে প্রবাহিত হয়, অন্যগুলি বিভিন্ন দিক থেকে প্রবাহিত হয় এবং এখনও অন্যরা বিভক্ত হয়ে আবার একসাথে মিশে যেতে পারে। কিন্তু কোন কিছুই কখনও পিছনের দিকে প্রবাহিত হয় না, তাই কোন চক্র নেই; এটি DAG-এর সাথে কাজ করা অনেক সহজ করে তোলে।
গবেষকরা দীর্ঘকাল ধরে জানেন যে কীভাবে দ্রুত DAG-এ এমনকি নেতিবাচক ওজনের সাথেও সংক্ষিপ্ততম পথগুলি খুঁজে পাওয়া যায়। সুতরাং ফ্র্যাকচারিং কৌশলটি তিন গবেষককে যেকোনও নির্দেশিত গ্রাফকে দুটি বিশেষ ক্ষেত্রের সংমিশ্রণে কমাতে সক্ষম করেছে - DAGs এবং টাইট ক্লাস্টার - যেগুলি পরিচালনা করা সহজ ছিল।
নতুন শর্টেস্ট-পাথ অ্যালগরিদম বারবার ফ্র্যাকচারিং পদ্ধতি ব্যবহার করে একটি গ্রাফকে একটি DAG দ্বারা সংযুক্ত টাইট-নিট ক্লাস্টারে বিভক্ত করতে। তারপরে এটি সেই ক্লাস্টারগুলিকে আরও এবং আরও ভেঙে দেয়। প্রক্রিয়া শেষে, অন্তর্নিহিত স্তরের ক্লাস্টারগুলি যতটা সম্ভব ঘনিষ্ঠভাবে সংযুক্ত থাকে। অ্যালগরিদমটি এত দ্রুত হওয়ার কারণটির একটি অংশ হল যে এটি একটি খুব বড় গ্রাফকে সম্পূর্ণরূপে ভেঙে ফেলতে অনেক পুনরাবৃত্তির প্রয়োজন হয় না, ঠিক যেমন আপনি যদি বারবার বিভাজন করেন তবে একটি বৃহৎ সংখ্যাকে একটি যুক্তিসঙ্গত আকারে কমাতে সময় লাগে না। এটা অর্ধেক.
এই পদ্ধতিতে গ্রাফটিকে সম্পূর্ণভাবে ভেঙে ফেলার সাথে, গবেষকরা গ্রাফের প্রতিটি অংশের মাধ্যমে দ্রুততম পথ খুঁজে পেতে পারেন। নেস্টেড গ্রাফ কাঠামোর অভ্যন্তরীণ স্তরে আঁটসাঁট ক্লাস্টারগুলির জন্য, এটি সহজ ছিল - তাদের কার্যত কোনও নেতিবাচকতা অবশিষ্ট ছিল না। এবং গবেষকরা ইতিমধ্যেই জানতেন কিভাবে তাদের সাথে যোগদানকারী DAG বিভাগগুলিতে সংক্ষিপ্ততম পথগুলি খুঁজে বের করতে হয়।
অবশেষে, অ্যালগরিদম ফ্র্যাকচারিং প্রক্রিয়ার দ্বারা মুছে ফেলা প্রান্তগুলিকে আবার যুক্ত করে এবং সংক্ষিপ্ততম পথগুলিতে তাদের প্রভাবগুলি গণনা করে৷ গবেষকরা প্রমাণ করেছেন যে প্রান্তগুলি এলোমেলোভাবে মুছে ফেলার জন্য তাদের প্রক্রিয়াটি প্রায় সবসময়ই "অগ্রসর" প্রান্তগুলিকে দূর করার জন্য শুধুমাত্র কয়েকটি মুছে ফেলার প্রয়োজন হয় - যে ধরনের তাদের DAG কে বড় চক্রের সাথে একটি গ্রাফে পরিণত করবে। এটি অত্যন্ত অসম্ভাব্য করে তুলেছে যে কোনও সংক্ষিপ্ততম পথটি অনেকগুলি পশ্চাৎপদ অংশের মধ্য দিয়ে যাবে, তাই তারা 1950 এর দশকের দুটি পাঠ্যপুস্তক পদ্ধতির সমন্বয় করে এই জটিল চূড়ান্ত পদক্ষেপটি সমাধান করতে পারে: ডিজকস্ট্রার অ্যালগরিদম এবং নেতিবাচক-ওজন গ্রাফগুলির জন্য প্রথম অ্যালগরিদম তৈরি করা হয়েছিল।
"এটি এই ধারণাগুলির একটি অত্যন্ত চতুর রচনা," খান্না বলেছিলেন। অ্যালগরিদম হল নেতিবাচক-ওজন গ্রাফগুলির জন্য প্রথম যা "নিকট-রৈখিক" সময়ে চলে — যার অর্থ হল এর রানটাইম সমস্ত প্রান্তগুলি গণনা করার জন্য প্রয়োজনীয় সময়ের প্রায় সমানুপাতিক, এটি সম্ভবত সবচেয়ে দ্রুত হতে পারে।
এবং নেতিবাচক চক্র সহ গ্রাফগুলির কী, যা গবেষকরা শুরুতে উপেক্ষা করার সিদ্ধান্ত নিয়েছিলেন? তাদের সংক্ষিপ্ততম-পাথ অ্যালগরিদমকে শেষ করার পরে, তারা দেখিয়েছে যে এটি নেতিবাচক চক্রগুলি চিহ্নিত করার জন্য একটি দ্রুত অ্যালগরিদম হিসাবেও কাজ করতে পারে। কার্যত কোন গ্রাফ তার নাগালের বাইরে ছিল.
সমান্তরাল পথ
বার্নস্টেইন 2022 ফাউন্ডেশনস অফ কম্পিউটার সায়েন্স কনফারেন্সে দলের ফলাফল উপস্থাপন করেছিলেন, যেখানে তাদের নতুন অ্যালগরিদম বর্ণনাকারী পাণ্ডুলিপি দুটি সেরা কাগজের মধ্যে একটি হিসাবে বিবেচিত হয়েছিল। দ্য অন্য কাগজ গ্রাফ তত্ত্বের দীর্ঘস্থায়ী সমস্যা সমাধানের জন্য একটি নতুন কাছাকাছি-রৈখিক-সময় অ্যালগরিদম বর্ণনা করতেও ঘটেছে।
সেই অ্যালগরিদমটি, প্রোবস্ট গুটেনবার্গ এবং অন্য পাঁচজন গবেষক দ্বারা তৈরি করা হয়েছে, ন্যূনতম-খরচ প্রবাহ নামে একটি আরও সাধারণ সমস্যা সমাধান করেছে, যার লক্ষ্য হল সমান্তরালভাবে অনেকগুলি পাথের মাধ্যমে পরিবহন অপ্টিমাইজ করা, এবং প্রতিটি প্রান্তের সর্বোচ্চ ক্ষমতার পাশাপাশি একটি সংশ্লিষ্ট খরচ রয়েছে। . সংক্ষিপ্ততম-পাথের সমস্যাগুলি ন্যূনতম-খরচের প্রবাহের একটি বিশেষ ক্ষেত্রে, তাই নতুন ন্যূনতম-খরচ-প্রবাহ অ্যালগরিদমটি আমূল ভিন্ন পদ্ধতির সত্ত্বেও, কাছাকাছি-রৈখিক সময়ে নেতিবাচক-ওজন-স্বল্পতম-পাথের সমস্যা সমাধানের জন্য ব্যবহার করা যেতে পারে।
ন্যূনতম-খরচের প্রবাহের উপর কাজ করা দলটি তাদের সাধারণ-উদ্দেশ্যের দ্রুত অ্যালগরিদমকে বিকশিত করেছে একটি জটিল সংশ্লেষণের সমন্বয়ে এবং ক্রমাগত অপ্টিমাইজেশান কৌশল ব্যবহার করে যা এটিকে অনুশীলনে অবাধ্য করে তোলে, অন্তত বর্তমানে। বার্নস্টাইন এবং তার সহকর্মীদের দ্বারা সম্মিলিত অ্যালগরিদম, যদিও একটি আরও নির্দিষ্ট সমস্যার মধ্যে সীমাবদ্ধ, সরলতা ত্যাগ ছাড়াই এর কাছাকাছি-রৈখিক রানটাইম অর্জন করে।
প্রবস্ট গুটেনবার্গ বলেছেন, "এই কাগজটি সম্পর্কে এটিই বিস্ময়কর। "আপনি এটি একজন স্নাতক ছাত্রকে ব্যাখ্যা করতে পারেন এবং আপনি এটি আপনার কম্পিউটারে প্রয়োগ করতে পারেন।"
ফলস্বরূপ, এই নতুন অ্যালগরিদমটি গ্রাফ তত্ত্বের অন্যান্য সমস্যার সমন্বিত পদ্ধতির প্রতি আগ্রহ পুনরুজ্জীবিত করেছে। বিশুদ্ধভাবে সম্মিলিত অ্যালগরিদম ব্যবহার করে কোন সমস্যাগুলি দ্রুত সমাধান করা যেতে পারে এবং যেগুলির জন্য বিগত 20 বছরে বিকশিত ক্রমাগত কৌশলগুলি সত্যিই প্রয়োজন তা দেখার বিষয়।
"এটি একটি দার্শনিক প্রশ্ন যা আমি বোঝার চেষ্টা করছি," নানংকাই বলেছেন। "এই সংক্ষিপ্ততম-পথের সমস্যাটি কিছুটা আশা দেয়।"
- এসইও চালিত বিষয়বস্তু এবং পিআর বিতরণ। আজই পরিবর্ধিত পান।
- প্লেটোব্লকচেন। Web3 মেটাভার্স ইন্টেলিজেন্স। জ্ঞান প্রসারিত. এখানে প্রবেশ করুন.
- উত্স: https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/
- 20 বছর
- 2021
- 2022
- a
- সম্পর্কে
- অনুযায়ী
- হিসাব
- অর্জন
- দিয়ে
- প্রকৃতপক্ষে
- অ্যাসাইক্লিক
- খাপ খাওয়ানো
- যোগ করে
- পর
- বিরুদ্ধে
- অ্যালগরিদম
- আলগোরিদিম
- সব
- ইতিমধ্যে
- সর্বদা
- উচ্চাকাঙ্ক্ষী
- প্রাচীন
- এবং
- অন্য
- পৃথক্
- অভিগমন
- পন্থা
- কাছাকাছি
- যুক্ত
- পিছনে
- ভারসাম্য
- ভিত্তি
- কারণ
- পরিণত
- আগে
- শুরু হয়
- বিশ্বাস করা
- বার্নস্টেন
- সর্বোত্তম
- মধ্যে
- তার পরেও
- বিশাল
- ধার করা
- শাখা
- বিরতি
- বিরতি
- ভাঙা
- হিসাব করে
- নামক
- ধারণক্ষমতা
- কেস
- মামলা
- কিছু
- সিআইএস
- ঘনিষ্ঠ
- ঘনিষ্ঠভাবে
- গুচ্ছ
- সহযোগিতা
- সহকর্মীদের
- সমাহার
- মিশ্রন
- আসা
- গণনা
- কম্পিউটার
- কম্পিউটার বিজ্ঞান
- ঘনীভূত
- সম্মেলন
- সংযুক্ত
- সংযোজক
- বিবেচনা
- গঠিত
- একটানা
- মূল্য
- পারা
- সৃষ্টি
- বর্তমান
- এখন
- কাটা
- চক্র
- DAG
- কয়েক দশক ধরে
- সিদ্ধান্ত নিয়েছে
- সিদ্ধান্ত
- বিলি
- বর্ণনা করা
- গন্তব্য
- নির্ধারিত
- বিকাশ
- উন্নত
- DID
- পার্থক্য
- বিভিন্ন
- কঠিন
- সরাসরি
- অভিমুখ
- আবিষ্কৃত
- দূরত্ব
- না
- Dont
- নিচে
- চালক
- ডাচ
- প্রতি
- আয় করা
- সহজ
- সবচেয়ে সহজ পদ্ধিতি হল
- প্রান্ত
- প্রভাব
- বাছা
- অপনীত
- সক্ষম করা
- সম্পূর্ণরূপে
- মূলত
- হিসাব
- অনুমান
- এমন কি
- কখনো
- সবাই
- বিদ্যমান
- বিদ্যমান
- বিশেষজ্ঞদের
- ব্যাখ্যা করা
- এক্সপ্লোরিং
- অত্যন্ত
- সহজতর করা
- ফ্যান
- দ্রুত
- দ্রুততম
- যুক্তরাষ্ট্রীয়
- কয়েক
- চূড়ান্ত
- পরিশেষে
- আবিষ্কার
- আবিষ্কার
- খুঁজে বের করে
- প্রথম
- প্রথমবার
- প্রবাহ
- প্রবাহ
- কেন্দ্রবিন্দু
- পাওয়া
- ফাউন্ডেশন
- স্বাধীনতা
- থেকে
- সম্পূর্ণরূপে
- অধিকতর
- গ্যাস
- সাধারণ
- সাধারন ক্ষেত্রে
- জার্মানি
- পাওয়া
- প্রদত্ত
- দেয়
- Go
- লক্ষ্য
- চিত্রলেখ
- গ্রাফ
- লোভী
- নিশ্চিত
- গুটেনবার্গ
- অর্ধেক
- থাবা
- হাতল
- ঘটেছিলো
- শিরোনাম
- সাহায্য
- ঊর্ধ্বতন
- আশা
- কিভাবে
- কিভাবে
- যাহোক
- এইচটিএমএল
- HTTPS দ্বারা
- ধারনা
- সনাক্ত করা
- বাস্তবায়ন
- in
- আয়
- স্বাধীন
- স্বতন্ত্র
- তথ্য
- অনুপ্রাণিত
- উদাহরণ
- প্রতিষ্ঠান
- স্বার্থ
- উদ্ভাবিত
- জড়িত করা
- IT
- পুনরাবৃত্তি
- যোগদানের
- যোগদান
- চাবি
- রকম
- জানা
- পরিচিত
- বড়
- বৃহত্তর
- উচ্চতা
- জীবন
- সীমিত
- সীমা
- লিঙ্ক
- স্থানীয়
- দীর্ঘ
- অনেকক্ষণ
- দীর্ঘস্থায়ী
- আর
- দেখুন
- প্রণীত
- করা
- তৈরি করে
- মেকিং
- পদ্ধতি
- অনেক
- মানচিত্র
- ম্যাচ
- গাণিতিক
- সর্বোচ্চ
- সর্বাধিক
- মানে
- এদিকে
- মার্জ
- পদ্ধতি
- হতে পারে
- আধুনিক
- টাকা
- অধিক
- প্যাচসমূহ
- চলন্ত
- প্রায়
- নেতিবাচক
- প্রতিবেশী
- জাল
- নেটওয়ার্ক
- নতুন
- পরবর্তী
- নোড
- নোড
- ধারণা
- সংখ্যা
- সংখ্যার
- অফসেট
- ONE
- খোলা
- অপারেশনস
- অপ্টিমাইজেশান
- অপ্টিমিজ
- মূল
- সম্ভূত
- অন্যান্য
- অন্যরা
- অন্যভাবে
- প্যাকেজ
- পেয়ারিং
- কাগজ
- কাগজপত্র
- সমান্তরাল
- অংশ
- যন্ত্রাংশ
- পাসিং
- গত
- পথ
- পেনসিলভানিয়া
- বাছাই
- Plato
- প্লেটো ডেটা ইন্টেলিজেন্স
- প্লেটোডাটা
- বিন্দু
- পয়েন্ট
- ধনাত্মক
- সম্ভাবনার
- সম্ভব
- কার্যকরীভাবে
- অনুশীলন
- উপস্থাপন
- সমস্যা
- সমস্যা
- প্রক্রিয়া
- মুনাফা
- লাভজনক
- উন্নতি
- প্রকল্প
- সম্পত্তি
- প্রতিপন্ন
- উপলব্ধ
- বিশুদ্ধরূপে
- স্থাপন
- কোয়ান্টাম্যাগাজিন
- প্রশ্ন
- দ্রুত
- মূলত
- এলোমেলো
- দ্রুত
- নাগাল
- বাস্তব
- প্রতীত
- কারণ
- ন্যায্য
- সম্প্রতি
- হ্রাস করা
- প্রতিফলিত করা
- অঞ্চল
- অপেক্ষাকৃতভাবে
- রয়ে
- দেহাবশেষ
- পুনরাবৃত্ত
- পুনঃপুনঃ
- চিত্রিত করা
- প্রতিনিধিত্ব
- প্রতিনিধিত্ব করে
- প্রয়োজন
- প্রয়োজনীয়
- গবেষণা
- গবেষকরা
- দায়ী
- সীমাবদ্ধ
- ফল
- ফলে এবং
- পুরষ্কার
- রাস্তা
- রুট
- চালান
- দৌড়
- রুতগর বিশ্ববিদ্যালয়
- বলিদান
- বলেছেন
- একই
- বিজ্ঞান
- বিজ্ঞানী
- বিজ্ঞানীরা
- অনুসন্ধানের
- বিভাগে
- রেখাংশ
- অংশ
- অনুভূতি
- ক্রম
- স্থায়ী
- বিভিন্ন
- সংক্ষিপ্ত
- অনুরূপ
- সহজ
- সরলতা
- থেকে
- একক
- আয়তন
- ছোট
- So
- সমাধান
- সমাধানে
- কিছু
- কেউ
- কিছু
- কোথাও
- বাস্তববুদ্ধিসম্পন্ন
- উৎস
- সোর্স
- প্রশিক্ষণ
- নির্দিষ্ট
- স্পীড
- বানান করা
- বিভক্ত করা
- মান
- শুরু
- শুরু
- শুরু হচ্ছে
- ধাপ
- এখনো
- গল্প
- কৌশল
- প্রবাহ
- রাস্তা
- গঠন
- ছাত্র
- এমন
- গ্রীষ্ম
- সুইস
- গ্রহণ করা
- লাগে
- গ্রহণ
- টীম
- প্রযুক্তি
- প্রযুক্তিঃ
- বলে
- পাঠ্যপুস্তক
- সার্জারির
- গ্রাফ
- উৎস
- তাদের
- কিছু
- তিন
- দ্বারা
- সময়
- থেকে
- একসঙ্গে
- অত্যধিক
- বিষয়
- স্পর্শ
- পরিবহন
- ভ্রমণ
- ব্যাধি
- সত্য
- চালু
- পরিণত
- নিম্নাবস্থিত
- বোঝা
- বিশ্ববিদ্যালয়
- আপডেট
- ব্যবহার
- অবকাশ
- ফলত
- চেয়েছিলেন
- পানি
- webp
- ওজন
- কি
- কিনা
- যে
- হু
- মধ্যে
- ছাড়া
- হয়া যাই ?
- কাজ
- কাজ
- would
- বছর
- আপনি
- আপনার
- zephyrnet
- জুরিখ