Travel from city 1 to city n, visiting at least 3 odd cities

Question

Problem: Find the minimum cost path from city 1 to city n visiting at least 3 odd cities, only moving forward. It costs c[i][j] to go from i to j.

I have to solve this defining search problem class(is_end,start_state,succ_and_cost methods must be implemented) so it can be solved via any algorithm (DFS,DP,A*.etc).

here is my attempt but it works wrong. Is there any idea how to solve it ?:

class OddCitiesProblem:

    def __init__(self, n, costs):
        self.n = n
        self.costs = costs  # cost to move from i to j is costs[i][j]

    def start_state(self) -> tuple[int, int]:
        return (0, 1)  # min(number_of_visited_odd_citites,3), currentState

    def is_end(self, state) -> bool:
        number_of_odd_visited_citites, current_state = state
        return current_state == self.n and number_of_odd_visited_citites >= 3

    def succ_and_cost(self, state: tuple[int, int]) -> list[tuple]:
        number_of_odd_visited_citites, current_city = state
        result = []     # list of tuples: newState
        for i in range(current_city+1, self.n + 1):
            if i % 2 == 1:
                number_of_odd_visited_citites += 1

            new_state = (min(number_of_odd_visited_citites, 3), i)
            cost = self.costs[current_city-1][i-1]
            result.append((new_state, cost))

        return result

Answer 1

You should not actually increment number_of_odd_visited_cities, as that messes up its value for later iterations. Instead, directly calculate the new state based on it.

new_state = min(number_of_odd_visited_citites + i % 2, 3), i