That's good. II think at least for marines should be stationed, because ships will be everywear.
-----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Phil Vlasak Sent: Friday, October 05, 2007 2:47 PM To: Gamers Discussion list Subject: [Audyssey] Deep space Attack Games we'd like to play... The title for the Marine game is: Deep space Attack The Storyline is: In the deep realms of space, an evil so powerful has just awoken. The evil is powerful enough to destroy the hole galaxy...... who is going to do this? As he walks to the main office, John the Space Marine and the chief go up to the office. The chief sits down and says, "The Set Covering Deployment Problem could be an invaluable aid in positioning your Space Marine units." John smiles and replies, "Yes, the Set covering deployment seeks an optimal stationing of Marine troops in a set of space regions so that a relatively small number of Marine troop units can control a large space region." The Chief continues, "The Set covering deployment can be mathematically formulated as a (0,1)-integer programming problem. Integer programming is a special case of linear programming, which refers to optimizing an outcome based on some set of constraints using a linear mathematical model, and (0,1)-integer programming means that all variables are required to be integers equal to either 0 or 1--in other words, the variables are binary. To formulate your Powerful Evil domination problem, consider the 8 provinces of the Powerful Evil Empire illustrated on this chart. Each region is represented as a white disk, and the red lines indicate region connections. Call a region secured if one or more field Marines are stationed in that region, and call a region securable if a field Marine can be deployed to that area from an adjacent area. In addition, assume that a field Marine can only be deployed to an adjacent region if at least one Marine remains in the original region to provide logistical support. Also assume that each region contains at most two Marines , as the number of available Marines are limited and cannot be concentrated in any one region. This problem can then be mathematically formulated by representing the Powerful Evil area as a graph. We can then associate two binary variables and with each vertex (i.e., each province) in the vertex set of the Powerful Evil Empire graph which specify whether a first and second field Marine (respectively) is located at a given vertex . In the terminology of graph theory, the Powerful Evil Empire graph is a simple connected graph on eight vertices and with 13 edges. In set covering deployment, the problem to be solved is to maximize the quantity subject to the constraints which guarantees that the first Marine is stationed at a given vertex before a second can be, which guarantees that if does not contain a field Marine , it has a neighbor with two field Marines, and which enforces the integer constraint (i.e., when combined with the first constraint, only zero, one, or two field Marines may be placed in any given region). This integer programming problem can then be translated into matrix terms and solved using standard techniques to find the minimum number of field Marines needed to secure the Powerful Evil Empire. John shakes his head in amazement. the Chief continues In the case of Marine officers in Space, to first approximation (ignoring local topography such as planets, stars etc.) we can assume that each officer "covers" a circular region (i.e., a disk) whose size is proportional to the distance that officer can see (or travel). Taking the search region as a square set of space sectors (shown in gray below), the following visualization shows a configuration of randomly distributed Marines officers with random coverage radii, giving an arrangement that covers only 50% of the search region. Obviously, the larger the size of the Marines force and the larger the coverage radii of individual Marines units, the higher the fraction of area that can be covered. However, optimal placement gives the best coverage possible for a fixed set of Marines units. In the case above, it turns out to be possible to arrange the six disks so that they have no overlap, so the maximum coverage is given by , i.e., the sum of the disk areas, each of which is given by times the radius squared, where radii are measured in units of the edge length of the square. In general, achieving optimal coverage requires minimizing disk overlap, as well as minimizing the amount by which disks extend outside the area of surveillance. As you can see below, an optimal solution is not necessarily unique; in this case, there are several separate disk arrangements that all share an optimal 69% coverage. You can interactively explore optimal coverages for different numbers of Marines units. Spatial optimization Covering problems are a form of Spatial optimization problem. In general, such problems are difficult to solve even approximately, let alone exactly. In the more complicated case of placing even as many as ten Marines, one can imagine moving them around "by hand." But in general, as the number of Marines becomes large, problems of this type become unmanageable using not only "hand" methods, but also using any sort of combinatorial methods. Effective practical methods are thus needed." John replies, in the case of Powerful Evil domineering space, addressing a problem mathematically generally requires two steps: (1) formulating the problem mathematically and (2) using appropriate methods to find a solution. Depending on the nature of the problem, one of these steps may be harder than the other. In the idealized Marines deployment problem, step 1 is "easy," as the problem can be rather succinctly formulated as maximizing the function --that is, finding the set of points constrained to the unit square () that give , where is the Iverson bracket, denotes a vector norm, and ? is the logical OR operator. Here, we have made the assumptions that a given Marines officer's covering radius is fixed regardless of the officer's position, and that we know or can estimate a value of this radius for each Marines officer. Finally, the double integral over the unit square that gives the total amount of area covered by Marines. So the mathematical formulation simply says, "For a given set of Marines positions and coverage radii, find all regions in the unit square covered by at least one Marines officer, sum their areas (making sure to count regions of overlap only once), and maximize this area for fixed radii over all possible Marines positions." Once the problem has been mathematically formulated, it can be solved using one of a number of optimization algorithms. John smiles and says that will certainly solve where the Powerful Evil is and how to destroy it with the minimum number of Marines! As John leaves, the game begins! --- Gamers mailing list __ [email protected] If you want to leave the list, send E-mail to [EMAIL PROTECTED] You can make changes or update your subscription via the web, at http://audyssey.org/mailman/listinfo/gamers_audyssey.org. All messages are archived and can be searched and read at http://www.mail-archive.com/[EMAIL PROTECTED] If you have any questions or concerns regarding the management of the list, please send E-mail to [EMAIL PROTECTED] --- Gamers mailing list __ [email protected] If you want to leave the list, send E-mail to [EMAIL PROTECTED] You can make changes or update your subscription via the web, at http://audyssey.org/mailman/listinfo/gamers_audyssey.org. All messages are archived and can be searched and read at http://www.mail-archive.com/[EMAIL PROTECTED] If you have any questions or concerns regarding the management of the list, please send E-mail to [EMAIL PROTECTED]
