Satisfiability Problem

Clear[a,b,c]

Here is a sample formula:

formula=(a||b||!c)&&(a||!b||c)&&(!a||b||!c)

Evaluate the formula given some assignment of true/false values to the variables:

formula/.{a->True,b->False,c->True}

Finds up to 10 choices of variables that make the formula true:

SatisfiabilityInstances[formula,{a,b,c},10]

Counts all choices of variables that make the formula true:

SatisfiabilityCount[formula,{a,b,c}]

Traveling Salesperson Problem

Generate a bunch of points in the unit square [0,1]×[0,1].

numPoints=10
points=RandomReal[1,{numPoints,2}]

ListPlot[points->Range[numPoints]]

Let a tour be represented by a list of indexes that specify the order in which we visit the points.

trivialTour=Range[numPoints]

goodTour={1,7,8,4,3,5,6,2,10,9}

Define a module to draw the tour:

plotTour[points_,tour_]:=Module[
{n=Length[points],tourPts},
tourPts=Table[0,n+1]; (*initialize list of size n+1*)

(* fill in the cities in order in tourPts *)
Do[
tourPts[[i]]=points[[tour[[i]]]],
{i,1,n}];
tourPts[[n+1]]=points[[tour[[1]]]] ;(* return to starting point *)

(* return the plot *)
ListPlot[tourPts,Joined->True]
]

plotTour[points,goodTour]

Compute the total distance along the tour:

EuclideanDistance[{x1,y1},{x2,y2}]

distTour[points_,tour_]:=Module[
{dist=0},

Do[
dist+=EuclideanDistance[points[[tour[[i]]]],points[[tour[[i+1]]]]],
{i,1,Length[tour]-1}];
dist+=EuclideanDistance[points[[tour[[-1]]]],points[[tour[[1]]]]]; (* return to starting point*)

(* return the distance *)
dist
]

distTour[points,trivialTour]

distTour[points,goodTour]

If we wanted to examine all possible tours on 10 points, how many tours would that be?

9!

Suppose we start at point 1. Here are all the ways of visiting the other nine points:

Permutations[Range[2,numPoints]]