- WELCOME TO A LESSON ON THE NEAREST NEIGHBOR ALGORITHM
THAT CAN BE USED WHEN ATTEMPTING TO FIND
THE OPTIMAL HAMILTONIAN CIRCUIT.
UNFORTUNATELY NO ONE HAS FOUND AN EFFICIENT
AND OPTIMAL ALGORITHM
TO SOLVE THE TRAVELING SALESPERSON PROBLEM.
IT SEEMS UNLIKELY ANYONE EVER WILL.
IF YOU WERE ABLE TO SOLVE THE TSP PROBLEM,
YOU WOULD BECOME VERY RICH AND FAMOUS.
SINCE IT IS NOT PRACTICAL TO USE BRUTE FORCE
TO SOLVE ALL TSP PROBLEMS,
WE WILL NOW LOOK AT HEURTISTIC ALGORITHMS.
HEURTISTIC ALGORITHMS ARE EFFICIENT ALGORITHMS
THAT GIVE APPROXIMATE SOLUTIONS.
IN OTHER WORDS, HEURTISTIC ALGORITHMS ARE FAST
BUT MAY OR MAY NOT PRODUCE THE OPTIMAL HAMILTONIAN CIRCUIT.
THE FIRST HEURISTIC ALGORITHM WE'LL LOOK AT IS CALLED
THE NEAREST NEIGHBOR ALGORITHM, ABBREVIATED NNA,
AND HERE ARE THE STEPS.
NUMBER 1, WE SELECT A STARTING POINT,
2, MOVE TO THE NEAREST UNVISITED VERTEX USING THE EDGE
WITH THE SMALLEST WEIGHT,
3, REPEAT UNTIL THE CIRCUIT IS COMPLETE.
THE NEAREST NEIGHBOR ALGORITHM IS AN EXAMPLE
OF A GREEDY ALGORITHM,
BECAUSE AT EACH VERTEX THE BEST CHOICE IS MADE
WITHOUT CONSIDERING FUTURE CONSEQUENCES.
IN OUR PREVIOUS LESSON ON THE BRUTE FORCE ALGORITHM,
WE FOUND THE OPTIMAL HAMILTONIAN CIRCUIT OF THIS GRAPH HERE
TO BE "A," B, C, E, D, "A,"
OR IN THE REVERSE ORDER, "A," D, E, C, B, A.
REMEMBER THESE 2 CIRCUITS ARE EQUIVALENT.
NOW, WE WANT TO DRAW HAMILTONIAN CIRCUIT USING THE SAME GRAPH
BUT USING THE NEAREST NEIGHBOR ALGORITHM
STARTING AT VERTEX "A."
SO IF WE START AT VERTEX "A,"
WE HAVE 3 POSSIBLE VERTICES TO VISIT.
WE CAN GO FROM "A" TO B WITH A WEIGHT OF 5,
"A" TO E WITH A WEIGHT OF 2, OR "A" TO D WITH A WEIGHT OF 4.
WE SELECT THE EDGE WITH THE LEAST WEIGHT,
SO WE'LL GO FROM "A" TO E.
FROM HERE, WE ONLY HAVE TWO CHOICES, NOT THREE.
WE CAN'T GO TO C,
BECAUSE IF WE DO, WE WOULD NOT BE ABLE TO VISIT VERTEX B AND D
AND RETURN TO "A" WITHOUT USING A VERTEX MORE THAN ONCE.
SO WE CAN GO FROM E TO B WITH A WEIGHT OF 3
OR FROM E TO D WITH A WEIGHT OF 1.
SINCE 1 IS LESS THAN 3, WE'LL GO FROM E TO D.
FROM D, WE DON'T HAVE A CHOICE, WE HAVE TO GO TO C.
FROM C, WE DON'T HAVE A CHOICE, WE HAVE TO GO TO B.
AND TO COMPLETE OUR CIRCUIT, WE NOW RETURN TO "A."
SO THE HAMILTONIAN CIRCUIT USING THE NEAREST NEIGHBOR ALGORITHM
IS "A," E, D, C, B, "A,"
OR IN THE REVERSE ORDER, "A," B, C, D, E, "A."
LOOKING AT THE TABLE, NOTICE "A," B, C, D, E, "A"
ACTUALLY HAS A TOTAL WEIGHT OF 21,
NOT THE OPTIMAL HAMILTONIAN CIRCUIT.
AND OF COURSE THE EQUIVALENT CIRCUIT HERE
HAS THE SAME WEIGHT OF 21.
THIS IS EXACTLY WHY THE NEAREST NEIGHBOR ALGORITHM
IS A HEURISTIC ALGORITHM.
IT MAY OR MAY NOT GIVE THE OPTIMAL HAMILTONIAN CIRCUIT.
IN THIS CASE, IT DID NOT.
LET'S TAKE A LOOK AT ANOTHER EXAMPLE.
WE WANT TO DRAW AND FIND THE WEIGHT
OF THE HAMILTONIAN CIRCUIT
PRODUCED USING THE NEAREST NEIGHBOR ALGORITHM
STARTING AT VERTEX "A."
SO IF WE START AT VERTEX "A,"
WE CAN VISIT ANY OF THE OTHER VERTICES,
BUT WE WANT TO SELECT THE EDGE WITH THE LEAST WEIGHT.
SO FROM "A" TO E, WE'D HAVE A WEIGHT OF 2,
"A" TO D, WE'D HAVE A WEIGHT OF 7,
"A" TO C A WEIGHT OF 6,
AND "A" TO B HAS A WEIGHT OF 3.
SO 2 HAS THE LEAST WEIGHT, SO WE'LL GO FROM "A" TO E.
FROM E, WE HAVE 3 CHOICES, WE CAN GO TO B TO OR D.
NOTICE EDGE E, B HAS A WEIGHT OF 13,
EDGE E, C HAS A WEIGHT OF 14,
AND EDGE E, D HAS A WEIGHT OF 5.
5 IS THE LEAST WEIGHT, SO WE'LL GO FROM E TO D.
NOW FROM HERE WE HAVE TWO CHOICES,
WE CAN GO FROM D TO C THAT HAS A WEIGHT OF 11
OR D TO B THAT HAS A WEIGHT OF 15.
SO WE'LL GO FROM D TO C, AND THEN FROM C,
WE HAVE TO GO TO B,
AND THEN FROM B, WE HAVE TO RETURN TO "A."
SO THE HAMILTONIAN CIRCUIT THAT WE FOUND
USING THE NEAREST NEIGHBOR ALGORITHM
WOULD BE "A," E, D, C, B, "A"
WHICH IS EQUIVALENT TO "A," B, C, D, E, A.
AND NOW TO FIND THE TOTAL WEIGHT,
EDGE "A," E HAS A WEIGHT OF 2, EDGE E, D HAS A WEIGHT OF 5,
EDGE D, C HAS A WEIGHT OF 11, EDGE C, B HAS A WEIGHT OF 12,
AND EDGE B, "A" HAS A WEIGHT OF 3,
SO THE TOTAL WEIGHT WOULD BE 33.
NOW, LET'S TAKE A LOOK AT ONE MORE EXAMPLE
WHERE THE INFORMATION IS GIVEN IN TABLE FORM.
THE WEIGHTS OF EDGES IN A GRAPH ARE SHOWN IN THE TABLE BELOW.
APPLY THE NEAREST NEIGHBOR ALGORITHM
TO FIND A HAMILTONIAN CIRCUIT STARTING AT VERTEX "A."
GIVE YOUR ANSWER AS A LIST OF VERTICES
STARTING AND ENDING AT VERTEX "A."
SO IF WE START AT VERTEX "A,"
WE WANT TO SELECT THE EDGE WITH THE LEAST WEIGHT
WHICH WE CAN SEE WOULD BE THE EDGE LEADING TO VERTEX F.
SO WE WANT TO GO FROM "A" TO F.
IT MAY BE HELPFUL TO ALSO SKETCH THIS USING THE VERTICES HERE.
SO WE'LL GO FROM "A" TO F FIRST,
AND NOW WE'LL GO TO COLUMN F.
WE CAN CROSS OF THE WEIGHT GOING BACK TO VERTEX "A"
SINCE WE JUST CAME FROM THERE.
SO LOOKING AT THE WEIGHTS HERE,
THE LEAST WEIGHT IS 5 WHICH LEADS TO VERTEX D.
SO NOW, WE'LL GO FROM VERTEX F TO VERTEX D WHICH WOULD BE HERE.
SO NOW, WE'LL GO TO COLUMN D.
WE CAN CROSS OFF THE WEIGHT TO VERTEX "A"
AS WELL AS THE WEIGHT TO VERTEX F.
NOTICE THE LEAST WEIGHT IS 6.
SO NOW, WE'LL GO FROM VERTEX D TO VERTEX E.
SO D TO E, WE'LL GO FROM HERE TO HERE.
NOW, WE'LL GO TO COLUMN E.
FROM E, WE WON'T BE RETURNING TO D, F OR "A,"
SO WE'LL CROSS THOSE OFF, D, F, "A."
LOOKING AT THE REMAINING WEIGHTS,
WE'LL NOW GO TO VERTEX C
WHERE THE EDGE WOULD HAVE A WEIGHT OF 48, SO GO FROM E TO C.
NOW LOOKING AT COLUMN C,
WE WON'T RETURN TO E, D, F OR "A,"
SO E, D, F OR "A."
SO WE DON'T HAVE A CHOICE, WE NOW MUST VISIT VERTEX B.
SO WE'LL GO FROM C TO B.
AND THEN FINALLY FROM HERE WE DON'T HAVE A CHOICE,
WE HAVE TO GO FROM B BACK TO "A" TO COMPLETE THE CIRCUIT.
SO AGAIN FROM COLUMN B, WE ONLY HAVE ONE CHOICE.
WE'VE ALREADY VISITED C, D, E AND F,
WE NOW HAVE TO RETURN TO VERTEX "A."
SO NOTICE HOW, BY CREATING THE GRAPH HERE ON THE SIDE,
IT DOES MAKE IT MUCH EASIER
TO REMEMBER THE ORDER OF THE CIRCUIT.
THE HAMILTONIAN CIRCUIT FOUND WOULD BE "A," F, D,
E, C, B, "A,"
OR THE DUPLICATE IN REVERSE ORDER WOULD BE
"A," B, C, E, D, F, "A."
NOW, LET'S FIND THE TOTAL WEIGHT OF THE CIRCUIT.
WE DON'T HAVE TO FIND THE SUM OF THE WEIGHTS
IN A PARTICULAR ORDER,
SO WE CAN JUST FIND THE SUM OF THE CIRCLED VALUES.
SO WE'D HAVE 34 + 58 + 44 + 6 + 48 + 5 = 195.
SO NOTICE IN THE LAST TWO EXAMPLES,
BY APPLYING THE NEAREST NEIGHBOR ALGORITHM,
WE'RE NOT REALLY SURE
IF WE FOUND THE OPTIMAL HAMILTONIAN CIRCUIT.
WE FOUND THE HAMILTONIAN CIRCUIT
MAY OR MAY NOT HAVE THE LEAST WEIGHT.
I HOPE YOU FOUND THIS HELPFUL.