مسیله ی Rod Cutting یا برش میله یکی از بهترین مسایل برای بررسی حل سوال با روش های بازگشتی ( recursive ) و برنامه نویسی پویا ( dynamic programming ) است.

در این پست این مسیله را به سه روش مختلف حل می کنیم و از نظر زمانی سه روش را مقایسه می کنیم.با این سه الگوریتم  این سوال را حل خواهیم کرد :

1.  الگوریتم بازگشتی یا Recursive
2. الگوریتم برنامه نویسی پویا از بالا به پایین یا Dynamic programming Top Down
3. الگوریتم برنامه نویسی پویا از پایین به بالا یا Dynamic programming Bottom Up

معرفی سوال برش میله یا Rod Cutting :

یک کارخانه، میله های آهنی (البته ورژن هایی دیگر از این مسیله با عنوان برش شیرینی و غیره هم موجود است) را از یک کارخانه ی دیگر می خرد و آن ها را به مشتری های خود می فروشد ، این کارخانه میله ها را در ۱۰ سایز مختلف می فروشد که در زیر اندازه ی هر میله را همراه با قیمتش می بینید:

وقتی مشتری میله با طول ۴ سفارش می دهد کارخانه می تواند یک میله به طول چهار به او بدهد که قیمتش می شود ۹ دلار و یا میکله با طول ۴ را برش بدهد و دو میله با طول ۲ بدهد که قیمتش می شود ۱۰ دلار و یا … نحوه ی برش کاملا در اختیار کارخانه است.

توجه داشته باشید که اگر خریدار میله ای با طول ۲۲ متر سفارش داد کارخانه نمی تواند میله ای کامل و بدون برش به او بدهد بلکه طول میله ها باید در جدول بالا موجود باشد و باید ۲۲ متر میله را در قالب میله هایی با طول کمتر بدهد که در جدول بالا است به خریدار تحویل دهد.

 هدف این مسیله آن است که بیشترین سودی را که از انواع برش یک میله به دست می آید را مشخص کنیم.

الگوریتم و کد سوال برش میله ( Rod cutting ) با روش بازگشتی ( Recursive )

در این روش فضای حالات مسیله را به صورت بازگشتی و عقبگرد ( backtrack  ) جست و جو می کنیم و راهی که بیشترین سود را ایجاد را پیدا می کنیم.

فرض کنید میله ای به طول ۴ را می خواهیم بفروشیم درخت حالات برش ها برای این میله به شکل زیر است:

همین طور که در بالا مشاهده می کنید بیشترین سود را زمانی می بریم که میله به طول چهار را به دو قسمت با طول دو برش دهیم و از آنجایی که هر برش به طول ۲ قیمتی برابر ۵ دلار دارد سود به دست آمده برابر ۱۰ دلار می شود در سایر حالت ها سود کم تر از ۱۰ دلار می شود.

تابع زیر به صورت بازگشتی و عقبگرد درخت بالا را جست و جو می کند و بیشترین سود ممکن را به دست می آورد.

p وکتوری است که مقادیر پیش فرض برش ها و قیمت آن ها را در آن نگه داشته ایم و n طول میله است.

int rodCutingRecursive(vector<int> p, int n)
{
	if (n == 0)
	{
		return 0;
	}
	else
	{
		int resultOfCut;
		int max = INT_MIN;

		for (size_t i = 1; i <= p.size() && i <= n; i++)
		{
			resultOfCut = p[i - 1] + rodCutingRecursive(p, n - i);

			if (max < resultOfCut)
			{
				max = resultOfCut; 
			}
		}

		return max;
	}
}

و این هم کد کلی برنامه به صورت بازگشتی است که در main برنامه تابع را برای میله هایی با طول صفر تا بیست و یک فراخوانده ایم و زمان اجرای آن را به دست آورده ایم تا با دو روش دیگر مقایسه کنیم:

// rod cutting - recursive.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>
#include <chrono>

using namespace std;

int rodCutingRecursive(vector<int> p, int n)
{
	if (n == 0)
	{
		return 0;
	}
	else
	{
		int resultOfCut;
		int max = INT_MIN;

		for (size_t i = 1; i <= p.size() && i <= n; i++)
		{
			resultOfCut = p[i - 1] + rodCutingRecursive(p, n - i);

			if (max < resultOfCut)
			{
				max = resultOfCut; 
			}
		}

		return max;
	}
}

int main( )
{
	int priceOfSection[] = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

	//vector of price
	vector<int> priceOfEachSection(priceOfSection, priceOfSection + 10);

	//start time
	auto startTime = chrono::high_resolution_clock::now();

	for (int i = 0; i < 22; i++)
	{
		cout << "Max Price for rod that is " <<  setw(5) << i << " : " << rodCutingRecursive(priceOfEachSection, i) << endl;
	}

	//end time
	auto endTime = chrono::high_resolution_clock::now();

	cout << endl << "time : " << chrono::duration_cast<chrono::seconds> (endTime - startTime).count() << " second" << endl;
	return 0;
}

در تصویر زیر نتیجه را می بینید:

همان طور که در تصویر بالا می بینید ۳۱ ثانیه طول کشید تا برنامه جواب ها را محاسبه کرد ولی در روش های دیگر این زمان را به میلی ثانیه می رسانیم.

الگوریتم و کد سوال برش میله ( Rod cutting ) با روش برنامه نویسی پویا از بالا به پایین ( Dynamic programming Top Down )

همان طور که در شکل بالا می بینید در روش قبل بارها برای ورودی یکسانی به برنامه تابع فراخوانده می شود. در شکل بالا برای مثال میله با طول چهار دوبار تابع برای برش میله با طول دو و چهار بار برش میله با طول یک فراخوانده شده است . البته مثال بالا برای میله به طول چهار مثال کوچکی است و هرچه طول میله بیشتر شود تعداد این تکرار ها به شدت افزایش می یابد به طوری که احتمالا برای میله به طول صد باید ساعت ها منتظر ماند! دلیل هم این است که تابع محاسبه حداکثر هزینه، بارها و بارها برای مقادیر یکسانی فراخوانده می شود در حالی که ما بار ها جواب آن را به دست آورده ایم.

در الگوریتم برنامه نویسی پویا با روش بالا به پایین دقیقا همان کار الگوریتم بازگشتی را انجام می دهیم با این تفاوت که مقادیر تابع را در هر بار محاسبه در یک لیست یا hash table نگه می داریم تا بار بعدی که همان مقدار نیازمان شد دوباره حسابش نکنیم.

در تابع زیر سوال برش میله را با الگوریتم برنامه نویسی پویا با روش بالا به پایین حل کرده ایم:

وکتور remember همان ساختمان داده این است که مقادیر بدست آورده را در آن ذخیره می کنیم تا دوباره استفاده کنیم

، بقیه ی عملکردش هم دقیقا مثل روش قبلی است.

int rodCuting_DP_TopDown(vector<int> p, vector<int> &remember, int n)
{
	if (n == 0)
	{
		return 0;
	}
	else
	{
		if (remember.at(n) > INT_MIN)
		{
			return remember.at(n);
		}
		else
		{
			int resultOfCut;
			int max = INT_MIN;

			for (size_t i = 1; i <= p.size() && i <= n; i++)
			{
				resultOfCut = p[i - 1] + rodCuting_DP_TopDown(p, remember,n - i);

				if (max < resultOfCut)
				{
					max = resultOfCut;
					remember.at(n) = resultOfCut;
				}
			}

			return max;
		}
	}
}

در زیر هم کد کلی برنامه را همراه main می بینید که بیشترین هزینه ی موجود را برای میله هایی با طول صفر تا ۹۹۹ حساب می کند.

// rod cutting 
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>
#include <chrono>

using namespace std;

int rodCuting_DP_TopDown(vector<int> p, vector<int> &remember, int n)
{
	if (n == 0)
	{
		return 0;
	}
	else
	{
		if (remember.at(n) > INT_MIN)
		{
			return remember.at(n);
		}
		else
		{
			int resultOfCut;
			int max = INT_MIN;

			for (size_t i = 1; i <= p.size() && i <= n; i++)
			{
				resultOfCut = p[i - 1] + rodCuting_DP_TopDown(p, remember,n - i);

				if (max < resultOfCut)
				{
					max = resultOfCut;
					remember.at(n) = resultOfCut;
				}
			}

			return max;
		}
	}
}

int main()
{
	int priceOfSection[] = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

	//vector of price
	vector<int> priceOfEachSection(priceOfSection, priceOfSection + 10);

	//vector for save value to avoid calling recursive function for same parameter again
	vector<int> remember;

	//start time
	auto startTime = chrono::high_resolution_clock::now();

	for (int i = 0; i < 1000; i++)
	{
		remember.assign(i + 1,INT_MIN);
		
		cout << "Max Price for rod that is " << setw(5) << i << " : " << rodCuting_DP_TopDown(priceOfEachSection, remember,i) << endl;
		
		remember.clear();
	}

	//end time
	auto endTime = chrono::high_resolution_clock::now();

	cout << endl << "time : " << chrono::duration_cast<chrono::seconds> (endTime - startTime).count() << " second" << endl;
	return 0;
}

در تصویر زیر جواب را برای میله هایی با طول ۰ تا ۲۱ مشاهده می کنید و همان طور که می بینید ۰ ثانیه طول کشیده است یعنی برنامه در چند میلی ثانیه تمام شده است در حالی که در روش قبل ۳۱ ثانیه طول کشیده بود.

ولی برای این که سرعت این روش را با روش بعدی اندازه بگیریم برنامه را برای میله هایی با طول ۰ تا ۹۹۹ اجرا کردم که در زیر نتایج آن را می بینید – زمان اجرایی برنامه ۱۱۲ ثانیه شد.

الگوریتم و کد سوال برش میله ( Rod cutting ) با روش برنامه نویسی پویا از پایین به بالا ( Dynamic programming Bottom Up )

در دو روش قبل به صورت بازگشتی عمل می کردیم و از بالا به پایین درخت فضای حالات برنامه را جست و جو می کردیم ولی در الگوریتم برنامه نویسی پویا در روش پایین به بالا عکس دو روش قبل عمل می کنیم و درخت را از پایین به بالا می سازیم.

برای فهمیدن کارکرد این الگوریتم به مراحل زیر توجه کنید:

برای به دست آوردن هزینه ی میله ای به طول ۱ به میله های دیگر نیاز نداریم چون میله ای به طول یک را نمی شود برش داد.

برای به دست آوردن هزینه ی میله ای به طول ۲ به بیشترین هزینه ممکن برای میله ای به طول یک نیاز داریم چون میله به طول دو را می توان برش نداد یا به میله هایی به طول یک برش داد ، ولی در مرحله ی قبل هزینه ی میله ای به طول ۱ را حساب کرده ایم.

برای بدست آوردن هزینه ی میله ای به طول ۳ بهبیشترین هزینه ممکن برای میله هایی به طول یک و دو نیار داریم ولی در مراحل قبل آن ها را به دست آورده ایم .

به همین ترتیب تا آخر.

در شکل زیر گراف ایده ی بالا را می بینید:

تابع زیر بیشترین سود ممکن را با الگوریتم برنامه نویسی پویا با روش پایین به بالا تولید می کند:

int rodCuting_DownTop(vector<int> p, int n)
{
	//vector for saving data
	vector<int> remember;

	int result;
	int max;

	for (size_t i = 0; i <= n; i++)
	{
		max = 0;

		remember.push_back(0);

		for (size_t j = 1; j <= i && j <= p.size(); j++)
		{
			result = p.at(j - 1) + remember.at(i - j);
		
			if (max < result)
			{
				max = result;
			}
		}

		remember.at(i) = max;
	}

	return remember.back();
}

p وکتور قیمت هر برش است و n طول میله است. در زیر هم کد کلی برنامه را می بینید که بیشترین سود را برای میله هایی با اندازه ی ۰ تا ۹۹۹ را حساب کرده ایم

// rod cuting - DP down top.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>
#include <chrono>

using namespace std;

int rodCuting_DownTop(vector<int> p, int n)
{
	//vector for saving data
	vector<int> remember;

	int result;
	int max;

	for (size_t i = 0; i <= n; i++)
	{
		max = 0;

		remember.push_back(0);

		for (size_t j = 1; j <= i && j <= p.size(); j++)
		{
			result = p.at(j - 1) + remember.at(i - j);
		
			if (max < result)
			{
				max = result;
			}
		}

		remember.at(i) = max;
	}

	return remember.back();
}

int main()
{
	int priceOfSection[] = { 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };

	//vector of price
	vector<int> priceOfEachSection(priceOfSection, priceOfSection + 10);

	
	//start time
	auto startTime = chrono::high_resolution_clock::now();

	for (int i = 0; i < 1000; i++)
	{
		cout << "Max Price for rod that is " << setw(5) << i << " : " << rodCuting_DownTop(priceOfEachSection, i) << endl;
	}

	//end time
	auto endTime = chrono::high_resolution_clock::now();

	cout << endl << "time : " << chrono::duration_cast<chrono::seconds> (endTime - startTime).count() << " second" << endl;
	return 0;
}

خروجی برنامه را در تصویر زیر می بینید ، در روش قبل برای همین ورودی برنامه ۱۱۲ ثانیه زمان برده بود در حالی که این روش ۲۱ ثانیه زمان می برد. ممکن است این سوال پیش بیاید  هر دو روش تکراری ها را حساب نمی کنند پس چرا دومی بسیار سریع تر است ؟ دلیلش این است در روش قبل چک می کرد آیا مقدار مورد نظر قبلا حساب شده است یا نه و همین طور تابع به صورت بازگشتی بود وقتی یک تابع فراخوانده می شود در call Stack آن تابع و تمام ورودی هایش کپی می شود به همین دلیل زمان بیشتری می برد در حالی که در دومی ساختار بازگشتی نداریم و مرتب یک تابع فراخوانده نمی شود و همین طور مطمین هستیم مقدار قبلی وجود دارد در حالی که در روش بالا به پایین چک می کردیم وجود دارد یا نه.

هزینه ی سه الگوریتم :

الگوریتم بازگشتی اول هزنینه اش از مرتبه ی (O( 2 ^ n  است.

دو الگوریتم بعدی هزینه ی یکسانی دارند و هزینه آن ها از مرتبه ی  ( O( n ^ 2  است.