Graph Theory:  Repeated Nearest Neighbor Algorithm (RNNA)

Graph Theory: Repeated Nearest Neighbor Algorithm (RNNA)

Articles, Blog , , , , , , , , , , , , , , , , , , , , , , 4 Comments


– WELCOME TO A LESSON ON THE REPEATED NEAREST NEIGHBOR
ALGORITHM. USING THE GRAPH HERE ON THE LEFT
IN A PREVIOUS LESSON, WE FOUND THE LOWEST COST
HAMILTONIAN CIRCUIT USING THE BRUTE FORCE ALGORITHM TO BE THE CIRCUIT “A,” B, C, E,
D, “A” TO HAVE A TOTAL WEIGHT OF 19. WE KNEW THIS WAS THE LOWEST COST
HAMILTONIAN CIRCUIT OR OPTIMAL HAMILTONIAN CIRCUIT BECAUSE REMEMBER THE BRUTE FORCE
METHOD IS THE ONLY METHOD THAT GUARANTEES TO FIND THE
LOWEST COST HAMILTONIAN CIRCUIT. THEN WE FOUND THE HAMILTONIAN
CIRCUIT USING THE NEAREST NEIGHBOR
ALGORITHM TO BE “A,” E, D, C, B, “A” WHICH HAD A TOTAL WEIGHT OF 21, NOT THE LOWEST COST
HAMILTONIAN CIRCUIT. BUT WE CAN IMPROVE ON THE
NEAREST NEIGHBOR ALGORITHM BY APPLYING THE ALGORITHM
FROM EACH VERTEX AND THIS IS THE REPEATED
NEAREST NEIGHBOR ALGORITHM. SO STEP ONE WE PERFORM THE
NEAREST NEIGHBOR ALGORITHM STARTING IN EACH VERTEX AND THEN TWO, WE CHOOSE
THE CIRCUIT PRODUCED WITH A MINIMAL TOTAL WEIGHT. AND JUST TO REVIEW, TO APPLY
THE NEAREST NEIGHBOR ALGORITHM, STEP ONE, WE START AT A VERTEX, STEP TWO, WE MOVE TO THE NEAREST
UNVISITED VERTEX USING THE EDGE WITH THE SMALLEST WEIGHT AND THEN THREE, WE REPEAT
UNTIL THE CIRCUIT IS COMPLETE. SO LET’S GO AHEAD AND APPLY THE REPEATED NEAREST NEIGHBOR
ALGORITHM TO THE SAME GRAPH. SO WE’LL BEGIN AT VERTEX “A” AND NOTICE HOW WE CAN VISIT
VERTEX B, E, OR D BUT HE IS THE CLOSEST BECAUSE
EDGE “A,” E HAS A WEIGHT OF TWO. SO WE’LL GO FROM “A” TO E AND NOW FROM HERE IT DOES APPEAR
LIKE WE HAVE THREE CHOICES BUT WE REALLY ONLY HAVE TWO
BECAUSE IF WE WENT TO C, WE COULD NOT VISIT D AND B
AND THEN RETURN TO “A” WITHOUT USING OUR VERTEX
MORE THAN ONCE. SO WE CAN VISIT EITHER B OR D. NOTICE EDGE E, D
IS A WEIGHT OF ONE, SO WE’LL VISIT D NEXT
AND NOW WE ONLY HAVE ONE CHOICE, WE HAVE TO VISIT C, B,
AND THEN “A.” SO WE HAVE THE CIRCUIT
“A,” E, D, AND THEN C, B, “A.” SO THE TOTAL WEIGHT WOULD BE
2 + 1 + 6 + 7 + 5 WHICH IS EQUAL TO A TOTAL WEIGHT
OF 21. NOW WE’LL START AT VERTEX B, THE CLOSEST VERTEX TO VERTEX B
IS GOING TO BE VERTEX E BECAUSE EDGE B, E
HAS A WEIGHT OF 3. AND AGAIN HERE WE ONLY HAVE
TWO CHOICES, WE CAN VISIT EITHER “A” OR C BUT NOTICE HOW THE TWO EDGES
HAVE THE SAME WEIGHT SO WE’RE ACTUALLY GOING TO HAVE
TWO CIRCUITS STARTING AT VERTEX B. LET’S FIRST VISIT “A”
SO WE’LL GO FROM E TO “A.” FROM HERE WE HAVE ONE CHOICE WE
HAVE TO VISIT VERTEX D, THEN C, AND THEN B. SO THIS GIVES US THE CIRCUIT
B, E, “A,” D, C, B WHICH WOULD HAVE A TOTAL WEIGHT
OF 3 + 2 + 4 + 6 + 7 WHICH IS EQUAL TO 22. AND AGAIN WE’LL HAVE
ANOTHER CIRCUIT STARTING WITH B, AND THEN E, REMEMBER HERE WE WENT FROM E TO
“A” NOW WE’LL GO FROM E TO C. SO FROM B WE VISIT E, AND THEN BECAUSE THESE TWO EDGES
HAVE THE SAME WEIGHT AND WE JUST WENT TO “A,”, WE’LL NOW GO TO C. AND NOW WE HAVE ONE CHOICE WE’LL
GO FROM C TO D, FROM D TO “A” AND “A” BACK TO B. SO THE CIRCUIT IS B, E, C,
D, “A,” B. SO THE WEIGHT WOULD BE 3 + 2 + 6
+ 4 + 5 GIVING US A TOTAL WEIGHT OF 20 AND NOW WE’LL MOVE
TO A VERTEX C. STARTING AT VERTEX C, THE
NEAREST VERTEX WOULD BE VERTEX E SINCE EDGE C, E
HAS A WEIGHT OF TWO. FROM HERE THE NEAREST VERTEX IS
VERTEX D WITH A WEIGHT OF ONE. FROM HERE WE HAVE ONE CHOICE
WE HAVE TO VISIT “A” THEN B, THEN BACK TO C. SO OUR CIRCUIT IS C, E, D,
“A,” B, C WHICH HAS A WEIGHT OF 2 + 1 + 4
+ 5 + 7 WHICH IS EQUAL TO 19. AND NOW WE’LL MOVE TO VERTEX D. SO STARTING AT VERTEX D,
THE NEAREST VERTEX IS VERTEX E, EDGE D, E HAS A WEIGHT OF ONE. AND AGAIN FROM HERE,
WE ONLY HAVE TWO CHOICES, WE CAN VISIT “A” OR C AND NOTICE HOW THESE TWO EDGES
HAVE THE SAME WEIGHT SO AGAIN WE’LL HAVE TWO CIRCUITS
STARTING AT VERTEX D. LET’S FIRST VISIT VERTEX “A.” NOW WE ONLY HAVE ONE CHOICE, WE HAVE TO VISIT VERTEX B
THEN C, AND THEN D. SO THIS GIVES US THE CIRCUIT
D, E, “A,” B, C, D. SO WE’D HAVE TOTAL WEIGHT OF
1 + 2 + 5 + 7 + 6 WHICH IS EQUAL TO 21. AND NOW INSTEAD OF GOING
FROM E TO “A,” WE’LL NOW GO FROM E TO C. SO AGAIN BECAUSE THESE TWO EDGES
HAVE THE SAME WEIGHT AND WE JUST VISITED “A,”
WE’LL NOW VISIT C. AND NOW WE ONLY HAVE ONE CHOICE,
WE HAVE TO VISIT B, THEN “A,” AND THEN D. SO THE CIRCUIT WOULD BE
D, E, C, B, “A,” D. SO THE TOTAL WEIGHT WOULD BE
1 + 2 + 7 + 5 + 4 WHICH IS 19. AND FINALLY WE NEED TO START
AT VERTEX E. SO STARTING AT VERTEX E,
THE NEAREST VERTEX IS VERTEX D, EDGE E, D HAS A WEIGHT OF ONE. FROM HERE WE CAN VISIT EITHER
VERTEX “A” OR C BUT SINCE EDGE D, “A”
HAS A WEIGHT OF FOUR, WE’LL VISIT VERTEX “A.” FROM HERE WE HAVE TO GO
TO VERTEX B, THEN C, THEN BACK TO E. SO WE HAVE THE CIRCUIT
E, D, “A,” B, C, E WITH THE TOTAL WEIGHT OF 1 + 4
+ 5 + 7 + 2 WHICH IS ALSO 19. AND NOW WE SELECT THE CIRCUIT
WITH THE LEAST WEIGHT, BUT NOTICE HOW THERE ARE
THREE CIRCUITS HERE THAT HAVE A TOTAL WEIGHT OF 19. SO LET’S TAKE A CLOSER LOOK
AT THESE THREE CIRCUITS. IN OUR PREVIOUS EXAMPLES, WE
ALWAYS STARTED AT VERTEX “A” PLUS WE WRITE THESE CIRCUITS
STARTING AT VERTEX “A” TO THE CIRCUITS FOUND USING
THE DIFFERENT METHODS. SO LOOKING AT THIS CIRCUIT HERE,
IF WE START AT VERTEX “A,” NOTICE HOW WE’D GO
FROM “A” TO B TO C AND THEN FROM C, NOTICE HOW WE
WOULD VISIT VERTEX E, D, AND THEN RETURN TO “A.” NOW LET’S TAKE A LOOK AT THIS
CIRCUIT HERE STARTING AT “A” WE’D GO FROM VERTEX “A”
TO VERTEX D AND THEN FROM D WE’D VISIT
VERTEX E, C, B AND THEN BACK TO “A.” AND THESE CIRCUITS
ARE ACTUALLY DUPLICATES, THEY’RE JUST GIVEN
IN THE REVERSE ORDER. NOTICE “A,” B, C, E, D, “A,”
IN REVERSE ORDER WOULD BE THE SAME CIRCUIT
AS “A,” D, E, C, B, “A.” NOW LET’S TAKE A LOOK
AT THIS LAST CIRCUIT, AGAIN STARTING AT VERTEX “A,” WE’D HAVE THE CIRCUIT “A,” B, C
WHICH WE HAVE HERE, E, AND THEN D, AND THEN “A,” WHICH IS THE SAME
AS THIS CIRCUIT HERE. SO IF WE COMPARE THIS CIRCUIT
TO OUR PREVIOUS RESULTS, WE SEE HERE AT THE BOTTOM, NOTICE HOW THIS IS
THE SAME CIRCUIT THAT WE FOUND USING BRUTE FORCE WHICH WE KNOW IS THE — OR
LOWEST COST HAMILTONIAN CIRCUIT. SO BY USING THE REPEATED
NEAREST NEIGHBOR ALGORITHM, WE DO HAVE A BETTER CHANCE, WE DO HAVE A BETTER CHANCE
OF DETERMINING THE LOWEST COST OR OPTIMAL HAMILTONIAN CIRCUIT. I THINK WE’LL HAVE TO STOP HERE
FOR THIS LESSON. I HOPE YOU FOUND THIS HELPFUL.  

4 thoughts on “Graph Theory: Repeated Nearest Neighbor Algorithm (RNNA)

Leave a Reply

Your email address will not be published. Required fields are marked *