Неэкспоненциальное решение проблемы лабиринта?
https://stackoverflow.com/questions/535859
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая многоглавый ациклический граф размером n*n, в котором каждый узел имеет не более трех дочерних элементов и трех родительских узлов, существует ли неэкспоненциальный алгоритм, позволяющий определить, существует ли путь длиной n, в котором нет двух узлов, имеющих одинаковое значение, и все учитывается стоимость комплекта?
По сути, у меня есть лабиринт n*n, где каждое пространство имеет случайное значение (1..n).Мне нужно найти путь (сверху вниз) из n узлов, включающий каждое значение.
Сейчас я использую поиск в глубину, но это T(n) = 3T(n-1) + O(1), который O(3^n), неидеальное решение.
Я был бы очень признателен, если бы подтвердил мои опасения или указал мне правильное направление.
Редактировать:Чтобы сделать это немного более конкретным, вот лабиринт с решениями (решаемый с использованием решения в глубину).
1 2 5 5 4 1 5 1 3 5 4 1 2 3 2 5 5 4 4 3 4 2 1 2 4 S3, 5, 1, 3, 4, 2, F4 S3, 5, 1, 3, 4, 2, F2 S3, 5, 1, 3, 4, 2, F4 S3, 5, 3, 2, 4, 1, F3 S3, 5, 3, 2, 4, 1, F3 S3, 5, 3, 2, 4, 1, F3 S4, 5, 3, 2, 4, 1, F3 S4, 5, 3, 2, 4, 1, F3 S4, 5, 3, 2, 4, 1, F3 S4, 5, 1, 3, 4, 2, F4 S4, 5, 1, 3, 4, 2, F2 S4, 5, 1, 3, 4, 2, F4 S5, 4, 3, 2, 5, 1, F3 13 total paths`
Решение
Эта задача является NP-полной, поэтому неизвестно, существует ли решение за полиномиальное время.(Стандартные условия о том, что на практике это может быть легко, и т. д., все применимо.) Одно из возможных сокращений — от 3SAT.
Предположим, у нас есть экземпляр 3SAT, такой как (a ∨ b ∨ c) ∧ (¬a ∨ ¬b ∨ ¬c).Я покажу, как использовать «гаджеты» для создания примера вашей проблемы.Прежде чем мы начнем, перепишем задачу 3SAT как (a1 ∨ b1 ∨ c1) ∧ (¬a2 ∨ ¬b2 ∨ ¬c2) вместе с a1 = a2, b1 = b2 и c1 = c2;то есть сделать каждое вхождение переменной уникальным, но затем добавить условие, согласно которому разные вхождения одной и той же переменной должны быть равны.
Во-первых, мы убеждаемся, что вы должны выбрать число 0 в первой строке, чтобы мы могли использовать его позже в качестве «стража», которого вам следует избегать.
0 0 0
Теперь мы создадим гаджет, который реализует правило a1 = a2:(Подчеркивание _ вот новый уникальный номер при каждом использовании этого гаджета)
0 _ 0
a1 0 ¬a1
a2 0 ¬a2
Из-за первой строки вам следует избегать нулей.Это означает, что вы выбираете либо путь «a1, a2», либо путь «¬a1, ¬a2»;первый будет соответствовать (немного сбивчиво) установке значения false, а второй будет соответствовать установке значения true.Это потому, что наш гаджет предложения действительно прост, потому что мы просто записываем предложение, например.(снова _ вот новая переменная каждый раз):
0 _ 0
a1 b1 b2
или
0 _ 0
¬a1 ¬b1 ¬b2
Наконец, поскольку вы использовали только один из a1, ¬a1 и т. д., мы позволяем вам свободно использовать те, которые вы не использовали:
0 _ 0
a1 ¬a1 0
Это не совсем работает, потому что один из a1 и ¬a1 мог использоваться в гаджете выбора переменной, а другой — в предложении.Итак, мы включаем новую переменную @i для каждого предложения, которое вы можете взять вместо одной из переменных.Итак, если в пункте 1 появляется переменная a1, мы имеем
0 _ 0
a1 ¬a1 @1
Вот полный вывод перевода исходного предложения 3SAT (выделен путь, соответствующий установке a и b в true, c в false и выбору a из первого предложения), с цифрами слева и пояснением справа.Гаджеты переупорядочиваются (сначала гаджеты предложения, затем для каждой переменной гаджет равенства и затем неиспользуемый гаджет), но это не имеет значения, поскольку они в любом случае независимы.
0 0 < 0 . . < .
0 8 < 0 . _ < .
2 < 4 6 a1 < b1 c1
0 16 < 0 . _ .
11 13 15 < -a2 -b2 -c2<
0 17 < 0 . _ < .
2 0 3 < a1 . -a1<
10 0 11 < a2 . -a2<
0 18 < 0 . _ < .
2 3 1 < a1 -a1 @1 <
0 19 < 0 . _ .
10 < 11 9 a2 < -a2 @2
0 20 < 0 . _ < .
4 0 5 < b1 . -b1<
12 0 13 < b2 . -b2<
0 21 < 0 . _ < .
4 < 5 1 b1 < -b1 @1
0 22 < 0 . _ < .
12 < 13 9 b2 < -b2 @2
0 23 < 0 . _ < .
6 < 0 7 c1 < . -c1
14 < 0 15 c2 < . -c2
0 24 < 0 . _ < .
6 7 < 1 c1 -c1< @1
0 25 < 0 . _ < .
14 15 9 < c2 -c2 @2 <
(Если вы хотите, чтобы все было квадратным, просто добавьте несколько нулей в конце каждой строки.) Забавно видеть, что независимо от того, как вы это решаете, в глубине души вы решаете проблему 3SAT.
В конце моего поста приведена наспех написанная программа на Perl, которая генерирует одну из ваших проблем при вводе формы
a b c
-a -b -c
Количество переменных в результирующем экземпляре вашей проблемы равно 11C + V + 1.Дайте программе -r переключитесь на отображение блеска вместо цифр.
# Set useful output defaults
$, = "\t"; $\ = "\n";
# Process readability option and force sentinel
my $r = "0";
if( $ARGV[0] =~ /-r/ ) { shift; $r = "."; }
print $r, $r, $r;
# Clause gadgets
my( %v, %c, $m, $c );
$m = 1;
while( <> ) {
my( @v, @m );
$c = $m++;
chomp; @v = split;
for my $v ( @v ) {
push @{$v{strip($v)}}, -1; # hack, argh!
push @m, ($r ? $v.@{$v{strip($v)}} : $m + neg($v));
$c{($r ? (strip($v).@{$v{strip($v)}}) : $m)} = $c;
$v{strip($v)}->[-1] = ($r ? (strip($v).@{$v{strip($v)}}) : $m);
$m += 2 unless $r;
}
print $r, newv(), $r;
print @m;
}
# Variable gadget
for my $v ( sort keys %v ) {
# Force equal
print $r, newv(), $r;
for my $n ( @{$v{$v}} ) {
print $n, $r, ($r ? "-".$n : $n+1);
}
# Unused
for my $n ( @{$v{$v}} ) {
print $r, newv(), $r;
print $n, ($r ? "-".$n : $n+1), ($r ? "\@".$c{$n} : $c{$n});
}
}
# Strip leading -
sub strip {
my( $v ) = @_;
return substr $v, neg($v);
}
# Is this variable negative?
sub neg {
my( $v ) = @_;
return "-" eq substr( $v, 0, 1 );
}
# New, unused variable
sub newv {
return "_" if $r;
return $m++;
}
Другие советы
Я почти уверен, что это можно сделать за полиномиальное время.Я бы начал с пустого набора, а затем перебирал строки сверху вниз.Я собираюсь пропустить любой код и показать вам, как будет выглядеть состояние на каждом этапе, и оттуда вы сможете составить алгоритм.Я почти уверен, что лучший случай немного хуже, чем O (n ^ 2), используя вариант поиска в ширину и отслеживая текущие хорошие пути в таблице.
РЕДАКТИРОВАТЬ: Если это все еще недостаточно быстро, вы можете улучшить его, применив Оптимизация Арлекина.
Например:
1 2 3
3 2 1
1 2 1
Состояние 0:R = 0 // row p = {} // sett
// {{Path so far}, Column}
P' = {
{{1}, 0}
{{2}, 1}
{{3}, 2}
}
P = P'
Состояние 1:R = 1 // row p = {{{1}, 0} {{2}, 1} {{3}, 2}}}
P' = {
{{1 3}, 0}
{{1 2}, 1}
{{2 3}, 0}
{{2 1}, 2}
{{3 2}, 1}
{{3 1}, 2}
}
Состояние 2:R = 2 p = {{{1 3}, 0} {{1 2}, 1} {{2 3}, 0} {{2 1}, 2} {{3 2}, 1} {{3 1 }, 2}}
P' = {
{{1 3 2}, 1}
{{2 3 1}, 0}
{{3 2 1}, 0}
{{3 2 1}, 2}
{{3 1 2}, 1}
}
Результат:
Количество путей:5
С1 1 3 2 Ф2
С2 2 3 1 Ф1
С3 3 2 1 Ф1
С3 3 2 1 Ф3
С3 3 1 2 Ф2
Вы можете попробовать оптимизация колонии муравьев.Он быстро дает очень хорошие результаты, очень близкие к идеальному решению.
Одна оптимизация для Решение Кевина Лони может заключаться в объединении частичных путей, содержащих одни и те же элементы в одном столбце.Вам нужно будет записать количество слияний с путем, если вы хотите узнать количество решений в конце.
Пример:В вашем примере 5x5, когда вы достигаете третьей строки, третий столбец имеет три пути, ведущие к нему, которые содержат (1 2 5) в некотором порядке.С этого момента вам не обязательно следить за ними отдельно, но вы можете объединить их.Если вы хотите узнать количество решений в конце, вам просто нужно настроить структуру данных вашего пути, например.три (1 (1 2 5)) сольются в (3 (1 2 5)).
Найдите поиск A*.Это твой друг.
