- WELCOME TO A LESSON ON THE BRUT FORCE ALGORITHM
IN ORDER TO FIND THE LOWEST COST HAMILTONIAN CIRCUIT.
TO REVIEW, A HAMILTONIAN CIRCUIT IS A CIRCUIT
THAT VISITS EVERY VERTEX ONCE WITH NO REPEATS.
BEING A CIRCUIT, IT MUST AND START AND END
AT THE SAME VERTEX.
TO ANSWER THE QUESTION
OF HOW TO FIND THE LOWEST COST HAMILTONIAN CIRCUIT
WE WILL CONSIDER SOME POSSIBLE APPROACHES.
THE FIRST OPTION THAT MIGHT COME TO MIND
IS TO JUST TRY ALL THE DIFFERENT CIRCUITS.
AND THIS IS THE BRUTE FORCE ALGORITHM,
ALSO KNOWN AS THE EXHAUSTED SEARCH.
STEP ONE WE'LL LIST ALL POSSIBLE HAMILTONIAN CIRCUITS.
TWO, WE'LL FIND THE LENGTH OF EACH CIRCUIT
BY ADDING THE EDGE WEIGHTS.
AND THEN, THREE, WE'LL SELECT THE CIRCUIT
WITH MINIMAL TOTAL WEIGHT.
SO WHILE THIS ALGORITHM DOES SEEM VERY BASIC,
MATHEMATICIANS HAVE NOT BEEN ABLE TO PROVE
THAT ANOTHER METHOD EXIST
OR PROVE THAT ONE DOESN'T EXIST
TO FIND THE LOWEST COST HAMILTONIAN CIRCUIT.
LET'S TAKE A LOOK AT AN EXAMPLE.
WE WANT TO APPLY THE BRUTE FORCE ALGORITHM
TO FIND THE LOWEST COST HAMILTONIAN CIRCUIT.
IT DOESN'T MATTER WHICH VERTEX WE BEGIN AT,
BUT TO KEEP THINGS ORGANIZED LET'S BEGIN AT VERTEX "A".
AND THEN WE'LL LIST ALL THE HAMILTONIAN CIRCUITS
BEGINNING WITH "A" AND THEN B.
SO IF WE GO FROM "A" TO B, NOTICE HOW WE HAVE TWO CHOICES.
WE CAN GO FROM B TO E OR B TO C.
LET'S GO TO C.
FROM HERE WE STILL HAVE TWO CHOICES.
WE CAN GO FROM C TO E OR C TO D.
LET'S GO TO D.
SO FROM HERE WE HAVE TO GO TO E AND THEN BACK TO "A".
SO WE HAVE "A," B, C, D, E, A.
NOW FOR THE NEXT CIRCUIT LET'S GO FROM "A" TO B, BACK TO C.
BUT NOW INSTEAD OF GOING TO D LET'S GO TO E.
SO WE HAVE A, B, C, E, D, A.
AGAIN, WE HAVE "A," B, C, E, D, "A".
WE HAVE ONE MORE STARTING WITH "A," B.
GO FROM "A" TO B,
BUT NOW INSTEAD OF GOING TO C LET'S GO TO E.
SO WE HAVE "A," B, E.
NOW FROM HERE IT MIGHT LOOK LIKE WE HAVE TWO CHOICES
BUT WE ONLY HAVE ONE.
IF WE GO TO D NEXT, AND THEN TO C,
WE CANNOT GET BACK TO "A"
WITHOUT USING A VERTEX MORE THAN ONCE.
SO FROM E WE HAVE TO GO TO C, THEN TO D, THEN TO "A".
SO, AGAIN, WE HAVE "A," B, E, C, D, "A".
LET'S GO AHEAD AND RECORD THESE CIRCUITS IN A TABLE,
WHICH WE SEE HERE.
AND NOW WE'LL CONTINUE.
AND NOW WE'LL START WITH VERTEX "A" AND THEN VERTEX D.
THE WAY WE'RE LISTING THESE
WE ARE GOING TO HAVE SOME DUPLICATIONS IN THE CIRCUITS,
BUT I THINK IT'S THE BEST WAY TO GO
BECAUSE IT'S DIFFICULT TO RECOGNIZE THE DUPLICATES
BY JUST LISTING OUT THE POSSIBLE HAMILTONIAN CIRCUITS.
SO WE'LL START WITH "A" AND THEN D.
AND LET'S GO TO C.
FROM C, AGAIN, WE HAVE TWO CHOICES, WE CAN GO TO E OR B.
LET'S GO TO B, AND THEN E, AND THEN "A".
SO WE HAVE "A," D, C, B, E, "A".
AND WE'LL GO AHEAD AND FIND THESE WEIGHTS AT THE VERY END.
NEXT LET'S GO BACK TO C, SO "A," D, C.
AND NOW INSTEAD OF GOING TO B LETS GO TO E.
SO WE HAVE "A," D, C, E, B, "A".
AND WE HAVE ONE MORE STARTING WITH "A" AND THEN D.
WE CAN GO FROM "A" TO D,
AND INSTEAD OF GOING TO C, WE'LL GO TO E.
AND, AGAIN, FROM HERE WE ONLY HAVE ONE CHOICE.
WE CAN'T GO TO B BECAUSE IF WE FROM B TO C
WE CAN'T GET BACK TO "A" WITHOUT USING A VERTEX TWICE.
SO "A," D, E, AND THEN C, B, "A".
SO "A," D, E, C, B, "A".
SO, AGAIN, NOTICE HOW THIS CIRCUIT HERE
"A," D, E, C, B, "A" IS REALLY THE SAME CIRCUIT
AS THE SECOND CIRCUIT HERE IN REVERSE ORDER
"A," B, C, E, D, "A".
BUT WE CAN MORE EASILY IDENTIFY THIS BY LOOKING AT THE WEIGHTS
WHEN WE FINISH.
NOW THAT WE'VE DONE ALL THE "A," B's AND "A," D's,
WE'LL NOW TAKE A LOOK AT THE CIRCUIT STARTING WITH "A"
THEN E.
SO IF WE START AT "A" AND THEN GO TO E,
YOU MIGHT THINK WE HAVE THREE CHOICES BUT WE REALLY DON'T.
IF WE GO TO C WE CAN'T VISIT B AND D AND GET BACK TO "A"
WITHOUT USING A VERTEX TWICE.
SO FOR "A" TO E WE HAVE TO GO TO EITHER B OR D.
LET'S GO TO B FIRST.
SO WE HAVE "A," E, B, C, D, "A".
LEAVING US WITH THE LAST HAMILTONIAN CIRCUIT,
WHICH WOULD BE FROM "A" TO E, TO D, TO C, TO B, TO "A".
NOW THAT WE FOUND ALL THE HAMILTONIAN CIRCUITS,
AND, AGAIN, EVEN THOUGH THERE IS REPETITION HERE,
WE'LL NOW FIND THE WEIGHTS AND FIND THE SMALLEST TOTAL WEIGHT.
WE WON'T GO THROUGH ALL OF THESE.
LET'S TAKE A LOOK AT THE FIRST ONE THOUGH.
FROM "A" TO B, THAT WOULD BE 5 + FROM B TO C THAT WOULD BE 7.
FROM C TO D IS 6, FROM D TO EIS 1,
AND FROM E TO "A" IS 2.
SO WE HAVE 5 + 7 + 6 + 1 + 2 THAT'S 21.
AND NOW WE WOULD DO THE SAME
FOR THE REMAINING HAMILTONIAN CIRCUITS,
WHICH TO SAVE SOME TIME I'VE ALREADY DONE.
NOTICE HOW SEVERAL OF THE CIRCUITS HAVE THE SAME WEIGHT,
WHICH MAKES IT EASIER TO IDENTIFY THE DUPLICATE CIRCUITS.
FOR EXAMPLE, NOTICE THE CIRCUITS WITH TOTAL WEIGHT OF 19
ARE DUPLICATES.
"A," B, C, E, D, "A" IS THE SAME CIRCUIT IN REVERSE ORDER
AS "A," D, E, C, B, "A".
AND THE SAME THING IS TRUE FOR THE TWO CIRCUITS
FOR THE TOTAL WEIGHT OF 21,
THE FIRST AND LAST CIRCUIT,
AS WELL AS THE TWO CIRCUITS FOR THE TOTAL WEIGHT OF 20,
AND WITH THE TWO CIRCUITS WITH THE WEIGHT OF 22.
AND WE'RE LOOKING FOR THE LOWEST COST HAMILTONIAN CIRCUIT,
WHICH WE CAN SEE WOULD HAVE A TOTAL WEIGHT OF 19,
THIS CIRCUIT AND THIS CIRCUIT, WHICH ARE DUPLICATE CIRCUITS.
WE CAN'T ASSUME THEY'RE DUPLICATE CIRCUITS
JUST BECAUSE THEY HAVE THE SAME WEIGHT,
BUT WE CAN VERIFY THIS BY REVERSING THE ORDER.
"A," B, C, E, D, "A" IS EQUIVALENT TO
"A," D, E, C, B, "A".
SO THE LOWEST COST HAMILTONIAN CIRCUIT CAN BE GIVEN
EITHER OF THESE TWO WAYS.
I DO ALSO WANT TO MENTION
THAT IF WE DIDN'T START WITH VERTEX "A"
WE WOULD HAVE AN EQUIVALENT CIRCUIT
THAT WOULD BE LISTED DIFFERENTLY.
FOR EXAMPLE, IF WE STARTED WITH VERTEX B
WE CAN LIST THE SAME HAMILTONIAN CIRCUIT AS B, C, E, D, "A,"
BUT THEN BACK TO B.
SO WE SHOULD RECOGNIZE THAT THIS WOULD BE AN EQUIVALENT CIRCUIT
AS THE ONE THAT WE GAVE HERE BELOW.
AND OF COURSE WE CAN ALSO REVERSE THE ORDER
AS B, "A," D, E, C, B.
I HOPE YOU FOUND THIS LESSON HELPFUL.