36 September 2010 5Class NP
Anothe

3
6 September 2010 5
Class NP

Another Example:
 Find minimal length tour of n cities where we begin and
end at the same place.
 This is called closed tour problem.
 N! different tours are possible.
 If we have a tour (a solution), we can easily check to
see how long it is.
 Thus, if we want a tour of less than some fixed length,
we can quickly check candidates to see if they qualify.
 Also, previous tours can help find a new one that could
potentially provide better result

Genetic algorithm

ผลลัพธ์ (ไทย) 1:

36 2553 กันยายน 5เรียน NPตัวอย่างอื่น:ความยาวน้อยทัวร์เมือง n ที่เราเริ่มค้นหา และจบในเดียวกันนี้คือปัญหาปิดทัวร์N ทัวร์ต่าง ๆ เป็นไปได้ถ้าเรามีทัวร์ (การแก้ไข), เราสามารถตรวจสอบการดูนานเป็นดังนั้น หากเราต้องการของบางน้อยกว่าคงความยาวเราสามารถตรวจสอบผู้สมัครว่าจะรับรองอย่างรวดเร็วยัง ทัวร์ก่อนหน้านี้สามารถช่วยคุณค้นหาอันใหม่ที่สามารถอาจให้ผลลัพธ์ที่ดีกว่าขั้นตอนวิธีพันธุกรรม

ผลลัพธ์ (ไทย) 2:

3
6 กันยายน 2010 5
ชั้น NP
? อีกตัวอย่าง:
? ค้นหาทัวร์ระยะเวลาที่น้อยที่สุดของเมือง n ที่เราเริ่มต้นและ
สิ้นสุดที่สถานที่เดียวกัน.
? นี้เรียกว่าปิดปัญหาทัวร์.
? ไม่มี! ทัวร์ที่แตกต่างกันเป็นไปได้.
? ถ้าเรามีทัวร์ (สารละลาย) เราสามารถตรวจสอบเพื่อ
ดูว่าระยะเวลามันเป็น.
? ดังนั้นหากเราต้องการทัวร์น้อยกว่าบางความยาวคงที่,
เราได้อย่างรวดเร็วสามารถตรวจสอบผู้สมัครเพื่อดูว่าพวกเขามีคุณสมบัติ.
? นอกจากนี้ก่อนหน้าทัวร์สามารถช่วยหาใหม่ที่อาจ
อาจให้ผลที่ดีกว่า
? ขั้นตอนวิธีทางพันธุกรรม

ผลลัพธ์ (ไทย) 3:

3
6 กันยายน 2553 5

เรียน NP
อีกตัวอย่าง :
 หาทัวร์ความยาวน้อยที่สุดของเมืองที่เราเริ่มต้น และจบในที่เดียวกัน
.
 นี้เรียกว่าปิดปัญหาทัวร์
 n ! ทัวร์ที่แตกต่างกันเป็นไปได้ .
 ถ้าเรามีทัวร์ ( โซลูชั่น ) เราสามารถตรวจสอบ

ดูนานเท่าไหร่ .
 ดังนั้น ถ้าเราต้องการให้ทัวร์น้อยกว่าบางความยาวคงที่
เราสามารถตรวจสอบได้อย่างรวดเร็ว , ผู้สมัครเพื่อดูว่าพวกเขามีคุณสมบัติ .
 นอกจากนี้ก่อนหน้าทัวร์สามารถช่วยหาอันใหม่ที่อาจให้ผลที่ดีกว่า


ขั้นตอนวิธีเชิงพันธุกรรม