หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

อัลกอริทึมใน Python

ที่เก็บนี้ฉันจะใช้ Python เพื่อใช้อัลกอริทึมที่มีชื่อเสียง อัลกอริทึมถูกจัดเรียงตามกลยุทธ์ที่ใช้ อัลกอริทึมแต่ละตัวจะมีคำอธิบายเกี่ยวกับปัญหาที่พยายามแก้ปัญหาและทรัพยากรที่เกี่ยวข้อง
(เป้าหมายของที่เก็บนี้คือการสร้าง readme ที่สวยงามสำหรับอัลกอริทึมที่ยอดเยี่ยมเหล่านี้ทั้งหมดที่ฉันได้ตรวจสอบ)

เนื้อหา:

  • 1.0 - หารและพิชิต
    • 1.1 - ปัญหาการคูณ Interger
    • 1.2 - การเรียงลำดับ (และเรียงลำดับการแทรก)
    • 1.3 - นับการผกผัน
    • 1.4 - subarray สูงสุด
  • 2.0 - อัลกอริทึมแบบสุ่ม
    • 2.1 - จัดเรียงอย่างรวดเร็ว
    • 2.2 - อัลกอริทึมของ Karger
  • 3.0 - โครงสร้างข้อมูล
    • 3.1 - การค้นหาคิวและความกว้างก่อน
    • 3.2 - การค้นหาครั้งแรกสแต็กและความลึก
    • 3.3 - การบำรุงรักษากองและค่ามัธยฐานเฉลี่ย
    • 3.4 - ส่วนประกอบที่เชื่อมต่ออย่างมาก
    • 3.5 - Disjoint -Set และ SCC
  • 4.0 - อัลกอริทึมโลภ
    • 4.1 - กิจกรรม shedule
    • 4.2 - การเลือกกิจกรรม
    • 4.3 - การเขียนโค้ด Huffman
    • 4.4 - อัลกอริทึมของ Dijkstra
    • 4.5 - อัลกอริทึมของ Prim
    • 4.6 - อัลกอริทึมและปัญหาการจัดกลุ่มของ Kruskal
  • 5.0 - การเขียนโปรแกรมแบบไดนามิก
    • 5.1 - การตัดก้าน
    • 5.2 - การคูณโซ่เมทริกซ์
    • 5.3 - ต่อมาที่ยาวที่สุดทั่วไป
    • 5.4 - อัลกอริทึม Floyd -Warshall
  • 6.0 - อัลกอริทึมการประมาณสำหรับ NPC
    • 6.1 - ปกจุดยอด
    • 6.2 - ปัญหาพนักงานขายเดินทาง
    • 6.3 - ปัญหาความน่าพอใจของบูลีน

1.0 - หารและพิชิต

ส่วนนี้ฉันจะพูดคุยเกี่ยวกับกลยุทธ์การแบ่งแยกและพิชิตที่มีชื่อเสียงและแสดงแอปพลิเคชันบางอย่างของกลยุทธ์นี้

1.1 - ปัญหาการคูณ Interger

  • ลิงค์ที่มีประโยชน์
    interger_mul

ขั้นตอนมาตรฐานสำหรับการคูณของตัวเลข N สองตัวเลขต้องใช้จำนวนการดำเนินงานเบื้องต้นตามสัดส่วน สำหรับอัลกอริทึม Karatsuba จะช่วยลดเวลาทำงานได้มากที่สุด

ความคิดหลัก ๆ
ขั้นตอนพื้นฐานของอัลกอริทึมของ Karatsuba เป็นสูตรที่ช่วยให้หนึ่งสามารถคำนวณผลิตภัณฑ์ของตัวเลขจำนวนมากสองตัวและใช้การคูณของตัวเลขที่เล็กกว่าสามครั้งแต่ละตัวมีตัวเลขประมาณครึ่งหลักเป็นหรือรวมถึงการเพิ่มเติมและการเปลี่ยนแปลงหลัก
คุณสมบัติ

  • เวลาทำงาน:
    Back to Top

1.2 - การเรียงลำดับ (และเรียงลำดับการแทรก)

  • ลิงค์ที่มีประโยชน์
    ก่อนที่เราจะพูดถึงการเรียงลำดับการเรียงลำดับอัลกอริทึมการเรียงลำดับการแทรกจะได้รับการวิเคราะห์และเวลาทำงานเพื่อชื่นชมการเรียงลำดับ ภาพด้านล่างแสดงแนวคิดที่ใช้งานง่ายสำหรับการเรียงลำดับคือการเลียนแบบวิธีการจัดเรียงการ์ดตามขนาดของมัน เมื่อเราได้รับการ์ดเราจะจัดเรียงมันทันทีตามการ์ดอื่น ๆ ในมือของเรา

แทรก

เวลาทำงานที่เลวร้ายที่สุดสำหรับอัลกอริทึมนี้คือ
GIF ด้านบนแสดงให้เห็นว่าการเรียงลำดับการทำงานแบบผสานทำงานอย่างไร: ผสาน

ความคิดหลัก ๆ
แบ่งรายการที่ไม่ได้เรียงลำดับออกเป็น n sublist แต่ละรายการที่มี 1 องค์ประกอบ (รายการ 1 องค์ประกอบได้รับการพิจารณาเรียงลำดับ) และรวม sublists ซ้ำ ๆ เพื่อผลิต sublist ที่เรียงลำดับใหม่จนกว่าจะมีเพียง 1 sublist ที่เหลืออยู่ นี่จะเป็นรายการเรียงลำดับ
คุณสมบัติ

  • เวลาทำงาน:
    Back to Top

1.3 - นับการผกผัน

  • ลิงค์ที่มีประโยชน์
    ที่จริงแล้วสิ่งนี้สามารถถือว่าเป็นแอปพลิเคชันของการควบรวมกิจการ ทุกครั้งที่เรารวมการดำเนินการในการเรียงลำดับเราคำนวณโดยปริยาย
    การผกผัน

ความคิดหลัก ๆ
เช่นเดียวกับรูปด้านบนเมื่อเราใช้องค์ประกอบจากการอาร์เรย์ย่อยที่ถูกต้องเป็นครั้งแรกในการดำเนินการผสานซึ่งบ่งชี้ว่าองค์ประกอบด้านขวามีขนาดเล็กกว่า (ความยาวของการอาเรย์ย่อยซ้าย-ดัชนีขององค์ประกอบด้านซ้าย)
เมื่ออัลกอริทึมดำเนินไปเพิ่มการรุกรานทั้งหมดจะทำให้เรามีการรุกรานทั้งหมด
คุณสมบัติ

  • เวลาทำงาน:
    Back to Top

1.4 - subarray สูงสุด

  • ลิงค์ที่มีประโยชน์
    ปัญหา subarray สูงสุดคืองานในการค้นหา subarray ที่ต่อเนื่องกันภายในอาร์เรย์หนึ่งมิติ A [1 ... n] ของตัวเลขที่มีผลรวมที่ใหญ่ที่สุด
    ความคิดหลัก ๆ
    หากเราใช้กลยุทธ์การแบ่งแยกและพิชิตหากอาร์เรย์เป็น [ต่ำ .. สูง] และจุดกึ่งกลางจะแสดงเป็นกลาง A [I..J] คือสิ่งที่เราต้องการคำนวณ A [i..j] ต้องเป็นหนึ่งในสามกรณี:
  • A [i..J] เป็นของ [ต่ำ .. มิด]
  • A [i..j] เป็นของ [mid+1..high]
  • i <= mid <j
    ดังนั้นงานของเราคือการหาอาร์เรย์ย่อยที่ใหญ่ที่สุดข้ามจุดกลางและเลือกที่ใหญ่ที่สุดในสามอัลกอริทึมนี้ ข้าม

คุณสมบัติ

  • เวลาทำงาน:
    Back to Top

2.0 - อัลกอริทึมแบบสุ่ม

ส่วนนี้ฉันจะพูดถึงอัลกอริทึมสองตัวที่ใช้ตัวแปรสุ่มภายใน

2.1 - จัดเรียงอย่างรวดเร็ว

  • ลิงค์ที่มีประโยชน์
    เร็ว

ความคิดหลัก ๆ
Quicksort ก่อนแบ่งอาเรย์ขนาดใหญ่ออกเป็นสองอาร์เรย์ขนาดเล็กสองอัน: องค์ประกอบต่ำและองค์ประกอบสูงที่สัมพันธ์กับองค์ประกอบที่เลือกแบบสุ่ม Quicksort สามารถจัดเรียงอาร์เรย์ย่อยซ้ำได้ ดังนั้นจุดสำคัญในการเรียงลำดับอย่างรวดเร็วคือการเลือกองค์ประกอบพาร์ติชัน
คุณสมบัติ

  • ประสิทธิภาพกรณีที่แย่ที่สุด o (n^2)
  • ประสิทธิภาพกรณีที่ดีที่สุด o (n log n) หรือ o (n) พร้อมพาร์ติชันสามทาง
  • ประสิทธิภาพกรณีเฉลี่ย o (n log n)
    Back to Top

2.2 - อัลกอริทึม Karger

  • ลิงค์ที่มีประโยชน์
    แนวคิดของอัลกอริทึมนั้นขึ้นอยู่กับแนวคิดของการหดตัวของขอบ (u, v) ในกราฟ g = (v, e) การพูดอย่างไม่เป็นทางการการหดตัวของขอบจะรวมโหนด U และ V เป็นหนึ่งเดียวลดจำนวนโหนดทั้งหมดของกราฟโดยหนึ่ง รูปด้านล่างแสดงให้เห็นว่าการหดตัวของการทำงานอย่างไร ในรูปย่อยซ้ายโหนดสีดำตัวหนาสองโหนดจะถูกหลอมรวมเป็นหนึ่ง (รูปย่อยทางด้านขวา) คนขี้เกียจ

ความคิดหลัก ๆ
ด้วยการทำซ้ำอัลกอริทึมการหดตัวด้วยตัวเลือกแบบสุ่มอิสระและส่งคืนการตัดที่เล็กที่สุดความน่าจะเป็นที่จะไม่พบการตัดขั้นต่ำคือ
คุณสมบัติ

  • ด้วยความน่าจะเป็นสูงเราสามารถพบการตัดขั้นต่ำทั้งหมดในเวลาทำงานของ
  • การไม่พบความน่าจะเป็นในการตัดขั้นต่ำคือเวลา
    Back to Top

3.0 - โครงสร้างข้อมูล

การวางโครงสร้างข้อมูลเป็นส่วนที่เป็นอิสระทำให้เข้าใจผิด อย่างไรก็ตามฉันจะแนะนำปัญหาที่น่างงงวยซึ่งได้รับการแก้ไขอย่างหรูหราโดยโครงสร้างข้อมูล โครงสร้างข้อมูลบางอย่างอาจมีกลยุทธ์การออกแบบอัลกอริทึมที่ยังไม่ได้รับการตรวจสอบ

3.1 - การค้นหาคิวและความกว้างก่อน

  • link1 ที่เป็นประโยชน์ link2
    คิวหรือที่รู้จักกันในชื่อ FIFO เป็นตัวย่อสำหรับครั้งแรกในครั้งแรกเป็นวิธีการจัดระเบียบและจัดการบัฟเฟอร์ข้อมูลซึ่งรายการที่เก่าแก่ที่สุด (แรก) หรือ 'หัว' ของคิวถูกประมวลผลก่อน คิว

ความคิดหลัก ๆ
BFS ใช้เพื่อนับโหนดที่เข้าถึงได้จากโหนดต้นทางในกราฟที่ไม่ได้กำกับหรือกำกับ โหนดที่เข้าถึงได้จะถูกพิมพ์ตามลำดับที่พบ คิวใช้เพื่อเก็บสีเทาสีโหนด (ดู GIF ด้านล่าง) คำว่า "ความกว้าง" ใน BFS หมายถึงการค้นหาโหนดที่เข้าถึงได้ด้วยความยาวที่สั้นที่สุด ความกว้างขยายขอบเขตระหว่างโหนดที่เข้าชมและโหนดที่ยังไม่ได้เปิด

BFS

คุณสมบัติ

  • เวลาทำงาน: t (n) = o (v+e), v คือจำนวนจุดยอด, e คือจำนวนขอบ
    Back to Top

3.2 - การค้นหาครั้งแรกสแต็กและความลึก

  • link1 ที่เป็นประโยชน์ link2
    สแต็คหรือที่รู้จักกันในชื่อ LIFO มีคุณสมบัติของการเข้ามาครั้งสุดท้าย
    กองซ้อน

ความคิดหลัก ๆ
และ DFS ถูกใช้ในกราฟกำกับและบอกว่าโหนดแหล่งกำเนิดสามารถเข้าถึงและพิมพ์ได้กี่โหนดตามลำดับที่เราพบ เราใช้สแต็กเพื่อจัดเก็บโหนดที่เราจัดประเภทเป็นจุดเริ่มต้นสำหรับกราฟ "ความลึก" ในชื่อของมันหมายความว่าอัลกอริทึมนี้จะไปอย่างลึกซึ้งที่สุดเท่าที่จะทำได้สำหรับแหล่งที่มาและเมื่อถึงจุดสิ้นสุดมันจะกลับไปที่โหนดเริ่มต้น

ความลึก

คุณสมบัติ

  • เวลาทำงาน: t (n) = o (v+e), v คือจำนวนจุดยอด, e คือจำนวนขอบ
    Back to Top

3.3 - การบำรุงรักษากองและค่ามัธยฐานเฉลี่ย

  • link1 ที่เป็นประโยชน์ link2
    HEAP เป็นโครงสร้างข้อมูลตามต้นไม้พิเศษที่เป็นไปตามคุณสมบัติของฮีป: ถ้า p เป็นโหนดหลักของ C ดังนั้นคีย์ (ค่า) ของ P จะสูงกว่าหรือเท่ากับ (ในกองสูงสุด) หรือน้อยกว่าหรือเท่ากับ โหนดที่ "ด้านบน" ของกอง (ที่ไม่มีพ่อแม่) เรียกว่ารูทโหนด

กอง

ปัญหาการบำรุงรักษาค่ามัธยฐานคือถ้าจำนวนเต็มถูกอ่านจากกระแสข้อมูลให้ค้นหาค่ามัธยฐานขององค์ประกอบที่อ่านได้อย่างมีประสิทธิภาพ เพื่อความเรียบง่ายสมมติว่าไม่มีการทำซ้ำ

ความคิดหลัก ๆ
เราสามารถใช้กองสูงสุดทางด้านซ้ายเพื่อเป็นตัวแทนขององค์ประกอบที่น้อยกว่าค่ามัธยฐานที่มีประสิทธิภาพและกองนาทีด้านขวาเพื่อแสดงองค์ประกอบที่มากกว่าค่ามัธยฐานที่มีประสิทธิภาพ เมื่อความแตกต่างระหว่างขนาดของสองกองสูงกว่าหรือเท่ากับ 2 เราจะสลับองค์ประกอบหนึ่งเป็นกองขนาดเล็กกว่าอื่น

คุณสมบัติ

  • เวลาทำงาน:
    Back to Top

3.4 - ส่วนประกอบที่เชื่อมต่ออย่างมาก

  • ลิงค์ที่มีประโยชน์
    กราฟกำกับที่เรียกว่าเชื่อมต่ออย่างมากหากมีเส้นทางในแต่ละทิศทางระหว่างแต่ละจุดของกราฟ ในกราฟ G โดยตรงที่อาจไม่ได้เชื่อมต่ออย่างมากคู่ของจุดยอด U และ V ถูกกล่าวว่าเชื่อมต่อกันอย่างมากหากมีเส้นทางในแต่ละทิศทางระหว่างพวกเขา

SCC

ความคิดหลัก ๆ
จากการสังเกตอย่างง่ายเราพบว่า tranpose ของกราฟมี SCCs เดียวกับกราฟดั้งเดิม เราเรียกใช้ DFS สองครั้ง ครั้งแรกเราเรียกใช้กับ G และคำนวณเวลาจบสำหรับแต่ละจุดสุดยอด จากนั้นเราเรียกใช้ dfs บน g^t แต่ในห่วงหลักของ DFS ให้พิจารณาจุดยอดตามลำดับเวลาที่ลดลง
คุณสมบัติ

  • เวลาทำงาน:, V คือจำนวนจุดยอด, E คือจำนวนขอบ
    Back to Top

3.5 - Disjoint -Set และ SCC

  • ลิงค์ที่มีประโยชน์
    โครงสร้างข้อมูลแบบแยกส่วนหรือที่เรียกว่าโครงสร้างข้อมูลสหภาพ-ค้นหาหรือชุดการค้นหาแบบรวมเป็นโครงสร้างข้อมูลที่ติดตามชุดขององค์ประกอบที่แบ่งพาร์ติชันลงในชุดย่อย (ไม่ทับซ้อน) จำนวนหนึ่ง
    สำหรับการแยกที่ไร้เดียงสานั้นรองรับการดำเนินงานหลักสองประการคือการตั้งค่าและการรวมกัน Make-Set ทำให้ทุกจุดสุดยอดเป็นกลุ่มอิสระ ยูเนี่ยนวางจุดยอดสองจุดในกลุ่มเดียว

สหภาพ

ความคิดหลัก ๆ
ในกราฟที่ไม่ได้กำกับเราสามารถใช้โครงสร้างข้อมูลนี้เพื่อค้นหาจำนวน SCC รูปด้านล่างแสดงวิธีการทำงาน

scc_uf

คุณสมบัติ

  • เราสามารถใช้ฮิวริสติกแบบ Ununion ถ่วงน้ำหนักเพื่อประหยัดเวลาเมื่อการดำเนินการโทร find_set
  • การบีบอัดเส้นทางสามารถปรับปรุงประสิทธิภาพเวลาของการค้นหาสหภาพได้อย่างมาก
    Back to Top

4.0 - อัลกอริทึมโลภ

ในส่วนนี้ฉันจะแนะนำอัลกอริทึมโลภซึ่งเป็นกลยุทธ์การออกแบบอัลกอริทึมที่ทรงพลังอย่างหนึ่ง
จาก Wikipedia อัลกอริทึมโลภเป็นกระบวนทัศน์อัลกอริทึมที่ตามมาด้วยการแก้ปัญหาการแก้ปัญหาการเลือกที่ดีที่สุดในท้องถิ่นในแต่ละขั้นตอน [1] ด้วยความหวังว่าจะได้พบกับที่ดีที่สุดทั่วโลก ในปัญหาหลายอย่างกลยุทธ์โลภไม่ได้ผลิตทางออกที่ดีที่สุดโดยทั่วไป แต่ถึงกระนั้นก็ตามฮิวริสติกโลภอาจให้โซลูชั่นที่ดีที่สุดในท้องถิ่น

4.1 - กิจกรรม shedule

ในปัญหาการเลือกกิจกรรมทุกกิจกรรมมีน้ำหนักและความยาวของตัวเอง และเป้าหมายของเราคือลดผลรวมของน้ำหนัก* มันเป็นตัวอย่างที่ง่ายและยอดเยี่ยมในการแสดงให้เห็นว่าอัลกอริทึมโลภทำงานได้อย่างไรและให้การพิสูจน์ที่หรูหราโดยใช้เทคนิคการแลกเปลี่ยนอาร์กิวเมนต์
ความคิดหลัก ๆ
หากเราเรียงลำดับกิจกรรมตามค่าน้ำหนัก/ความยาวเราสามารถพิสูจน์โครงสร้างที่ดีที่สุดที่มีอยู่ไม่สามารถดีกว่าการจัดเรียงนี้ กระทำ

ดังที่แสดงไว้ข้างต้นเราพิจารณาค่าใช้จ่ายที่เกิดจากสองกิจกรรมที่อยู่ในช่วงแตกต่างกันในสองข้อ (i, j) เราพบว่าค่าใช้จ่ายในอัลกอริทึมโลภมีขนาดเล็กกว่าโครงสร้างที่ดีที่สุดโดยค่าของ wi*lj - wj*li ซึ่งมากกว่าหรือเท่ากับ 0

คุณสมบัติ

  • เวลาทำงานถูกครอบงำโดยการเรียงลำดับ
    Back to Top

4.2 - การเลือกกิจกรรม

  • ลิงค์ที่มีประโยชน์
    ในปัญหานี้ทุกกิจกรรมมีเวลาเริ่มต้นและเวลาจบ เป้าหมายของเราคือการเลือกชุดย่อยความยาวสูงสุดซึ่งงานเข้ากันได้

การเลือก

ความคิดหลัก ๆ
เราจัดเรียงอาร์เรย์ตามเวลาเสร็จสิ้น อัลกอริทึมทำให้งานแรกที่เวลาเริ่มต้นใหญ่กว่าเวลาทำงานสุดท้ายของงาน
คุณสมบัติ

  • การเลือกกิจกรรมแบบเรียกซ้ำเวลาทำงานอยู่
    Back to Top

4.3 - การเขียนโค้ด Huffman

  • ลิงค์ที่มีประโยชน์
    Huffman Code เป็นรหัสคำนำหน้าประเภทที่ดีที่สุดที่ใช้กันทั่วไปสำหรับการบีบอัดข้อมูลที่ไม่สูญเสีย ตัวอย่างเช่นตารางด้านล่างแสดงความถี่ของตัวอักษรใน "หนังสือ"

ความพร้อม

วิธีหนึ่งในการเข้ารหัสหนังสือเล่มนี้คือการใช้การเข้ารหัสความยาวคงที่ ดังที่แสดงด้านล่าง:

ที่ตายตัว

สำหรับการเข้ารหัส Huffman โครงสร้างต้นไม้ที่แท้จริงมีลักษณะเช่นนี้:

โกรธ

ความคิดหลัก ๆ
เรารักษาต้นไม้ไบนารีและสร้างโหนดใหม่เป็นพาเรนต์สำหรับตัวอักษรสองตัวน้อยที่สุด และกุญแจสำคัญสำหรับโหนดใหม่นี้คือผลรวมของกุญแจสำหรับเด็กสองคน เราทำซ้ำสิ่งนี้จนกว่าจะไม่มีโหนดเหลืออยู่ใน "หนังสือ" นี้

huff_works

คุณสมบัติ

  • ขั้นตอน Huffman ผลิตรหัสคำนำหน้าสูงสุด
    Back to Top

4.4 - อัลกอริทึม Dijkstra

  • ลิงค์ที่มีประโยชน์

อัลกอริทึมของ Dijkstra เป็นอัลกอริทึมสำหรับการค้นหาเส้นทางที่สั้นที่สุดระหว่างโหนดในกราฟ อย่างไรก็ตามมันมีข้อกำหนดเบื้องต้นหนึ่งเส้นทางจะต้องสูงกว่าหรือเท่ากับ 0

Dij

ความคิดหลัก ๆ
โหนดแยกออกเป็นสองกลุ่มกลุ่มหนึ่งถูกทำเครื่องหมายว่าสำรวจ และเราอัปเดตระยะทางจากกลุ่มที่ยังไม่ได้สำรวจไปยังกลุ่มสำรวจในระยะทางที่สั้นที่สุด

คุณสมบัติ

  • เวลาทำงานตามคิวขั้นตอนขั้นต่ำที่ดำเนินการโดยกอง Fibonacci
    Back to Top

4.5 - อัลกอริทึม Prim

  • ลิงค์ที่มีประโยชน์
    อัลกอริทึมของ Prim เป็นอัลกอริทึมโลภที่พบต้นไม้ที่ทอดน้อยที่สุดสำหรับกราฟที่ไม่ได้ทำ คล้ายกับอัลกอริทึม Dijkstra เรารักษาสองชุดสำรวจหนึ่งและไม่มีการสำรวจ ทุกครั้งที่เราดูดซับจุดสุดยอดเท่านั้นซึ่งมีระยะทางที่เล็กที่สุดในการสำรวจ สิ่งนี้แสดงอย่างชัดเจนในรูปด้านล่าง:

ปฐมย์

ความคิดหลัก ๆ
อัลกอริทึมอาจอธิบายอย่างไม่เป็นทางการว่าทำตามขั้นตอนต่อไปนี้:

เริ่มต้นต้นไม้ด้วยจุดสุดยอดเดียวที่เลือกโดยพลการจากกราฟ
ปลูกต้นไม้ด้วยขอบด้านเดียว: จากขอบที่เชื่อมต่อต้นไม้เข้ากับจุดยอดที่ยังไม่ได้อยู่ในต้นไม้ค้นหาขอบน้ำหนักต่ำสุดและถ่ายโอนไปยังต้นไม้
ทำซ้ำขั้นตอนที่ 2 (จนกว่าจุดยอดทั้งหมดจะอยู่ในต้นไม้)

คุณสมบัติ

  • เวลาทำงาน
  • Matrix adjacency, ค้นหา
  • ฮีปไบนารีและรายการ adjacency
  • Fibonacci HEAP และ adjacency List
    Back to Top

4.6 - อัลกอริทึม Kruskal และปัญหาการจัดกลุ่ม

  • ลิงค์ที่มีประโยชน์
    อัลกอริทึมของ Prim เป็นอัลกอริทึมโลภอีกอย่างหนึ่งที่พบต้นไม้ที่ทอดน้อยที่สุดสำหรับกราฟที่ไม่ได้ทำ แทนที่จะดูแลต้นไม้อย่างพรีมันจะรักษาป่าไว้

Kruskal

ความคิดหลัก ๆ
คล้ายกับ SCC มากเราสามารถหยุด Alogrithm ได้ก่อนเพื่อควบคุมจำนวนคลาสในกราฟของเราซึ่งก็คือบอกว่าเราสามารถจัดกลุ่มกราฟได้

คุณสมบัติ

  • เวลาทำงาน o (elogv)
    Back to Top

5.0 - การเขียนโปรแกรมแบบไดนามิก

ในส่วนนี้ฉันจะแนะนำอัลกอริทึมแบบไดนามิกซึ่งเป็นกลยุทธ์การออกแบบอัลกอริทึมที่ทรงพลังอย่างหนึ่ง
จาก Wikipedia การเขียนโปรแกรมแบบไดนามิก (หรือที่เรียกว่าการเพิ่มประสิทธิภาพแบบไดนามิก) เป็นวิธีการแก้ปัญหาที่ซับซ้อนโดยแบ่งมันออกเป็นคอลเลกชันของปัญหาย่อยที่ง่ายกว่าแก้ปัญหาย่อยเหล่านั้นเพียงครั้งเดียวและเก็บโซลูชันของพวกเขา

5.1 - การตัดก้าน

  • ลิงค์ที่มีประโยชน์
    ได้รับความยาวของก้าน N นิ้วและราคาอาร์เรย์ที่มีราคาทุกขนาดเล็กกว่า n กำหนดค่าสูงสุดที่หาได้โดยการตัดก้านและขายชิ้นส่วน
    ตารางต่อไปนี้แสดงความสัมพันธ์ระหว่างราคาและความยาว

len_price

ดังนั้นหากความยาวของก้านคือ 8 และค่าของชิ้นส่วนต่าง ๆ จะได้รับดังต่อไปนี้ค่าสูงสุดที่หาได้คือ 22 (โดยการตัดในสองชิ้นของความยาว 2 และ 6)

ความคิดหลัก ๆ
เราดูการสลายตัวซึ่งประกอบด้วยความยาวชิ้นแรกที่ฉันตัดปลายซ้ายมือจากนั้นส่วนที่เหลืออยู่ทางขวาของความยาว n-i ดังนั้น pseudocode จึงดูเหมือนว่า:

rod_code

ต้นไม้เรียกซ้ำที่แสดงการโทรแบบเรียกซ้ำเป็นผลมาจากการโทร cut_rod (p, n) ดูเหมือนว่า:

Rod_tree

เพื่อบันทึกการคำนวณซ้ำสำหรับปัญหาย่อยขนาดเล็กเราได้จดจำอาร์เรย์เพื่อเก็บค่าเหล่านี้

คุณสมบัติ

  • ความซับซ้อนของเวลาของการใช้งานข้างต้นคือ o (n^2)
    Back to Top

5.2 - การคูณโซ่เมทริกซ์

  • ลิงค์ที่มีประโยชน์
    การคูณเมทริกซ์โซ่ (หรือปัญหาการสั่งซื้อห่วงโซ่เมทริกซ์ MCOP) เป็นปัญหาการเพิ่มประสิทธิภาพที่สามารถแก้ไขได้โดยใช้การเขียนโปรแกรมแบบไดนามิก เมื่อพิจารณาจากลำดับของเมทริกซ์เป้าหมายคือการหาวิธีที่มีประสิทธิภาพมากที่สุดในการคูณเมทริกซ์เหล่านี้ ปัญหาไม่ได้จริงที่จะทำการคูณ แต่เพียงเพื่อตัดสินใจลำดับของการคูณเมทริกซ์ที่เกี่ยวข้อง

matrix_mul

ความคิดหลัก ๆ
โครงสร้างที่ดีที่สุด:

mul_opt

คุณสมบัติ

  • ความซับซ้อนของเวลาของการดำเนินการข้างต้นคือ
    Back to Top

5.3 - ต่อมาที่ยาวที่สุดทั่วไป

  • ลิงค์ที่มีประโยชน์
    ปัญหาต่อมาที่ยาวนานที่สุด (LCS) คือปัญหาในการค้นหาลำดับที่ยาวที่สุดที่ใช้กันทั่วไปกับลำดับทั้งหมดในชุดลำดับ (มักจะเพียงสองลำดับ)

ความคิดหลัก ๆ
จาก CLRS โครงสร้างที่ดีที่สุดสำหรับปัญหานี้คือ:

long_op

คุณสมบัติ

  • ความซับซ้อนของเวลาของการดำเนินการข้างต้นคือ $ Theta (Mn) $
    Back to Top

5.4 - อัลกอริทึม Floyd -Warshall

  • ลิงค์ที่มีประโยชน์
    อัลกอริทึม Floyd - Warshall เป็นอัลกอริทึมสำหรับการค้นหาเส้นทางที่สั้นที่สุดในกราฟถ่วงน้ำหนักที่มีน้ำหนักบวกหรือลบ (แต่ไม่มีวัฏจักรลบ)

ความคิดหลัก ๆ
อัลกอริทึมนี้ขึ้นอยู่กับการสังเกตที่ใช้งานง่ายมาก สมมติว่าเรามีชุดย่อย {1, 2, 3, 4, ... , k} (แสดงว่า V (k)) ของกลุ่มจุดยอดดั้งเดิม {1, 2, 3, ... , n} หาก P เป็นเส้นทางที่สั้นที่สุดจาก I ถึง J ใน V (K) เรามีสองกรณี ก่อนอื่นถ้า k ไม่ได้อยู่ใน P ดังนั้น p จะต้องเป็นเส้นทางที่สั้นที่สุดใน V (K-1) ประการที่สองถ้า k อยู่ใน p เราสามารถแยกเส้นทางออกเป็นสอง p1: i K, P2: K j. และ P1 จะต้องเป็นเส้นทางที่สั้นที่สุดจาก I ถึง K ด้วย V (K-1), P2 ต้องเป็นเส้นทางที่สั้นที่สุดจาก K ถึง J ด้วย V (K-1)

Floyd-Warshall_example

คุณสมบัติ

  • ความซับซ้อนของเวลาของการดำเนินการข้างต้นคือ
    Back to Top

6.0 - อัลกอริทึมการประมาณสำหรับ NPC

จากจาก Wikipedia ปัญหาการตัดสินใจของ NP-complete เป็นหนึ่งในคลาส NP และคลาสความซับซ้อนของ NP-Hard ในบริบทนี้ NP หมายถึง "เวลาพหุนามแบบไม่ใช้เวลา" ชุดของปัญหา NP-complete มักแสดงโดย NP-C หรือ NPC

ในส่วนนี้ฉันจะแนะนำปัญหา NPC ที่มีชื่อเสียงสามประการและอธิบายอัลกอริทึมการประมาณเพื่อเข้าหาพวกเขา

6.1 - ปกจุดยอด

  • ลิงค์ที่มีประโยชน์
    ฝาครอบจุดยอด (บางครั้งปกโหนด) ของกราฟเป็นชุดของจุดยอดซึ่งแต่ละขอบของกราฟเกิดขึ้นอย่างน้อยหนึ่งจุดสุดยอดของชุด รูปด้านล่างแสดงฝาครอบจุดสุดยอดขั้นต่ำ (ที่ชุดฝาครอบต้องมี vertice อย่างน้อยสอง zero และหนึ่งจะไม่ช่วย)

ปิดบัง

ความคิดหลัก ๆ
มันยากมากที่จะหาปกจุดสุดยอดขั้นต่ำ แต่เราสามารถหาฝาครอบโดยประมาณได้มากที่สุดสองเท่าของจุดยอดในเวลาพหุนาม

cover_app

คุณสมบัติ

  • Appror-Vertex-Cover เป็นอัลกอริทึมการผันแปร 2 พหุนาม
    Back to Top

6.2 - ปัญหาพนักงานขายเดินทาง

  • ลิงค์ที่มีประโยชน์
    ปัญหาพนักงานขายการเดินทาง (TSP) ถามคำถามต่อไปนี้: "เมื่อได้รับรายชื่อเมืองและระยะทางระหว่างแต่ละเมืองแต่ละคู่เส้นทางที่สั้นที่สุดที่เป็นไปได้ที่จะเยี่ยมชมแต่ละเมืองและกลับไปที่เมืองต้นกำเนิดคืออะไร" GIF แสดงพลังเดรัจฉานสำหรับ TSP

บรูซ

ความคิดหลัก ๆ
อัลกอริทึมการประมาณสำหรับ TSP เป็นอัลกอริทึมโลภ (CLRS P1114) ที่นี่ฉันต้องการแนะนำ อัลกอริทึมที่แน่นอน สำหรับ TSP โดยใช้การเขียนโปรแกรมแบบไดนามิก

subproblem: สำหรับทุกปลายทาง j ∈ {1,2, ... , n}, ชุดย่อยทุกชุด s ⊆ {1,2, ... , n} ที่มี 1 และ j, ให้ ls, j = ความยาวขั้นต่ำของเส้นทางจาก 1 ถึง J ดังนั้นการเกิดซ้ำที่สอดคล้องกัน:

Exact_tsp

คุณสมบัติ

  • เวลาทำงานสำหรับอัลกอริทึมที่แน่นอน:
    Back to Top

6.3 - ปัญหาความน่าพอใจของบูลีน

  • ลิงค์ที่มีประโยชน์
    ปัญหาความพึงพอใจของบูลีน (บางครั้งเรียกว่าปัญหาความน่าพอใจเชิงเสนอและย่อเป็นความน่าพอใจหรือ SAT) เป็นปัญหาของการพิจารณาว่ามีการตีความที่เป็นไปตามสูตรบูลีนที่กำหนดหรือไม่

3-SAT เป็นหนึ่งในปัญหา 21 NP ที่สมบูรณ์ของ Karp และใช้เป็นจุดเริ่มต้นสำหรับการพิสูจน์ว่าปัญหาอื่น ๆ นั้นเป็น NP-hard

ในที่นี้ฉันแนะนำอัลกอริทึมของ Papadimitriou สำหรับ 2-Sat (นี่เป็น อัลกอริทึมที่น่าสนใจมาก ดังนั้นฉันจึงตัดสินใจที่จะแนะนำแม้ว่า 2-SAT ไม่ใช่ NPC)

ความคิดหลัก ๆ
เลือกการมอบหมายเริ่มต้นแบบสุ่มและเลือกประโยคที่ไม่พอใจโดยพลการและพลิกค่าของตัวแปรใดตัวหนึ่ง นี่คือ pseudocode:

2sat

การจัดการแบบสบาย ๆ เช่นนี้จะทำให้เรามีความน่าจะเป็นที่ใหญ่มากในการค้นหาคำตอบที่แท้จริง กลไกอยู่ในระยะฟิสิกส์ (การเดินแบบสุ่ม) หากคุณสนใจฉันขอแนะนำให้คุณผ่านการเดินแบบสุ่มที่เกี่ยวข้องกับ papadimitriou

คุณสมบัติ

  • สำหรับอินสแตนซ์ 2-SAT ที่น่าพอใจด้วยตัวแปร N อัลกอริทึมของ Papadimitriou จะสร้างการมอบหมายที่น่าพอใจด้วยความน่าจะเป็น≥ 1-1/N
  • วิ่งในเวลาพหุนาม
  • แก้ไขอินสแตนซ์ที่ไม่น่าพอใจเสมอ
    Back to Top
ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด