Psudeocode for an Exhaustive Search in C++: I have an assignment and am looking

Question

Psudeocode for an Exhaustive Search in C++:

I have an assignment and am looking for some psuedocode to help put it together. Doesn't have to be perfect, just give me a legitamate idea as to how to put it together if you can.

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 finished, 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 using mathematical expressions of all combinations computed.

Explanation / Answer

One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class.
The problem is as:
first (P): generate a first candidate solution for P.
next (P, c): generate the next candidate for P after the current one c.
valid (P, c): check whether candidate c is a solution for P.
output (P, c): use the solution c of P as appropriate to the application.

The brute-force method is then expressed by the algorithm:

c gets first(P)
while' c eq ? do
if' valid(P,c) then output(P, c)
c gets next(P,c)
end while

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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