Trabalho de Inteligência Artificial Busca não informada

Alunos:

• Jaziel Loureiro
• Josafá Dieb
• Samuel Jonas

Universidade Federal do Ceará - Campus Russas

Dimacs challenge

9th DIMACS Implementation Challenge - Shortest Paths

Shortest path problems are ones of the most fundamental combinatorial optimization problems
with many applications, both direct and as subroutines in other combinatorial optimization algorithms.
Algorithms for these problems have been studied since 1950's and still remain an active area of research.

Applying this one in Artificial Intelligence context using agent

Goal-based agent

Some constraints assumptions for the environment:

1. Static
2. Fully Observable
3. Discrete
4. Deterministic

Problem formulation

The agent need to have knowledge to perform the problem and must looks like:

1. Initial condition
2. Actions description (generate conditions)
   • Condition Successor function
   • Operators conjunct
3. The goal test
4. Cost function
5. Seach enveironment between conditions
6. Path
7. Optimal solution
8. Seach tree

Misinformed seach

1. Breadth first
2. Depth first
3. Uniform cost
4. Limited depth first
5. Interative depth first

RELATÓRIO

Questão 1: A Heurística Haversine é admissível? Não, ela é muito lenta para calcular

Questão 2: Se não é admissível, como você faria para torná-la admissível ou com resultados melhores? Ainda seria melhor que a heurística “terra plana”? Para deixar ela admissível, teria que ver uma forma de torná-la mais rápida. Mas ainda sim, dificilmente seria melhor q a terra plana, pq ela só eleva dois elementos ao quadrado e depois faz uma raiz quadrada, são poucas operações, e são executadas muito rápido

Contexto de execução:

Título	Descrição
Amostragem	Estados Unidos da América
Estrutura de Dados	Grafos
Memória compartilhada	1232981872 Bytes

Pontos de execução

Execução	P1	P2
1	21283431	11725592
2	14421968	17073296
3	2373091	4425274
4	12971632	148141
5	8914756	21174630
6	13754049	22260038
7	7925357	13279025
8	8350061	7430140
9	18171901	14205190
10	1196745	3724983
11	4071068	9833905
12	7038099	7020721
13	9069228	4782645
14	20102311	18748148
15	8137871	21255533
16	4956933	5473955
17	16811359	19378900
18	22547250	3014685
19	23804173	19349116
20	10940407	16549163
21	16576398	747108
22	14861853	554408
23	14026133	7042149
24	7984547	16028268
25	21247338	16958873
26	3583486	9148641
27	2845430	10621584
28	16169361	19692240
29	15404228	12324324
30	22270622	23542098
31	17410091	3280207
32	12846287	18051685
33	22659106	19223771
34	21066369	6346167
35	14625539	15837010
36	22895329	15032172
37	16584118	21587417
38	23364161	14440485
39	4682218	7401360
40	14298987	1982208
41	8190468	17882472
42	11130848	18813479
43	12334290	11130443
44	22335953	11568752
45	7285002	20659227
46	18941085	747745
47	7769668	15617606
48	2629664	14259009
49	10894030	7526267
50	20605175	9349803

Números de execuções	50
Total - memória usada (Bytes)	24336180704
Total - Nós expandidos (Inteiro)	1479901126
Total - Fator de Ramifição (Porcentagem)	241,159991
Total - Tempo de Execução (Segundos)	6875,932077
Media dos resultados
Média - Memória usada (Bytes)	486723614,1
Média - Nós expandidos (Inteiro)	29598022,52
Média - Fator de Ramificação (Porcentagem)	4,82319982
Média - Tempo de execução (Segundos)	137,5186415

Resultados execuções

Memória adicional

Memória Adicional	n 1	n 2	n 3	n 4	n 5	n 6	n 7	n 8	n 9	n 10	n 11	n 12	n 13	n 14	n 15	n 16	n 17	n 18	n 19	n 20	n 21	n 22	n 23	n 24	n 25	n 26	n 27	n 28	n 29	n 30	n 31	n 32	n 33	n 34	n 35	n 36	n 37	n 38	n 39	n 40	n 41	n 42	n 43	n 44	n 45	n 46	n 47	n 48	n 49	n 50
BFS	48064336	48049328	48056448	48104832	48098816	48057456	48074272	48083584	48066624	48066272	48053360	1343376	48064656	48105584	48072928	48047888	48046448	48074704	48087888	48105664	48093808	48040688	48049008	48064864	48086960	48107616	48053360	319472	48085504	48074592	48069520	48070736	48048448	48054752	2311424	48078160	48096144	48082656	48053360	48080608	31693872	48058816	48091136	48095616	48096032	48044240	48100352	48057888	37024352	48122912
DFS	53092752	52138112	52093392	54966464	53294032	54109392	53381120	53983472	54090384	15129696	54095216	54350848	4485008	53342400	54111552	54104960	54593696	23316768	53146160	53178848	54129680	54637808	54751792	53367984	53107120	53130240	54099216	53638128	53562800	53106624	7264528	30888496	49906112	49934240	8975904	54355184	54135664	54364960	54104176	53112672	54751584	53323712	52592336	53328064	53767104	54148736	54481408	52141984	53182048	52455408
Busca Uniforme	224900320	258418352	79329296	196628240	71445760	248607680	265146208	72254080	130484688	162606112	244579456	2275376	204681120	147478928	243059968	254337440	126651280	169570800	263473472	363062064	383015408	333260864	150442016	204556640	255063120	321564064	289372688	462480	277666608	252616496	45120624	344497088	308718736	102459072	2204784	340670336	53615952	314841920	273188912	78358288	35603360	167260304	253097376	261556272	106085232	341782576	153394592	95136336	29924352	230653856
A* Haversine	225756608	257731936	79232384	198014576	70778288	248108816	264471808	71599152	131340880	161447008	245817360	2172256	204735296	146112480	242258096	254069872	126783728	168806400	262512848	361932512	383096608	333944064	151726464	203389600	256473536	321390912	289565968	457920	275654672	254000928	45238944	344296496	306624544	102218144	2114000	340407760	53033600	313245104	273140752	77514272	35297776	167145056	253019184	263836960	104742784	342103744	152968448	94766064	29214640	231471856
A* Euclidean	54072752	11901440	3745152	32515056	3179440	22216000	29481360	2040352	18224752	18534944	46772688	343088	50411376	8086560	29058736	60859584	37664048	31479920	36857744	8034736	20902272	73015056	5677648	45224880	30976560	860752	84866784	82192	23139088	66568304	12636304	74560688	77576672	15208096	487072	27158848	8105424	3594688	75478736	3349104	10094000	13134432	61501536	47600096	14511312	92535648	7783760	34964464	1957232	38058000

Nós expandidos

Nós Expandidos	n 1	n 2	n 3	n 4	n 5	n 6	n 7	n 8	n 9	n 10	n 11	n 12	n 13	n 14	n 15	n 16	n 17	n 18	n 19	n 20	n 21	n 22	n 23	n 24	n 25	n 26	n 27	n 28	n 29	n 30	n 31	n 32	n 33	n 34	n 35	n 36	n 37	n 38	n 39	n 40	n 41	n 42	n 43	n 44	n 45	n 46	n 47	n 48	n 49	n 50
BFS	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	83107	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	19635	3000000	3000000	3000000	3000000	3000000	3000000	143691	3000000	3000000	3000000	3000000	3000000	1978560	3000000	3000000	3000000	3000000	3000000	3000000	3000000	2309282	3000000
DFS	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	874432	3000000	3000000	250029	3000000	3000000	3000000	3000000	1297892	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	397146	1761967	3000000	2822767	466782	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000	3000000
Busca Uniforme	14052367	16148733	4956694	12285374	4461693	15535240	16568769	4512963	8152542	10158778	15282934	141358	12789974	9213206	15189039	15893765	7913685	10595732	16465131	22689815	23938084	20827766	9400275	12781456	15937571	20095355	18084487	28651	17351713	15784300	2818679	21528941	19292023	6400413	137185	21290386	3348045	19675729	17071911	4894716	2224430	10449861	15816380	16344646	6626440	21360524	9582162	5944340	1867924	14413240
A* Haversine	14105253	16105101	4950367	12371324	4418711	15503397	16525793	4471775	8205609	10085495	15359734	134757	12793011	9127177	15138797	15876743	7921768	10547504	16404800	22618501	23943370	20870228	9480244	12707978	16025155	20083274	18096531	28299	17225611	15870415	2825618	21515911	19160386	6384923	131395	21273831	3311126	19575593	17068980	4841212	2205252	10442078	15811245	16486455	6542088	21380444	9554832	5920969	1823030	14463867
A* Euclidean	3375628	735407	231552	2028169	195695	1378735	1837161	125043	1133207	1155752	2916034	21104	3147507	501673	1803744	3799790	2350286	1965201	2298223	495863	1297175	4553714	347726	2822401	1927991	46774	5298568	4990	1443914	4155488	788528	4654852	4839111	947429	29785	1693684	504895	221788	4713426	206874	627249	817398	3838141	2967524	905016	5768581	482619	2181729	120821	2374041

Fator de ramificação

Fator de ramificação	n 1	n 2	n 3	n 4	n 5	n 6	n 7	n 8	n 9	n 10	n 11	n 12	n 13	n 14	n 15	n 16	n 17	n 18	n 19	n 20	n 21	n 22	n 23	n 24	n 25	n 26	n 27	n 28	n 29	n 30	n 31	n 32	n 33	n 34	n 35	n 36	n 37	n 38	n 39	n 40	n 41	n 42	n 43	n 44	n 45	n 46	n 47	n 48	n 49	n 50
BFS	1,001340	1,001027	1,001175	1,002183	1,002058	1,001196	1,001547	1,001741	1,001387	1,001380	1,001111	1,010252	1,001346	1,002199	1,001519	1,000997	1,000967	1,001556	1,001830	1,002201	1,001954	1,000847	1,001020	1,001351	1,001811	1,002241	1,001111	1,016807	1,001781	1,001553	1,001448	1,001473	1,001009	1,001140	1,005366	1,001628	1,002002	1,001721	1,001111	1,001679	1,001165	1,001225	1,001898	1,001991	1,002000	1,000921	1,002090	1,001205	1,002052	1,002560
DFS	1,106098	1,086210	1,085278	1,145134	1,110292	1,127278	1,112106	1,124655	1,126882	1,081392	1,126983	1,132309	1,121114	1,111299	1,127323	1,127186	1,137368	1,122818	1,107211	1,107892	1,127701	1,138287	1,140662	1,111832	1,106398	1,106879	1,127066	1,117460	1,115891	1,106387	1,143234	1,095667	1,039710	1,105613	1,201829	1,132399	1,127826	1,132603	1,127170	1,106513	1,140657	1,110910	1,095673	1,111001	1,120147	1,128098	1,135029	1,086291	1,107959	1,092820
Busca Uniforme	1,000278	1,000149	1,000280	1,000317	1,000822	1,000176	1,000173	1,000646	1,000337	1,000404	1,000215	1,006027	1,000203	1,000459	1,000145	1,000146	1,000255	1,000230	1,000119	1,000069	1,000016	1,000050	1,000250	1,000261	1,000243	1,000119	1,000072	1,008830	1,000141	1,000268	1,000482	1,000099	1,000150	1,000512	1,004468	1,000071	1,000881	1,000096	1,000140	1,000547	1,000350	1,000374	1,000139	1,000160	1,000586	1,000041	1,000522	1,000283	1,001256	1,000182
A* Haversine	1,000321	1,000195	1,000335	1,000371	1,001116	1,000220	1,000224	1,000709	1,000389	1,000490	1,000251	1,007480	1,000230	1,000532	1,000154	1,000165	1,000279	1,000274	1,000137	1,000101	1,000007	1,000061	1,000280	1,000305	1,000277	1,000182	1,000074	1,011308	1,000163	1,000292	1,000642	1,000122	1,000190	1,000581	1,005548	1,000078	1,001049	1,000114	1,000136	1,000708	1,000389	1,000430	1,000155	1,000203	1,000663	1,000049	1,000596	1,000322	1,001582	1,000216
A* Euclidean	1,001161	1,011466	1,010879	1,001983	1,015427	1,007082	1,002952	1,019817	1,005153	1,002320	1,002489	1,016016	1,001018	1,007447	1,006889	1,001035	1,001581	1,001167	1,002343	1,012719	1,007105	1,002136	1,020493	1,001471	1,004172	1,150126	1,001058	1,029259	1,001578	1,001210	1,001573	1,001115	1,001949	1,003247	1,022025	1,002210	1,003353	1,012981	1,000847	1,011814	1,005779	1,004286	1,001486	1,002521	1,002144	1,002582	1,008008	1,001627	1,012456	1,001930

Tempo de execução em segundos

Tempo de execução	n 1	n 2	n 3	n 4	n 5	n 6	n 7	n 8	n 9	n 10	n 11	n 12	n 13	n 14	n 15	n 16	n 17	n 18	n 19	n 20	n 21	n 22	n 23	n 24	n 25	n 26	n 27	n 28	n 29	n 30	n 31	n 32	n 33	n 34	n 35	n 36	n 37	n 38	n 39	n 40	n 41	n 42	n 43	n 44	n 45	n 46	n 47	n 48	n 49	n 50
BFS	35,346387	38,680668	29,158770	41,995386	33,091054	28,126427	31,775379	39,860274	28,882634	31,143556	20,265701	0,191463	27,595740	36,495700	37,950949	27,940490	28,786656	32,995986	33,908644	49,869263	40,521136	19,786748	20,834759	28,307375	33,350180	40,747113	22,330399	0,013416	41,837915	30,226988	32,718371	30,065714	16,522397	25,706010	0,348042	44,642856	51,120226	32,253515	19,531634	30,400738	8,259092	31,386236	33,002353	35,870950	50,232784	29,622606	57,779279	37,154297	25,986166	42,837047
DFS	0,380662	0,263056	0,227153	0,301187	0,228302	0,228740	0,236150	0,225011	0,223899	0,064222	0,232466	0,230539	0,019074	0,225526	0,226006	0,224730	0,227249	0,097320	0,354943	0,228900	0,230794	0,226520	0,227950	0,223036	0,223393	0,222556	0,226178	0,225802	0,225707	0,223234	0,030731	0,131237	0,276086	0,221731	0,051974	0,312038	0,224337	0,231871	0,222922	0,223427	0,245526	0,223312	0,220911	0,223474	0,222946	0,223361	0,229712	0,226277	0,222203	0,223596
Busca Uniforme	73,337459	62,213085	7,790890	66,345734	16,979340	66,381883	84,172163	15,097190	30,398428	45,436829	63,471837	0,098458	37,241804	50,079387	67,777689	80,081653	20,856416	37,465713	81,251426	136,525694	86,204096	60,474681	28,563811	57,479316	69,481011	100,705847	70,943742	0,007070	86,392324	69,572921	3,772627	100,293817	53,851262	18,964624	0,077857	132,306758	12,188647	104,246769	68,575504	13,700189	2,153000	52,059342	59,852471	76,471971	31,592133	68,844389	76,149122	11,839742	4,976682	56,516796
A* Haversine	81,540200	71,725138	12,819319	73,596256	17,828229	66,287532	80,092352	17,311339	31,575771	50,305154	65,035429	0,237770	45,218835	50,314058	58,595454	67,795921	24,634990	41,705296	84,504649	132,147713	92,807850	68,545252	27,799285	59,099323	74,498781	101,916164	77,150412	0,038659	95,313797	75,868785	6,674761	104,890737	63,044157	25,753917	0,224961	147,939946	13,169467	109,364287	74,099045	18,005468	3,985576	54,173041	63,141347	80,788248	31,801638	70,952126	72,936691	16,709906	6,313300	66,254378
A* Euclidean	18,441727	1,476973	0,219468	7,779295	0,544477	6,846018	12,128999	0,046397	2,927195	3,231507	7,913481	0,006962	10,298177	2,349613	13,846312	16,037754	9,341539	5,244641	12,220087	0,586176	2,882559	22,547680	0,477730	12,649447	12,593708	0,012886	26,984434	0,001241	3,691705	20,849523	1,070432	28,440226	26,818398	3,233372	0,014995	6,463015	0,794401	0,207177	20,437382	0,315167	1,454797	3,035298	18,752343	17,986377	2,159469	48,195459	1,905767	6,471926	0,136338	4,179183