Search code examples
algorithmartificial-intelligencegraph-theoryshortest-path

Shortest path problem with variable edge availability and other constraints

I'm trying to work out an algorithm that will be used by an AI agent for a board game called Brass.

The board state is represented by an undirected and unweighted graph of nodes ("cities") and edges. I have a source node, and a set of possible target nodes. My goal is to find a path from the source node to any one of the target nodes. However there are some complications:

Each edge in the graph can be considered to be in a "built" or "un-built" state. The edges can either have been built by me or another player. Once an edge is built by one player, it cannot be built by any other player. I want to find the path from the source to a target along "built" edges (built by any player) that requires building the fewest number of new edges. This might mean that my solution involves building two or more edges that aren't adjacent to each-other, because it might involve linking up various components of the graph that are already connected by previously "built" edges.

There is yet another twist: I'm not allowed to "build" every edge in the network. I can only build an edge if one of its end nodes is in a predetermined set of nodes in which I have "presence" (thematically, these are cities where I have previously built industry), OR if the edge is adjacent to another edge which I have built. This means that some edges will only become eligible for building by me as other edges are built.

So my question is: what is an algorithm that would allow me to find the fewest number of edges that must be built which will connect my source to any one of my targets through built edges.

Even if you don't know a full algorithm, I would greatly appreciate knowing if there are any terms or words to describe this type of problem that might help me when searching existing algorithm work out there. For instance, I think this problem might be somewhat related to the Steiner Tree problem, but the constraint around which edges can be "built" seems to be something somewhat different.

Consider the following example. My source node is labeled "S". My three target nodes are "T1", "T2", and "T3". A grey edge is an "un-built" edge. A purple edge is built, but by one of the other players. A green edge is an edge that is built by me. Green nodes (A and T1) are nodes in which I have "presence".

network example

Two optimal solutions in this example are as follows:

  • Edge S-A and edge A-B. This solution connects my source to T2 with two builds. Note that both these edges are legal builds from the outset because node A is in my set of nodes in which I have previously established "presence".
  • Edge C-D and edge D-T3. This solution connects my source to T3 with two builds. Note that at the outset, edge D-T3 is not a legal build, but once C-D has been built, then D-T3 does become legal.

Additionally, S-A and D-T3 is not a legal solution because edge D-T3 never becomes legal for me to build in (it is not adjacent to one of my edges or one of my nodes in which I have "presence")

Solution

  • As we trace the final path from source to target, we can at all points be in one of four states.

    1. traveling - just went through an edge built by someone else.
    2. building - just went through my node, or my edge, or just built an edge.
    3. looking - going along edges I just built, which will have to attach to one of mine.
    4. found_and_looking - I found a target, but still need to have built a chain of edges to the target.

    And now you just need to do a search through (node, state) pairs until you find a target while in the state traveling or building, or find your own node or edge while in state found_and_looking.

    For that search you need a dequeue. When you find a new (node, state) pair you put free available moves (moving along built edges) at the front of the dequeue, and the ones that require building at the end. As you go, you fill in a data structure of how you got to that (node, state) pair.

    The result is like a breadth-first search except that already built edges are explored immediately because they are free.

    This will find an optimal path to any target. Per the game rules, you have to build the new building edges forward along your path, and the two variations of looking have to be built in reverse order.