網(wǎng)絡(luò)放大器

問題描述

對于一個(gè)石油傳送網(wǎng)絡(luò)可由一個(gè)加權(quán)有向無環(huán)圖G表示。該圖中有一個(gè)稱為源點(diǎn)的頂點(diǎn)S ( 保證S的入度為0 ) , 從S出發(fā) , 石油流向圖中的其他頂點(diǎn) . G中每條邊上的權(quán)重為它所連接的兩點(diǎn)間的距離。

在輸送石油的過程中 , 需要有一定的壓力才能使石油從一個(gè)點(diǎn)到達(dá)另一個(gè)點(diǎn)，但壓力會(huì)隨著路程的增加而降低 ( 即壓力的損失量是路程的函數(shù) ) .

因此為了保證石油在網(wǎng)絡(luò)的正常運(yùn)輸，在網(wǎng)絡(luò)傳輸中必須保證在任何位置的壓力都要不小于最小壓力Pmin。為了維持這個(gè)最小壓力，可在G中的一些或全部頂點(diǎn)放置壓力放大器 , 壓力放大器可以將壓力恢復(fù)至該網(wǎng)絡(luò)允許的最大壓力Pmax。

可以設(shè)d為石油從壓力Pmax降為壓力Pmin所走的距離 , 在無壓力放大器的情況下石油可運(yùn)輸?shù)木嚯x不超過d .

在該問題中 , 需要在G中放置最少的壓力放大器 , 使得該傳輸網(wǎng)絡(luò)從S出發(fā)，能夠?qū)⑵洼斔偷綀D中的所有位置。

基本要求

1.針對該問題做出一定的合理分析和假設(shè)

2.確定輸入的數(shù)據(jù)格式并給出數(shù)據(jù)生成器.

3.給出兩種方法以解決上述問題，思考如何驗(yàn)證兩種方法的正確性.

4.比較兩種方法的時(shí)間和空間性能，用圖表顯示比較結(jié)果。

已經(jīng)實(shí)現(xiàn)

1. 使用分支定界和回溯解決了問題。
2. 對程序的正確性有推導(dǎo)或?qū)Ρ? 將對拍程序封裝成函數(shù)，并且驗(yàn)證了兩個(gè)方法的正確性.
3. 合理且完善的性能分析與圖表展示: 使用python的matplotlib 實(shí)現(xiàn)了時(shí)間和空間性能用圖表顯示比較結(jié)果,進(jìn)行了分析。
4. 用庫cyaron的數(shù)據(jù)生成器make.py 生成了部分?jǐn)?shù)據(jù)進(jìn)行了測試
5. 使用dot作圖的方法，實(shí)現(xiàn)了圖的可視化方便驗(yàn)證正確性，可以直觀的展示程序的結(jié)果 , 包括放大器的位置 , 每個(gè)位置的壓力 , 邊權(quán)等.
6. 程序設(shè)計(jì)規(guī)范，封裝良好，擁有詳細(xì)的注釋。
7. 壓縮包包括solution1.h solution2.h graph.h main.cpp 以及生成圖表的testRoom.py testtime.py make.py
8. GitHub實(shí)驗(yàn)代碼

部分展示

一次跑完100個(gè)樣例并且輸出到文件,包括性能分析圖表、每個(gè)樣例的圖片!

性能分析圖表，時(shí)間和空間

結(jié)構(gòu)

• graph.h 定義圖結(jié)構(gòu)DAG以及用于分支定界的子集樹
• solution1.h 回溯算法實(shí)現(xiàn)
• sooluton2.h 分支定界算法實(shí)現(xiàn)
• main.cpp Drive Program

可視化

void visualize(int i)

使用dot作圖 的方式進(jìn)行畫圖驗(yàn)證正確性，只需要輸入描述性語言，例如圖的節(jié)點(diǎn)以及信息，邊的信息，執(zhí)行dot命令 就可以畫出每個(gè)樣例的圖的信息的圖片。

最后進(jìn)行系統(tǒng)調(diào)用，把dot 作圖成為jpg

void DAG::visualize(int i)
{//可視化
	recountpre();
	//system("cd C:\\Users\\12042\\Desktop\\dagData\\outputimage");
	string name = to_string(i) + ".dot";
	std::ofstream out(name);
	out << "digraph g {\n";
	for (int i = 1; i < nodes.size(); i++) {
		out << i;
		if (place_bst[i])
			out << "[label=\"node" << i << ";pre = " << nodes[i].press << "\",style=filled, fillcolor=red];\n";
		else
			out << "[label=\"node" << i << ";pre = " << nodes[i].press << "\",style=filled, fillcolor=white];\n";
	}
	for (auto i = 1; i <= n; ++i) {
		for (auto& edge : nodes[i].edges) {
			out << i << "->" << edge.to << "[label=\"cost=" << edge.cost << "\"];\n";
		}
	}
	out << "}\n";
	out.close();
	string order = "dot -Tjpg " + to_string(i) + ".dot -o solve" + to_string(i) + ".jpg";
	system(order.c_str());
}

對拍

void check()

對拍程序即對自己程序的輸出文件與標(biāo)準(zhǔn)（正確）答案的輸出文件進(jìn)行答案比對，如果完全相同，則證明正確性上沒有問題，如果有不同，則證明正確性無法保證。 通常是單獨(dú)寫一個(gè)cpp文件，然后執(zhí)行exe，鑒于本實(shí)驗(yàn)輸出結(jié)果每個(gè)樣例有且只有一個(gè)數(shù)字，所以把他封裝成函數(shù)，每次輸入STDOUTPUT的結(jié)果和自己的結(jié)果進(jìn)行挨個(gè)比對，進(jìn)行對拍即可！

void check() {
	int flag = 0;
	stringstream ss;
	for (int i = 1; i <= 100; i++) {
		cout << "正在測試數(shù)據(jù)集: " << i << "\n";
		string opstd = "C:\\Users\\12042\\Desktop\\dagData\\outputSTD\\";
		string myin = "C:\\Users\\12042\\Desktop\\dagData\\output\\";
		opstd += to_string(i) + ".out";
		myin += to_string(i) + ".out";
		ifstream finstd(opstd);
		if (!finstd.is_open()) {
			cout << "文件打開失敗\n";
		}
		int ans; finstd >> ans;
		finstd.close();

		ifstream finmy(myin);
		if (!finmy.is_open()) {
			cout << "文件打開失敗\n";
		}
		int me; finmy >> me;
		finmy.close();
		if (me != ans) {
			cout << "Wrong Answer\n";
			ss << i << "WA！\n";
			flag = 1;
		}
		else {
			cout << "Accept\n";
		}
	}
	if (!flag) {
		cout << "All Accept!\n";
	}
	else cout << "Wrong Answer\n";
	cout << ss.str();
}

基本算法

void topsort() 拓?fù)渑判?/h4>

因?yàn)楦鱾€(gè)頂點(diǎn)之間存在著前后關(guān)系，并且有源點(diǎn)，所以為了布置好放大器，必須要建立一個(gè)拓?fù)湫蛄?，根?jù)拓?fù)湫蛄羞M(jìn)行油壓的檢測以及放大器的放置的判斷。

具體思路：

①每次找出入度為0的點(diǎn)

②將這些頂點(diǎn)以及他們的出邊刪除

③記錄刪除的順序作為拓?fù)湫蛄小?/p>

④更新受影響的點(diǎn)的入度。

⑤重復(fù)1-4直到每個(gè)點(diǎn)都確定了一個(gè)拓?fù)浯涡颉?/p>

void DAG::topsort()
{//確定一個(gè)拓?fù)湫蛄?以便后續(xù)
	int cnt = 1;
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (in_deg[i] == 0) q.push(i);
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		nodes[u].toponum = cnt;
		dig[cnt++] = u;//排序
		for (auto e : nodes[u].edges) {
			if (--in_deg[e.to] == 0)
				q.push(e.to);
		}
	}
	if (cnt < n) {
		cout << "圖中有環(huán)路！不符合要求！\n";
		return;
	}
	//for (int i = 1; i <= n; i++) 
		//cout << "top " << i << " " << dig[i] << "\n";
}

回溯算法

第一種解決算法是使用回溯+剪枝的方式解決放大器放置的問題

回溯是按照DFS的策略從根節(jié)點(diǎn)開始出發(fā)，搜索解空間樹（決策樹），每個(gè)點(diǎn)都有可能放置或者不放置放大器，而這樣的復(fù)雜度是$O（2^n）$ 為了降低復(fù)雜度，就必須使用剪枝函數(shù)，在搜索最優(yōu)解的過程中對解空間進(jìn)行剪枝，例如確定某點(diǎn)必須放置，或者確定某解空間必定不為最優(yōu)解等等，來減少解空間的搜索次數(shù)。

具體思路

void DAG::backtracking(int level, int cnt)

level 是 搜索層數(shù)，n是節(jié)點(diǎn)個(gè)數(shù)，cnt是放置的放大器個(gè)數(shù)，best是指迄今為止記錄的最優(yōu)解

①level >= n時(shí)便求得了一個(gè)解，如果此時(shí)的cnt 更小，則是一個(gè)更優(yōu)解，進(jìn)行更新最優(yōu)解的操作。

②如果level < n-1, 當(dāng)前擴(kuò)展的節(jié)點(diǎn)有兩種可能，放置或者不放置，如果該點(diǎn)向其他點(diǎn)輸送時(shí)，有的點(diǎn)油壓<PMIN,則該點(diǎn)必須放置，剪掉不放置的情況，進(jìn)行遞歸和回溯。其次，如果該點(diǎn)的油壓<Pmin 則該點(diǎn)必須放置，剪掉不放置的情況，進(jìn)行遞歸和回溯。否則，需要進(jìn)行放置和不放置的兩個(gè)決策的遞歸。

剪枝：

①如果在某層決策的時(shí)候，cnt以及大于best了，則不需要進(jìn)行決策了，因?yàn)楸厝徊皇亲顑?yōu)解。

②如果某點(diǎn)PRESS < PMIN 則必須放。 但是，事實(shí)上，從前向后按拓?fù)湫驔Q策，前面的決策已經(jīng)保證了該點(diǎn)的油壓>Pmin了，所以此種情況不會(huì)遇到!

③如果送去相鄰節(jié)點(diǎn)PRESS < PMIN，必須放增壓器，不需要考慮不放！

注意 ：如果某點(diǎn)油壓>=PMAX 或者說到其他節(jié)點(diǎn)都符合要求，也要考慮放置放大器，因?yàn)榍笞顑?yōu)解，此處不放置可能導(dǎo)致后面多個(gè)子節(jié)點(diǎn)放置，導(dǎo)致求出不為最優(yōu)解的情況，所以兩個(gè)決策都要考慮！

數(shù)據(jù)結(jié)構(gòu)

回溯方法，需要考慮解空間樹（決策樹） 但是不需要實(shí)際建立，需要在每次決策中體現(xiàn)出來即可。之后維護(hù)level cnt分別作為決策的深度，以及放置的個(gè)數(shù)，用來剪枝和確定最優(yōu)解。鄰接表的表頭node 存儲(chǔ)每個(gè)點(diǎn)的信息，例如press 以及 booster，最后需要把信息輸入到place_booster 數(shù)組，確定哪些點(diǎn)放了放大器。

// 回溯需要按照拓?fù)湫蚺埽?dfs
void DAG::backtracking(int level, int cnt)
{//進(jìn)行回溯決策樹里面 左是該節(jié)點(diǎn)不放 右子樹是放
	//搜索第level層 
	int u = dig[level];//當(dāng)前點(diǎn) level也代表了拓?fù)湫?
	if (level >= n) {//最底層了
		best_ans = min(cnt, best_ans);
		//記錄下最好的情況 不然會(huì)被沖了
		//更新放置情況
		for (int i = 1; i <= n; i++) {
			place_bst[i] = false;
			place_bst[i] = nodes[i].booster;
		}
		return;
	}

	if (level == 1) {//第一層 源點(diǎn)肯定放了（不算）只需要判斷其他邊 如果低了 就在v放
		backtracking(2, 0);
	}
	else {//其他層  如果到v 不行 則在 u放
		int j;
		int flag = 0;
		int temp_pre = -1;//臨時(shí)變量pre 用來回溯！

		//求press[u]  優(yōu)化 用入邊
		//for (auto& c : nodes[u].inedges) {
		//	int f = c.from;
		//	if (nodes[f].toponum < nodes[u].toponum)
		//	{//必須是拓?fù)湫蚯懊娴?		//		temp_pre = max(temp_pre, nodes[u].press - c.cost);
		//	}
		//}
		for (int k = 1; k < level; k++) {//求 前面到 
			for (auto& x : nodes[dig[k]].edges) {
				if (x.to == u)
					//nodes[u].press = max(nodes[u].press, nodes[dig[k]].press - x.cost);
					temp_pre = max(temp_pre, nodes[dig[k]].press - x.cost);
			}
		}

		for (j = 0; j < 2; j++)
		{//進(jìn)行兩種決策
			//剪枝1
			if (temp_pre >= Pmax) {
				backtracking(level + 1, cnt);
				break;
			}
			//剪枝2
			if (temp_pre < Pmin)
			{
				cnt++;
				nodes[u].booster = true;
				//剪枝3
				if (cnt >= best_ans) {
					return;
				}
				backtracking(level + 1, cnt);
			}
			if (j == 0) {//不放 但是需要
				for (auto& v : nodes[u].edges) {//對于所有出邊進(jìn)行判斷
					int next_pr = temp_pre - v.cost;
					if (next_pr < Pmin) {
						flag = 1;
						break;
					}
				}
			}
			//決策 put
			if (j == 1 || flag == 1) {//放
				cnt++;
				nodes[u].press = Pmax;
				nodes[u].booster = true;
				//剪枝
				if (cnt >= best_ans)
					return;
				else {
					backtracking(level + 1, cnt);
				}
			}
			//not put
			else if (j == 0) {//對應(yīng)的 j==0 && flag!=1 
				nodes[u].press = temp_pre;
				nodes[u].booster = false;
				backtracking(level + 1, cnt);
			}
		}
	}
}

分支定界

最小耗費(fèi)的優(yōu)先隊(duì)列 分支定界求解

分支定界采用子集樹來表示解空間，但是每個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)，活結(jié)點(diǎn)一旦成為擴(kuò)展節(jié)點(diǎn)，就會(huì)產(chǎn)生所有的兒子節(jié)點(diǎn)，不可能行的都丟棄。使用最小耗費(fèi)分支定界的限界函數(shù)來進(jìn)行生成和展開活結(jié)點(diǎn)數(shù)量。每次確定最小耗費(fèi)的下限，即最少的cnt數(shù)。

具體思路

①最開始的活結(jié)點(diǎn)是根節(jié)點(diǎn)，之后求活結(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行判斷其能否作為擴(kuò)展結(jié)點(diǎn)。

②求出子節(jié)點(diǎn)壓力，如果子節(jié)點(diǎn)有不符合要求的，則必須把該節(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，如果他符合不油壓要求，則cnt++，作為活結(jié)點(diǎn)，否則兩種情況作為活結(jié)點(diǎn)，直到level == n-1結(jié)束（最后一個(gè)一定不put）

數(shù)據(jù)結(jié)構(gòu)

使用一個(gè)子集樹節(jié)點(diǎn) subsetnode (btnode) 里面存儲(chǔ)每個(gè)擴(kuò)展結(jié)點(diǎn)的父節(jié)點(diǎn)，即從哪來的，press,level,是否放放大器，以及bstnum,該路上已經(jīng)放了多少個(gè)booster,以此max_to_cost，用來減少復(fù)雜度限界使用！之后進(jìn)行求解，使用優(yōu)先隊(duì)列存儲(chǔ)子集樹節(jié)點(diǎn)，按照bstnum排序，最后求出的第一個(gè)level = n-1的解，即最優(yōu)解！

//最小耗費(fèi) 分支定界
void DAG::branch_bound()
{//分支定界 活結(jié)點(diǎn)--擴(kuò)展結(jié)點(diǎn)-- 子集空間樹
	btnode* enode = new btnode(Pmax, 2);//活結(jié)點(diǎn)
	int level = 2;
	while (level <= n - 1)
	{//進(jìn)行活結(jié)點(diǎn)的拓展
		int vert = dig[level];//該層擴(kuò)展的節(jié)點(diǎn)
		int temp_press = -1;
		int flag = 0;

		//求擴(kuò)展結(jié)點(diǎn)的壓力
		for (int k = 1; k <= level - 1; k++) {
			for (auto& e : nodes[dig[k]].edges) {
				if (e.to == vert) {
					btnode* p = enode;
					//????
					for (int j = level - 1; j > k; j--)
						p = p->parent;

					temp_press = max(temp_press, p->press - e.cost);
				}
			}
		}
		//限界函數(shù) -最大花費(fèi) 小必須放
		if (temp_press - nodes[vert].max_to_cost < Pmin) {
			flag = 1;
		}
		//check 到 鄰接點(diǎn)是否符合要求
		/*for (auto& e : nodes[vert].edges) {
			if (temp_press < Pmin + e.cost) {
				flag = 1; break;
			}
		}*/
		if (flag == 0) {//兩種 放或者放

			btnode* t = new btnode(temp_press, level + 1, enode, enode->bstnum);
			pq.push(t);
			btnode* tt = new btnode(Pmax, level + 1, enode, enode->bstnum + 1);
			tt->bst_here = true;
			pq.push(tt);
		}
		else {//必須放
			btnode* tt = new btnode(Pmax, level + 1, enode, enode->bstnum + 1);
			tt->bst_here = true;
			pq.push(tt);
		}
		enode = pq.top(); pq.pop();
		level = enode->level;
	}
	best_ans = enode->bstnum;

	btnode* p = enode;
	while (p) {
		place_bst[dig[p->level - 1]] = p->bst_here;
		p = p->parent;
	}

}

性能分析

進(jìn)行性能對比，在跑每個(gè)樣例的過程中記錄一下時(shí)間，輸出到文件中，并且計(jì)算每個(gè)樣例所用的空間大小，輸出到文件。

使用Python matplotlib作圖，做出折線圖對比性能。 使用LARGE_INTEGER + QueryPerformanceCounter() 統(tǒng)計(jì)時(shí)間

統(tǒng)計(jì)時(shí)間

		LARGE_INTEGER start_time; //開始時(shí)間
		LARGE_INTEGER end_time;   //結(jié)束時(shí)間
		double dqFreq;            //計(jì)時(shí)器頻率
		LARGE_INTEGER freq;       //計(jì)時(shí)器頻率
		QueryPerformanceFrequency(&freq);
		dqFreq = (double)freq.QuadPart;
		QueryPerformanceCounter(&start_time); //計(jì)時(shí)開始

		DAG g;
		g.topsort();
		g.backtracking(1, 0);
		fout << g.best_ans << "\n";

		QueryPerformanceCounter(&end_time); //計(jì)時(shí)end
		// write out!
		ofstream fo("cost1.txt", ios::app);
		double run_time = (end_time.QuadPart - start_time.QuadPart) / dqFreq * 1000;
		fo << i << " " << run_time << "\n";
		fo.close();

		//空間 第一種 回溯
		ofstream foo("room1.txt", ios::app);
		//int 4 bool 1
		ll romcost = 5 * g.n + 4 * g.m + 4 * g.n;
		foo << i << " " << romcost << "\n";
		foo.close();

測試time并畫圖的Python代碼

import matplotlib.pyplot as plt


input_txt = 'cost1.txt'
x = []
y = []
z = []

f = open(input_txt)
for line in f:
    line = line.strip('\n')
    line = line.split(' ')

    x.append(int(line[0]))
    y.append(float(line[1]))

f.close

input_txt = 'cost2.txt'
f = open(input_txt)
for line in f:
    line = line.strip('\n')
    line = line.split(' ')

    z.append(float(line[1]))

f.close

plt.plot(x, y, marker='o', label='backtrack')
plt.plot(x, z, marker='*', label='branch_bound',linestyle="--")


plt.xticks(x[0:len(x):2], x[0:len(x):2], rotation=45)
plt.margins(0)
plt.xlabel("data")
plt.ylabel("cost(ms)")
plt.title("compare time")
plt.tick_params(axis="both")
plt.legend()
plt.show()

測試空間性能并畫圖的Python代碼，空間性能是我大致根據(jù)字節(jié)數(shù)計(jì)算的，沒找到如何測量

import matplotlib.pyplot as plt


input_txt = 'room1.txt'
x = []
y = []
z = []

f = open(input_txt)
for line in f:
    line = line.strip('\n')
    line = line.split(' ')

    x.append(int(line[0]))
    y.append(int(line[1]))

f.close

input_txt = 'room2.txt'
f = open(input_txt)
for line in f:
    line = line.strip('\n')
    line = line.split(' ')

    z.append(int(line[1]))

f.close

plt.plot(x, y, marker='o', label='backtrack')
plt.plot(x, z, marker='*', label='branch_bound',linestyle="--")


plt.xticks(x[0:len(x):2], x[0:len(x):2], rotation=45)
plt.margins(0)
plt.xlabel("data")
plt.ylabel("cost(Byte)")
plt.title("compare roomspace")
plt.tick_params(axis="both")
plt.legend()
plt.show()

結(jié)果展示

生成DAG的圖片

具體DAG圖片，紅色mark 放大器的位置

結(jié)果分析

復(fù)雜度

回溯和分支定界：時(shí)間復(fù)雜度都為O(2^n)，但是經(jīng)過剪枝和限界之后會(huì)遠(yuǎn)小于這個(gè)復(fù)雜度。

性能表現(xiàn)

回溯法和分支定界法，這兩個(gè)算法都需要有一個(gè)限界函數(shù)，并且設(shè)計(jì)思想類似。對于這兩個(gè)算法，時(shí)間復(fù)雜度都是O(2^n)，雖然復(fù)雜度一樣，但是在具體問題特別是數(shù)據(jù)較多的時(shí)候，由于回溯法即使找到了最優(yōu)解也不能馬上就肯定他是最優(yōu)的，必須把所有可行解都求出來才能確定。而分支定界，只需要找到一個(gè)解，這個(gè)解必為最優(yōu)的。分支定界比回溯法檢查更少的情況和節(jié)點(diǎn)，時(shí)間性能更好。

但是在空間性能上：回溯法如果建立解空間的話，使用的內(nèi)存是O（n）即最長路徑的空間大小，而分支定界占用的內(nèi)存為O（2^n）加之回溯法不需要真的建立節(jié)點(diǎn)，而分支定界需要建立節(jié)點(diǎn)，又多了一層空間代價(jià)。

在回溯時(shí)，如果一個(gè)節(jié)點(diǎn)>Pmax并且臨界點(diǎn)都>Pmin 不能直接剪去放置的情況，經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，Vi沒放置，但是他的下一個(gè)臨界點(diǎn)Vi+1 Vi+2… 可能會(huì)因?yàn)樗麄兊南乱粋€(gè)節(jié)點(diǎn)而放置，也就是放置了>1個(gè)。此時(shí)如果Vi 放置了，會(huì)提升他們的Press，可能他不需要額外放置，所以總共放置了1個(gè)，所以需要對兩種決策都進(jìn)行遞歸回溯。為此，我也刪除了我的一個(gè)剪枝函數(shù)，才得到了最優(yōu)解。文章來源地址http://www.zghlxwxcb.cn/news/detail-457318.html

改進(jìn)

1. 可以嘗試暴力算法求解
2. 剪枝算法可以進(jìn)一步優(yōu)化剪枝，提高效率
3. 在數(shù)據(jù)結(jié)構(gòu)方面，或許可以考慮圖結(jié)構(gòu)的反轉(zhuǎn) ，根據(jù)使用頻率來優(yōu)化數(shù)據(jù)結(jié)構(gòu)
4. 計(jì)算所需空間性能，可以思考如何度量
5. 優(yōu)化整體項(xiàng)目結(jié)構(gòu)，(現(xiàn)在回看寫的太chou了~)
   定他是最優(yōu)的，必須把所有可行解都求出來才能確定。而分支定界，只需要找到一個(gè)解，這個(gè)解必為最優(yōu)的。分支定界比回溯法檢查更少的情況和節(jié)點(diǎn)，時(shí)間性能更好。

但是在空間性能上：回溯法如果建立解空間的話，使用的內(nèi)存是O（n）即最長路徑的空間大小，而分支定界占用的內(nèi)存為O（2^n）加之回溯法不需要真的建立節(jié)點(diǎn)，而分支定界需要建立節(jié)點(diǎn)，又多了一層空間代價(jià)。

[外鏈圖片轉(zhuǎn)存中…(img-Zi8B3xRG-1651889072411)]

在回溯時(shí)，如果一個(gè)節(jié)點(diǎn)>Pmax并且臨界點(diǎn)都>Pmin 不能直接剪去放置的情況，經(jīng)過實(shí)驗(yàn)發(fā)現(xiàn)，Vi沒放置，但是他的下一個(gè)臨界點(diǎn)Vi+1 Vi+2… 可能會(huì)因?yàn)樗麄兊南乱粋€(gè)節(jié)點(diǎn)而放置，也就是放置了>1個(gè)。此時(shí)如果Vi 放置了，會(huì)提升他們的Press，可能他不需要額外放置，所以總共放置了1個(gè)，所以需要對兩種決策都進(jìn)行遞歸回溯。為此，我也刪除了我的一個(gè)剪枝函數(shù)，才得到了最優(yōu)解。

改進(jìn)

1. 可以嘗試暴力算法求解
2. 剪枝算法可以進(jìn)一步優(yōu)化剪枝，提高效率
3. 在數(shù)據(jù)結(jié)構(gòu)方面，或許可以考慮圖結(jié)構(gòu)的反轉(zhuǎn) ，根據(jù)使用頻率來優(yōu)化數(shù)據(jù)結(jié)構(gòu)
4. 計(jì)算所需空間性能，可以思考如何度量
5. 優(yōu)化整體項(xiàng)目結(jié)構(gòu)，(現(xiàn)在回看寫的太chou了~)

到了這里，關(guān)于網(wǎng)絡(luò)放大器的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！