Anar al contingut

Algoritme de Deu

De L'Enciclopèdia, la wikipedia en valencià

L'algoritme de Deu és un concepte originat en discussions sobre formes de resoldre el rompecabezas del gaveta de Rubik,[1] pero que també es pot aplicar a uns atres rompecabezas combinatoris i jocs matemàtics.[2] Es referix a qualsevol algoritme que produïxca una solució en la menor cantitat de moviments possibles, sent l'idea que solament un ser omnisciente coneixeria un pas òptim de qualsevol configuració donada. Pero hi ha un rompecabezas cridat Pyraminx Duo a on hi ha una taula a on se soluciona el rompecabezas en l'algoritme de Deu per a cada una dels seus 324 combinacions totals i qualsevol persona que entenga la taula pot resoldre-ho en l'algoritme de Deu.[3]

Alcance

Definició

La noció s'aplica als rompecabezas que poden assumir un número finit de "configuracions", en una atarassana relativament chicoteta i ben definit de "moviments" que poden ser aplicables a configuracions i despuix conduir a una nova configuració. Resoldre el rompecabezas significa aplegar a una "configuració final" designada, una configuració singular o una d'una colecció de configuracions. Per a resoldre el rompecabezas s'aplica una seqüència de moviments, partint d'alguna configuració inicial arbitrària.

Solució

Es pot considerar que un algoritme resol tal rompecabezas si pren com a entrada una configuració inicial arbitrària i produïx com a eixida una seqüència de moviments que conduïxen a una configuració final (si el rompecabezas es pot resoldre a partir d'eixa configuració inicial, de lo contrari, indica l'impossibilitat d'una solució). Una solució és òptima si la seqüència de moviments és lo més curta possible. Este reconte es coneix com el número de Deu,[4] o, més formalment, el valor minimax.[5] L'algoritme de Deu, llavors, per a un rompecabezas donat, és un algoritme que resol el rompecabezas i produïx solament solucions òptimes.

Alguns escritors, com David Joyner, consideren que per a que un algoritme es denomine correctament "algoritme de Deu", també deuria ser pràctic, lo que significa que l'algoritme no requerix cantitats extraordinàries de memòria o temps. Per eixemple, l'us d'una taula de busca jaganta indexada per configuracions inicials permetria trobar solucions molt ràpidament, pero requeriria una cantitat extraordinària de memòria.[6]


En lloc de demanar una solució completa, es pot demanar de manera equivalent un sol moviment d'una configuració inicial pero no final, a on el moviment és el primer d'alguna solució òptima. Un algoritme per a la versió d'un sol moviment del problema es pot convertir en un algoritme per al problema original invocant-ho repetidament mentres s'aplica cada moviment informat a la configuració actual, fins que s'alcança un de final. Pel contrari, qualsevol algoritme per al problema original pot convertir-se en un algoritme per a la versió d'un sol moviment truncant la seua eixida al seu primer moviment.

Eixemples

Gaveta de Rubik.

Els acertijos més coneguts que encaixen en esta descripció són els acertijos mecànics com el gaveta de Rubik, les Torres de Hanói i el joc del 15. També es cobrix el joc per a una persona del solitari Senku, aixina com molts acertijos de llògica, com el problema dels misionero i caníbals. Estos tenen en comú que es poden modelar matemàticament com un grafo dirigit, en el que les configuracions són els vèrtiços i els moviments els arcs.

Rompecabezas mecànics

n-Puzles

el joc del 15 es pot resoldre en 80 moviments d'una sola ficha[7] o 43 moviments de vàries fiches[8] en el pijor dels casos. Per a la seua generalisació el n- rompecabezas, el problema de trobar una solució òptima és NP-hard.[9] Per lo tant, es desconeix si existix un algoritme de Deu pràctic per a este problema, pero sembla poc provable.

Torres de Hanói

Per a les Torres de Hanói, es coneix l'algoritme d'un Deu per a qualsevol número de discs. El número de moviments és exponencial en el número de discs Plantilla:Nobr.[10]

Gaveta de Rubik

Artícul principal → Solucions òptimes per a la gaveta de Rubik.


Richard Korf va publicar en 1997 un algoritme per a determinar el número mínim de moviments per a resoldre el gaveta de Rubik.[11] Si be se sabia des de 1995 que 20 era un llímit inferior en el número de moviments per a la solució en el pijor dels casos, es va demostrar en 2010 a través d'extensos càlculs per computadora que cap configuració requerix més de 20 moviments.[12] Per tant, 20 és un llímit superior marcat en la llongitut de les solucions òptimes. El matemàtic David Singmaster hi havia "conjeturado precipitadamente" que este número era 20 en 1980.[5]

S'han trobat números per a la gaveta de tres colors, el número total dels quals de configuracions és:

211⋅37⋅C124⋅(C84)2=10 863 756 288 000


En març-abril de 2012, es va descobrir que el número de Deu per a la gaveta de tres colors oposts és 15 FTM, 17 QTM o 14 STM (segons la mètrica STM, la rotació de qualsevol capa intermija també es considera un moviment).[13]

Vore també

Referències

  1. ↑ Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Tingues Phrases and Expressions, Hachette UK, 2014 ISBN 1472116224.
  2. ↑ See i.g. Rubik's Cubic Compendium by Ernö Rubik, Tamás Varga, Gerzson Kéri, György Marx, and Tamás Vekerdy (1987, Oxford University Press, ISBN 0-19-853202-4), p. 207: "... el Pyraminx és molt més simple que la Gaveta Màgica ... Nicholas Hammond ha demostrat que l'algoritme de Deu té com a màxim 21 moviments (inclosos els quatre moviments de vèrtiç trivials). [Més recentment, tres persones han trobat l'algoritme de Deu. El número màxim de moviments és 15 (inclosos els moviments de quatre vèrtiços).]"
  3. ↑ Nilson Rafael Bolívar Barris (2022). «Resoldre el Pyraminx Duo en l'algoritme de Deu. Li ensenyarem com resoldre la gaveta de Rubik i molts atres rompecabezas en 3 dimensions en l'algoritme de Deu.». ResearchGate.
  4. ↑ Jonathan Fildes. «Rubik's Cube quest for speedy solution menges to an end», BBC News, 2010-08-11.
  5. ↑ 5,0 5,1 Singmaster, p. 311, 1980
  6. ↑ Joyner, page 149
  7. ↑ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45–63.
  8. ↑ "The Fifteen Puzle ca be solved in 43 moves". Domain of the Cube Forum
  9. ↑ Daniel Ratner, Manfred K. Warmuth (1986). "Finding a shortest solution for the N × N extension of the 15-puzle is intractable". in Proceedings AAAI-86. National Conference on Artificial Intelligence, 1986. pp. 168–172.
  10. ↑ Carlos Roda, "An optimal solution to the Towers of Hanoi Puzle".
  11. ↑ Richard E. Korf, "Finding optimal solutions to Rubik's Cube using pattern databases", Proc. Natl. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700–705.
  12. ↑ "God's Number is 20". Cube20.org
  13. ↑ «Some 3-color cube results». Domain of the Cube Forum. Archivat des de l'original, el 2013-09-04. Consultat el 2013-07-29.

Bibliografia

  • Baum, Eric B., What is Thought?, MIT Press, 2004 ISBN 0262025485.
  • Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., "Artificial-life, agents and Go", in Mohammadian, Masoud, New Frontiers in Computational Intelligence and its Applications, pp. 125–139, IOS Press, 2000 ISBN 9051994761.
  • Fraser, Rober (ed); Hannah, W. (ed), The Draught Players' Weekly Magazine, vol. 2, Glasgow: J H Berry, 1885.
  • David Joyner (2002). Adventures in Group Theory, Johns Hopkins University Press. ISBN 0-8018-6947-1.
  • Moore, Cristopher; Mertens, Stephan, The Nature of Computation, Oxford University Press, 2011 ISBN 0191620807.
  • Rothenberg, Gadi, Catalysis, God's Algorithm, and the Green Demon, Amsterdam University Press, 2009 ISBN 9056295896.
  • Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, "Checkers is solved", Science, vol. 317, no. 58444, pp. 1518–1522, 14 September 2007.
  • Singmaster, David, Notes on Rubik's Magic Cube, Penguin, 1981 ISBN 0-907395-00-7.
  • Singmaster, David, "The educational value of the Hungarian 'Magic Cube'", Proceedings of the Fourth International Congress on Mathematical Education, celebrada en Berkeley, Califòrnia, 10–16 d'agost de 1980, pp. 307–312, Birkhauser Boston Inc, 1983 ISBN 978-0-8176-3082-9.


Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Algoritme_de_Deu&oldid=1619125»