| CIS 730 Introduction to Artificial Intelligence | Kansas State University | Fall 2001 | http://www.kddresearch.org/Courses/Fall-2001/CIS730 | | Machine Problem 1 of 3 | Case 5 of 5: UGLY | | "Muddle-earth": randomly-generated example | (see /The Hobbit/ and /Lord of The Rings/ by J.R.R. Tolkien) | Sat 15 Sep 2001 by William H. Hsu | Corrected Mon 17 Sep 2001 by John Yockey | | Generator Formulas | ================== | Edge weights: =RAND()*100+25 | Heuristic values: =RAND()*25 | Direct edges from start node to goals were deleted. | (I used Microsoft Excel XP, but I'm sure you could do this in GNUmeric | or any spreadsheet with a decent [R]andom [N]umber [G]enerator.) | | Randomly selected edges were deleted until there was no path of length | 2 from the start node to a goal node. | | Annun 0 | Bree 1 | Bywater 2 | Caradhras 3 | Cuivienen 4 | Druadan 5 | Dunland 6 | Edoras 7 | Erebor 8 | Fornost 9 | Gebir 10 | Guldur 11 | Havens 12 | Hobbiton 13 | Isengard 14 | Khand 15 | Laketown 16 | Lothlorien 17 | Morannon 18 | Morgul 19 | Moria 20 | Nogrod 21 | Osgiliath 22 | Pelargir 23 | Rivendell 24 | Smials 25 | Tirith 26 | Umbar 27 | Weathertop 28 | Zirakzigil 29 30 | | Start node: Hobbiton (13) 13 | Goal nodes: Erebor (8) - the Lonely Mountain 8 | Adjacency matrix with costs * 72 * 64 * 35 * 49 70 * 106 * 29 * 96 * 99 52 * 103 * 107 * 89 * * * 35 * 43 72 * 72 * * 110 * 110 * 72 * 60 * 37 * 97 51 * 94 38 * 46 73 * * 26 * * 73 * * 72 * 115 76 36 * 26 * 34 54 * 72 121 * 92 60 * 78 * 64 * 37 * 37 * 68 56 92 53 64 * 115 * 87 * 49 72 * * 55 * 101 * 46 48 * 49 * 81 81 44 * 30 104 * 66 80 * 98 * * 76 87 * 125 70 * * 82 * 80 * 37 85 * 34 76 76 31 * 64 110 38 * 94 28 * 82 50 35 110 36 * 125 * 47 71 * 30 55 * 124 27 * 84 73 * 48 52 71 61 37 * 51 41 * 46 122 25 * * * 49 70 47 * 84 42 76 30 54 117 * 47 95 98 107 88 53 99 96 * 93 66 39 102 102 39 86 49 110 26 72 * 71 84 * * 63 * 79 * 117 60 51 89 55 60 49 48 122 119 111 100 95 123 52 27 63 70 * * * * * 42 * * * 120 47 91 * * 57 * 43 * * * 71 * * * * 86 * * * * 72 34 * 82 30 76 63 * * 36 * 97 102 * 79 107 * * 34 95 * 63 * 81 * 48 * 70 47 106 * 54 55 * 55 30 * 120 36 * 117 79 * 123 * 110 64 * 60 * 46 * 106 * * 87 52 103 59 * 60 * * 80 * 54 79 47 * 117 * * * * 44 * 104 28 39 * 31 110 * 56 103 * 55 110 114 29 * 72 101 * 124 117 * 91 97 79 * * * 120 37 * * 90 31 * 74 * 68 * 75 91 58 100 54 * 37 121 * 37 27 * 117 * 102 * * * * 91 * * * 113 51 88 * 60 * 91 114 * 113 27 74 96 * * 46 85 * 47 60 * * 123 * 120 91 * * 45 * 42 * 76 100 49 * 66 * 106 75 31 27 * 97 92 48 * 84 95 51 57 79 * 44 37 * * * 78 29 * 100 * 49 * 52 * 41 102 62 79 105 99 51 60 * 34 73 98 89 * 107 110 * * * 45 78 * 81 104 * 53 * 51 110 * 35 107 42 42 109 52 * * 49 76 * 107 55 43 * 64 104 * * * 29 81 * 85 81 * 45 88 * 36 * 41 59 57 100 * 94 78 * 76 48 88 60 * * * 28 90 113 42 * 104 85 * * 120 * 122 59 * 40 64 63 57 109 103 38 * 81 31 52 53 49 * 34 60 39 31 51 * 100 * 81 * * 108 * 72 114 * 54 * 39 46 68 * * 64 81 * 71 99 48 * 95 * * * 88 76 * 53 * 120 108 * * 115 * 29 * 32 27 87 79 107 46 * 44 64 61 96 122 71 * 46 31 74 * 100 49 * 45 * * * * 115 * 99 35 * 88 103 27 * 73 37 * 110 37 * 119 * 63 * 110 * 60 49 * 51 88 122 72 115 115 * 67 * 102 75 50 36 99 89 * * 30 38 * 93 111 * * 106 * 68 * * 52 110 * 59 114 * * 67 * * 101 * 77 43 125 * * 37 104 * 51 66 100 * 81 * 56 * 91 66 * * 36 * * 29 99 * * * * 65 100 89 80 * 26 * * 94 41 39 95 * * * 103 75 114 * 41 35 * 40 54 * 35 102 101 * * 92 112 73 114 * * 68 66 28 * 102 123 86 48 87 * * 88 106 102 107 41 64 * 32 * 75 * 65 92 * 28 103 36 35 * 56 80 * 46 102 52 * * 52 55 58 113 75 62 42 59 63 39 27 88 50 77 100 112 28 * 77 27 * 73 92 * 82 122 39 27 * 70 103 110 100 27 31 79 42 57 57 46 87 103 36 43 89 73 103 77 * 121 43 * 53 98 50 25 86 63 * 47 59 114 54 74 27 105 109 100 109 68 79 27 99 125 80 114 36 27 121 * | Randomly-generated (trivially admissible) heuristic 22 10 15 9 25 15 12 19 0 8 11 19 21 2 15 7 22 22 10 15 10 7 9 19 6 22 4 7 24 9