| CIS 730 Introduction to Artificial Intelligence
| Kansas State University
| Fall 2001
| http://www.kddresearch.org/Courses/Fall-2001/CIS730
|
| Machine Problem 1 of 3
| Example 3 of 3: UGLY
|
| "Muddle-earth": randomly-generated example
| Mon 10 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.)
|
| 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: Lothlorien (17)
17
| Goal nodes: Druadan (5), Erebor (8), Laketown (16)
5 8 16
| Adjacency matrix with costs
*	72	40	64	58	35	72	49	70	116	106	78	29	60	96	53	99	52	122	103	81	107	94	89	30	87	31	35	96	43
93	*	72	30	32	110	43	110	57	72	102	60	97	37	121	97	51	58	94	38	80	46	73	87	62	26	63	44	73	94
51	74	*	115	76	36	92	26	122	34	54	101	72	121	55	92	60	100	78	29	64	37	37	59	37	84	68	56	92	53
36	95	88	*	87	85	49	72	80	113	55	111	101	115	46	48	102	49	104	81	81	44	63	30	104	39	66	80	55	98
83	114	89	106	*	125	70	113	99	82	118	80	109	37	85	118	34	76	76	31	87	64	110	38	49	94	28	115	82	50
71	65	45	59	43	*	47	71	87	30	55	60	124	27	29	84	73	110	48	52	71	61	37	59	51	41	107	46	122	25
86	76	47	38	77	115	*	84	42	76	30	54	117	98	47	95	98	107	88	53	99	96	60	93	66	39	102	102	39	86
40	71	116	64	120	64	38	*	79	63	31	79	116	117	60	51	89	55	60	49	48	122	119	111	100	95	123	52	27	63
56	92	124	71	75	53	106	80	*	125	120	47	91	44	52	57	72	43	40	114	96	71	34	117	79	115	86	89	98	31
73	75	84	48	71	56	37	110	75	*	36	57	97	102	108	79	107	45	38	34	95	109	63	69	81	75	48	103	70	47
111	73	93	74	41	66	102	55	64	111	*	117	79	65	123	61	110	64	69	60	125	46	118	106	83	99	87	52	103	59
40	59	121	112	68	103	42	121	89	84	72	*	57	67	108	44	36	104	28	39	108	31	110	105	56	103	95	55	110	114
40	81	84	74	56	30	49	115	114	77	71	90	*	108	120	37	76	43	90	31	121	74	45	68	26	75	91	58	100	54
56	35	115	48	73	58	42	45	55	77	47	108	111	*	91	123	70	36	113	51	88	61	60	104	91	114	88	113	27	74
53	70	101	108	33	46	39	100	36	28	61	75	107	113	*	63	45	73	42	88	76	100	49	33	66	66	106	75	31	27
64	71	86	80	47	25	107	58	112	105	63	57	99	31	47	*	78	29	52	100	87	49	103	52	123	41	102	62	79	105
82	27	37	104	92	32	39	113	121	90	52	121	42	110	69	95	*	81	104	70	53	122	51	110	29	35	107	42	42	109
95	110	43	50	77	*	72	62	*	105	56	28	50	53	27	35	*	*	85	81	54	45	88	35	36	96	41	59	57	100
83	86	35	35	111	33	78	84	109	108	118	124	30	54	82	115	36	78	*	84	120	64	122	59	32	40	64	63	57	109
64	66	104	36	58	90	72	39	96	59	36	34	41	38	33	89	123	39	117	*	108	26	72	114	69	54	68	39	46	68
84	97	46	93	28	80	118	34	50	89	89	114	41	110	96	92	54	110	102	101	*	110	115	75	29	117	32	27	87	79
34	105	33	95	112	61	66	33	58	29	66	113	73	83	36	51	42	117	30	115	76	*	115	78	99	35	52	88	103	27
80	113	117	111	36	116	97	46	118	81	58	71	102	103	34	92	114	55	79	38	107	115	*	67	47	102	75	50	36	99
104	60	32	112	82	93	73	45	26	56	122	100	82	63	27	60	50	123	98	30	46	103	112	*	25	101	92	77	43	125
95	69	88	32	107	58	46	35	102	106	54	98	46	119	71	100	25	118	75	121	49	88	66	72	*	26	65	100	89	80
31	101	108	80	71	92	45	116	73	36	76	41	99	103	77	119	95	40	59	52	63	94	86	86	121	*	92	112	73	114
66	101	104	73	111	107	46	105	87	68	87	96	71	115	70	32	119	26	115	42	44	74	100	83	48	98	*	28	103	36
42	35	123	61	28	105	85	96	40	103	120	81	39	34	34	39	95	97	109	40	110	47	30	38	72	120	94	*	77	27
79	112	72	57	49	45	87	43	81	73	105	106	83	56	107	68	87	122	30	105	124	47	69	35	45	43	54	68	*	121
123	32	52	115	121	95	53	60	118	44	92	74	41	62	52	120	95	91	87	100	46	46	73	26	103	93	35	44	49	*
| Randomly-generated (trivially admissible) heuristic
22
10
15
9
25
0
12
19
0
8
11
19
21
2
15
7
0
22
10
15
10
7
9
19
6
22
4
7
24
9