Thu March 7

Traveling Salesman Problem

• probably the most famous graph theory problem of all
• no polynomial-time algorithm is known
• (aside: traveling US ; travelling UK)
• wikipedia: traveling salesman
• go over some exact & heuristic approaches
• kaggle - traveling santa
  • sample paths

P vs NP

• wikipedia: P vs NP
• P is "problems that can be solved in polynomial time"
• NP is "problems that can be verified in polynomial time" (_not_ "not polynomial")
  • example: SAT
  • counter-example: generate all permutations (takes n! just to write them down...)
• is travelling salesman in NP? No and yes.
  • "optimization" version (find shortest) is not: cannot check answer in polynomial time.
  • "decision" version (is there a path shorter than C) is.
• NP-complete : NP problems that can be converted into one another - solve one, you've solved them all.

exercise

Write a funciton that returns all the permutations of a string like 'abcdefg' ... here's one way .

attachments

		last modified	size
	jimmy_perm.py	Sat May 04 2024 10:59 am	1.1K