From BRYAN@wvnvm.wvnet.edu Thu Feb 16 03:12:38 1995 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA23166; Thu, 16 Feb 95 03:12:38 EST Message-Id: <9502160812.AA23166@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8706; Wed, 15 Feb 95 21:47:09 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 6982; Wed, 15 Feb 1995 21:47:09 -0500 X-Acknowledge-To: Date: Wed, 15 Feb 1995 21:47:07 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Start-rooted vs. X-rooted Search Example It's a fool's errand, I suppose, but in light of our recent discussions, I created an X-rooted data base up through level 5, where X is the representative element of {m'Fm}. Here are the results compared to a standard Start-rooted data base. It is most important to realize that both data bases contain only representative elements, and that the results with total cubes are derived from the representative elements by calculating the sizes of the conjugacy classes. Start- Repr{m'Fm}- Rooted Rooted Representative Representative Level Cubes Elements Cubes Elements 0 1 1 12 1 1 12 1 115 6 2 114 5 1,068 25 3 1,068 25 10,011 219 4 10,011 219 93,840 1,978 5 93,840 1,978 878,880 18,395 Performing the search in this fashion, it seems to me that there are only four positions for which the search would look the same as for Start -- Start itself, the Superflip, the Pons Asinorum, and the composition of the Superflip with Pons Asinorum. Martin Shoenert and Mark Longridge have convinced me that the Pons Asinorum and the composition of the Superflip with Pons Asinorum are not in the center of the cube group. But I still believe that the search space for all four position looks essentially the same because these are the only four positions for which the associated symmetry group is M. That is, it is only these four positions for which X=m'Xm for all m in M. It was in this sense -- that the search space structure using representative elements is the same for Start and for superflip -- that I meant that two half-depth searches using representative elements were easy for the superflip, but would be harder for other positions. Here is a question for Dik Winter and Mike Reid (and my apologies if I have asked this before): have you tried your Kociemba's algorithm programs for the composition of Pons Asinorum with superflip? I would find the results to be *very* interesting. Finally, as one last fool's errand, I performed the search for the first five levels again, this time using cubes instead of representative elements. With this last search, the results are the same whether the root of the search is Start or something else, which is the point both der Mouse and Martin Schoenert were making. In this chart, "level" has to be interpreted as "distance from root", not "distance from Start". Start- Repr{m'Fm}- Rooted Rooted Level Cubes Cubes 0 1 1 1 12 12 2 114 114 3 1,068 1,068 4 10,011 10,011 5 93,840 98,840 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU