This question is on state space representation. You are given the following classical problem, which is called the traveling salesperson problem $($TSP$).$ A salesperson has to visit a set of cities, visiting each only once and getting back to the starting city. The objective is to minimize the total distance traveled. Assume each city is directly connected to each other city. As an example, consider a set of $4$ cities to be visited, A$,$ B$,$ C$,$ and D$,$ all connected directly to each other with connections of different lengths. You start in city A and need to get back to A at the end of the tour after taking the shortest tour through all the cities. Describe precisely:

how you would represent the states $($i$.$e$.,$ what information needs to be included in any state to make sure the state describes all the information you need to apply the actions$)$

what is the initial state. The representation of the initial state has to be consistent with the way states are represented.

what goal test you would use.

what are the actions. Be precise.

is the state$-$space a tree or a graph? Please justify your answer.