Generalized distributive law
জেনারেলাইজড ডিস্ট্রিবিউটিভ ল (জিডিএল) হল ডিস্ট্রিবিউটিভ প্রপার্টির একটি সাধারণীকরণ যা একটি সাধারণ বার্তা পাসিং অ্যালগরিদমের জন্ম দেয়। এটি তথ্য তত্ত্ব, ডিজিটাল যোগাযোগ, সংকেত প্রক্রিয়াকরণ, পরিসংখ্যান এবং কৃত্রিম বুদ্ধিমত্তা সম্প্রদায়ের অনেক লেখকের কাজের একটি সংশ্লেষণ। শ্রীনিবাস এম. আজি এবং রবার্ট জে. ম্যাকএলিস একই শিরোনামে একটি সেমি-টিউটোরিয়ালে আইন এবং অ্যালগরিদম চালু করেছিলেন। ভূমিকা "গণিতে বিতরণমূলক সূত্র হল গুণ এবং যোগের ক্রিয়াকলাপ সম্পর্কিত সূত্র, যা প্রতীকীভাবে বর্ণিত হয়েছে, অর্থাৎ, দ্বিপদী গুণকের প্রতিটি পদের জন্য মনোমিয়াল ফ্যাক্টর বিতরণ করা হয়, বা আলাদাভাবে প্রয়োগ করা হয়, যার ফলে গুণফল হয়"-ব্রিটানিকা যেমন সংজ্ঞা থেকে দেখা যায়, একটি গাণিতিক অভিব্যক্তিতে বিতরণমূলক সূত্রের প্রয়োগ এতে ক্রিয়াকলাপের সংখ্যা হ্রাস করে। পূর্ববর্তী উদাহরণে ক্রিয়াকলাপের মোট সংখ্যা তিনটি (দুটি গুণ এবং একটি যোগ) থেকে কমে দুই (একটি গুণ এবং একটি যোগ) হয়েছে। বিতরণ আইনের সাধারণীকরণ দ্রুত অ্যালগরিদমের একটি বড় পরিবারের দিকে পরিচালিত করে। এর মধ্যে রয়েছে এফ. এফ. টি এবং ভিটারবি অ্যালগরিদম। নীচের উদাহরণে এটি আরও আনুষ্ঠানিক উপায়ে ব্যাখ্যা করা হয়েছেঃ কোথায় এবং বাস্তব-মূল্যবান ফাংশন, এবং (বলুন) এখানে আমরা ফলাফল পাওয়ার জন্য স্বাধীন চলকগুলিকে (,, এবং) "প্রান্তিককরণ" করছি। যখন আমরা গণনামূলক জটিলতা গণনা করি, তখন আমরা দেখতে পাই যে প্রতিটি জোড়ার জন্য, ত্রয়ীটির কারণে কিছু পদ রয়েছে যা প্রতিটি ধাপে একটি যোগ এবং একটি গুণন সহ মূল্যায়নে অংশ নিতে হবে। অতএব, প্রয়োজনীয় গণনার মোট সংখ্যা হল। তাই উপরের ফাংশনের অ্যাসিম্পটোটিক জটিলতা হল। যদি আমরা সমীকরণের আর. এইচ. এস-এ ডিস্ট্রিবিউটিভ আইন প্রয়োগ করি, তবে আমরা নিম্নলিখিতটি পেতে পারিঃ এটি বোঝায় যে এটি একটি গুণফল হিসাবে বর্ণনা করা যেতে পারে যেখানে এবং এখন, যখন আমরা গণনামূলক জটিলতা গণনা করছি, তখন আমরা দেখতে পাচ্ছি যে মূল্যায়নের জন্য পণ্যটি ব্যবহার করার সময় এবং প্রত্যেকটিতে যোগ এবং গুণ রয়েছে। অতএব, প্রয়োজনীয় গণনার মোট সংখ্যা হল। তাই গণনার অ্যাসিম্পটোটিক জটিলতা থেকে কমে যায়। এটি একটি উদাহরণের মাধ্যমে দেখায় যে বিতরণমূলক আইন প্রয়োগ গণনামূলক জটিলতা হ্রাস করে যা একটি "দ্রুত অ্যালগরিদম"-এর একটি ভাল বৈশিষ্ট্য। ইতিহাস সমাধানের জন্য বিতরণমূলক আইন ব্যবহার করা কিছু সমস্যা নিম্নরূপ গোষ্ঠীভুক্ত করা যেতে পারে। ডিকোডিং অ্যালগরিদম কম ঘনত্বের প্যারিটি-চেক কোডগুলি ডিকোডিং করার জন্য গ্যালাজার দ্বারা একটি জিডিএল-এর মতো অ্যালগরিদম ব্যবহার করা হয়েছিল। গ্যালাজারের কাজের উপর ভিত্তি করে ট্যানার ট্যানার গ্রাফ চালু করেন এবং গ্যালাজারের কাজকে বার্তা প্রেরণের আকারে প্রকাশ করেন। ট্যানার গ্রাফ ভিটারবি অ্যালগরিদম ব্যাখ্যা করতেও সহায়তা করেছিল। ফরনি লক্ষ্য করেছেন যে ভিটারবির কনভোলিউশনাল কোডগুলির সর্বাধিক সম্ভাব্যতা ডিকোডিং জিডিএল-এর মতো সাধারণতার অ্যালগরিদমও ব্যবহার করেছে। 2. ফরওয়ার্ড-ব্যাকওয়ার্ড অ্যালগরিদম ফরওয়ার্ড ব্যাকওয়ার্ড অ্যালগরিদম মার্কভ চেইনের অবস্থাগুলি ট্র্যাক করার জন্য একটি অ্যালগরিদম হিসাবে সহায়তা করেছিল। এবং এটি সাধারণ 3-এর মতো জি. ডি. এল-এর অ্যালগরিদমও ব্যবহার করা হয়েছিল। কৃত্রিম বুদ্ধিমত্তা কৃত্রিম বুদ্ধিমত্তার অনেক সমস্যা সমাধানের জন্য জংশন গাছের ধারণা ব্যবহার করা হয়েছে। এছাড়াও বালতি অপসারণের ধারণাটি অনেকগুলি ধারণা ব্যবহার করেছে। এম. পি. এফ সমস্যা এম. পি. এফ বা প্রান্তিককরণ একটি পণ্য ফাংশন একটি সাধারণ গণনামূলক সমস্যা যা বিশেষ ক্ষেত্রে বিচ্ছিন্ন হ্যাডামার্ড রূপান্তরের গণনা, মেমরি-কম চ্যানেলে একটি রৈখিক কোডের সর্বাধিক সম্ভাব্যতা ডিকোডিং এবং ম্যাট্রিক্স চেইন গুণনের মতো অনেক শাস্ত্রীয় সমস্যা অন্তর্ভুক্ত করে। জি. ডি. এল-এর শক্তি এই সত্যের মধ্যে নিহিত যে এটি এমন পরিস্থিতিতে প্রযোজ্য যেখানে সংযোজন এবং গুণগুলি সাধারণীকরণ করা হয়। এই আচরণ ব্যাখ্যা করার জন্য একটি বিনিময়যোগ্য সেমিয়ারিং একটি ভাল কাঠামো। এটি অপারেটর "" এবং "" সহ একটি সেটের উপর সংজ্ঞায়িত করা হয় যেখানে এবং একটি বিনিময়মূলক মনোয়েড এবং বিতরণ আইন ধারণ করে। ভ্যারিয়েবলগুলি এমন হতে দিন যেখানে একটি সীমাবদ্ধ সেট এবং। এখানে। যদি এবং, যাক, এবং যেখানে যাক। ধরুন একটি ফাংশনকে সংজ্ঞায়িত করা হয়েছে, যেখানে একটি বিনিময়যোগ্য সেমিয়ারিং। এছাড়াও, স্থানীয় ডোমেন এবং স্থানীয় কার্নেল হিসাবে নামকরণ করা হয়। এখন গ্লোবাল কার্নেলকে সংজ্ঞায়িত করা হয়েছেঃ এম. পি. এফ সমস্যার সংজ্ঞাঃ এক বা একাধিক সূচকের জন্য, গ্লোবাল কার্নেলের-মার্জিনালাইজেশনের মানগুলির একটি টেবিল গণনা করুন, যা এইভাবে সংজ্ঞায়িত ফাংশন। এটি লক্ষ্য করা যায় যে সুস্পষ্ট উপায়ে উদ্দেশ্যমূলক ফাংশনের গণনার জন্য ক্রিয়াকলাপ প্রয়োজন। এর কারণ হল উদ্দেশ্যমূলক ফাংশনের গণনায় সংযোজন এবং গুণন প্রয়োজন। পরবর্তী বিভাগে ব্যাখ্যা করা জি. ডি. এল অ্যালগরিদম এই গণনামূলক জটিলতা হ্রাস করতে পারে। নিম্নে এম. পি. এফ সমস্যার একটি উদাহরণ দেওয়া হল। আসুন এবং এইরকম চলক হতে দিন। এখানে এবং। এই ভেরিয়েবলগুলি ব্যবহার করে প্রদত্ত ফাংশনগুলি হল এবং এবং আমাদের গণনা এবং সংজ্ঞায়িত করতে হবেঃ এখানে স্থানীয় ডোমেন এবং স্থানীয় কার্নেলগুলি নিম্নরূপ সংজ্ঞায়িত করা হয়েছেঃ যেখানে উদ্দেশ্যমূলক ফাংশন এবং উদ্দেশ্যমূলক ফাংশন। আরেকটি উদাহরণ বিবেচনা করুন যেখানে এবং একটি প্রকৃত মূল্যবান ফাংশন। এখন, আমরা এম. পি. এফ সমস্যাটি বিবেচনা করব যেখানে বিনিময়যোগ্য সেমিয়ারিংকে সাধারণ যোগ এবং গুণ সহ বাস্তব সংখ্যার সেট হিসাবে সংজ্ঞায়িত করা হয় এবং স্থানীয় ডোমেন এবং স্থানীয় কার্নেলগুলি নিম্নরূপ সংজ্ঞায়িত করা হয়ঃ এখন যেহেতু গ্লোবাল কার্নেলকে স্থানীয় কার্নেলের গুণফল হিসাবে সংজ্ঞায়িত করা হয়, এটি এবং স্থানীয় ডোমেনের উদ্দেশ্যমূলক ফাংশন হল এটি ফাংশনের হাদামার্ড রূপান্তর। সুতরাং আমরা দেখতে পাচ্ছি যে হ্যাডামার্ড রূপান্তরের গণনা এম. পি. এফ সমস্যার একটি বিশেষ ক্ষেত্রে। আরও উদাহরণ প্রমাণ করার জন্য প্রদর্শিত হতে পারে যে এম. পি. এফ সমস্যা অনেক ধ্রুপদী সমস্যার বিশেষ কেস গঠন করে যেমন উপরে ব্যাখ্যা করা হয়েছে যার বিশদ বিবরণ জি. ডি. এল-এ পাওয়া যাবেঃ এম. পি. এফ সমস্যা সমাধানের জন্য একটি অ্যালগরিদম যদি কেউ প্রদত্ত সেটের উপাদানগুলির মধ্যে একটি সম্পর্ক খুঁজে পেতে পারে, তবে কেউ বিশ্বাস প্রচারের ধারণার উপর ভিত্তি করে এম. পি. এফ সমস্যা সমাধান করতে পারে যা "বার্তা প্রেরণ" কৌশলের একটি বিশেষ ব্যবহার। প্রয়োজনীয় সম্পর্কটি হ 'ল স্থানীয় ডোমেনের প্রদত্ত সেটটিকে একটি জংশন ট্রি হিসাবে সংগঠিত করা যেতে পারে। অন্য কথায়, আমরা গাছের শীর্ষগুলির উপাদানগুলির সাথে একটি গ্রাফ তাত্ত্বিক গাছ তৈরি করি, যেমন যে কোনও দুটি নির্বিচারে শীর্ষগুলির জন্য বলুন এবং যেখানে এবং সেখানে এই দুটি শীর্ষগুলির মধ্যে একটি প্রান্ত রয়েছে, তারপরে সংশ্লিষ্ট লেবেলগুলির ছেদ, অর্থাৎ, প্রতিটি শীর্ষে লেবেলের একটি উপসেট যা থেকে অনন্য পথে রয়েছে। উদাহরণস্বরূপ, উদাহরণ 1: নিম্নলিখিত নয়টি স্থানীয় ডোমেন বিবেচনা করুনঃ উপরে প্রদত্ত স্থানীয় ডোমেনের সেটের জন্য, নীচে দেখানো হিসাবে একটি জংশন ট্রি-তে সাজানো যেতে পারেঃ একইভাবে যদি নীচের মতো আরেকটি সেট দেওয়া হয় উদাহরণ 2: নিম্নলিখিত চারটি স্থানীয় ডোমেন বিবেচনা করুনঃ তাহলে শুধুমাত্র এই স্থানীয় ডোমেনগুলির সাথে ট্রি তৈরি করা সম্ভব নয় কারণ এই মানগুলির সেটের কোনও সাধারণ ডোমেন নেই যা উপরের সেটের যে কোনও দুটি মানের মধ্যে স্থাপন করা যেতে পারে। তবে, নীচে দেখানো হিসাবে যদি দুটি ডামি ডোমেন যুক্ত করা হয় তবে একটি জংশন ট্রি-তে আপডেটেড সেটটি সংগঠিত করাও সম্ভব এবং সহজ হবে। 5., 6. একইভাবে ডোমেনের এই সেটের জন্য, জংশন ট্রিটি নীচের মতো দেখায়ঃ জেনারেলাইজড ডিস্ট্রিবিউটিভ ল (জিডিএল) অ্যালগরিদম ইনপুটঃ স্থানীয় ডোমেনের একটি সেট। আউটপুটঃ ডোমেনের প্রদত্ত সেটের জন্য, সমস্যা সমাধানের জন্য প্রয়োজনীয় সম্ভাব্য ন্যূনতম সংখ্যক অপারেশন গণনা করা হয়। সুতরাং, যদি এবং জংশন গাছের একটি প্রান্ত দ্বারা সংযুক্ত থাকে, তবে থেকে থেকে একটি বার্তা একটি ফাংশন দ্বারা প্রদত্ত মানগুলির একটি সেট/টেবিলঃঃ। সমস্ত ফাংশন দিয়ে শুরু করা অর্থাৎ। প্রদত্ত গাছের মধ্যে এবং সমস্ত সংমিশ্রণের জন্য, অভিন্ন হিসাবে সংজ্ঞায়িত করা হয় এবং যখন একটি নির্দিষ্ট বার্তা আপডেট করা হয়, তখন এটি নীচে দেওয়া সমীকরণটি অনুসরণ করে। = যেখানে মানে এটি গাছের সংলগ্ন একটি শীর্ষ। একইভাবে প্রতিটি শীর্ষের একটি অবস্থা রয়েছে যা ফাংশন থেকে মান ধারণকারী একটি টেবিল হিসাবে সংজ্ঞায়িত করা হয়, ঠিক যেমন বার্তাগুলি 1-এ একইভাবে সূচনা করে, এর অবস্থাকে স্থানীয় কার্নেল হিসাবে সংজ্ঞায়িত করা হয়, তবে যখনই আপডেট করা হয়, এটি নিম্নলিখিত সমীকরণটি অনুসরণ করেঃ অ্যালগরিদমের মৌলিক কাজ ইনপুট হিসাবে স্থানীয় ডোমেনের প্রদত্ত সেটের জন্য, আমরা খুঁজে বের করি যে আমরা একটি জংশন ট্রি তৈরি করতে পারি কিনা, হয় সেটটি সরাসরি ব্যবহার করে বা প্রথমে সেটে ডামি ডোমেন যুক্ত করে এবং তারপরে জংশন ট্রি তৈরি করে, যদি নির্মাণ জংশন সম্ভব না হয় তবে অ্যালগরিদম আউটপুট যে প্রদত্ত সমীকরণ সমস্যাটি গণনা করার জন্য পদক্ষেপের সংখ্যা হ্রাস করার কোনও উপায় নেই, তবে একবার আমাদের জংশন ট্রি থাকলে, অ্যালগরিদমকে বার্তা নির্ধারণ করতে হবে এবং অবস্থা গণনা করতে হবে, এগুলি করে আমরা জানতে পারি যে কোথায় ধাপ রয়েছে। আমরা এখানে দুটি বিশেষ ক্ষেত্রে কথা বলতে চলেছি যথা একক ভার্টেক্স সমস্যা যেখানে উদ্দেশ্যমূলক ফাংশনটি শুধুমাত্র একটি শীর্ষে গণনা করা হয় এবং দ্বিতীয়টি হল সমস্ত ভার্টিসেস সমস্যা যেখানে লক্ষ্য হল সমস্ত শীর্ষে উদ্দেশ্যমূলক ফাংশন গণনা করা। একক-ভার্টেক্স সমস্যা দিয়ে শুরু করা যাক, জিডিএল প্রতিটি প্রান্তকে লক্ষ্যযুক্ত শীর্ষের দিকে নির্দেশ করে শুরু করবে। এখানে বার্তাগুলি শুধুমাত্র লক্ষ্যযুক্ত শীর্ষের দিকে পাঠানো হয়। মনে রাখবেন যে সমস্ত নির্দেশিত বার্তা শুধুমাত্র একবার পাঠানো হয়। বার্তাগুলি পাতার নোডগুলি থেকে শুরু হয় (যেখানে ডিগ্রি 1) লক্ষ্য শীর্ষের দিকে যায়। বার্তাটি পাতা থেকে তার পিতামাতার কাছে এবং তারপর সেখান থেকে তাদের পিতামাতার কাছে এবং লক্ষ্য শীর্ষে না পৌঁছানো পর্যন্ত চলে যায়। লক্ষ্য শীর্ষটি কেবল তখনই তার অবস্থা গণনা করবে যখন এটি তার সমস্ত প্রতিবেশীদের কাছ থেকে সমস্ত বার্তা গ্রহণ করবে। একবার আমাদের অবস্থা হয়ে গেলে, আমরা উত্তরটি পেয়ে গেছি এবং তাই অ্যালগরিদমটি শেষ হয়ে যায়। উদাহরণস্বরূপ, আসুন আমরা উপরে দেওয়া স্থানীয় ডোমেনের সেট থেকে নির্মিত একটি জংশন ট্রি বিবেচনা করি। উদাহরণ 1 থেকে সেট, এখন এই ডোমেনগুলির জন্য সময়সূচী টেবিলটি হল (যেখানে লক্ষ্য শীর্ষ)। সুতরাং একক ভার্টেক্স জি. ডি. এল-এর জটিলতা গাণিতিক ক্রিয়াকলাপ হিসাবে দেখানো যেতে পারে যেখানে (দ্রষ্টব্যঃ উপরের সমীকরণের ব্যাখ্যাটি নিবন্ধে পরে ব্যাখ্যা করা হয়েছে) এর লেবেল। এর ডিগ্রি হল (অর্থাৎ। v) সংলগ্ন শীর্ষগুলির সংখ্যা। অল-ভার্টিস সমস্যা সমাধানের জন্য, আমরা বিভিন্ন উপায়ে জিডিএল নির্ধারণ করতে পারি, তাদের মধ্যে কয়েকটি সমান্তরাল বাস্তবায়ন যেখানে প্রতিটি রাউন্ডে, প্রতিটি রাজ্য আপডেট করা হয় এবং প্রতিটি বার্তা একই সময়ে গণনা ও প্রেরণ করা হয়। এই ধরনের বাস্তবায়নে রাজ্য এবং বার্তাগুলি চক্রের সংখ্যার পরে স্থিতিশীল হবে যা গাছের ব্যাসের সর্বাধিক সমান। এই মুহুর্তে শীর্ষগুলির সমস্ত অবস্থা কাঙ্ক্ষিত উদ্দেশ্যমূলক ফাংশনের সমান হবে। এই সমস্যার জন্য জি. ডি. এল-এর সময়সূচী নির্ধারণের আরেকটি উপায় হল ক্রমিক বাস্তবায়ন যেখানে এটি একক শীর্ষ সমস্যার অনুরূপ ব্যতীত আমরা অ্যালগরিদমটি বন্ধ করি না যতক্ষণ না একটি প্রয়োজনীয় সেটের সমস্ত শীর্ষগুলি তাদের সমস্ত প্রতিবেশীদের কাছ থেকে সমস্ত বার্তা না পায় এবং তাদের অবস্থা গণনা করে। সুতরাং এই বাস্তবায়নের জন্য প্রয়োজনীয় গাণিতিক সংখ্যা সর্বাধিক গাণিতিক ক্রিয়াকলাপ। একটি জংশন ট্রি নির্মাণ একটি জংশন ট্রি নির্মাণের মূল চাবিকাঠি স্থানীয় ডোমেইন গ্রাফের মধ্যে থাকে, যা উল্লম্বতা সহ একটি ওজনযুক্ত সম্পূর্ণ গ্রাফ। প্রতিটি স্থানীয় ডোমেনের জন্য একটি, যার দ্বারা প্রান্তের ওজন সংজ্ঞায়িত করা হয়েছে। যদি, তাহলে আমরা বলি যে অন্তর্ভুক্ত রয়েছে। দ্বারা চিহ্নিত করা হয় (একটি সর্বাধিক ওজনের বিস্তৃত গাছের ওজন), যা দ্বারা সংজ্ঞায়িত করা হয় যেখানে n হল সেই সেটের উপাদানগুলির সংখ্যা। আরও স্পষ্টতা এবং বিশদ বিবরণের জন্য, দয়া করে এগুলি দেখুন। শিডিউলিং উপপাদ্য ধরা যাক একটি জংশন ট্রি যার ভার্টেক্স সেট এবং এজ সেট রয়েছে। এই অ্যালগরিদমে, বার্তাগুলি যে কোনও প্রান্তের উভয় দিকেই পাঠানো হয়, তাই আমরা প্রান্ত সেট ই-কে শীর্ষগুলির ক্রমযুক্ত জোড়ার সেট হিসাবে বলতে/বিবেচনা করতে পারি। উদাহরণস্বরূপ, চিত্র 1 থেকে নিম্নরূপ সংজ্ঞায়িত করা যেতে পারে দ্রষ্টব্যঃ উপরে আপনাকে সমস্ত সম্ভাব্য দিকনির্দেশ দেয় যা একটি বার্তা গাছে ভ্রমণ করতে পারে। জি. ডি. এল-এর সময়সূচীকে এর উপসেটগুলির একটি সীমাবদ্ধ ক্রম হিসাবে সংজ্ঞায়িত করা হয়। যা সাধারণত {} দ্বারা প্রতিনিধিত্ব করা হয়, অ্যালগরিদম চালানোর সময় আপডেট হওয়া বার্তাগুলির সেট কোথায়। কিছু স্বরলিপি সংজ্ঞায়িত/দেখার পরে, আমরা দেখতে পাব যে উপপাদ্যটি বলে, যখন আমাদের একটি সময়সূচী দেওয়া হয়, তখন সংশ্লিষ্ট বার্তাটি ভার্টেক্স সেটের সাথে একটি সীমাবদ্ধ নির্দেশিত গ্রাফ হিসাবে প্রদর্শিত হয়, যেখানে একটি সাধারণ উপাদান দ্বারা চিহ্নিত করা হয়, তারপর বার্তাটি পাস করার সমাপ্তির পরে, ভার্টেক্সে অবস্থাটি সংজ্ঞায়িত উদ্দেশ্য হবে এবং যদি গণনামূলক জটিলতা থেকে একটি পথ থাকে এখানে আমরা গণনার জন্য প্রয়োজনীয় গাণিতিক ক্রিয়াকলাপের সংখ্যার পরিপ্রেক্ষিতে এম. পি. এফ সমস্যা সমাধানের জটিলতা ব্যাখ্যা করার চেষ্টা করি। অর্থাৎ। আমরা স্বাভাবিক পদ্ধতি ব্যবহার করে গণনা করার সময় প্রয়োজনীয় ক্রিয়াকলাপের সংখ্যা (এখানে সাধারণ পদ্ধতি দ্বারা আমরা এমন পদ্ধতি দ্বারা বোঝাই যা জিডিএল-এর ধারণাগুলি ব্যবহার করে না এমন সংক্ষিপ্ত পদ্ধতিতে বার্তা পাসিং বা জংশন ট্রি ব্যবহার করে না) এবং সাধারণীকৃত বিতরণ আইন ব্যবহার করে ক্রিয়াকলাপের সংখ্যা তুলনা করি। উদাহরণস্বরূপঃ সবচেয়ে সহজ উদাহরণটি বিবেচনা করুন যেখানে আমাদের নিম্নলিখিত অভিব্যক্তিটি গণনা করতে হবে। সরলভাবে এই অভিব্যক্তিটির মূল্যায়ন করার জন্য দুটি গুণ এবং একটি সংযোজন প্রয়োজন। এই অভিব্যক্তিটি যখন বিতরণমূলক সূত্র ব্যবহার করে প্রকাশ করা হয় তখন একটি সহজ অপ্টিমাইজেশন হিসাবে লেখা যেতে পারে যা ক্রিয়াকলাপের সংখ্যাকে একটি সংযোজন এবং একটি গুণনে হ্রাস করে। উপরের বর্ণিত উদাহরণের মতো আমরা জিডিএল প্রয়োগ করে যতটা সম্ভব কম অপারেশন সম্পাদনের জন্য বিভিন্ন আকারে সমীকরণগুলি প্রকাশ করব। পূর্ববর্তী বিভাগগুলিতে যেমন ব্যাখ্যা করা হয়েছে আমরা জংশন গাছের ধারণাটি ব্যবহার করে সমস্যাটি সমাধান করি। এই গাছগুলির ব্যবহারের মাধ্যমে প্রাপ্ত অপ্টিমাইজেশান গাছের উপর একটি আধা গোষ্ঠী সমস্যা সমাধানের মাধ্যমে প্রাপ্ত অপ্টিমাইজেশনের সাথে তুলনীয়। উদাহরণস্বরূপ, সংখ্যার একটি গোষ্ঠীর সর্বনিম্ন খুঁজে বের করার জন্য আমরা লক্ষ্য করতে পারি যে যদি আমাদের একটি গাছ থাকে এবং সমস্ত উপাদানগুলি গাছের নীচে থাকে, তবে আমরা সমান্তরালভাবে সর্বনিম্ন দুটি আইটেমের তুলনা করতে পারি এবং ফলাফলের সর্বনিম্নটি মূলের কাছে লেখা হবে। যখন এই প্রক্রিয়াটি গাছে ছড়িয়ে দেওয়া হবে তখন মূলটিতে উপাদানগুলির গোষ্ঠীর সর্বনিম্ন পাওয়া যাবে। বার্তা পাসিং ব্যবহার করে জংশন ট্রি সমাধানের জটিলতা নিম্নরূপ আমরা পূর্ববর্তী ফর্মটিতে ব্যবহৃত সূত্রটি পুনর্লিখন করি। ভার্টেক্স v থেকে---- বার্তা সমীকরণে একটি বার্তা পাঠানোর জন্য এটি ইক্যুএন। একইভাবে আমরা ভার্টেক্স v-এর অবস্থা গণনা করার জন্য সমীকরণটি নিম্নরূপ পুনর্লিখন করি। ধরুন আমাদের একটি প্রান্ত আছে যা আমরা বার্তা সমীকরণ ব্যবহার করে বার্তাটি গণনা করি। গণনা করার জন্য সংযোজন এবং গুণন প্রয়োজন। (আমরা হিসাবে প্রতিনিধিত্ব করি।) কিন্তু এর জন্য অনেক সম্ভাবনা থাকবে। সুতরাং সমগ্র বার্তাটির জন্য সংযোজন এবং গুণন প্রয়োজন হবে গাছের প্রান্ত বরাবর একটি বার্তা পাঠানোর জন্য প্রয়োজনীয় গাণিতিক ক্রিয়াকলাপের মোট সংখ্যা হবে সংযোজন এবং গুণন। একবার সমস্ত বার্তা প্রেরণ করা হয়ে গেলে অ্যালগরিদমটি অবস্থার গণনার সাথে শেষ হয়। এইভাবে অবস্থা গণনা করার জন্য প্রয়োজনীয় গণনার সংখ্যা নীচে যোগ এবং গুণ হিসাবে দেওয়া হয়েছে সুতরাং গণনার সংখ্যার মোট সংখ্যা হল---যেখানে একটি প্রান্ত এবং এর আকার দ্বারা সংজ্ঞায়িত করা হয় উপরের সূত্রটি আমাদের উপরের সীমা দেয়। যদি আমরা প্রান্তের জটিলতাকে এইভাবে সংজ্ঞায়িত করি, তাহলে এইভাবে লেখা যেতে পারে যে আমরা এখন চিত্র 1-এ সংজ্ঞায়িত সমস্যার প্রান্তের জটিলতা নিম্নরূপ গণনা করি। (এখানে সরাসরি পদ্ধতি দ্বারা আমরা এমন পদ্ধতিগুলি বোঝাতে চাইছি যা বার্তা প্রেরণ ব্যবহার করে না। সরাসরি পদ্ধতি ব্যবহার করে নেওয়া সময় প্রতিটি নোডের অবস্থা গণনা করার জন্য প্রতিটি নোড এবং সময়ে বার্তা গণনা করার সমতুল্য হবে।) এখন আমরা অল-ভার্টেক্স সমস্যাটি বিবেচনা করি যেখানে বার্তাটি উভয় দিকেই পাঠাতে হবে এবং উভয় শীর্ষে অবস্থা গণনা করতে হবে। এর জন্য সময় লাগবে কিন্তু প্রাক-গণনার মাধ্যমে আমরা গুণনের সংখ্যা হ্রাস করতে পারি। এখানে ভার্টেক্সের ডিগ্রি রয়েছে। উদাহরণস্বরূপঃ যদি সংখ্যা সহ একটি সেট থাকে। এর সমস্ত ডি গুণফল সুস্পষ্টের পরিবর্তে সর্বাধিক গুণন দিয়ে গণনা করা সম্ভব। আমরা পরিমাণগুলি প্রাক-গণনা করে এটি করি এবং এর জন্য গুণন লাগে। তারপর যদি আমাদের যা আছে তা ছাড়া সবকিছুর গুণফলকে নির্দেশ করে এবং আরও অনেক কিছুর জন্য মোট গুণনের প্রয়োজন হবে জংশন ট্রি নির্মাণের ক্ষেত্রে আমরা খুব বেশি কিছু করতে পারি না, তবে আমাদের অনেকগুলি সর্বাধিক ওজন বিস্তৃত গাছ থাকতে পারে এবং আমাদের স্প্যানিং ট্রিটি সবচেয়ে কম দিয়ে বেছে নেওয়া উচিত এবং কখনও কখনও এর অর্থ জংশন ট্রি জটিলতা কমাতে একটি স্থানীয় ডোমেন যুক্ত করা হতে পারে। মনে হতে পারে যে জি. ডি. এল শুধুমাত্র তখনই সঠিক হয় যখন স্থানীয় ডোমেনগুলিকে জংশন ট্রি হিসাবে প্রকাশ করা যায়। তবে এমন ক্ষেত্রেও যেখানে চক্র এবং বেশ কয়েকটি পুনরাবৃত্তি রয়েছে সেখানে বার্তা প্রায় উদ্দেশ্যমূলক ফাংশনের সমান হবে। কম ঘনত্বের প্যারিটি-চেক কোডের জন্য গ্যালাজার-ট্যানার-উইবার্গ অ্যালগরিদমের পরীক্ষাগুলি এই দাবির সমর্থনে ছিল। তথ্যসূত্র তথ্য তত্ত্ব অ্যালগরিদম গ্রাফিক্যাল মডেল ডিজিটাল সংকেত প্রক্রিয়াকরণ