[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Survival Mode

It is currently Mon Aug 21, 2017 11:42 pm Advanced search

Survival Mode

Share and discuss ideas for your entries here.

Re: Survival Mode

Postby DjinnKahn » Wed Mar 03, 2010 7:21 pm

DjinnKahn
Lieutenant
 
Posts: 18
Joined: Wed Feb 17, 2010 11:32 pm

Re: Survival Mode

Postby Fritzlein » Wed Mar 03, 2010 8:34 pm

Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Survival Mode

Postby DjinnKahn » Wed Mar 03, 2010 8:57 pm

Oh, I see. I thought you just wanted a proof that longest path is NP-hard. Going directly from 3SAT is a nice challenge : )

Using only 3 chambers isn't a big problem, since cheating only allows you to use 2 chambers.
DjinnKahn
Lieutenant
 
Posts: 18
Joined: Wed Feb 17, 2010 11:32 pm

Re: Survival Mode

Postby Fritzlein » Wed Mar 03, 2010 9:45 pm

Fritzlein
Colonel
 
Posts: 81
Joined: Thu Feb 18, 2010 9:20 pm

Re: Survival Mode

Postby barxool » Wed Mar 03, 2010 10:25 pm

barxool
Lieutenant
 
Posts: 13
Joined: Wed Feb 10, 2010 9:22 pm

Re: Survival Mode

Postby barxool » Wed Mar 03, 2010 10:26 pm

barxool
Lieutenant
 
Posts: 13
Joined: Wed Feb 10, 2010 9:22 pm

Re: Survival Mode

Postby Hippo » Thu Mar 04, 2010 10:20 am

Hmm, I didn't notice I was last on page 4 and discussion continued on page 5 ... I am used to edit last post instead of autoreplaying ... so look at the version on the bottom of page 4 where the authors of the original proof (HC on graph with small degree vertices) was located :)

BTW: Plesnik proof allows undirecting by adding vertex on outdegree 1 to indegree 1 edges. And if you want cubic graph (all vertices of degree exactly 3) you can add a square with diagonal instead of just one vertex there. So Plesnik's proof is much easier than the original one ([3]).

BTW2: An alternative ... my last step of Tron proof used "fractal corridors as edges" to make all edges (or at least these that are not forced ... (meaninig out deg 2 in deg 2)) same length (forced ones could be longer but not shorter). It would lead probably to simillar scaling as creating big chambers. My resulting map would be graph on grid with maximal degree 3.

P.S.: The book name was probably "Grafové algorítmy" ... Graph algorithms, not Graph Theory I have supposed.
Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Re: Survival Mode

Postby barxool » Thu Mar 11, 2010 12:14 pm

The proof in the .pdf files is about a hamiltonian cycle, but in tron we are interested in an hamiltonian path only.
Moreover it looks like the proof assumes a cubic graphe, and a tron map is not a cubic graph.

If someone has understand Fritzlein's proof, can you post the full map for the following 3SAT expression: (A or B or ~C) and (~A or C or D) ?
that would be great.
barxool
Lieutenant
 
Posts: 13
Joined: Wed Feb 10, 2010 9:22 pm

Re: Survival Mode

Postby Hippo » Fri Mar 12, 2010 7:47 pm

If you know an edge which must be on HC, you can split the edge in the middle adding two dead ends. Or in directed graph you can split a vertex to two veritces one with indegree 0 the other with outdegree 0.

The argument would be more complicated in undirected graphs with all vertices having degree more than 2. There is a construction which trasforms undirected HC to directed as well as the other way. So I would probably use this side step.

The graph is of degrees less than 4 while grid has degree 4 in each vertex. Adding walls you can reduce degrees. You can replace edges by corridors (paths of degree 2 verices) ...
Hippo
Lieutenant-Colonel
 
Posts: 49
Joined: Wed Mar 03, 2010 6:42 pm

Previous

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron