01204512/congestion1 - ประวัติรุ่นแก้ไข

Jittat: ย้อนการแก้ไขของ CarolAnderson (Talk) ไปยังรุ่นของ Jittat

2012-08-05T06:03:24Z

ย้อนการแก้ไขของ CarolAnderson (Talk) ไปยังรุ่นของ Jittat

CarolAnderson: minor updates

2012-08-05T02:25:18Z

minor updates

Jittat เมื่อ 06:22, 4 กรกฎาคม 2555

2012-07-04T06:22:42Z

Jittat: /* การปรับระยะทางแบบยกกำลัง */

2012-07-04T06:22:31Z

การปรับระยะทางแบบยกกำลัง

Jittat: /* การปรับระยะทางแบบยกกำลัง */

2012-07-04T06:21:27Z

การปรับระยะทางแบบยกกำลัง

Jittat: /* การปรับระยะทางเป็นกำลังสอง */

2012-07-04T06:18:45Z

การปรับระยะทางเป็นกำลังสอง

Jittat: /* การปรับระยะทางเป็นกำลังสอง */

2012-07-04T06:17:42Z

การปรับระยะทางเป็นกำลังสอง

Jittat: /* การปรับระยะทางเป็นกำลังสอง */

2012-07-04T06:17:19Z

การปรับระยะทางเป็นกำลังสอง

Jittat เมื่อ 06:10, 4 กรกฎาคม 2555

2012-07-04T06:10:43Z

Jittat: /* การปรับระยะทางแบบเชิงเส้น */

2012-07-04T06:04:05Z

การปรับระยะทางแบบเชิงเส้น

@@ แถว 51: / แถว 51: @@
 เมื่อ <math>e_i</math> คือ edge แรกใน path ที่มีจำนวน edge เท่ากับ <math>i</math> edges (สังเกตว่าทุก ๆ edge ใน path เดี่ยวกัน จะต้องมี congestion เท่ากัน)
-สังเกตว่า ผลลัพธ์ที่เราได้ จะต้องเป็น flow ที่มีขนาด k หน่วย  จากจุดสมดุลย์ข้างต้น เราส่ง flow ไปแล้วทั้งสิ้นเท ... \n
+สังเกตว่า ผลลัพธ์ที่เราได้ จะต้องเป็น flow ที่มีขนาด k หน่วย  จากจุดสมดุลย์ข้างต้น เราส่ง flow ไปแล้วทั้งสิ้นเท่ากับ
-== The Radical Linguist Noam Chomsky ==
+<math>c(e_1)+c(e_2)+\cdots+c(e_k)</math> หน่วย ดังนั้นเราจะ scale flow ดังกล่าวลง เพื่อให้ได้ผลรวมเท่ากับ <math>k</math> เราจะต้องหาตัวคูณ <math>\alpha</math> ที่สอดคล้องกับ
-For centuries experts held that every language is unique. Then one day in 1956, a young linguistics professor gave a legendary presentation at the Symposium on Information Theory at MIT. He argued that every intelligible sentence conforms not only to the rules of its particular language but to a universal grammar that encompasses all languages.
+<math>\alpha\cdot(c(e_1)+c(e_2)+\cdots+c(e_k))=k</math> นั่นคือ  <math>\alpha=\frac{k}{c(e_1)+c(e_2)+\cdots+c(e_k)}</math>
- [[http://goodvillenews.com/The-Radical-Linguist-Noam-Chomsky-WKTWnp.html The Radical Linguist Noam Chomsky]]
+จัดนิพจน์ใหม่ ตามสมการด้านบน โดยแทนค่า <math>c(e_i)=c(e_1)/i</math> เราจะได้ว่า
-[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
+<math>
-== The Story of Change ==
+สังเกตว่าจำนวน flow ทั้งหมดที่ผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ
-"Ive come to see that we have two parts to ourselves; its almost like two muscles -- a consumer muscle and a citizen muscle. Our consumer muscle, which is fed and exercised constantly, has grown strong: So strong that "consumer" has become our primary identity, our reason for being. Were told so often that were a nation of consumers that we dont blink when the media use "consumer" and "person" interchangeably."
+<math>
-  [[http://goodvillenews.com/The-Story-of-Change-hgReTV.html The Story of Change]]
+ซึ่งดีกว่าค่า congestion  <math>k</math> ในตอนแรก
-[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
+=== การปรับระยะทางเป็นกำลังสอง ===
-== The Importance of Learned Optimism ==
+ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ
-What 25 years of research reveal about the cognitive skills of happiness and finding lifes greater purpose.The illiterate of the 21st century, Alvin Toffler famously said, will not be those who cannot read and write, but those who cannot learn, unlearn, and relearn. Our outlook on the world and our daily choices of disposition and behavior are in many ways learned patterns to which Tofflers insight applies with all the greater urgency
+<math>
- [[http://goodvillenews.com/The-Importance-of-Learned-Optimism-jmZjsG.html The Importance of Learned Optimism]]
+หรือ <math>c(e_i) = \sqrt{c(e_1)^2/i} = c(e_1)/\sqrt{i}</math>
-[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
+เราแทนค่านี้ลงไปใหม่ ในการวิเคราะห์เดิมในกรณีที่ปรับค่าความยาวเป็นเชิงเสิ้น เราจะได้ว่า
-== Little Things You Can Do to Make the World a Lot Nicer ==
+<math>
-A few years ago, Debbie Tenzer was feeling overwhelmed by all the crises in the news. But rather than give in to despair, she thought, Maybe I cant solve our big problems, but I know I can do something.
+ดังนั้นจำนวน flow ทั้งหมดผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ
- [[http://goodvillenews.com/Little-Things-You-Can-Do-to-Make-the-World-a-Lot-Nicer-PxxL5F.html Little Things You Can Do to Make the World a Lot Nicer]]
+<math>
-[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
+สังเกตว่า <math>\frac{1}{\sqrt{i}}\geq \frac{1}{\sqrt{k}}</math> เมื่อ <math>1\leq i \leq k</math> ดังนั้น
-== Journey to the End of the Earth ==
+<math>\frac{1}{1}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}\geq
-I realized quickly, after just having traveled to various villages in rural India, that distance is relative. Hailing from a city like San Francisco, going even a few hours outside of town is far but twelve hours outside of a major city? I half expected to run into another country.
+ดังนั้น ค่า congestion บน <math>e_1</math> หลักการ scale จะมีค่าไม่เกิน <math> k/\sqrt{k} = \sqrt{k}</math>
- [[http://goodvillenews.com/Journey-to-the-End-of-the-Earth-tbNql3.html Journey to the End of the Earth]]
+=== การปรับระยะทางแบบยกกำลัง ===
-[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
+ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ

@@ แถว 51: / แถว 51: @@
 เมื่อ <math>e_i</math> คือ edge แรกใน path ที่มีจำนวน edge เท่ากับ <math>i</math> edges (สังเกตว่าทุก ๆ edge ใน path เดี่ยวกัน จะต้องมี congestion เท่ากัน)
-สังเกตว่า ผลลัพธ์ที่เราได้ จะต้องเป็น flow ที่มีขนาด k หน่วย  จากจุดสมดุลย์ข้างต้น เราส่ง flow ไปแล้วทั้งสิ้นเท่ากับ
+สังเกตว่า ผลลัพธ์ที่เราได้ จะต้องเป็น flow ที่มีขนาด k หน่วย  จากจุดสมดุลย์ข้างต้น เราส่ง flow ไปแล้วทั้งสิ้นเท ... \n
-<math>c(e_1)+c(e_2)+\cdots+c(e_k)</math> หน่วย ดังนั้นเราจะ scale flow ดังกล่าวลง เพื่อให้ได้ผลรวมเท่ากับ <math>k</math> เราจะต้องหาตัวคูณ <math>\alpha</math> ที่สอดคล้องกับ
+== The Radical Linguist Noam Chomsky ==
-<math>\alpha\cdot(c(e_1)+c(e_2)+\cdots+c(e_k))=k</math> นั่นคือ  <math>\alpha=\frac{k}{c(e_1)+c(e_2)+\cdots+c(e_k)}</math>
+For centuries experts held that every language is unique. Then one day in 1956, a young linguistics professor gave a legendary presentation at the Symposium on Information Theory at MIT. He argued that every intelligible sentence conforms not only to the rules of its particular language but to a universal grammar that encompasses all languages.
-จัดนิพจน์ใหม่ ตามสมการด้านบน โดยแทนค่า <math>c(e_i)=c(e_1)/i</math> เราจะได้ว่า
+ [[http://goodvillenews.com/The-Radical-Linguist-Noam-Chomsky-WKTWnp.html The Radical Linguist Noam Chomsky]]
-<math>
+[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
-สังเกตว่าจำนวน flow ทั้งหมดที่ผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ
+== The Story of Change ==
-<math>
+"Ive come to see that we have two parts to ourselves; its almost like two muscles -- a consumer muscle and a citizen muscle. Our consumer muscle, which is fed and exercised constantly, has grown strong: So strong that "consumer" has become our primary identity, our reason for being. Were told so often that were a nation of consumers that we dont blink when the media use "consumer" and "person" interchangeably."
-ซึ่งดีกว่าค่า congestion  <math>k</math> ในตอนแรก
+  [[http://goodvillenews.com/The-Story-of-Change-hgReTV.html The Story of Change]]
-=== การปรับระยะทางเป็นกำลังสอง ===
+[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
-ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ
+== The Importance of Learned Optimism ==
-<math>
+What 25 years of research reveal about the cognitive skills of happiness and finding lifes greater purpose.The illiterate of the 21st century, Alvin Toffler famously said, will not be those who cannot read and write, but those who cannot learn, unlearn, and relearn. Our outlook on the world and our daily choices of disposition and behavior are in many ways learned patterns to which Tofflers insight applies with all the greater urgency
-หรือ <math>c(e_i) = \sqrt{c(e_1)^2/i} = c(e_1)/\sqrt{i}</math>
+ [[http://goodvillenews.com/The-Importance-of-Learned-Optimism-jmZjsG.html The Importance of Learned Optimism]]
-เราแทนค่านี้ลงไปใหม่ ในการวิเคราะห์เดิมในกรณีที่ปรับค่าความยาวเป็นเชิงเสิ้น เราจะได้ว่า
+[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
-<math>
+== Little Things You Can Do to Make the World a Lot Nicer ==
-ดังนั้นจำนวน flow ทั้งหมดผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ
+A few years ago, Debbie Tenzer was feeling overwhelmed by all the crises in the news. But rather than give in to despair, she thought, Maybe I cant solve our big problems, but I know I can do something.
-<math>
+ [[http://goodvillenews.com/Little-Things-You-Can-Do-to-Make-the-World-a-Lot-Nicer-PxxL5F.html Little Things You Can Do to Make the World a Lot Nicer]]
-สังเกตว่า <math>\frac{1}{\sqrt{i}}\geq \frac{1}{\sqrt{k}}</math> เมื่อ <math>1\leq i \leq k</math> ดังนั้น
+[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]
-<math>\frac{1}{1}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}\geq
+== Journey to the End of the Earth ==
-ดังนั้น ค่า congestion บน <math>e_1</math> หลักการ scale จะมีค่าไม่เกิน <math> k/\sqrt{k} = \sqrt{k}</math>
+I realized quickly, after just having traveled to various villages in rural India, that distance is relative. Hailing from a city like San Francisco, going even a few hours outside of town is far but twelve hours outside of a major city? I half expected to run into another country.
-=== การปรับระยะทางแบบยกกำลัง ===
+ [[http://goodvillenews.com/Journey-to-the-End-of-the-Earth-tbNql3.html Journey to the End of the Earth]]
-ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ
+[[http://goodvillenews.com/wk.html GoodvilleNews.com - good, positive news, inspirational stories, articles]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:22, 4 กรกฎาคม 2555
แถว 1:		แถว 1:
	: หน้านี้เป็นเอกสารประกอบวิชา [[01204512]] เนื้อหาจาก [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] lecture 1		: หน้านี้เป็นเอกสารประกอบวิชา [[01204512]] เนื้อหาจาก [http://www.cs.berkeley.edu/~satishr/cs270/sp12/ http://www.cs.berkeley.edu/~satishr/cs270/sp12/] lecture 1
−
−	~~: '''เนื้อหายังไม่เรียบร้อย... น่าจะแก้เสร็จภายในวันนี้ (หลังเลิกเรียน)'''~~

	== ปัญหา congestion minimization ==		== ปัญหา congestion minimization ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:22, 4 กรกฎาคม 2555
แถว 116:		แถว 116:
	</math>		</math>

−	หรือ <math>c(e_i) = \log 2^{c(e_1)}/i = c(e_1)-\log i</math>	+	หรือ <math>c(e_i) = \log 2^{c(e_1)}/i = c(e_1)-\log i</math> เมื่อนำสมการนี้เข้าไปแทนในการวิเคราะห์เราสามารถแสดงได้ไม่ยากว่า congestion ที่มากที่สุด จะมีค่าไม่เกิน <math>O(\log k)</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:21, 4 กรกฎาคม 2555
แถว 108:		แถว 108:

	=== การปรับระยะทางแบบยกกำลัง ===		=== การปรับระยะทางแบบยกกำลัง ===
		+	ถ้าเราจะปรับความยาวให้มากขึ้น โดยให้ <math>\ell(e)=2^{c(e)}</math> สำหรับทุก ๆ เส้นเชื่อม
		+
		+	ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ
		+
		+	<math>
		+	2^{c(e_1)}=2\cdot 2^{c(e_2)}=3\cdot 2^{c(e_3)}=\cdots = k\cdot 2^{c(e_k)}
		+	</math>
		+
		+	หรือ <math>c(e_i) = \log 2^{c(e_1)}/i = c(e_1)-\log i</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:18, 4 กรกฎาคม 2555
แถว 75:		แถว 75:

	=== การปรับระยะทางเป็นกำลังสอง ===		=== การปรับระยะทางเป็นกำลังสอง ===
−
	แทนที่เราจะปรับแบบเชิงเส้น เราจะปรับความยาวให้มากขึ้น โดยเราจะให้ <math>\ell(e)=c(e)^2</math> สำหรับทุก ๆ เส้นเชื่อม		แทนที่เราจะปรับแบบเชิงเส้น เราจะปรับความยาวให้มากขึ้น โดยเราจะให้ <math>\ell(e)=c(e)^2</math> สำหรับทุก ๆ เส้นเชื่อม

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:17, 4 กรกฎาคม 2555
แถว 95:		แถว 95:
	ดังนั้นจำนวน flow ทั้งหมดผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ		ดังนั้นจำนวน flow ทั้งหมดผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ

		+	<math>
		+	c(e_1)\cdot\frac{k}{c(e_1)\left(1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}\right)}=
		+	\frac{k}{1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}}
		+	</math>

		+	สังเกตว่า <math>\frac{1}{\sqrt{i}}\geq \frac{1}{\sqrt{k}}</math> เมื่อ <math>1\leq i \leq k</math> ดังนั้น
		+
		+	<math>\frac{1}{1}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}\geq
		+	k\cdot\frac{1}{\sqrt{k}}=
		+	\sqrt{k}</math>
		+
		+	ดังนั้น ค่า congestion บน <math>e_1</math> หลักการ scale จะมีค่าไม่เกิน <math> k/\sqrt{k} = \sqrt{k}</math>

	=== การปรับระยะทางแบบยกกำลัง ===		=== การปรับระยะทางแบบยกกำลัง ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:10, 4 กรกฎาคม 2555
แถว 75:		แถว 75:

	=== การปรับระยะทางเป็นกำลังสอง ===		=== การปรับระยะทางเป็นกำลังสอง ===
		+
		+	แทนที่เราจะปรับแบบเชิงเส้น เราจะปรับความยาวให้มากขึ้น โดยเราจะให้ <math>\ell(e)=c(e)^2</math> สำหรับทุก ๆ เส้นเชื่อม
		+
		+	ในกรณีนี้ เราจะได้ว่า เส้นทางทุกเส้นจะมีความยาวเท่ากันก็ต่อเมื่อ
		+
		+	<math>
		+	c(e_1)^2=2\cdot c(e_2)^2=3\cdot c(e_3)^2=\cdots = k\cdot c(e_k)^2
		+	</math>
		+
		+	หรือ <math>c(e_i) = \sqrt{c(e_1)^2/i} = c(e_i)/\sqrt{i}</math>
		+
		+	เราแทนค่านี้ลงไปใหม่ ในการวิเคราะห์เดิมในกรณีที่ปรับค่าความยาวเป็นเชิงเสิ้น เราจะได้ว่า
		+
		+	<math>
		+	\alpha = \frac{k}{c(e_1)+\frac{c(e_1)}{\sqrt{2}}+\frac{c(e_1)}{\sqrt{3}}+\cdots+\frac{c(e_1)}{\sqrt{k}}}
		+	= \frac{k}{c(e_1)\left(1+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots+\frac{1}{\sqrt{k}}\right)}
		+	</math>
		+
		+	ดังนั้นจำนวน flow ทั้งหมดผ่านเส้นเชื่อม <math>e_1</math> หลังจากการ scale ด้วย <math>\alpha</math> แล้ว จะมีค่าเท่ากับ
		+
		+

	=== การปรับระยะทางแบบยกกำลัง ===		=== การปรับระยะทางแบบยกกำลัง ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:04, 4 กรกฎาคม 2555
แถว 73:		แถว 73:

	ซึ่งดีกว่าค่า congestion <math>k</math> ในตอนแรก		ซึ่งดีกว่าค่า congestion <math>k</math> ในตอนแรก
		+
		+	=== การปรับระยะทางเป็นกำลังสอง ===
		+
		+	=== การปรับระยะทางแบบยกกำลัง ===