CODEWITHSUNDEEP
calgorithmgraph-theory
Alberto Bonsanto
Alberto Bonsanto

Reputation: 18042

Graph Theory - Fill nodes with a limited number of routes

First I must say this is not a Homework or something related, this is a problem of a game named (freeciv).

Ok, in the game we have 'n' number of cities usually (8-12), each city can have a max number of trade-routes of 'k' usually (4), and those trade-routes need to be 'd' distance or further (8 Manhattan tiles).

The problem consist in to find the k*n trade-routes with (max distances or min distances), obviously this problem can be solved with a brute-force algorithm but it is really slow when you the player have more than 10 cities because the program has to make several iterations; I tried to solve it using graph theory but I am not an not an expert in it, I even asked some of my teachers and none could explain me an smart-algorithm, so I didn't come here to find the exact solution but I did to get the idea or the steps to analyze this.

Problem Description

Graph Part City

Upvotes: 2

Views: 356

Answers (2)

Roee Gavirel
Roee Gavirel

Reputation: 19453

continue @Jan Hudec way:

Init Stage:
lets say you have N cities (c1, c2,... cN). you should build a list of connections when each entity in the list will have a format of (cX, cY, Distance) (while X < Y, this is n^2/2 time) and order it by distance (descending for max distance or ascending for min distance), and you should also have an array/list which will hold the number of connection per City (cZ = W) which initialized for each city at N-1 because they all connected at the beginning.

Iterations: iterate over the lists of connections for each (cX, cY, D) if the number of connection (in the connection number array) of cX > k and cY > k then delete (cX, cY, D) from the connection list and also decrees by one the value of cX and cY in the connection array.

in the end, you'll have the connection list with the value you wish for.

Upvotes: 0

Jan Hudec
Jan Hudec

Reputation: 76346

The problem has two parts:

  1. Calculate pair-wise distances between the cities
  2. Select which pairs should become trade-route

I don't think the first part can be calculated faster than O(n·t) where t is number of tiles, as each run of Dijkstra's algorithm will give you distances from one city to all other cities. However if I understand correctly, distance between two cities never changes and is symmetrical. So whenever a new city is built, you just need to run Dijkstra's algorithm from it and cache the distances.

For the second part I would expect greedy algorithm to work. Order all pairs of cities by suitability and in each step pick the first one that does not violate the constraint of k routes per city. I am not sure whether it can be proven (the proof should be similar to the one for Kruskal's minimal spanning-tree algorithm if it exists. But I suspect it will work fine in practice even if you find that it does not work in theory (I haven't tried to either prove or disprove it; it's up to you)

Upvotes: 2

Related Questions