নুথের অপটিমাইজেশন#
নুথের অপটিমাইজেশন, যা নুথ-ইয়াও স্পিডআপ নামেও পরিচিত, রেঞ্জ ডায়নামিক প্রোগ্রামিংয়ের একটি বিশেষ ক্ষেত্র, যা সমাধানের টাইম কমপ্লেক্সিটি একটি লিনিয়ার ফ্যাক্টর দ্বারা কমাতে পারে — স্ট্যান্ডার্ড রেঞ্জ ডিপি-র $O(n^3)$ থেকে $O(n^2)$-এ।
শর্তসমূহ#
এই স্পিডআপটি নিম্নলিখিত আকারের ট্রানজিশনের ক্ষেত্রে প্রয়োগ করা হয়
$$dp(i, j) = \min_{i \leq k < j} [ dp(i, k) + dp(k+1, j) + C(i, j) ].$$ডিভাইড অ্যান্ড কনকার ডিপি-র মতোই, ধরি $opt(i, j)$ হলো $k$-র সেই সর্বোচ্চ মান যা ট্রানজিশনের রাশিটিকে মিনিমাইজ করে (এই আর্টিকেলে $opt$-কে “অপটিমাল স্প্লিটিং পয়েন্ট” বলা হয়েছে)। অপটিমাইজেশনটির জন্য নিম্নলিখিত শর্তটি সত্য হতে হবে:
$$opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j).$$আমরা দেখাতে পারি যে এটি সত্য হয় যখন কস্ট ফাংশন $C$ নিম্নলিখিত শর্তগুলো পূরণ করে, যেখানে $a \leq b \leq c \leq d$:
১. $C(b, c) \leq C(a, d)$;
২. $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ (চতুর্ভুজ অসমতা [QI])।
এই ফলাফলটি নিচে প্রমাণ করা হয়েছে।
অ্যালগরিদম#
আসুন ডিপি স্টেটগুলো এমনভাবে প্রসেস করি যাতে আমরা $dp(i, j)$-র আগে $dp(i, j-1)$ এবং $dp(i+1, j)$ হিসাব করি, এবং একইসাথে $opt(i, j-1)$ এবং $opt(i+1, j)$-ও হিসাব করি। তাহলে $opt(i, j)$ হিসাব করতে, $k$-র মান $i$ থেকে $j-1$ পর্যন্ত পরীক্ষা করার বদলে, আমাদের শুধু $opt(i, j-1)$ থেকে $opt(i+1, j)$ পর্যন্ত পরীক্ষা করতে হবে। $(i,j)$ জোড়াগুলো এই ক্রমে প্রসেস করতে নেস্টেড ফর লুপ ব্যবহার করাই যথেষ্ট, যেখানে $i$ সর্বোচ্চ মান থেকে সর্বনিম্ন মানে যায় এবং $j$ যায় $i+1$ থেকে সর্বোচ্চ মানে।
সাধারণ ইমপ্লিমেন্টেশন#
ইমপ্লিমেন্টেশন ভিন্ন হতে পারে, তবে এখানে একটি মোটামুটি সাধারণ উদাহরণ দেওয়া হলো। কোডের গঠন রেঞ্জ ডিপি-র সাথে প্রায় অভিন্ন।
int solve() {
int N;
... // read N and input
int dp[N][N], opt[N][N];
auto C = [&](int i, int j) {
... // Implement cost function C.
};
for (int i = 0; i < N; i++) {
opt[i][i] = i;
... // Initialize dp[i][i] according to the problem
}
for (int i = N-2; i >= 0; i--) {
for (int j = i+1; j < N; j++) {
int mn = INT_MAX;
int cost = C(i, j);
for (int k = opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++) {
if (mn >= dp[i][k] + dp[k+1][j] + cost) {
opt[i][j] = k;
mn = dp[i][k] + dp[k+1][j] + cost;
}
}
dp[i][j] = mn;
}
}
return dp[0][N-1];
}কমপ্লেক্সিটি#
অ্যালগরিদমের কমপ্লেক্সিটি নিম্নলিখিত যোগফল দ্বারা অনুমান করা যায়:
$$ \sum\limits_{i=1}^N \sum\limits_{j=i+1}^N [opt(i+1,j)-opt(i,j-1)] = \sum\limits_{i=1}^N \sum\limits_{j=i}^{N-1} [opt(i+1,j+1)-opt(i,j)]. $$দেখা যায়, এই রাশির বেশিরভাগ পদ একে অপরকে বাতিল করে দেয়, শুধু $j=N-1$ সহ ধনাত্মক পদ এবং $i=1$ সহ ঋণাত্মক পদ ছাড়া। সুতরাং, পুরো যোগফলকে এভাবে অনুমান করা যায়
$$ \sum\limits_{k=1}^N[opt(k,N)-opt(1,k)] = O(n^2), $$যা রেগুলার রেঞ্জ ডিপি ব্যবহার করলে $O(n^3)$ হতো তার বদলে।
বাস্তবে প্রয়োগ#
নুথের অপটিমাইজেশনের সবচেয়ে সাধারণ প্রয়োগ হলো রেঞ্জ ডিপি-তে, প্রদত্ত ট্রানজিশন সহ। একমাত্র কঠিন বিষয় হলো প্রমাণ করা যে কস্ট ফাংশনটি প্রদত্ত শর্তগুলো পূরণ করে। সবচেয়ে সরল ক্ষেত্র হলো যখন কস্ট ফাংশন $C(i, j)$ কেবল কোনো অ্যারে (প্রশ্নের উপর নির্ভর করে) $S[i, i+1, ..., j]$ সাবঅ্যারের উপাদানগুলোর যোগফল। তবে, কখনো কখনো এগুলো আরো জটিল হতে পারে।
লক্ষ্য করুন যে ডিপি ট্রানজিশন এবং কস্ট ফাংশনের শর্তগুলোর চেয়েও গুরুত্বপূর্ণ হলো অপটিমাম স্প্লিটিং পয়েন্টের অসমতাটি। কিছু সমস্যায়, যেমন অপটিমাল বাইনারি সার্চ ট্রি সমস্যায় (যেটি আসলে এই অপটিমাইজেশনটি প্রথম যে সমস্যার জন্য তৈরি হয়েছিল), ট্রানজিশন এবং কস্ট ফাংশন কম স্পষ্ট হতে পারে, তবুও এটি প্রমাণ করা যায় যে $opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$, এবং তাই এই অপটিমাইজেশন ব্যবহার করা সম্ভব।
সঠিকতার প্রমাণ#
এই অ্যালগরিদমের সঠিকতা প্রমাণ করতে $C(i,j)$-র শর্তের ভিত্তিতে, এটি প্রমাণ করাই যথেষ্ট যে
$$ opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j) $$ধরে নিচ্ছি প্রদত্ত শর্তগুলো সত্য।
লেমা
$dp(i, j)$-ও চতুর্ভুজ অসমতা পূরণ করে, যদি সমস্যার শর্তগুলো সত্য হয়।
প্রমাণ
এই লেমার প্রমাণে স্ট্রং ইন্ডাকশন ব্যবহার করা হয়েছে। এটি F. Frances Yao রচিত Efficient Dynamic Programming Using Quadrangle Inequalities পেপার থেকে নেওয়া হয়েছে, যেটি নুথ-ইয়াও স্পিডআপ প্রবর্তন করেছিল (এই বিশেষ স্টেটমেন্টটি পেপারের লেমা ২.১)। ধারণাটি হলো দৈর্ঘ্য $l = d - a$ এর উপর ইন্ডাকশন করা। $l = 1$ এর ক্ষেত্রটি তুচ্ছ। $l > 1$ এর জন্য ২টি কেস বিবেচনা করি:
১. $b = c$ অসমতাটি $dp(a, b) + dp(b, d) \leq dp(a, d)$-তে সরল হয় (এটি ধরে নেয় যে সব $i$ এর জন্য $dp(i, i) = 0$, যা এই অপটিমাইজেশন ব্যবহারকারী সব সমস্যায় সত্য)। ধরি $opt(a,d) = z$।
- যদি $z < j$ হয়,
লক্ষ্য করুন যে
$$
dp(a, b) \leq dp_{z}(a, b) = dp(a, z) + dp(z+1, b) + C(a, b).
$$
সুতরাং,
$$
dp(a, b) + dp(b, d) \leq dp(a, z) + dp(z+1, b) + dp(b, d) + C(a, b)
$$
ইন্ডাকশন হাইপোথিসিস থেকে, $dp(z+1, b) + dp(b, d) \leq dp(z+1, d)$। এছাড়াও, দেওয়া আছে যে $C(a, b) \leq C(a, d)$। এই ২টি তথ্য উপরের অসমতার সাথে মিলিয়ে কাঙ্ক্ষিত ফলাফল পাওয়া যায়।
- যদি $z \geq j$ হয়, এই কেসের প্রমাণ পূর্ববর্তী কেসের সাথে সিমেট্রিক।
২. $b < c$ ধরি $opt(b, c) = z$ এবং $opt(a, d) = y$।
- যদি $z \leq y$ হয়,
$$
dp(a, c) + dp(b, d) \leq dp_{z}(a, c) + dp_{y}(b, d)
$$
যেখানে
$$
dp_{z}(a, c) + dp_{y}(b, d) = C(a, c) + C(b, d) + dp(a, z) + dp(z+1, c) + dp(b, y) + dp(y+1, d).
$$
$C$-তে QI ব্যবহার করে এবং $z+1 \leq y+1 \leq c \leq d$ ইনডেক্সের জন্য ডিপি স্টেটে (ইন্ডাকশন হাইপোথিসিস থেকে) কাঙ্ক্ষিত ফলাফল পাওয়া যায়।
- যদি $z > y$ হয়, এই কেসের প্রমাণ পূর্ববর্তী কেসের সাথে সিমেট্রিক।
এটি লেমার প্রমাণ সম্পন্ন করে।
মনে করি আমরা দেখাতে পারি যে
$$ dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \implies dp_{p}(i, j) \geq dp_{q}(i, j). $$$q = opt(i, j-1)$ রাখলে, সংজ্ঞানুসারে, $dp_{p}(i, j-1) \geq dp_{q}(i, j-1)$। সুতরাং, সব $i \leq p \leq q$-তে এই অসমতা প্রয়োগ করে, আমরা অনুমান করতে পারি যে $opt(i, j)$ কমপক্ষে $opt(i, j-1)$-র সমান, যা অসমতার প্রথম অংশ প্রমাণ করে।
এখন, কিছু ইনডেক্স $p+1 \leq q+1 \leq j-1 \leq j$-তে QI ব্যবহার করে, আমরা পাই
$$\begin{align} &dp(p+1, j-1) + dp(q+1, j) ≤ dp(q+1, j-1) + dp(p+1, j) \\ \implies& (dp(i, p) + dp(p+1, j-1) + C(i, j-1)) + (dp(i, q) + dp(q+1, j) + C(i, j)) \\ \leq& (dp(i, q) + dp(q+1, j-1) + C(i, j-1)) + (dp(i, p) + dp(p+1, j) + C(i, j)) \\ \implies& dp_{p}(i, j-1) + dp_{q}(i, j) ≤ dp_{p}(i, j) + dp_{q}(i, j-1) \\ \implies& dp_{p}(i, j-1) - dp_{q}(i, j-1) ≤ dp_{p}(i, j) - dp_{q}(i, j) \\ \end{align}$$সবশেষে,
$$\begin{align} &dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \\ &\implies 0 \leq dp_{p}(i, j-1) - dp_{q}(i, j-1) \leq dp_{p}(i, j) - dp_{q}(i, j) \\ &\implies dp_{p}(i, j) \geq dp_{q}(i, j) \end{align}$$এটি অসমতার প্রথম অংশ প্রমাণ করে, অর্থাৎ $opt(i, j-1) \leq opt(i, j)$। দ্বিতীয় অংশ $opt(i, j) \leq opt(i+1, j)$ একই ধারণায় দেখানো যায়, অসমতা $dp(i, p) + dp(i+1, q) ≤ dp(i+1, p) + dp(i, q)$ দিয়ে শুরু করে।
এটি প্রমাণ সম্পন্ন করে।