演算法 Branch-and-bound strategy－墨墨喵喵喵

摘自演算法筆記

中文譯作「分支定界」，以遞迴的方式，來列舉數據範圍、數據區間，找出數據界限的方法。

先把一段數據區間分成幾段較小的區間。如果有一段區間，我們當下看不出它是不是正確區間，就把該區間分得更細，並遞迴下去，釐清細節；如果能看出，就停止遞迴。

branch 是指當一段區間不確定界限，就分割區間，並遞迴下去。 bound 是指當一段區間確定了界限，並停止遞迴。

期中後第一次小考題目

∞	3	93	13	33	9	57
4	∞	77	42	24	16	34
45	17	∞	36	16	28	25
39	90	80	∞	56	7	91
28	46	88	33	∞	25	57
3	88	18	46	92	∞	7
44	26	33	27	84	39	∞

為了讓每行每列都有0,每列先減掉每列的最小值,接著觀察每行,該行沒有0,就該行整行減掉剛行的最小值

∞	0	83	9	30	6	50	3
0	∞	66	37	17	12	26	4
29	1	∞	19	0	12	5	16
32	83	66	∞	49	0	80	7
3	21	56	7	∞	0	28	25
0	85	8	42	89	∞	0	3
18	0	0	0	58	13	∞	26
		7	1			4

基本 cost 等於紅字加起來 = 96

接著尋找每行每列的0,

把那個0拿走,可以增加最多的lower bound

未命名

最大的點出現在第4列第六行

現在分兩個cost = 96 + 32 = 128 (沒有劃掉的0)

把第四列,和第六行刪除,然後將第六行.第四列設成無限大42->∞

未命名1

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
3	21	56	7	∞	28
0	85	8	∞	89	0
18	0	0	0	58	∞

更新後表格長這樣

然後又要找哪一行or哪一列沒有0(第四列的3)

所以另一個cost = 96+3 = 99

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
0	19	53	4	∞	25
0	85	8	∞	89	0
18	0	0	0	58	∞

有好多0 O口O

又到了一個一個0尋找lower bound的時間了

未命名2

選18刪除,然後找該行該列的相反補上∞(無限大)

直到結束

可以得到這棵樹

接著是

A Job Scheduling Problem

T1	T2	T3	T4	T5	T6	T7	T8	T9
3	2	2	2	4	5	3	2	3

表格代表每個時間能做幾件工作

Tree代表必須先完成哪項工作才能往下做甚麼

先把完成後可以做更多工作的工作先完成

T1	T2	T3	T4	T5	T6
A	B	C	H	M	J
*	D	I	L	E	K
*				F	N
				P	O
					G

最快可以在T6時全部做完#

cc08310112tw

墨墨喵喵喵

cc08310112tw 發表在痞客邦留言(0) 人氣()

E-mail轉寄

墨墨喵喵喵

墨墨是從台中被人撿到領養的米克斯, Elly是從貓舍買的挪威森林貓, 決定要開始記錄他們的成長

Game

演算法 Branch-and-bound strategy

歷史上的今天

留言列表

站方公告

活動快報

【寵物...

我的好友

熱門文章

文章分類

貓貓 (2)

娃坑 (2)

手製品/開箱/日誌 (3)

課堂筆記 (5)

小說坑 (2)

最新文章

最新留言

動態訂閱

文章精選

文章搜尋

新聞交換(RSS)

誰來我家

參觀人氣

QR Code

POWERED BY

∞	3	93	13	33	9	57
4	∞	77	42	24	16	34
45	17	∞	36	16	28	25
39	90	80	∞	56	7	91
28	46	88	33	∞	25	57
3	88	18	46	92	∞	7
44	26	33	27	84	39	∞

∞	0	83	9	30	6	50	3
0	∞	66	37	17	12	26	4
29	1	∞	19	0	12	5	16
32	83	66	∞	49	0	80	7
3	21	56	7	∞	0	28	25
0	85	8	42	89	∞	0	3
18	0	0	0	58	13	∞	26
		7	1			4

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
3	21	56	7	∞	28
0	85	8	∞	89	0
18	0	0	0	58	∞

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
0	19	53	4	∞	25
0	85	8	∞	89	0
18	0	0	0	58	∞

∞	3	93	13	33	9	57
4	∞	77	42	24	16	34
45	17	∞	36	16	28	25
39	90	80	∞	56	7	91
28	46	88	33	∞	25	57
3	88	18	46	92	∞	7
44	26	33	27	84	39	∞

∞	0	83	9	30	6	50	3
0	∞	66	37	17	12	26	4
29	1	∞	19	0	12	5	16
32	83	66	∞	49	0	80	7
3	21	56	7	∞	0	28	25
0	85	8	42	89	∞	0	3
18	0	0	0	58	13	∞	26
		7	1			4

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
3	21	56	7	∞	28
0	85	8	∞	89	0
18	0	0	0	58	∞

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
0	19	53	4	∞	25
0	85	8	∞	89	0
18	0	0	0	58	∞

∞	3	93	13	33	9	57
4	∞	77	42	24	16	34
45	17	∞	36	16	28	25
39	90	80	∞	56	7	91
28	46	88	33	∞	25	57
3	88	18	46	92	∞	7
44	26	33	27	84	39	∞

∞	0	83	9	30	6	50	3
0	∞	66	37	17	12	26	4
29	1	∞	19	0	12	5	16
32	83	66	∞	49	0	80	7
3	21	56	7	∞	0	28	25
0	85	8	42	89	∞	0	3
18	0	0	0	58	13	∞	26
		7	1			4

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
3	21	56	7	∞	28
0	85	8	∞	89	0
18	0	0	0	58	∞

∞	0	83	9	30	50
0	∞	66	37	17	26
29	1	∞	19	0	5
0	19	53	4	∞	25
0	85	8	∞	89	0
18	0	0	0	58	∞