首页 > > 详细

辅导IA留学生、讲解c/c++,Python编程设计、辅导algorithm、讲解Java/Python 辅导Database|讲解数据库S

Insertion Algorithm (IA)Introduction
Insertion Algorithm is a widely used approximation algorithm
for finding a sequence with shortest distance
Can be used to find the sequences between multiple nodes/
cities/points to visit with the shortest distanceThe IA Process
The following are the main steps for IA
Begin with the sequence H – H where you start and end with the
home position
Then propose the first candidate sequence involving visiting only
one point; for this, it can be H-A-H, H-B-H or H-C-H
Based on these options choose the sequence which has the lowest
travelling distance. These can be calculated. let us assume the
sequence H-A-H is the lowest
Now, the remaining points to visit are B and C
In the candidate sequence H-A-H, now we have two positions where
either B or C can be filled
Between H-A or between A-H
We have the four choices
H-B-A-H
H-A-B-H
H-C-A-H
H-A-C-H
Chose the one with the least increase in the total distance
Let us assume H-A-B-H has shortest increase in total distance
Now, the remaining point to visit in sequence is C
In the candidate sequence H-A-B-H, now we have three positions where either C be
filled
Between H-A or A-B or B-H
We have the three options
H-C-A-B-H
H-A-C-B-H
H-A-B-C-H
As before, Choose the one with the least increase in the total distance
Of the above mentioned 3 options, let us assume H-A-C-B-H has the shortest total
distance (this can be calculated as before)
Hence, H-A-C-B-H will be the final sequence
In general, repeat this until all points have been visited in the sequence
Using the Insertion Algorithm, calculate the shortest sequence
involving the points A, B, C and D.
Remember you have to start from the home position and return
to the home position
X
[2,2]
[3,1]
[4,5]
[1,6]
H (0, 0)

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!