Psudeocode for an Exhaustive Search: need path that goes from starting position

Question

Psudeocode for an Exhaustive Search: need path that goes from starting position and returns to starting position after traversing through all destinations, need to compute every possible path, then calculate shortest distance from all combinations

I have an assignment and am looking for some brief explanation/psuedocode to put it together. Doesn't have to be perfect, just give me a legitamate idea as to how to put it together so I don't have to struggle like I have for the past 8 hrs.

I have a .txt document of of 10 cities, each with distances to every other city. An example:

This means Boston is 0 distance to boston, 2000 to Chicago, ect. . . there is a destination, and a weight held with that destination for each city.

I somewhat know the steps to an exhaustive search (could be wrong):

1) I can't mark the cities as visited like a normal traversal from origin to a destination

2) I need to search through each combination of every city, then mark those combinations visited. Take cities 1-10 as A-J, so combination: A->B->C->D->E->F->G->H->I->J->A

(Note the traversal goes from A->J then back to A because it has to come back to the origin: think of it like a road trip)

Then after this is done, you mark this combination as visited, or false, and go onward to the next combination, until EVERY combination is completed

3) Next log all those combinations into a stack or something that you can revert back to, and find the minimum distance of all combinations computed.

---I was told I could set up a for loop for each vertex, or compute partial paths and add a next step for each vertex. A factorial for every combination.

Explanation / Answer

start

a=array(a,b,c,d,e,f,g,h,i,j)

for i = 1 to a.lenght

s=distance(a[i])

for j=1 to a.length

search(a[i], a[j])

if(distance(a[j]<s)

s=a[j]

end of if

end of inner for loop

print shortest distnce from a[i] is s

end of outer for loop

end

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.