Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

José Alberto Hernández Aguilar (Autonomous University of Morelos State, Mexico), Augusto Renato Pérez Mayo (Autonomous University of Morelos State, Mexico), Santiago Yip Ortuño (Autonomous University of Morelos State, Mexico), Alberto Ochoa-Zezzatti (Autonomous University of Juarez City, Mexico) and Julio César Ponce Gallegos (Autonomous University of Aguascalientes, Mexico)

Copyright: © 2016
|Pages: 12

DOI: 10.4018/978-1-4666-9779-9.ch022

Chapter Preview

TopLots of situations in real life present a configuration of items stacked up to a pile that requires to be transferred in another pile with another order of items, this type of problems can be identified in management logistics also. According Hempfel and Schmiedel (2006) the question that involves an optimization problem is: How to do it in the best way using only available resources and devices?

Some examples are mentioned in (Hempel and Schmiedel, 2006): imagine a port where there are several containers and is necessary to load or to unload loading from the containerships, or suppose large concrete parts for a modern bridge or construction of buildings, or the shunt of trains in a marshaling yard, or patient plays. A container pre-marshaling problem is reported in (Shan-Huen & Tsan-Hwan, 2012) which purpose is finding a set of container movements to reach a final container arrangement by satisfying certain restrictions. Lu & Dillon (1995) discuss a parallelism implementation of Towers of Hanoi on which is permitted concurrent moves of disks in a single step. These authors analyzed three versions of parallelism considering two factors: the order of moves of disks and the resource utilization of pegs. They present a common technique for getting the non-recursive implementation by considering minimum steps. All of these problems can be modeled by applying basic principles of the Towers of Hanoi.

Puzzles are connected with graphs, it means can be modeled by using graphs, vertices of the graph represent configuration and graph edges define possible moves of the puzzle (Cull, Merril and Van, 2013). According (Hempel & Schmiedel, 2006) to describe pile problems more precisely is highly recommended using graph theory. For these authors:

For a given directed graph G = (V, A) and its vertices v ϵ V can be used the following notations: N_{G+}(v) is the set of all successors of v, N_{G-}(V) is the set of all predecessors of v. d_{G+}(v) represents numbers of outgoing arcs of v and d_{G-}(v) numbers of incoming arcs of v respectively. For G_{1} = (V_{1}, A_{1}) and G_{2} = (V_{2}, A_{2}) the union of G_{1} and G2 is defined as G_{1} U G_{2}:= (V_{1} U V_{2}, A_{1} U A_{2}). A cycle in a directed graph G = (V, A) is a closed path in G. The directed graph G = (V, A) is called a pile, if and only if G is finite and does not contain a loop or a cycle. The vertices of G represent the elements of the pile; the arcs of G represent the order in which the elements are piled up. A step is the move of an element of data structure to another place. This place can be in different pile or in an auxiliary place if it exists (Hempel & Schmiedel, 2006).

Figure 1 and Figure 2, show an example of typical pile problems, meanwhile graphs representing the starting *Gs* and final *Gf* are shown below (Hempfel and Schmiedel, 2006):

Note how arcs in Figure 3 and Figure 4 correspond to inverted graphs.

Also called the Towers of Brahma or Towers of Lucas; is a mathematical game, puzzle or toy that is made of three pegs (poles) and a number of disks of different sizes (in its basic form consisting of three disks), which can be moved into any peg (Hofstadter, 1996). The game starts with the disks placed in ascending order of size in one peg, the smallest at the top, forming a cone or pyramid (see Figure 5).

The purpose of the game is moving the entire pile of disks from the origin peg to the destiny peg, by considering next simple rules (Scheinerman, 2000):

**Step 1:**Sole one disk can be moved each turn.**Step 2:**A move consists of taking the upper disk from one of the stacks and placing it on top of another stack.**Step 3:**Is not allowed a disk be placed on top of a smaller disk.

According Mishra and Vishnoi (2015) with three single disks, the game can be solved in seven steps. The minimum moves required to solve a Tower of Hanoi puzzle is 2^{n} - 1, where n represents number of disks, as can be seen, this is an exponential number that increases when n increases.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved