# Search Results

• ### How to choose an integer linear programming solver ?

##### - by Cassie
Hi all, I am newbie for integer linear programming. I plan to use a integer linear programming solver to solve my combinatorial optimization problem. I am more familiar with C++/object oriented programming on an IDE. Now I am using NetBeans with Cygwin to write my applications most of time. May I ask if there is an easy use ILP solver for me? Or it depends on the problem I want to solve ? I am trying to do some resources mapping optimization. Please let me know if any further information is required. Thank you very much, Cassie.

• ### Jpeg Algorithm vs BMP Algorithm?

I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks.

• ### Significance of Bresenhams Line of Sight algorithm

##### - by GamDroid
What is the significance of Bresenhams Line of Sight algorithm in chasing and evading in games? As far as i know and implemented this algorithm calulates the straight line between two given points. However while implementing it in game development i stored the points calculated using this algorithm in an array.Then im traversing this array for chasing and evading purpose. This looks to be working good with some angles only.In an pixel based environment/tile based. What if there are some obstacles added in the paths of the two points? then this algorithm will not work right? How well can we use the Bresenhams Line algorithm in game development?

• ### The best algorithm enhancing alpha-beta?

##### - by Risa
I'm studying AI. My teacher gave us source code of a chess-like game and asked us to enhance it. My exercise is to improve the alpha/beta algorithm implementing in that game. The programmer already uses transposition tables, MTD(f) with alpha/beta+memory (MTD(f) is the best algorithm I know by far). So is there any better algorithm to enhance alpha-beta search or a good way to implement MTD(f) in coding a game?

• ### Matchmaking algorithm with a set of filters

##### - by Yuriy Pogrebnyak
I'm looking for matchmaking algorithm for 1x1 online game. Players must be matched not by their skill or level, as usual, but by some specific filters. Each player sends request, where he specifies some set of parameters (generally, 2-4 parameters). If some parameter is specified, player can be matched only with those who has sent this parameter with exactly the same value, or those who hasn't specified this parameter. I need this algorithm to be thread-safe and preferably fast. It would be great if it'll work for 3-4 or even more parameters, but also I'm looking for algorithm that works with only one parameter (in my case it's game bet). Also I'd appreciate ideas on how to implement or improve this algorithm on my server platform - ASP.NET. One more problem I'm facing is that finding match can't be executed right after user sends request, because if other user sends request before matching for previous is finished, they won't be matched even is they possibly could. So it seems that match finding should be started on schedule, and I need help on how to optimize it and how to choose time interval for starting new match finding. P.S. I've also posted this question on stackoverflow

• ### Control diamond square algorithm to generate islands/pangea.

##### - by Gabriel A. Zorrilla
I generated a height map with the diamond square algorithm. The thing is i do not manage to create islands, this is, restrict the height other than water level range to a certain value in the center of the map. I manualy seeded a circle in the middle of the map but the rest of the map still receives heights over the water level. I dont fully understand the Perlin noise algorithm so i'd like to work with my current implementation of the diamond square algorithm which took me 3 days to interpret and code in PHP. :P

• ### word disambiguation algorithm (Lesk algorithm)

##### - by anyssnordin
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the synonyms must be suitable according to a context.

• ### Hopcroft–Karp algorithm in Python

##### - by Simon
I am trying to implement the Hopcroft Karp algorithm in Python using networkx as graph representation. Currently I am as far as this: #Algorithms for bipartite graphs import networkx as nx import collections class HopcroftKarp(object): INFINITY = -1 def __init__(self, G): self.G = G def match(self): self.N1, self.N2 = self.partition() self.pair = {} self.dist = {} self.q = collections.deque() #init for v in self.G: self.pair[v] = None self.dist[v] = HopcroftKarp.INFINITY matching = 0 while self.bfs(): for v in self.N1: if self.pair[v] and self.dfs(v): matching = matching + 1 return matching def dfs(self, v): if v != None: for u in self.G.neighbors_iter(v): if self.dist[ self.pair[u] ] == self.dist[v] + 1 and self.dfs(self.pair[u]): self.pair[u] = v self.pair[v] = u return True self.dist[v] = HopcroftKarp.INFINITY return False return True def bfs(self): for v in self.N1: if self.pair[v] == None: self.dist[v] = 0 self.q.append(v) else: self.dist[v] = HopcroftKarp.INFINITY self.dist[None] = HopcroftKarp.INFINITY while len(self.q) > 0: v = self.q.pop() if v != None: for u in self.G.neighbors_iter(v): if self.dist[ self.pair[u] ] == HopcroftKarp.INFINITY: self.dist[ self.pair[u] ] = self.dist[v] + 1 self.q.append(self.pair[u]) return self.dist[None] != HopcroftKarp.INFINITY def partition(self): return nx.bipartite_sets(self.G) The algorithm is taken from http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm However it does not work. I use the following test code G = nx.Graph([ (1,"a"), (1,"c"), (2,"a"), (2,"b"), (3,"a"), (3,"c"), (4,"d"), (4,"e"),(4,"f"),(4,"g"), (5,"b"), (5,"c"), (6,"c"), (6,"d") ]) matching = HopcroftKarp(G).match() print matching Unfortunately this does not work, I end up in an endless loop :(. Can someone spot the error, I am out of ideas and I must admit that I have not yet fully understand the algorithm, so it is mostly an implementation of the pseudo code on wikipedia

• ### Space partitioning algorithm

##### - by Karol Kolenda
I have a set of points which are contained within the rectangle. I'd like to split the rectangles into subrectangles based on point density (giving a number of subrectangles or desired density, whichever is easiest). The partitioning doesn't have to be exact (almost any approximation better than regular grid would do), but the algorithm have to cope with the large number of points - approx. 200 millions. The desired number of subrectangles however is substantially lower (around 1000). Does anyone knows any algorithm which may help me with this particular task?

• ### Polygonal Triangulation - algorithm with O(n log n) complexity

##### - by Arthur Wulf White
I wish to triangulate a polygon I only have the outline of (p0, p1, p2 ... pn) like described in this question: polygon triangulation algorithm and this webpage: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html I do not wish to learn the subject and have a deep understanding of it at the moment. I only want to see an effective algorithm that can be used out of the box. The one described in the site seems to be of somewhat high complexity O(n) for finding one ear. I heard this could be done in O(n log n) time. Is there any well known easy to use algorithm that I can translate port to use in my engine that runs with somewhat reasonable complexity? The reason I need to triangulate is that I wish to feel out a 2d-outline and render it 3d. Much like we fill out a 2d-outline in paint. I could use sprites. This would not serve cause I am planning to play with the resulting model on the z-axis, giving it different heights in the different areas. I would love to try the books that were mentioned, although I suspect that is not the answer most readers are hoping for when they read this Q & A format. Mostly I like to see a code snippet I can cut and paste with some modifications and start running.

• ### Non-perfect maze generation algorithm

##### - by Shylux
I want to generate a maze with the following properties: The maze is non-perfect. Means it has loops and multiple ways to reach the exit. The maze should be random. The algorithm should output different mazes for different input parameters The maze doesn't have to be braided. Means dead-ends are allowed and appreciated. I just can't find the right resources on google. The closest i found was this description of the different types of algorithms: http://www.astrolog.org/labyrnth/algrithm.htm. All other algorithms were for perfect mazes. Can anyone give me a website where i can look this up or maybe an algorithm directly?

• ### Quick 2D sight area calculation algorithm?

##### - by Rogach
I have a matrix of tiles, on some of that tiles there are objects. I want to calculate which tiles are visible to player, and which are not, and I need to do it quite efficiently (so it would compute fast enough even when I have a big matrices (100x100) and lots of objects). I tried to do it with Besenham's algorithm, but it was slow. Also, it gave me some errors: ----XXX- ----X**- ----XXX- -@------ -@------ -@------ ----XXX- ----X**- ----XXX- (raw version) (Besenham) (correct, since tunnel walls are still visible at distance) (@ is the player, X is obstacle, * is invisible, - is visible) I'm sure this can be done - after all, we have NetHack, Zangband, and they all dealt with this problem somehow :) What algorithm can you recommend for this? EDIT: Definition of visible (in my opinion): tile is visible when at least a part (e.g. corner) of the tile can be connected to center of player tile with a straight line which does not intersect any of obstacles.

• ### Dijkstra's Bankers Algorithm

##### - by idea_
Could somebody please provide a step-through approach to solving the following problem using the Banker's Algorithm? How do I determine whether a "safe-state" exists? What is meant when a process can "run to completion"? In this example, I have four processes and 10 instances of the same resource. Resources Allocated | Resources Needed Process A 1 6 Process B 1 5 Process C 2 4 Process D 4 7

• ### Suggested GA operators for a TSP problem?

##### - by Mark
I'm building a genetic algorithm to tackle the traveling salesman problem. Unfortunately, I hit peaks that can sustain for over a thousand generations before mutating out of them and getting better results. What crossover and mutation operators generally do well in this case?

• ### Infinite loop during A* algorithm

##### - by Tashu
The A* algorithm is used by enemies to have a path to the goal. It's working but when sometimes I placed a tower in a grid (randomly) it produces a stack overflow error. The A* algorithm would iterate the enemy and find its path and pass the list to the enemy's path. I added debug logs and the list that I'm getting it looks like it would arrive from start cell to goal cell. Here's the log - 06-19 19:26:41.982: DEBUG/findEnemyPath, enemy X:Y(4281): X2.8256836:Y3.5 06-19 19:26:41.990: DEBUG/findEnemyPath, grid X:Y(4281): X3:Y2 06-19 19:26:41.990: DEBUG/START CELL ID:(4281): 38 06-19 19:26:41.990: DEBUG/GOAL CELL ID:(4281): 47 06-19 19:26:41.990: DEBUG/Best : 38(4281): passThrough:0.0 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 38 06-19 19:26:41.990: DEBUG/Best : 39(4281): passThrough:8.875 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 39 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 39 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 39 06-19 19:26:41.990: DEBUG/Best : 40(4281): passThrough:7.9375 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 40 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 40 06-19 19:26:41.990: DEBUG/Best : 52(4281): passThrough:8.9375 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 52 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 52 06-19 19:26:41.990: DEBUG/Best : 53(4281): passThrough:7.96875 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 53 06-19 19:26:41.990: DEBUG/Best : 28(4281): passThrough:8.9375 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 28 06-19 19:26:41.990: DEBUG/Best : 65(4281): passThrough:8.984375 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 65 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 65 06-19 19:26:41.990: DEBUG/Best : 66(4281): passThrough:7.9921875 06-19 19:26:41.990: DEBUG/Neighbor's Parent:(4281): 66 06-19 19:26:42.000: DEBUG/Best : 78(4281): passThrough:8.99609375 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 78 06-19 19:26:42.000: DEBUG/Best : 79(4281): passThrough:7.998046875 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 79 06-19 19:26:42.000: DEBUG/Best : 80(4281): passThrough:6.9990234375 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 80 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 80 06-19 19:26:42.000: DEBUG/Best : 81(4281): passThrough:5.99951171875 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 81 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 81 06-19 19:26:42.000: DEBUG/Best : 82(4281): passThrough:4.999755859375 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 82 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 82 06-19 19:26:42.000: DEBUG/Best : 83(4281): passThrough:3.9998779296875 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 83 06-19 19:26:42.000: DEBUG/Best : 71(4281): passThrough:2.99993896484375 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 71 06-19 19:26:42.000: DEBUG/Best : 59(4281): passThrough:1.99951171875 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 59 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 59 06-19 19:26:42.000: DEBUG/Neighbor's Parent:(4281): 59 06-19 19:26:42.000: DEBUG/Best : 47(4281): passThrough:0.99951171875 Then, the goal cell would be iterating its parent till start cell to break off the loop. private void populateBestList(Cell cell, List<Cell> bestList) { bestList.add(cell); if (cell.parent.start == false) { Log.d("ID:", ""+cell.id); Log.d("ParentID:", ""+cell.parent.id); populateBestList(cell.parent, bestList); } return; } The log with error above would show like this - 06-19 19:26:42.010: DEBUG/ID:(4281): 47 06-19 19:26:42.010: DEBUG/ParentID:(4281): 59 06-19 19:26:42.010: DEBUG/ID:(4281): 59 06-19 19:26:42.010: DEBUG/ParentID:(4281): 71 06-19 19:26:42.010: DEBUG/ID:(4281): 71 06-19 19:26:42.010: DEBUG/ParentID:(4281): 59 06-19 19:26:42.010: DEBUG/ID:(4281): 59 06-19 19:26:42.010: DEBUG/ParentID:(4281): 71 06-19 19:26:42.010: DEBUG/ID:(4281): 71 71 and 59 would switch over and goes on. I thought the grid is the issue due to the fact that enemies are using the single grid so I make the parent, start, and goal clear before starting the A* algorithm for an enemy. for(int i = 0; i < GRID_HEIGHT; i++) { for(int j = 0; j < GRID_WIDTH; j++) { grid[i][j].parent = null; grid[i][j].start = false; grid[i][j].goal = false; } } That didn't work. I thought it might be something related to this code, but not sure if I'm on right track - neighbor.parent = best; openList.remove(neighbor); closedList.remove(neighbor); openList.add(0, neighbor); Here's the code of the A* algorithm - private List<Cell> findEnemyPath(Enemy enemy) { for(int i = 0; i < GRID_HEIGHT; i++) { for(int j = 0; j < GRID_WIDTH; j++) { grid[i][j].parent = null; grid[i][j].start = false; grid[i][j].goal = false; } } List<Cell> openList = new ArrayList<Cell>(); List<Cell> closedList = new ArrayList<Cell>(); List<Cell> bestList = new ArrayList<Cell>(); int width = (int)Math.floor(enemy.position.x); int height = (int)Math.floor(enemy.position.y); width = (width < 0) ? 0 : width; height = (height < 0) ? 0 : height; Log.d("findEnemyPath, enemy X:Y", "X"+enemy.position.x+":"+"Y"+enemy.position.y); Log.d("findEnemyPath, grid X:Y", "X"+height+":"+"Y"+width); Cell start = grid[height][width]; Cell goal = grid[ENEMY_GOAL_HEIGHT][ENEMY_GOAL_WIDTH]; if(start.id != goal.id) { Log.d("START CELL ID: ", ""+start.id); Log.d("GOAL CELL ID: ", ""+goal.id); //Log.d("findEnemyPath, grid X:Y", "X"+start.position.x+":"+"Y"+start.position.y); start.start = true; goal.goal = true; openList.add(start); while(openList.size() > 0) { Cell best = findBestPassThrough(openList, goal); //Log.d("ID:", ""+best.id); openList.remove(best); closedList.add(best); if (best.goal) { System.out.println("Found Goal"); System.out.println(bestList.size()); populateBestList(goal, bestList); /* for(Cell cell : bestList) { Log.d("ID:", ""+cell.id); Log.d("ParentID:", ""+cell.parent.id); } */ Collections.reverse(bestList); Cell exit = new Cell(13.5f, 3.5f, 1, 1); exit.isExit = true; bestList.add(exit); //Log.d("PathList", "Enemy ID : " + enemy.id); return bestList; } else { List<Cell> neighbors = getNeighbors(best); for (Cell neighbor : neighbors) { if(neighbor.isTower) { continue; } if (openList.contains(neighbor)) { Cell tmpCell = new Cell(neighbor.position.x, neighbor.position.y, 1, 1); tmpCell.parent = best; if (tmpCell.getPassThrough(goal) >= neighbor.getPassThrough(goal)) { continue; } } if (closedList.contains(neighbor)) { Cell tmpCell = new Cell(neighbor.position.x, neighbor.position.y, 1, 1); tmpCell.parent = best; if (tmpCell.getPassThrough(goal) >= neighbor.getPassThrough(goal)) { continue; } } Log.d("Neighbor's Parent: ", ""+best.id); neighbor.parent = best; openList.remove(neighbor); closedList.remove(neighbor); openList.add(0, neighbor); } } } } Log.d("Cannot find a path", ""); return null; }

• ### Disk Search / Sort Algorithm

##### - by AlgoMan
Given a Range of numbers say 1 to 10,000, Input is in random order. Constraint: At any point only 1000 numbers can be loaded to memory. Assumption: Assuming unique numbers. I propose the following efficient , "When-Required-sort Algorithm". We write the numbers into files which are designated to hold particular range of numbers. For example, File1 will have 0 - 999 , File2 will have 1000 - 1999 and so on in random order. If a particular number which is say "2535" is being searched for then we know that the number is in the file3 (Binary search over range to find the file). Then file3 is loaded to memory and sorted using say Quick sort (which is optimized to add insertion sort when the array size is small ) and then we search the number in this sorted array using Binary search. And when search is done we write back the sorted file. So in long run all the numbers will be sorted. Please comment on this proposal.

• ### Help with Algorithm chinese auction

##### - by sam munkes
Hi, i am designing a Chinese auction website. Tickets (\$5, \$10 & \$20) are sold either individually, or via packages to receive discounts. There are various Ticket packages for example: 5-\$5 tickets = receive 10% off 5-\$10 tickets = receive 10% off 5-\$20 tickets = receive 10% off 5-\$5 tickets + 5-\$10 tickets + 5-\$20 tickets = receive 15% off When users add tickets to their cart, i need to figure out the cheapest package(s) to give them. the trick is that if a user adds 4-\$5 tickets + 5-\$10 tickets + 5-\$20 tickets, it should still give him package #3 since that would be the cheapest for him. Any help in figuring out a algorithm to solve this, or any tips would be greatly appreciate it. thanks

• ### Algorithm to price bulk discounts

##### - by sam munkes
Hi, i am designing a Chinese auction website. Tickets (\$5, \$10 & \$20) are sold either individually, or via packages to receive discounts. There are various Ticket packages for example: 5-\$5 tickets = receive 10% off 5-\$10 tickets = receive 10% off 5-\$20 tickets = receive 10% off 5-\$5 tickets + 5-\$10 tickets + 5-\$20 tickets = receive 15% off When users add tickets to their cart, i need to figure out the cheapest package(s) to give them. the trick is that if a user adds 4-\$5 tickets + 5-\$10 tickets + 5-\$20 tickets, it should still give him package #4 since that would be the cheapest for him. Any help in figuring out a algorithm to solve this, or any tips would be greatly appreciate it. thanks

• ### Creating a "crossover" function for a genetic algorithm to improve network paths

##### - by Dave
Hi, I'm trying to develop a genetic algorithm that will find the most efficient way to connect a given number of nodes at specified locations. All the nodes on the network must be able to connect to the server node and there must be no cycles within the network. It's basically a tree. I have a function that can measure the "fitness" of any given network layout. What's stopping me is that I can't think of a crossover function that would take 2 network structures (parents) and somehow mix them to create offspring that would meet the above conditions. Any ideas? Clarification: The nodes each have a fixed x,y coordiante position. Only the routes between them can be altered.

• ### Suggestion on algorithm to distribute objects of different value

##### - by Unknown
Hello, I have the following problem: Given N objects of different values (N < 30, and the values are multiple of a "k" constant, i.e. k, 2k, 3k, 4k, 6k, 8k, 12k, 16k, 24k and 32k), I need an algorithm that will distribute all items to M players (M <= 6) in such a way that the total value of the objects each player gets is as even as possible (in other words, I want to distribute all objects to all players in the fairest way possible). I don't need (pseudo)code to solve this (also, this is not a homework :) ), but I'll appreciate any ideas or links to algorithms that could solve this. Thanks!

• ### help with number calculation algorithm [hw]

##### - by sa125
Hi - I'm working on a hw problem that asks me this: given a finite set of numbers, and a target number, find if the set can be used to calculate the target number using basic math operations (add, sub, mult, div) and using each number in the set exactly once (so I need to exhaust the set). This has to be done with recursion. So, for example, if I have the set {1, 2, 3, 4} and target 10, then I could get to it by using ((3 * 4) - 2)/1 = 10. I'm trying to phrase the algorithm in pseudo-code, but so far haven't gotten too far. I'm thinking graphs are the way to go, but would definitely appreciate help on this. thanks.

• ### Algorithm for dynamic combinations

##### - by sOltan
My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events I would like to call a function with each combination of Events. To illustrate with an example: INPUTS: A(0,1,2), B(0,1), C(0,1,2,3) I need to call my function this many times for each combination (the input count is dynamic, in this example it is three parameter, but it can be more or less) function(A[0],B[0],C[0]) function(A[0],B[1],C[0]) function(A[0],B[0],C[1]) function(A[0],B[1],C[1]) function(A[0],B[0],C[2]) function(A[0],B[1],C[2]) function(A[0],B[0],C[3]) function(A[0],B[1],C[3]) function(A[1],B[0],C[0]) function(A[1],B[1],C[0]) function(A[1],B[0],C[1]) function(A[1],B[1],C[1]) function(A[1],B[0],C[2]) function(A[1],B[1],C[2]) function(A[1],B[0],C[3]) function(A[1],B[1],C[3]) function(A[2],B[0],C[0]) function(A[2],B[1],C[0]) function(A[2],B[0],C[1]) function(A[2],B[1],C[1]) function(A[2],B[0],C[2]) function(A[2],B[1],C[2]) function(A[2],B[0],C[3]) function(A[2],B[1],C[3]) This is what I have thought of so far: My approach so far is to build a list of combinations. The element combination is itself a list of "index" to the input arrays A, B and C. For our example: my list iCOMBINATIONS contains the following iCOMBO lists (0,0,0) (0,1,0) (0,0,1) (0,1,1) (0,0,2) (0,1,2) (0,0,3) (0,1,3) (1,0,0) (1,1,0) (1,0,1) (1,1,1) (1,0,2) (1,1,2) (1,0,3) (1,1,3) (2,0,0) (2,1,0) (2,0,1) (2,1,1) (2,0,2) (2,1,2) (2,0,3) (2,1,3) Then I would do this: foreach( iCOMBO in iCOMBINATIONS) { foreach ( P in INPUTS ) { COMBO.Clear() foreach ( i in iCOMBO ) { COMBO.Add( P[ iCOMBO[i] ] ) } function( COMBO ) --- (instead of passing the events separately) } } But I need to find a way to build the list iCOMBINATIONS for any given number of INPUTS and their events. Any ideas? Is there actually a better algorithm than this? any pseudo code to help me with will be great. C# (or VB) Thank You

• ### how to tackle this combinatorial algorithm problem

##### - by Andrew Bullock
I have N people who must each take T exams. Each exam takes "some" time, e.g. 30 min (no such thing as finishing early). Exams must be performed in front of an examiner. I need to schedule each person to take each exam in front of an examiner within an overall time period, using the minimum number of examiners for the minimum amount of time (i.e. no examiners idle) There are the following restrictions: No person can be in 2 places at once each person must take each exam once noone should be examined by the same examiner twice I realise that an optimal solution is probably NP-Complete, and that I'm probably best off using a genetic algorithm to obtain a best estimate (similar to this? http://stackoverflow.com/questions/184195/seating-plan-software-recommendations-does-such-a-beast-even-exist). I'm comfortable with how genetic algorithms work, what i'm struggling with is how to model the problem programatically such that i CAN manipulate the parameters genetically.. If each exam took the same amount of time, then i'd divide the time period up into these lengths, and simply create a matrix of time slots vs examiners and drop the candidates in. However because the times of each test are not necessarily the same, i'm a bit lost on how to approach this. currently im doing this: make a list of all "tests" which need to take place, between every candidate and exam start with as many examiners as there are tests repeatedly loop over all examiners, for each one: find an unscheduled test which is eligible for the examiner (based on the restrictions) continue until all tests that can be scheduled, are if there are any unscheduled tests, increment the number of examiners and start again. i'm looking for better suggestions on how to approach this, as it feels rather crude currently.