I am currently working on a project inspired by the Ticket to Ride board game. This board game is played on an undirected graph where each vertex represents a city and each edge represents a claimable train line connecting two cities. Players get points by claiming an edge for themselves, scoring points based upon how many cars the route requires to claim. There are also tickets that give bonus points if the player is able to claim a path that connects the two cities. Each player has only 45 cars, so this is a resource allocation problem.
I am trying to write a program that helps agents (humans or AIs) plan which routes to take based upon which tickets that agent needs to complete, which routes the agent has already claimed, and which routes are unavailable due to other players having claimed them. I need an algorithm that finds a set of subgraph(s) such that each ticket has its city in the same subgraph while trying to optimize some criteria (minimum car usage, maximum points per car, etc.). I do not care whether the algorithm gets all the cities in one subgraph, or whether it strings them all out in a line without branching (which would help toward getting the Longest Route bonus); I want something that enables the agent to complete the tickets quickly so he can start working on new ones.
The problem is that I do not have enough familiarity with graph theory to know the name for this type of problem. I have tried searches with text that describes what I am trying to do with no luck. I have also looked in my old textbooks (Introduction to Algorithms and Algorithms in C: Part 5 – Graph Algorithms) to try to find a graph problem domain that seems to relate to my issue; the closest seems to be network flow, but that does not seem to be close enough.
I have tried solving this problem on my own. I wrote an A* that scored each set of subgraphs based upon the estimated minimum distance to a node, but it did not work (as I would have discovered if I had read the Wikipedia article on A* first). I wrote an NSGA-II implementation to try to solve the problem stochastically, but it oddly seems to do worse the closer the initial set of owned edges is to connecting the tickets. In fact, the NSGA-II implementation "freaks out" and finds very strange routes to connect subgraphs when only one route that earlier calls to the algorithm recommended.
Could someone either tell me the name of this domain so I can start doing research, point me to an algorithm, or propose an algorithm that I could try?
Best Answer
It sounds like a combinatorial optimization problem. I would start by reading about branch and bound, and other techniques used in that type of problem. Your representation of a point in the problem space (the current combination) may have an effect on efficiency. If you can create a compact representation, you can compare points, and avoid redundant branch traversals in the tree of combinations. Your cost function is also very important: that is, how good a particular combination (branch) is so far, compared to others.