অসম অক্ষর খরচের জন্য সর্বোত্তম উপসর্গ-মুক্ত কোডগুলি খুঁজে পাওয়ার সমস্যা হল একটি ন্যূনতম খরচ উপসর্গ-মুক্ত কোড গণনা করা যেখানে এনকোডিং বর্ণমালা অসম খরচ (দৈর্ঘ্য) অক্ষর, দৈর্ঘ্য α এবং β, যেখানে α ≤ β থাকে। আমরা নিজেদেরকে বাইনারি গাছের মধ্যে সীমাবদ্ধ রাখি।
কোডটি একটি একমুখী গাছ দ্বারা প্রতিনিধিত্ব করা হয়, যেমন একটি হাফম্যান গাছ হাফম্যান কোডিং সমস্যার সমাধানকে উপস্থাপন করে। সাদৃশ্য থাকা সত্ত্বেও, অসম চিঠি খরচের ক্ষেত্রে ক্লাসিক্যাল হাফম্যান সমস্যার তুলনায় অনেক কঠিন; সমস্যা নিয়ে সমৃদ্ধ সাহিত্য থাকা সত্ত্বেও সাধারণ চিঠির খরচের জন্য কোনো বহুপদী সময় অ্যালগরিদম জানা বা উপলব্ধ নেই৷
যাইহোক, α এবং β হল পূর্ণসংখ্যার ধ্রুবক।
এই ক্ষেত্রে সর্বনিম্ন খরচের গাছের গণনা করার সমস্যাটি প্রথম 1961 সালে কার্প দ্বারা অধ্যয়ন করা হয়েছিল যিনি পূর্ণসংখ্যা রৈখিক প্রোগ্রামিংয়ে হ্রাস করে, n এবং β উভয় ক্ষেত্রেই একটি অ্যালগরিদম সূচক তৈরি করে সমস্যার সমাধান করেছিলেন। সেই সময় থেকে সমস্যাটির বিভিন্ন দিক নিয়ে অনেক কাজ হয়েছে যেমন; সর্বোত্তম গাছের খরচ সীমাবদ্ধ করা; বিশেষ ক্ষেত্রে সীমাবদ্ধতা যখন সমস্ত ওজন সমান হয়।
এই সমস্ত প্রচেষ্টা সত্ত্বেও এটি এখনও, আশ্চর্যজনকভাবে, অজানা যে মৌলিক সমস্যাটি বহুপদী-সময় সমাধানযোগ্য নাকি NP-সম্পূর্ণ।
Golin এবং Rote একটি O(nβ+2)-টাইম ডায়নামিক প্রোগ্রামিং অ্যালগরিদম বর্ণনা করে যা গাছটিকে টপ-ডাউন ফ্যাশনে তৈরি করে।
এটি একটি ভিন্ন পদ্ধতির প্রয়োগ করে উন্নত করা হয়েছে (একঘেয়ে-ম্যাট্রিক্স ধারণা, যেমন, মঙ্গে সম্পত্তি এবং SMAWK অ্যালগরিদম৷
থিওরেম 1:O(nβ) সময়ে সর্বোত্তম একপাশে গাছ তৈরি করা যেতে পারে।
এটি β-এর ছোট মানের ক্ষেত্রে সবচেয়ে দক্ষ পরিচিত অ্যালগরিদম; বাস্তবে চিঠির খরচ সাধারণত ছোট হয় (যেমন, মোর্স কোড)।
সম্প্রতি একটি দক্ষ আনুমানিক অ্যালগরিদমের একটি স্কিম প্রদান করা হয়েছে৷
৷থিওরেম 2
সর্বোত্তম একগাদা গাছের জন্য একটি বহুপদী সময়ের আনুমানিক স্কিম রয়েছে৷
