Lagrangian system: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
Newer edit →
en>Helpful Pixie Bot
m ISBNs (Build KE)
 
en>Yobot
m →External links: Categories more at one line and/or other fixes using AWB (9466)
Line 1: Line 1:
Surely the second option would be more beneficial for any website. If you loved this short article and you wish to receive more details with regards to [http://www.odessapd.com/redirect.aspx?url=https://wordpress.org/plugins/ready-backup/ wordpress backup plugin] please visit the web-site. Medical word press themes give you the latest medical designs. These templates are professionally designed and are also Adsense ready. If you are using videos on your site then this is the plugin to use. It's as simple as hiring a Wordpress plugin developer or learning how to create what is needed. <br><br>Luckily, for Word - Press users, WP Touch plugin transforms your site into an IPhone style theme. If you wish to sell your services or products via internet using your website, you have to put together on the website the facility for trouble-free payment transfer between customers and the company. You are able to set them within your theme options and so they aid the search engine to get a suitable title and description for the pages that get indexed by Google. Furthermore, with the launch of Windows 7 Phone is the smart phone market nascent App. Once you've installed the program you can quickly begin by adding content and editing it with features such as bullet pointing, text alignment and effects without having to do all the coding yourself. <br><br>The least difficult and very best way to do this is by acquiring a Word - Press site. By using Word - Press MLM websites or blogs, you and your companies presence on the internet can be created swiftly and simply. If Gandhi was empowered with a blogging system, every event in his life would have been minutely documented so that it could be recounted to the future generations. Provide the best and updated information to the web searchers and make use of these wonderful free themes and create beautiful websites. If you have any questions on starting a Word - Press food blog or any blog for that matter, please post them below and I will try to answer them. <br><br>Word - Press has plenty of SEO benefits over Joomla and Drupal. In case you need to hire PHP developers or hire Offshore Code - Igniter development services or you are looking for Word - Press development experts then Mindfire Solutions would be the right choice for a Software Development partner. The templates are designed to be stand alone pages that have a different look and feel from the rest of your website. Giant business organizations can bank on enterprise solutions to incorporate latest web technologies such as content management system etc, yet some are looking for economical solutions. Wordpress template is loaded with lots of prototype that unite graphic features and content area. <br><br>More it extends numerous opportunities where your firm is at comfort and rest assured of no risks & errors. Being a Plugin Developer, it is important for you to know that development of Word - Press driven website should be done only when you enable debugging. However, you must also manually approve or reject comments so that your website does not promote parasitic behavior. If this is not possible you still have the choice of the default theme that is Word - Press 3. Get started today so that people searching for your type of business will be directed to you.
The '''pebble motion problems''', or '''pebble motion on graphs''', are a set of related problems in [[graph theory]] dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a [[Graph (mathematics)|graph]] with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-[[robot]] [[motion planning]] (in which the pebbles are robots) and [[network routing]] (in which the pebbles are [[Data packet|packets]] of data). The best-known example of a pebble motion problem is the famous [[15 puzzle]] where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time.
 
==Theoretical formulation==
The general form of the pebble motion problem is Pebble Motion on Graphs<ref name="Kornhauser">[http://www2.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715921 ]{{dead link|date=September 2013}}</ref> formulated as follows:
 
Let <math>G = (V,E)</math> be a graph with <math>n</math> vertices. Let <math>P = \{1,\ldots,k\}</math> be a set of pebbles with <math>k < n</math>. An arrangement of pebbles is a mapping <math>S : P \rightarrow V</math> such that <math>S(i) \neq S(j)</math> for <math>i \neq j</math>. A move <math>m = (p, u, v)</math> consists of transferring pebble <math>p</math> from vertex <math>u</math> to adjacent unoccupied vertex <math>v</math>. The Pebble Motion on Graphs problem is to decide, given two arrangements <math>S_0</math> and <math>S_+</math>, whether there is a sequence of moves that transforms <math>S_0</math> into <math>S_+</math>.
 
===Variations===
Common variations on the problem limit the structure of the graph to be:
* a [[Tree graph|tree]]<ref name="Auletta">{{cite web|url=http://www.springerlink.com/content/fnq2nmmd7g7dpu3r/ |title=A Linear-Time Algorithm for the Feasibility of Pebble Motion on Trees - Springer |publisher=Springerlink.com |date= |accessdate=2013-09-27}}</ref>
* a [[Lattice graph|square grid]],<ref name="Calinescu">{{cite web|url=http://www.springerlink.com/content/f2v1985q85261410/ |title=Reconfigurations in Graphs and Grids - Springer |publisher=Springerlink.com |date= |accessdate=2013-09-27}}</ref>
* a [[Biconnected graph|bi-connected]]<ref name="Surynek">{{cite web|author=First Name Middle Name Last Name |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5152326 |title=IEEE Xplore - A novel approach to path planning for multiple robots in bi-connected graphs |doi=10.1109/ROBOT.2009.5152326 |publisher=Ieeexplore.ieee.org |date=2009-05-17 |accessdate=2013-09-27}}</ref> graph.
 
Another set of variations consider the case in which some<ref name="Papadimitriou">[http://www2.computer.org/portal/web/csdl/doi/10.1109/SFCS.1994.365740 ]{{dead link|date=September 2013}}</ref> or all<ref name="Calinescu" /> of the pebbles are unlabeled and interchangeable.
 
Other versions of the problem seek not only to prove reachability but to find a (potentially optimal) sequence of moves (i.e. a plan) which performs the transformation.
 
==Complexity==
Finding the shortest path in the pebble motion on graphs problem (with labeled pebbles) is known to be [[NP hard|NP-hard]]<ref name="Ratner">{{cite web|url=http://portal.acm.org/citation.cfm?id=102409 |title=The (n2-1)-puzzle and related relocation problems |doi=10.1016/S0747-7171(08)80001-6 |publisher=Portal.acm.org |date= |accessdate=2013-09-27}}</ref> and [[APX|APX-hard]].<ref name="Calinescu" /> The unlabeled problem can be solved in polynomial time when using the cost metric mentioned above (minimizing the total number of moves to adjacent vertices), but is [[NP hard|NP-hard]] for other natural cost metrics.<ref name="Calinescu" />
 
== References ==
<!--- See [[Wikipedia:Footnotes]] on how to create references using <ref></ref> tags which will then appear here automatically -->
{{Reflist}}
 
{{DEFAULTSORT:Pebble Motion Problems}}
[[Category:Multi-agent systems]]
[[Category:Automated planning and scheduling]]
[[Category:Computational problems in graph theory]]

Revision as of 12:38, 8 September 2013

The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-robot motion planning (in which the pebbles are robots) and network routing (in which the pebbles are packets of data). The best-known example of a pebble motion problem is the famous 15 puzzle where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time.

Theoretical formulation

The general form of the pebble motion problem is Pebble Motion on Graphs[1] formulated as follows:

Let G=(V,E) be a graph with n vertices. Let P={1,…,k} be a set of pebbles with k<n. An arrangement of pebbles is a mapping S:P→V such that S(i)≠S(j) for i≠j. A move m=(p,u,v) consists of transferring pebble p from vertex u to adjacent unoccupied vertex v. The Pebble Motion on Graphs problem is to decide, given two arrangements S0 and S+, whether there is a sequence of moves that transforms S0 into S+.

Variations

Common variations on the problem limit the structure of the graph to be:

Another set of variations consider the case in which some[5] or all[3] of the pebbles are unlabeled and interchangeable.

Other versions of the problem seek not only to prove reachability but to find a (potentially optimal) sequence of moves (i.e. a plan) which performs the transformation.

Complexity

Finding the shortest path in the pebble motion on graphs problem (with labeled pebbles) is known to be NP-hard[6] and APX-hard.[3] The unlabeled problem can be solved in polynomial time when using the cost metric mentioned above (minimizing the total number of moves to adjacent vertices), but is NP-hard for other natural cost metrics.[3]

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

  1. ↑ [1]Template:Dead link
  2. ↑ Template:Cite web
  3. ↑ 3.0 3.1 3.2 3.3 Template:Cite web
  4. ↑ Template:Cite web
  5. ↑ [2]Template:Dead link
  6. ↑ Template:Cite web
Retrieved from "https://en.formulasearchengine.com/index.php?title=Lagrangian_system&oldid=24749"