Как замедлить пьяницу по дороге домой

15

Рассмотрим квадрат сетки n на n, который выглядит следующим образом.

график сетки

Важно отметить, что этот график 11 на 11 .

В любой момент человек стоит на перекрестке, и он движется только вертикально или горизонтально только на один шаг за раз до следующего перекрестка. К сожалению, он выпил немного слишком много, поэтому он выбирает направление, в котором он движется случайным образом, из 4 возможных направлений (вверх, вниз, влево, вправо). Это до 4, как будто он стоит у стены, у него есть только 3 варианта, а в углу у него только 2.

Он начинает в левом нижнем углу, и его цель - добраться до дома, который находится в верхнем правом углу. Время - это просто количество шагов, которое ему требуется.

Тем не менее, вы злой противник, который хочет, чтобы он вернулся домой как можно медленнее. Вы можете удалить любое количество ребер из графика в любой момент во время его ходьбы. Единственное ограничение заключается в том, что вы всегда должны оставить ему какой-то путь домой, и вы не можете удалить ребро, которое он уже использовал.

Задача состоит в том, чтобы придумать как можно более злобного противника и затем протестировать его на графике 100 на 100 на 20 на 20 со случайным пьяным ходоком. Ваша оценка - это просто среднее время, которое требуется случайному ходячему, чтобы добраться домой за 10 1000 пробежек.

Вы можете использовать любой язык и библиотеки, которые вам нравятся, если они свободно доступны и легко устанавливаются в Linux.

Что мне нужно реализовать?

Вы должны реализовать код для случайного обходчика, а также для злоумышленника, и код должен быть скомбинирован так, чтобы результат при запуске был просто средним значением 1000 прогонов с использованием вашего кода противника. Случайный код Уокера должен быть очень простым для написания, поскольку он просто выбирает из (x-1, y), (x + 1, y), (x, y-1) и (x, y + 1), убедившись, что ни один из них не был удален или находится вне диапазона.

Код противника, конечно, сложнее, и ему также необходимо помнить, какие грани пьяница уже преодолел, чтобы он не пытался удалить ни одну из них, и чтобы убедиться, что для пьяницы все еще есть путь домой, что немного сложнее. делать быстро.

Addendum 10 пробегов на самом деле недостаточно, но я не хотел наказывать людей, которым удалось действительно долго гулять. Я теперь увеличил его до 1000 из-за популярного запроса. Однако, если ваша прогулка настолько длинная, что вы не можете выполнить 1000 пробежек за реалистичное время, просто укажите максимальное количество пробежек, которое вы можете.

Таблица рекордов 100 на 100.

  • 976124,754 от оптимизатора.
  • 103000363.218 Питера Тейлора.

Изменить 1. Изменен размер графика до 20 на 20, чтобы помочь время выполнения тестов людей. Я сделаю новый высокий балл за этот размер по мере того, как люди отправляют результаты.

Таблица рекордов 20 на 20.

230,794.38 (100k runs) by justhalf
227,934 by Sparr 
213,000 (approx) by Peter Taylor
199,094.3 by stokastic
188,000 (approx) by James_pic
 64,281 by Geobits
code-challenge graph-theory
источник
2
Я не понимаю; Вы не можете просто удалить все ребра в начале, кроме тех, которые образуют самый длинный путь?
Питер Олсон
3
Я не вижу никаких правил, показывающих, что пьяница не может дважды пройти один и тот же край дважды. Если он может дважды пройти один и тот же путь между двумя точками и выбрать случайные повороты, то логически не является ли граф с самым длинным средним (случайным) обходом тем, у которого больше всего ребер? То есть не будет ли оптимальный (самый длинный) граф без удаленных ребер?
Миллинон
3
Я не фанат того, чтобы каждый вход заново изобретал колесо (ходок). Если кто-то опубликует тестовый жгут / каркас, тогда я опишу его и буду его использовать.
Спарр
1
Преимущество удаления части пути, чтобы заставить его вернуться, чтобы пройти длинный путь, полностью теряется, когда его путь случайный; предположительно, в равной степени вероятно, что он повернет назад в какой-то момент, не требуя, чтобы вы убрали острие. Я хотел бы увидеть некоторые тестовые данные, показывающие среднее время без удаленных ребер, а затем с некоторыми удаленными ребрами, как вы, кажется, предлагаете. Что касается этой проблемы, я думаю, что было бы гораздо интереснее, если бы путь пьяницы был детерминированным.
Миллинон
3
10 раундов недостаточно. Даже при статическом лабиринте 10х10, не говоря уже об умном противнике и лабиринте 100х100, стандартное отклонение составляет около 50% от среднего случая. Я бегу 10000 раундов, и я все еще не считаю результаты достойными сравнения.
Спарр

Ответы:

10

230 794,38 на 20х20, 100 000 пробежек

Последнее обновление: я наконец-то создал идеальное динамическое решение с двумя путями. Я сказал «отлично», так как предыдущая версия на самом деле не симметрична, было проще получить более длинный путь, если пьяница прошел один путь над другим. Текущий симметричен, поэтому он может получить большее ожидаемое количество шагов. Похоже, что после нескольких испытаний он составляет около 230 тыс., По сравнению с предыдущим, около 228 тыс. Но, говоря статистически, эти цифры все еще находятся в пределах их огромного отклонения, поэтому я не утверждаю, что это значительно лучше, но я считаю, что это должно быть лучше, чем в предыдущей версии.

Код находится внизу этого поста. Он обновлен так, что он намного быстрее, чем предыдущая версия, завершая 1000 запусков за 23 секунды.

Ниже приведен пример запуска и образца лабиринта:

Идеальный ходок
Средний: 230794,384
Макс .: 1514506
Min: 25860
Завершено в 2317.374 годах
 _ _ _ _ _ _ _ _ _ _ _ _. 
| | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | _ | | _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | _ | | _ | | _ | | _ | | _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ | | _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Предыдущие представления

Наконец-то я могу сравниться с результатом Спарра! = D

Основываясь на моих предыдущих экспериментах (см. Нижнюю часть этого поста), лучшая стратегия состоит в том, чтобы иметь двойной путь и закрывать один, когда пьяница достигает любого из них, и переменная зависит от того, насколько хорошо мы можем динамически предсказать, куда пойдет пьяница. увеличьте шанс его попадания на более длинный путь.

Поэтому, основываясь на своей DOUBLE_PATHстратегии, я построил еще одну, которая меняет лабиринт (мой DOUBLE_PATHлабиринт легко изменялся) в зависимости от движения пьяницы. Поскольку он выбирает путь с более чем одним доступным вариантом, я закрою пути, чтобы оставить только два возможных варианта (один, из которого он пришел, другой - неисследованный).

Это звучит похоже на то, чего достиг Спарр, как показывает результат. Разница с ним слишком мала, чтобы его можно было считать лучше, но я бы сказал, что мой подход более динамичен, чем у него, поскольку мой лабиринт более изменчив, чем Спарр =)

Результат с образцом конечного лабиринта:

EXTREME_DOUBLE_PATH
Средний балл: 228034,89
Макс .: 1050816
Min: 34170
Завершено в 396.728 с
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Секция экспериментов

Лучшей оказывается та же стратегия, что и в Stokastic, я горжусь экспериментированием с использованием различных стратегий и выводом хороших результатов :)

Каждый из печатных лабиринтов ниже является последним лабиринтом после того, как пьяница добрался до дома, поэтому они могут немного отличаться от бега к бегу из-за случайности в движении пьяницы и динамичности противника.

Я опишу каждую стратегию:

Единый путь

Это самый простой подход, который создаст единый путь от входа до выхода.

SINGLE_PATH
Среднее: 162621,612
Макс .: 956694
Min: 14838
Завершено в 149.430
 _ _ _ _ _ _ _ _ _ _
| | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Остров (уровень 0)

Это подход, который пытается поймать пьяницу на почти изолированном острове. Не работает так, как я ожидал, но это одна из моих первых идей, поэтому я включил ее.

Есть два пути, ведущие к выходу, и когда пьяница приближается к одному из них, противник закрывает его, заставляя его найти другой выход (и, возможно, снова попадает в ловушку на острове)

ОСТРОВ
Средний: 74626,070
Макс .: 428560
Min: 1528
Завершено в 122.512
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Двойной путь

Это наиболее обсуждаемая стратегия, которая состоит в том, чтобы иметь два пути равной длины к выходу и закрыть один из них, когда пьяница приближается к одному из них.

DOUBLE_PATH
Средний балл: 197743,472
Макс .: 1443406
Min: 21516
Завершено в 308,177 годах
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Остров (уровень 1)

Вдохновленные множеством путей острова и большим количеством пешеходных дорожек в одном пути, мы соединяем остров с выходом и делаем лабиринт по одному пути на острове, создавая в общей сложности три пути для выхода и, как и в предыдущем случае, закрываем любой из выход, как пьяница приближается.

Это работает немного лучше, чем чистый единственный путь, но все еще не побеждает двойной путь.

ОСТРОВ
Средний: 166265,132
Макс .: 1162966
Min: 19544
Завершено в 471,982 годах
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ | _
| | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |  
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Остров (уровень 2)

Пытаясь расширить предыдущую идею, я создал вложенный остров, создав в общей сложности пять путей, но, похоже, он работает не так хорошо.

ОСТРОВ
Среднее: 164222,712
Макс: 927608
Min: 22024
Завершено в 793,591 годах
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ | _ |  
| | | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Остров (уровень 3)

Заметив, что двойной путь на самом деле работает лучше, чем один путь, давайте сделаем остров двойным путем!

Результатом является улучшение по сравнению с островом (уровень 1), но оно по-прежнему не преодолевает двойной путь.

Для сравнения, результат для двойной траектории размером с остров составляет в среднем 131 134,42 хода. Так что это добавляет довольно значительное количество ходов (около 40 тыс.), Но этого недостаточно, чтобы пройти двойной путь.

ОСТРОВ
Средний: 171730,090
Макс: 769080
Min: 29760
Завершено в 587.646 годах
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Остров (уровень 4)

Опять же, экспериментируя с вложенным островом, и снова это не так хорошо работает.

ОСТРОВ
Средний: 149723.068
Макс: 622106
Min: 25752
Завершено в 830.889 годах
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |  
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Вывод

В общем, это доказывает, что лучше всего иметь один длинный путь от текущей позиции пьяницы до выхода, что достигается стратегией двойного пути, поскольку после закрытия выхода пьяница должна пройти максимально возможное расстояние, чтобы добраться до выход.

Это также намекает на то, что базовой стратегией должен быть двойной путь, и мы можем только изменить то, как динамически создаются пути, что было сделано Sparr. Поэтому я верю, что его стратегия - это путь!

Код

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {

    enum Strategy{
        SINGLE_PATH,
        ISLAND,
        DOUBLE_PATH,
        EXTREME_DOUBLE_PATH,
        PERFECT_DOUBLE_PATH,
    }

    int width,height;
    int x,y; //walker's position
    int dX,dY; //destination
    Point[][] points;
    int stepCount = 0;

    public static void main(String[]args){
        int side = 20;
//      runOnce(side, Strategy.EXTREME_DOUBLE_PATH, 0);
        runOnce(side, Strategy.PERFECT_DOUBLE_PATH, 0);
//      for(Strategy strategy: Strategy.values()){
//          runOnce(side, strategy, 0);
//      }
//      runOnce(side, Strategy.ISLAND, 1);
//      runOnce(side, Strategy.ISLAND, 2);
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      while(scanner.hasNext()){
//          side = scanner.nextInt();
//          Strategy strategy = Strategy.valueOf(scanner.next());
//          int level = scanner.nextInt();
//          scanner.nextLine();
//          runOnce(side, strategy, level);
//          System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      }
//      scanner.close();
    }

    private static Walker runOnce(int side, Strategy strategy, int level) {
        Walker walker = null;
        long total = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        double count = 1000;
        long start = System.currentTimeMillis();
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, strategy, level, false);
            total += walker.stepCount;
            max = Math.max(walker.stepCount, max);
            min = Math.min(walker.stepCount, min);
//          System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("%s\nAverage: %.3f\nMax: %d\nMin:%d\n",strategy, total/count, max, min);
        System.out.printf("Completed in %.3fs\n", (System.currentTimeMillis()-start)/1000.0);
        walker.printPath();
        return walker;
    }

    private void createIsland(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY+1; i<topRightY; i++){
            if(i>botLeftY+1) deletePath(points[botLeftX][i].right());
            if(i<topRightY-1) deletePath(points[topRightX][i].left());
        }
        for(int i=botLeftX+1; i<topRightX; i++){
            if(i>botLeftX+1) deletePath(points[i][botLeftY].up());
            if(i<topRightX-1) deletePath(points[i][topRightY].down());
        }
    }

    private void createSinglePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==0){
                for(int j=botLeftX; j<topRightX; j++){
                    if(j==topRightX-1 && (j-botLeftX)%2==0){
                        deletePath(points[topRightX][topRightY].down());
                    } else {
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    }
                }
            } else {
                for(int j=botLeftX+(i-botLeftY)%2; j<topRightX+((i-botLeftY)%2); j++){
                    deletePath(points[j][i].up());
                }
            }
        }
    }

    private void createDoublePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i>botLeftY && (width%4!=1 || i<topRightY-1)) deletePath(points[width/2-1][i].right());
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==1){
                for(int j=botLeftX; j<topRightX; j++){
                    if((j-botLeftX)%2==0 || j<topRightX-1){
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    } else {
                        deletePath(points[topRightX-1][topRightY-1].right());
                    }
                }
            } else {
                if((i-botLeftY)%2==0){
                    for(int j=botLeftX+1; j<topRightX; j++){
                        deletePath(points[j][i].up());
                    }
                } else {
                    for(int j=botLeftX; j<topRightX+1; j++){
                        if(j!=width/2 && j!=width/2-1){
                            deletePath(points[j][i].up());
                        }
                    }
                }
            }
        }
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, Strategy strategy, int level, boolean animate){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        points = new Point[width][height];
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                points[x][y] = new Point(x,y);
            }
        }
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(x<width-1) new Edge(points[x][y], points[x+1][y]);
                if(y<height-1) new Edge(points[x][y], points[x][y+1]);
            }
        }

        if(strategy == Strategy.SINGLE_PATH) createSinglePath(0,0,width-1,height-1);

        if(strategy == Strategy.DOUBLE_PATH) createDoublePath(0,0,width-1,height-1);

        List<EdgeList> edgeLists = new ArrayList<EdgeList>();
        if(strategy == Strategy.ISLAND){
            List<Edge> edges = new ArrayList<Edge>();
            if(level==0){
                createIsland(0,0,width-1,height-1);
                deletePath(points[width-2][height-2].right());
                deletePath(points[width-2][height-2].up());
            } else {
                for(int i=0; i<level; i++){
                    createIsland(i,i,width-1-i, height-1-i);
                }
                createDoublePath(level,level,width-1-level,height-1-level);
                for(int i=height-1; i>=height-level; i--){
                    edges.add(points[i-2][i].right());
                    edges.add(points[i][i-2].up());
                    edgeLists.add(new EdgeList(points[i-1][i].right(), points[i][i-1].up()));
                }
            }
            edges.add(points[width-1-level][height-1-level].down());
            edges.add(points[width-1-level][height-1-level].left());
            edgeLists.add(new EdgeList(edges.toArray(new Edge[0])));
        }

        int[] availableVerticals = new int[height];
        if(strategy == Strategy.EXTREME_DOUBLE_PATH){
            for(int i=1; i<width-1; i++){
                deletePath(points[i][0].up());
            }
            availableVerticals[0] = 2;
            for(int i=1; i<height; i++){
                availableVerticals[i] = width;
            }
        }

        boolean[][] available = new boolean[width][height];
        if(strategy == Strategy.PERFECT_DOUBLE_PATH){
            for(int x=0; x<width; x++){
                for(int y=0; y<height; y++){
                    if(x%2==1 && y%2==1){
                        available[x][y] = true;
                    } else {
                        available[x][y] = false;
                    }
                }
            }
        }
//      printPath();
        while(!walk()){
            if(animate)try{Thread.sleep(500);}catch(InterruptedException e){}
            if(strategy == Strategy.ISLAND){
                if(x==y && (x==1 || (x>=2 && x<=level))){
                    if(!hasBeenWalked(points[x][x].down())){
                        deletePath(points[x][x].down());
                    } else if(!hasBeenWalked(points[x][x].left())){
                        deletePath(points[x][x].left());
                    }
                }
            }
            if(strategy == Strategy.EXTREME_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(untravelled>1){
                    if(cur.up()!=null && availableVerticals[y]>2 && !cur.up().walked){
                        deletePath(cur.up());
                        availableVerticals[y]--;
                    }
                    if(cur.down()!=null && !cur.down().walked){
                        deletePath(cur.down());
                        availableVerticals[y-1]--;
                    }
                    if(cur.up()!=null && cur.left()!=null && !cur.left().walked){
                        deletePath(cur.left());
                        deletePath(points[x][y+1].left());
                    }
                    if(cur.up()!=null && cur.right()!=null && !cur.right().walked){
                        deletePath(cur.right());
                        if(y<height-1) deletePath(points[x][y+1].right());
                    }
                }
            }
            if(strategy == Strategy.PERFECT_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(x%2!=1 || y%2!=1){
                    if(untravelled>1){
                        if(cur.down()==null && hasBeenWalked(cur.right())){
                            if(canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.down()==null && hasBeenWalked(cur.left())){
                            if(x%2==0 && y%2==1 && canBeDeleted(cur.right())) deletePath(cur.right());
                            else if(cur.right()!=null && canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.up())){
                            if(canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.down())){
                            if(x%2==1 && y%2==0 && canBeDeleted(cur.up())) deletePath(cur.up());
                            else if (cur.up()!=null && canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                    }
                } else {
                    if(!hasBeenWalked(cur.left())){
                        if(x>1 && available[x-2][y]){
                            if(untravelled>1){
                                available[x-2][y] = false;
                                deletePath(cur.up());
                            }
                        } else if(cur.up()!=null){
                            if(canBeDeleted(cur.left())) deletePath(cur.left());
                            if(canBeDeleted(points[x][y+1].left())) deletePath(points[x][y+1].left());
                        }
                    }
                    if(!hasBeenWalked(cur.down())){
                        if(y>1 && available[x][y-2]){
                            if(untravelled>1){
                                available[x][y-2] = false;
                                deletePath(cur.right());
                            }
                        } else if(cur.right()!=null){
                            if(canBeDeleted(cur.down())) deletePath(cur.down());
                            if(canBeDeleted(points[x+1][y].down())) deletePath(points[x+1][y].down());
                        }
                    }
                }
            }
            if(strategy == Strategy.DOUBLE_PATH || strategy == Strategy.EXTREME_DOUBLE_PATH
                    || strategy == Strategy.PERFECT_DOUBLE_PATH){
                if(x==width-2 && y==height-1 && points[width-1][height-1].down()!=null){
                    deletePath(points[width-1][height-1].left());
                }
                if(x==width-1 && y==height-2 && points[width-1][height-1].left()!=null){
                    deletePath(points[width-1][height-1].down());
                }
            } else if(strategy == Strategy.ISLAND){
                for(EdgeList edgeList: edgeLists){
                    boolean deleted = false;
                    for(Edge edge: edgeList.edges){
                        if(edge.start.x == x && edge.start.y == y){
                            if(!hasBeenWalked(edge)){
                                deletePath(edge);
                                edgeList.edges.remove(edge);
                                if(edgeList.edges.size() == 1){
                                    edgeLists.remove(edgeList);
                                }
                                deleted = true;
                                break;
                            }
                        }
                    }
                    if(deleted) break;
                }
            }
            if(animate)printPath();
        }
    }

    public boolean hasBeenWalked(Edge edge){
        if(edge == null) return false;
        return edge.walked;
    }

    public boolean canBeDeleted(Edge edge){
        if(edge == null) return false;
        return !edge.walked;
    }

    public List<Edge> getAdjacentUntravelledEdges(){
        List<Edge> result = new ArrayList<Edge>();
        for(Edge edge: points[x][y].edges){
            if(edge!=null && !hasBeenWalked(edge)) result.add(edge); 
        }
        return result;
    }

    public void printPath(){
        StringBuilder builder = new StringBuilder();
        for(int y=height-1; y>=0; y--){
            for(int x=0; x<width; x++){
                Point point = points[x][y];
                if(this.x==x && this.y==y){
                    if(point.up()!=null) builder.append('?');
                    else builder.append('.');
                } else {
                    if(point.up()!=null) builder.append('|');
                    else builder.append(' ');
                }
                if(point.right()!=null) builder.append('_');
                else builder.append(' ');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
    }

    public boolean walk(){
        ArrayList<Edge> possibleMoves = new ArrayList<Edge>();
        Point cur = points[x][y];
        for(Edge edge: cur.edges){
            if(edge!=null) possibleMoves.add(edge);
        }
        int random = (int)(Math.random()*possibleMoves.size());
        Edge move = possibleMoves.get(random);
        move.walked = true;
        if(move.start == cur){
            x = move.end.x;
            y = move.end.y;
        } else {
            x = move.start.x;
            y = move.start.y;
        }
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(points[x][y]);
        reachable.add(points[x][y]);
        while(next.size()>0){
            Point cur = next.poll();
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(cur.up()!=null) neighbors.add(cur.up().end);
            if(cur.right()!=null) neighbors.add(cur.right().end);
            if(cur.down()!=null) neighbors.add(cur.down().start);
            if(cur.left()!=null) neighbors.add(cur.left().start);
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor == points[dX][dY]) return true;
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean deletePath(Edge toDelete){
        if(toDelete == null) return true;
//      if(toDelete.walked){
//          System.err.println("Edge already travelled!");
//          return false;
//      }
        int startIdx = toDelete.getStartIdx();
        int endIdx = toDelete.getEndIdx();
        toDelete.start.edges[startIdx] = null;
        toDelete.end.edges[endIdx] = null;
//      if(!isSolvable()){
//          toDelete.start.edges[startIdx] = toDelete;
//          toDelete.end.edges[endIdx] = toDelete;
//          System.err.println("Invalid deletion!");
//          return false;
//      }
        return true;
    }

    static class EdgeList{
        List<Edge> edges;

        public EdgeList(Edge... edges){
            this.edges = new ArrayList<Edge>();
            this.edges.addAll(Arrays.asList(edges));
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;
        boolean walked;

        public Edge(Point start, Point end){
            walked = false;
            this.start = start;
            this.end = end;
            this.start.edges[getStartIdx()] = this;
            this.end.edges[getEndIdx()] = this;
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        public Edge(int x1, int y1, int x2, int y2){
            this(new Point(x1,y1), new Point(x2,y2));
        }

        public boolean exists(){
            return start.edges[getStartIdx()] != null || end.edges[getEndIdx()] != null;
        }

        public int getStartIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 0;
                else return 2;
            } else {
                if(start.x < end.x) return 1;
                else return 3;
            }
        }

        public int getEndIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 2;
                else return 0;
            } else {
                if(start.x < end.x) return 3;
                else return 1;
            }
        }

        public boolean isVertical(){
            return start.x==end.x;
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        Edge[] edges;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
            edges = new Edge[4];
        }

        public Edge up(){ return edges[0]; }
        public Edge right(){ return edges[1]; }
        public Edge down(){ return edges[2]; }
        public Edge left(){ return edges[3]; }

        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}
justhalf
источник
Это очень впечатляет. Как долго длится бег? Если победные записи останутся так близко, нам придется увеличить количество прогонов, чтобы посмотреть, сможем ли мы их разделить.
1
Сроки уже включены во фрагмент. Около 400 на 1000 трасс. Это включает проверку разрешимости при каждом удалении пути. Я могу удалить это, чтобы иметь около 170 с на 1000 пробежек. Таким образом, я могу сделать 20 тысяч пробежек за час.
Половина
На самом деле дальнейшая оптимизация позволила бы мне запустить 100k за 3,5 часа.
Половина
Мой счет с 100 000 пробежек и занял 10 минут. @justhalf очень хорош в более гибком двухстороннем лабиринте. Я знаю, как сделать еще лучше, но у меня нет терпения, чтобы реализовать это прямо сейчас.
Спарр
2
Рад видеть, что реализовано симметричное решение. У меня есть еще одна идея улучшить это решение, и на этот раз я думаю, что смогу реализовать его сам :)
Sparr
10

227934 (20х20)

Моя третья попытка Использует тот же общий подход, что и @stokastic с двумя путями к выходу. Когда ходок достигает конца одного пути, он закрывается, требуя, чтобы он вернулся, чтобы добраться до конца другого пути, чтобы выйти. Мое улучшение состоит в том, чтобы генерировать пути по мере продвижения ходящего, так что какой бы путь он ни продвинулся дальше в первой половине процесса, он оказался бы длиннее, чем другой путь.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 8:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'?';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'*';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                maze[r][c]=0;
            }
        }
        maze[1][1]=9;
        maze[1][2]=1;
        maze[2][1]=1;
        maze[1][3]=8;
        maze[3][1]=8;
        int progress_l = 0;
        int progress_r = 0;
        int side = 0;
        int closed_exit = 0;
        x=0;
        y=0;
        if (DEBUG) print_maze();
        long long turn = 0;
        int in = 0;
        while (x!=X-1||y!=Y-1) {
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int dx=0, dy=0;
            if (DEBUG) {
                std::cin>>in;
                switch(in) {
                    case 0:
                        dy=-1; dx=0; break;
                    case 1:
                        dy=0; dx=1; break;
                    case 2:
                        dy=1; dx=0; break;
                    case 3:
                        dy=0; dx=-1; break;
                    default:
                        dy=0; dx=0; break;
                }
            } else {
                int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
                int exit_choice = -1;
                do {
                    if (rand()%exits == 0) {
                        exit_choice = exits;
                        break;
                    } else {
                        exits--;
                    }
                }while(exits);

                --exits;

                if (maze[r-1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = -1;
                        dx = 0;
                    }
                }
                if (maze[r][c+1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = 1;
                    }
                }
                if (maze[r+1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 1;
                        dx = 0;
                    }
                }
                if (maze[r][c-1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = -1;
                    }
                }
            }

            x+=dx;
            y+=dy;

            if(x==X-1 && y==Y-1) continue;

            if (x==0&&y==1) side=-1;
            if (x==1&&y==0) side=1;
            if (maze[y*2+1][x*2+1]==8) { // room needs another exit, maybe
                if (side==-1) { // left half of maze
                    if (y==1) { // top of a column
                        if (x%2) { // going up, turn right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // going right, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-1) { // bottom of a column
                        if (x%2 && x<(X-progress_r-3)) { // going right, turn up if there's room
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                            progress_l=x+1;
                        } else { // going down or exiting, go right
                            if (x!=X-2 or closed_exit==1) {
                                maze[y*2+1][x*2+2]=1;
                                maze[y*2+1][x*2+3]=8;
                            } else {
                                closed_exit = -1;
                            }
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }
                } else { // right half of maze
                    if (y==0) { // top row
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-2) { // heading right to the exit
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            if (x!=X-1 or closed_exit==-1) {
                                maze[y*2+2][x*2+1]=1;
                                maze[y*2+3][x*2+1]=8;
                            } else {
                                closed_exit = 1;
                            }
                        }
                    } else if (y==Y-3) { // bottom of a column
                        if (x>progress_l+1) { // do we have room for another column?
                            if (!(x%2)&&y>1) { // going left, turn up
                                maze[y*2+0][x*2+1]=1;
                                maze[y*2-1][x*2+1]=8;
                            } else { // going down, turn left
                                maze[y*2+1][x*2+0]=1;
                                maze[y*2+1][x*2-1]=8;
                                progress_r=X-x-1;
                            }
                        } else { // abort, move down to escape row
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==1) { // top of a column
                        if (!(x%2)) { // going up, turn left
                            maze[y*2+1][x*2+0]=1;
                            maze[y*2+1][x*2-1]=8;
                        } else { // going left, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }

                }
                maze[y*2+1][x*2+1]=9;
            }

            if (DEBUG) print_maze();
        }
        // print_maze();
        printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    printf("%d rounds in a %d*%d maze\n",ROUNDS,X,Y);
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

вывод (со временем):

...
turns:194750
turns:506468
turns:129684
turns:200712
turns:158664
turns:156550
turns:311440
turns:137900
turns:86948
turns:107134
turns:81806
turns:310274
100000 rounds in a 20*20 maze
average:     227934
stddev:      138349
real    10m54.797s
...

Пример моего лабиринта, примерно равной длины, равной половине пути, показывающей левый / нижний путь, отрезанный от выхода (внизу справа):

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 |  _   _   _   _   _   _   _   _   _  |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | |_| |_| |_| |_| |_|
 | | | | | | | | | |_ _ _ _ _ _ _ _ _ _
 |_| |_| |_| |_| |_ _ _ _ _ _ _ _ _ _  !

PS: я знаю об очень незначительном улучшении этого алгоритма, который требует более умного кода, чтобы генерировать различную форму для двух путей, лестниц вместо последовательных зигзагов высоты.

Sparr
источник
Цвет меня впечатлил. У вас есть мой голос, сэр!
Stokastic
1
Это довольно впечатляюще. Помните, когда мы просто рисовали на лицах пьяниц?
Деннис
Довольно сложно различить ваш график, возможно, вы можете изменить его печать на что-то похожее на мое?
Половина
1
@justhalf Ваше желание - моя команда
Спарр
1
@justhalf Я вытянул его на бумаге. Просто нужно написать логику. Если я не сделаю это через пару дней, я дам тебе эскиз? :)
Спарр
6

135 488 307,9 для 98х98

199094,3 для 20x20

Я реализовал решение, которое создает два пути к финишу и закрывает ровно один из них, как только пьяница достигает его. Это имитирует длину пути, которая, по крайней мере, будет в 1,5 раза больше длины одного пути от начала до конца. После 27 пробежек я набрал в среднем около 135 миллионов. К сожалению, это занимает несколько минут на прогулку, поэтому мне придется запустить его в течение следующих нескольких часов. Одно предостережение - мой генератор двойного пути работает только в том случае, если размер графика находится в форме 4 * n + 2, что означает, что самое близкое к 100 значение, которое я могу получить, это 102 или 98. Я собираюсь опубликовать результаты, используя 98, что, как я ожидаю, все еще превосходить метод зигзагообразного пути. Я буду работать над лучшей системой маршрутизации позже. В настоящее время выводит результаты в виде (numSteps, currentAverage) после каждой прогулки.

РЕДАКТИРОВАТЬ: исправлено, поэтому код теперь работает с размерами графа, кратными 2, а не 4 * n + 2.

Код: (добавьте аргумент 'True' в конструктор ходунка в строке 187 для рисования графика черепахой).

import random
import turtle

WIDTH  = 20
HEIGHT = 20
L, U, R, D = 1, 2, 4, 8

def delEdge(grid, x1, y1, x2, y2):

    # check that coordinates are in-bounds
    if not (0 <= x1 < WIDTH):  return False
    if not (0 <= y1 < HEIGHT): return False
    if not (0 <= x2 < WIDTH):  return False
    if not (0 <= y2 < HEIGHT): return False

    # swap order such that x1 <= x2 and y1 <= y2
    if x2 < x1:
        x2 ^= x1
        x1 ^= x2
        x2 ^= x1
    if x2 < x1: print "Swap failure: {}, {}".format(x1, x2)

    if y2 < y1:
        y2 ^= y1
        y1 ^= y2
        y2 ^= y1
    if y2 < y1: print "Swap failure: {}, {}".format(y1, y2)

    # check that only one of the deltas is = 1
    dx = x2 - x1
    dy = y2 - y1

    if dx and dy:       return False
    if not (dx or dy):  return False
    if dx > 1:          return False
    if dy > 1:          return False

    #print "<{}, {}>, <{}, {}>".format(x1, y1, x2, y2)

    if dx > 0:
        try: grid[x1][y1].remove(R)
        except: pass
        try: grid[x2][y2].remove(L)
        except: pass
    if dy > 0:
        try: grid[x1][y1].remove(D)
        except: pass
        try: grid[x2][y2].remove(U)
        except: pass

    return True

def newGrid():

    grid = [[[] for y in xrange(HEIGHT)] for x in xrange(WIDTH)]

    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            if x > 0:
                grid[x][y].append(L)
            if x < WIDTH-1:
                grid[x][y].append(R)
            if y > 0:
                grid[x][y].append(U)
            if y < HEIGHT-1:
                grid[x][y].append(D)

    return grid

class walker:

    def __init__(self, grid, mode, draw=False):
        self.x  = 0
        self.y  = 0
        self.dx = WIDTH-1
        self.dy = HEIGHT-1

        self.grid     = grid
        self.mode     = mode
        self.draw     = draw
        self.numSteps = 0

        self.initGrid()

    def initGrid(self):
        if self.mode == 0:
            #pass
            if self.draw: drawGrid(grid)

        elif self.mode == 1:

            for y in xrange(HEIGHT-1):
                if y % 2 == 0:
                    for x in xrange(WIDTH - 1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(1, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            if self.draw: drawGrid(grid)

        elif self.mode == 2:
            for y in xrange(HEIGHT/2):
                if y % 2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(2, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(HEIGHT/2, HEIGHT-1):
                if y%2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(0, WIDTH-2):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(1, HEIGHT-1):
                midpoint = HEIGHT/2
                if HEIGHT % 4 == 0: 
                    midpoint = HEIGHT/2 + 1
                if y < midpoint:
                    delEdge(grid, 0, y, 1, y)
                else:
                    delEdge(grid, WIDTH-1, y, WIDTH-2, y)
            if self.draw: drawGrid(grid)

    def walk(self):
        self.numSteps += 1
        choices = grid[self.x][self.y]
        direction = random.choice(choices)
        #print (self.x, self.y), grid[self.x][self.y], direction
        if direction   == L: self.x -= 1
        elif direction == U: self.y -= 1
        elif direction == R: self.x += 1
        elif direction == D: self.y += 1

    def main(self):
        hasBlocked = False
        while (self.x, self.y) != (self.dx, self.dy):
            #print (self.x, self.y), (self.dx, self.dy)
            self.walk()
            if self.mode == 2:
                if not hasBlocked:
                    if (self.x, self.y) == (WIDTH-2, HEIGHT-1):
                        delEdge(self.grid, WIDTH-2, HEIGHT-1, WIDTH-1, HEIGHT-1)
                        hasBlocked = True
                    elif (self.x, self.y) == (WIDTH-1, HEIGHT-2):
                        delEdge(self.grid, WIDTH-1, HEIGHT-1, WIDTH-1, HEIGHT-2)
                        hasBlocked = True

        return self.numSteps

def drawGrid(grid):
    size = 3
    turtle.speed(0)
    turtle.delay(0)
    turtle.ht()
    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            dirs = grid[x][y]
            for dir in dirs:
                if dir == L:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x-1)*4, y*4))
                elif dir == R:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x+1)*4, y*4))
                elif dir == U:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y-1)*4))
                elif dir == D:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y+1)*4))
    turtle.mainloop()

numTrials  = 100
totalSteps = 0.0
i = 0
try:
    while i < numTrials:
        grid = newGrid()

        w = walker(grid, 2)
        steps = w.main()
        totalSteps += steps
        print steps, totalSteps/(i+1)
        i += 1

    print totalSteps / numTrials

except KeyboardInterrupt:
    print totalSteps / i

Необработанные данные: (текущий numSteps, скользящее среднее)

358796490 358796490.0
49310430 204053460.0
106969130 171692016.667
71781702 146714438.0
49349086 127241367.6
40874636 112846912.333
487607888 166384194.571
56423642 152639125.5
71077302 143576700.667
101885368 139407567.4
74423642 133499937.818
265170542 144472488.167
59524778 137938048.923
86919630 134293876.143
122462528 133505119.6
69262650 129489965.25
85525556 126903823.529
161165512 128807250.667
263965384 135920836.632
128907594 135570174.5
89535930 133378067.619
97344576 131740181.636
98772132 130306788.174
140769524 130742735.5
198274280 133443997.28
95417374 131981434.846
226667006 135488307.852
stokastic
источник
Я уменьшил размер графика до 20 на 20, чтобы ускорить время выполнения. Я надеюсь, что это помогает.
Вы в настоящее время выигрываете :)
Ваш 20 на 20 баллов за 1000 пробежек?
@Lembik да, это так.
стокастик
1
@Dennis au contraire :)
Спарр
6

Подход с 4 путями, 213 КБ

Односторонний подход

Прямая линия от S до E

и набирает в среднем N^2.

Двухсторонний подход

Цикл с S и E напротив друг друга

но затем в первый раз, когда пьяница оказывается в пределах досягаемости от конечной точки, его режут:

Петля обрезается, чтобы дать изогнутую линию от S до E

Это оценка в среднем (N/2)^2 + N^2.

Подход с четырьмя путями использует два сокращения:

Вложенные петли, соединенные в две вилки, по обе стороны от E Отрежьте одну из вилок на стороне E С другой стороны, отрежьте вилку на стороне не-E. Это оставляет один запутанный путь

Предположим, что длина внешнего цикла равна длине xNвнутреннего цикла (1-x)N. Для простоты я приведу в норму N=1.

От начала до первого среза баллы в среднем составляют (x/2)^2. От первого реза до второго реза имеет два варианта длины xи 1-x; это дает в среднем (1-x)x^2 + x(1-x)^2 = x-x^2. Наконец оставшийся путь дает 1. Таким образом, общий счет N^2 (1 + x - 3/4 x^2).

Первоначально я предполагал, что сохранение доступных путей одинаковой длины на каждом шаге будет оптимальным, поэтому мой первоначальный подход x = 1/2основывался на оценке 1.3125 N^2. Но после проведенного выше анализа выясняется, что оптимальное разделение дается, когда x = 2/3с оценкой 1.3333 N^2.

1000 walks with average 210505.738 in 202753ms


1000 walks with average 212704.626 in 205191ms

с кодом

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
public class RandomWalker {
    private static final int SIZE = 19;
    private static final Point dest = new Point(SIZE, SIZE);

    private final Random rnd = new Random();
    private Point p = new Point(0, 0);
    private int step = 0;
    private Set<Set<Point>> edges;
    private Map<Set<Point>, String> cuttableEdgeNames;
    private Set<String> cutSequences;
    private String cutSequence = "";

    public static void main(String[] args) {
        long start = System.nanoTime();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            RandomWalker rw = new RandomWalker();
            total += rw.walk();
            walks++;
        }

        long timeTaken = System.nanoTime() - start;
        System.out.println(walks + " walks with average " + total / (double)walks + " in " + (timeTaken / 1000000) + "ms");
    }

    RandomWalker() {
        loadMaze(
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+-+-+",
            "| | | | | | | | | | | | |             |",
            "+ + + + + + + + + + + + + +-+ +-+ +-+ +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+-+ + + + + + +",
            "| | | | | | | | | | | |     | | | | | |",
            "+ + + + + + + + + + + + +-+ + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "|                     | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | d",
            "+ + + + + + + + + + + + + + +-+ +-+ +c+",
            "| | | | | | | | | | | | | |           |",
            "+ + + + + + + + + + + + + +-+-+-+-+-+ +",
            "| | | | | | | | | | | | |           f b",
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+e+a+"
        );
        cutSequences = new HashSet<String>();
        cutSequences.add("ac");
        cutSequences.add("ad");
        cutSequences.add("be");
        cutSequences.add("bf");
    }

    private void loadMaze(String... row) {
        edges = new HashSet<Set<Point>>();
        cuttableEdgeNames = new HashMap<Set<Point>, String>();

        // Horizontal edges
        for (int y = 0; y <= SIZE; y++) {
            for (int x0 = 0; x0 < SIZE; x0++) {
                char ch = row[y * 2].charAt(x0 * 2 + 1);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x0, y));
                edge.add(new Point(x0 + 1, y));
                edges.add(edge);
                if (ch != '-') cuttableEdgeNames.put(edge, "" + ch);
            }
        }

        // Vertical edges
        for (int y0 = 0; y0 < SIZE; y0++) {
            for (int x = 0; x <= SIZE; x++) {
                char ch = row[y0 * 2 + 1].charAt(x * 2);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x, y0));
                edge.add(new Point(x, y0 + 1));
                edges.add(edge);
                if (ch != '|') cuttableEdgeNames.put(edge, "" + ch);
            }
        }
    }

    int walk() {
        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        Set<Point> edge = new HashSet<Point>();
        edge.add(p1);
        edge.add(p2);

        // Is it cuttable?
        String id = cuttableEdgeNames.get(edge);
        if (id != null) {
            String prefix = cutSequence + id;
            for (String seq : cutSequences) {
                if (seq.startsWith(prefix)) {
                    // Cut it
                    cutSequence = prefix;
                    edges.remove(edge);
                    return false;
                }
            }
        }

        return edges.contains(edge);
    }
}
Питер Тейлор
источник
Ах, я вижу, поэтому мой подход к острову не работает, я не уравновешивал длину пути. Просто чтобы прояснить мое понимание, длина от fк до cв вашем коде примерно N/2, через e(и d) или нет, верно?
Половина
Какова длина пути YE N вместо длины N / 2?
Спарр
@ просто так, да. Есть 400 вершин, так что есть 401 ребра (после одного разреза граф является гамильтоновым циклом); два внешних пути имеют по 100 ребер каждый, и поэтому внутренний цикл составляет 101 ребро.
Питер Тейлор
понял. два наблюдения: а) большие лабиринты выиграют от более 2 ^ n путей. б) если вы сделаете свой путь длины динамики, вы будете бить нынешних лидеров с динамическими решениями два-пути (себя и @justhalf)
Sparr
@Sparr: это N^2не так 2^N. И да, создание этой динамики сделает ее лучшей, проблема в том, как сделать ее динамичной, сохраняя при этом свойство с четырьмя путями. @PeterTaylor: красивые картинки!
Половина
5

Я экспериментировал с разрезанием сетки почти целиком по всем kстрокам. Это эффективно превращает его в нечто похожее на случайное блуждание kпо N * N/kсетке. Самый эффективный вариант - разрезать каждый ряд так, чтобы мы заставили пьяницу зигзагообразно.

Для случая 20x20 ( SIZE=19) у меня есть

time java RandomWalker 
1000 walks with average 148577.604

real    0m14.076s
user    0m13.713s
sys     0m0.360s

с кодом

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
// This handles a simpler problem where the grid is mutilated before the drunkard starts to walk.
public class RandomWalker {
    private static final int SIZE = 19;
    private final Random rnd = new Random();

    public static void main(String[] args) {
        RandomWalker rw = new RandomWalker();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            total += rw.walk();
            walks++;
        }

        System.out.println(walks + " walks with average " + total / (double)walks);
    }

    int walk() {
        Point dest = new Point(SIZE, SIZE);
        Point p = new Point(0, 0);
        int step = 0;

        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        return p1.x != p2.x || p1.x == SIZE * (Math.max(p1.y, p2.y) & 1);
    }
}
Питер Тейлор
источник
Правильно ли я считаю, что удаление всех ребер происходит до того, как начнется прогулка в вашем решении?
@Lembik, да. Я думал, что комментарий в верхней части прояснит это.
Питер Тейлор
Это так, спасибо. Интересно, сколько вы можете изменить, удалив края во время прогулки?
Из любопытства, сколько времени это займет, чтобы бежать (в целом и за пробег)?
Stokastic
@stokastic, около 3 секунд на пробег.
Питер Тейлор
3

Для тех, кто не хочет изобретать велосипед

Не волнуйся! Я изобрету это для тебя :)

Это на Java, кстати.

Я создал класс Уокера, который занимается случайной ходьбой. Он также включает в себя полезный метод определения того, является ли ход действительным (если он уже пройден).

Я предполагаю, что все вы, умные люди, можете найти случайные числа для конструктора, я оставил это на ваше усмотрение, чтобы вы могли проверить определенные случаи. Кроме того, просто вызовите функцию walk (), чтобы (как вы уже догадались!) Совершить прогулку пьяницы (случайным образом).

Я реализую функцию canComeHome () в другой раз. Желательно после того, как я найду лучший способ сделать это.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {
    int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    int dX,dY; //destination
    TreeSet<Edge> pathsNoLongerAvailable = new TreeSet<Edge>();
    TreeSet<Edge> previouslyTraveled = new TreeSet<Edge>();
    int stepCount = 0;

    public static void main(String[]args){
        int side = 10;
        Walker walker = null;
        int total = 0;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        while(!walk()){
            // Do something
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = (int)(Math.random()*possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge){
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}
Стрейч маньяк
источник
Это содержит некоторые ошибки и несоответствия. previouslyTraveled.add(new int[]{x,y,move[0],move[1]})должно быть x+move[0]и y+move[1]. Width-1И Height-1, и неэффективность проверки удалённых путей. Я отредактировал ваш код (с дополнительной функцией для печати лабиринта). Не стесняйтесь откат, если вы считаете, что это неуместно.
Половина
Вы Edgeне правильно реализуете Comparable<Edge>. Если вы хотите, чтобы ребра сравнивались как равные, даже если вы перевернули их, вам необходимо принять во внимание и обращение в неравном случае. Самый простой способ сделать это - изменить конструктор, чтобы сохранить упорядоченные точки.
Питер Тейлор
@PeterTaylor: Спасибо за внимание. Я немного подумал о неравном случае, но не мог понять, почему это важно. Вы знаете, где я могу найти требования к реализации Comparable?
Половина
1
docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html Ключ в том, что он должен определить общий порядок. Но если Aи Bте же ребра обращены и Cотличаются, вы можете получить, A.compareTo(B) == B.compareTo(A) == 0но A.compareTo(C) < 0и B.compareTo(C) > 0.
Питер Тейлор
Как насчет сейчас? Я добавил еще один класс. И я добавил функцию, чтобы проверить, разрешима ли она (или canComeHome())
justhalf
3

64281

Обновление, поскольку сетка была изменена с 100x100 на 20x20 (1000 тестов). Оценка по 100x100 (100 тестов) была примерно 36M.

Хотя это не будет лучше, чем 1D, я хотел поиграть с моей идеей.

Основная идея состоит в том, что сетка разделена на квадратные комнаты, и только один путь ведет «домой» от каждого. Открытый путь зависит от того, какой пьяный приближается к последнему , что означает, что он должен исследовать каждый возможный выход, только чтобы всем, кроме одного, ударить его по лицу.

Поиграв с размерами комнаты, я пришел к тому же выводу, что и Питер: лучше нарезать его на мелкие. Лучшие оценки приходят с размером комнаты 2.

Average score over 100 trials: 36051265

Код небрежный, не обращайте внимания на беспорядок. Вы можете нажать на SHOWпереключатель, и он будет показывать изображение путей на каждом SHOW_INTшагу, чтобы вы могли наблюдать его в действии. Завершенный пробег выглядит примерно так:

введите описание изображения здесь

(Это изображение из предыдущей сетки 100x100. Точно так же, как и 20x20, но меньше. Код ниже был обновлен для новых размеров / прогонов.)

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.image.*;
import java.util.*;
import javax.swing.*;

public class DrunkWalk {

    boolean SHOW = false;
    int SHOW_INT = 10;
    int SIZE = 20;
    Random rand = new Random();
    Point pos;
    int[][] edges;
    int[][] wally;
    int[] wallx;
    int roomSize = 2;
    JFrame frame;
    final BufferedImage img;

    public static void main(String[] args){
        long total=0,runs=1000;
        for(int i=0;i<runs;i++){
            int steps = new DrunkWalk().run();
            total += steps;
            System.out.println("("+i+") "+steps);
        }
        System.out.println("\n Average " + (total/runs) + " over " + runs + " trials.");
    }

    DrunkWalk(){
        edges = new int[SIZE][SIZE];
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if(x>0) edges[x][y] |= WEST;
                if(x+1<SIZE) edges[x][y] |= EAST;
                if(y>0) edges[x][y] |= NORTH;
                if(y+1<SIZE) edges[x][y] |= SOUTH;
            }
        }
        wallx = new int[SIZE/roomSize+1];
        wally = new int[SIZE/roomSize+1][SIZE/roomSize+1];
        pos = new Point(SIZE-1,SIZE-1);
        img = new BufferedImage(SIZE*6+1,SIZE*6+1, BufferedImage.TYPE_INT_RGB);
        frame = new JFrame(){
            public void paint(Graphics g) {
                g.drawImage(img, 50, 50, null);
            }
        };
        frame.setSize(700,700);
        if(SHOW)
            frame.show();
    }

    void draw(){
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        Graphics g = img.getGraphics();
        g.setColor(Color.WHITE);
        g.clearRect(0, 0, img.getWidth(), img.getHeight());
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if((edges[x][y]&EAST)==EAST)
                    g.drawLine(x*6, y*6, x*6+5, y*6);
                if((edges[x][y]&SOUTH)==SOUTH)
                    g.drawLine(x*6, y*6, x*6, y*6+5);
            }
        }
        g.setColor(Color.RED);
        g.drawOval(pos.x*6-2, pos.y*6-2, 5, 5);
        g.drawOval(pos.x*6-1, pos.y*6-1, 3, 3);
        frame.repaint();
    }

    int run(){
        int steps = 0;
        Point home = new Point(0,0);
        while(!pos.equals(home)){
            if(SHOW&&steps%SHOW_INT==0){
                System.out.println(steps);
                draw();
            }
            step();
            adversary();
            steps++;
        }
        if(SHOW)
            draw();
        return steps;
    }

    void adversary(){
        int rx = pos.x / roomSize;
        int ry = pos.y / roomSize;
        int maxWalls = roomSize - 1;
        if(wally[rx][ry] < maxWalls){
            if(pos.y%roomSize==0)
                if(delete(pos.x,pos.y,NORTH))
                    wally[rx][ry]++;
        }
        maxWalls = SIZE-1;
        if(pos.x%roomSize==0){
            if(wallx[rx] < maxWalls)
                if(delete(pos.x, pos.y,WEST))
                    wallx[rx]++;


        }       
    }

    void step(){
        List<Integer> choices = getNeighbors(pos);
        Collections.shuffle(choices);
        int dir = choices.get(0);
        pos.x += dir==WEST?-1:dir==EAST?1:0;
        pos.y += dir==NORTH?-1:dir==SOUTH?1:0;
    }

    boolean delete(int x, int y, int dir){
        if((edges[x][y] & dir) != dir)
            return false;
        edges[x][y] -= dir;
        if(dir == NORTH)
            if(y>0) edges[x][y-1] -= SOUTH;
        if(dir == SOUTH)
            if(y+1<SIZE) edges[x][y+1] -= NORTH;
        if(dir == EAST)
            if(x+1<SIZE) edges[x+1][y] -= WEST;
        if(dir == WEST)
            if(x>0) edges[x-1][y] -= EAST;
        return true;
    }

    List<Integer> getNeighbors(Point p){
        if(p.x==SIZE || p.y==SIZE){
            System.out.println("wtf");
            System.exit(0);
        }
        List<Integer> choices = new ArrayList<Integer>();
        if((edges[p.x][p.y] & NORTH) == NORTH)
            choices.add(NORTH);
        if((edges[p.x][p.y] & SOUTH) == SOUTH)
            choices.add(SOUTH);
        if((edges[p.x][p.y] & EAST) == EAST)
            choices.add(EAST);
        if((edges[p.x][p.y] & WEST) == WEST)
            choices.add(WEST);
        return choices;
    }

    final static int NORTH=1,EAST=2,SOUTH=4,WEST=8;
}
Geobits
источник
Я только заметил, что он должен идти от бота / слева-> сверху / справа, в то время как мой идет от бота / справа-> сверху / слева. Я могу изменить это, если это действительно имеет значение, но ...
Geobits
Это очень приятно и я думаю, что это первое динамическое решение. Мне интересно, что ваш путь пока не такой длинный, как статический.
Если под "не так долго" вы имеете в виду ~ 1/3 длины одного и ~ 36x длиннее другого? : P
Geobits
3

188К, с 2 дорожками

Все лучшие записи, кажется, используют подход, состоящий в том, чтобы генерировать 2 пути, а затем отрезать один, когда пьяница приближается к концу пути. Я не думаю, что смогу побить вступление Джастхалфа, но я не мог не задаться вопросом: почему 2 пути? Почему не 3, или 5, или 20?

TL; DR : 2 пути кажутся оптимальными

Итак, я сделал эксперимент. На основе фреймворка Stretch Maniac я написал статью для проверки различных путей. Вы можете настроитьfeatureSize параметр, чтобы варьировать количество путей. A featureSizeиз 20 дает 1 путь, 10 - 2 пути, 7 - 3, 5 - 4 и так далее.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class Walker {
    final int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    final int dX,dY; //destination
    final int featureSize;
    Set<Edge> pathsNoLongerAvailable = new HashSet<>();
    Set<Edge> previouslyTraveled = new HashSet<>();
    int stepCount = 0;
    private final BitSet remainingExits;

    public static void main(String[]args){
        int side = 20;
        Walker walker = null;
        int total = 0;
        int featureSize = 10;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, featureSize);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, int featureSize){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        this.featureSize = featureSize;

        deleteBars();

        remainingExits = new BitSet();
        for (int yy = 0; yy < height; yy++) {
            if (!pathsNoLongerAvailable.contains(new Edge(width - 2, yy, width - 1, yy))) {
                remainingExits.set(yy);
            }
        }

        while(!walk()){
            if (x == width - 2
                    && remainingExits.get(y)
                    && remainingExits.cardinality() > 1) {
                deletePath(x, y, x + 1, y);
                remainingExits.set(y, false);
            }
        }
    }

    private void deleteBars() {
        for (int xx = 0; xx < width - 1; xx++) {
            for (int yy = 0; yy < height / featureSize + 1; yy++) {
                if (xx != 0) deletePath(xx, featureSize * yy + featureSize - 1, xx, featureSize * yy + featureSize);
                boolean parity = xx % 2 == 0;
                if (yy == 0) parity ^= true; // First path should be inverted
                for (int i = 0; i < featureSize && featureSize * yy + i < height; i++) {
                    if (i == 0 && !parity) continue;
                    if ((i == featureSize - 1 || featureSize * yy + i == height - 1) && parity) continue;
                        deletePath(xx, featureSize * yy + i, xx + 1, featureSize * yy + i);
                }
            }
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = ThreadLocalRandom.current().nextInt(possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        Set<Point> reachable = new HashSet<>();
        Queue<Point> next = new LinkedList<>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge) {
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    public static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }

        @Override
        public String toString() {
            return start.toString() + "-" + end.toString();
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Objects.hashCode(this.start);
            hash = 83 * hash + Objects.hashCode(this.end);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Edge other = (Edge) obj;
            if (!Objects.equals(this.start, other.start)) {
                return false;
            }
            if (!Objects.equals(this.end, other.end)) {
                return false;
            }
            return true;
        }


    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 23 * hash + this.x;
            hash = 23 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }


    }
}

Есть несколько оптимизаций, которые я мог бы сделать, но не сделал, и он не поддерживает ни одного адаптивного трюка, который использует justhalf.

Во всяком случае, вот результаты для различных featureSizeзначений:

20 (1 path):  156284 
10 (2 paths): 188553
7 (3 paths):  162279
5 (4 paths):  152574
4 (5 paths):  134287
3 (7 paths):  118843
2 (10 paths): 94171
1 (20 paths): 64515

И вот карта с 3 путями:

 _   _   _   _   _   _   _   _   _    
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|_   _   _   _   _   _   _   _   _   _|
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|  _   _   _   _   _   _   _   _   _  |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
|_| |_| |_| |_| |_| |_| |_| |_| |_| | |
James_pic
источник
Спасибо за это. Похоже, все деньги теперь в адаптивной
Почему вы режете путь внизу? Я думаю, вы можете сократить путь между нижней и средней траекториями для лучшего результата.
Половина
@justhalf Да, я ожидаю. Я решил не делать этого, поскольку это сделало бы код более сложным, и в любом случае это не было бы выигрышной записью.
James_pic
1
Три пути (при условии оптимального 3-пути) будут в среднем такими же, как и один путь: пусть Nбудет длиной пути (то есть n^2-1), один путь в среднем потребует N^2перемещений, тогда как три пути (N/3)^2 + (2N/3)^2 + (2N/3)^2 = N^2плюс некоторое относительно небольшое значение, поэтому три пути не имеют существенного усиления по одиночному пути, не говоря уже о двойном пути. (Расчет основан на вероятностном результате, который гласит, что для случайного перемещения по одномерной траектории длины Nтребуется в среднем N^2перемещение от одного конца к другому.)
Полугодие
@justhalf Ницца. Я изо всех сил пытался придумать хороший аргумент из первых принципов о том, почему 2 был лучшим, но это прибивает его.
James_pic
2

131k (20x20)

Моя первая попытка состояла в том, чтобы удалить все горизонтальные края, кроме верхнего и нижнего ряда, затем каждый раз, когда ходок достигал нижней части столбца, я удалял край впереди него, пока он не посетил дно каждого столбца и, наконец, быть в состоянии добраться до выхода. Это привело в среднем к 1/8 столько же шагов, сколько и к 1-му ходу @ PeterTaylor.

Затем я решил попробовать что-то более крутое. Я разбил лабиринт на серию вложенных полых шевронов и требую, чтобы он пересек периметр каждого шеврона не менее 1,5 раз. Это имеет среднее время около 131 тыс. Шагов.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <math.h>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':' ';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                if (r==0 || r==H-1 || c==0 || c==W-1) maze[r][c]=0; // edges
                else if (r%2) { // rows with cells and E/W paths
                    if (c%2) maze[r][c] = 9; // col with cells
                    else if (r==1 || r==H-2) maze[r][c]=1; // E/W path on N/Smost row
                    else if (c>r) maze[r][c]=1; // E/W path on chevron perimeter
                    else maze[r][c]=0; // cut path between cols
                } else { // rows with N/S paths
                    if (c%2==0) maze[r][c] = 0; // empty space
                    else if (c==1 || c==W-2) maze[r][c]=1; // N/S path on E/Wmost row
                    else if (r>c) maze[r][c]=1; // N/S path on chevron perimeter
                    else maze[r][c]=0;
                }
            }
        }
        int progress = 0;
        int first_cut = 0;
        x=0;
        y=0;
        if(DEBUG) print_maze();
        long long turn = 0;
        while (x!=X-1||y!=Y-1) {
            if(DEBUG) std::cin.ignore();
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
            int exit_choice = -1;
            do {
                if (rand()%exits == 0) {
                    exit_choice = exits;
                    break;
                } else {
                    exits--;
                }
            }while(exits);
            int dx=0, dy=0;
            --exits;
            if (maze[r-1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = -1;
                    dx = 0;
                }
            }
            if (maze[r][c+1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = 1;
                }
            }
            if (maze[r+1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 1;
                    dx = 0;
                }
            }
            if (maze[r][c-1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = -1;
                }
            }
            x+=dx;
            y+=dy;
            if (first_cut==0) {
                if(x==X-1 && y==progress*2+1) {
                    first_cut = 1;
                    maze[y*2+2][x*2+1]=0;
                }
                if(y==Y-1 && x==progress*2+1) {
                    first_cut = 2;
                    maze[y*2+1][x*2+2]=0;
                }
            }
            else if (first_cut==1) {
                if (y==Y-1 && x==progress*2) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
                else if (y==Y-2 && x==progress*2+1) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
            }
            else if (first_cut==2) {
                if (x==X-1 && y==progress*2) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
                else if (x==X-2 && y==progress*2+1) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
            }
            if(DEBUG) print_maze();
        }
        // printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}
Sparr
источник
0

Ничего не делать

Поскольку человек движется случайным образом, можно подумать, что удаление любого узла только увеличит его шансы на возвращение домой в долгосрочной перспективе.

Во-первых, давайте посмотрим на одномерный случай, это может быть достигнуто путем удаления узлов, пока вы не получите волнистый путь, без затуханий или циклов, который посещает (почти) каждую точку сетки. На N x Nсетке максимальная длина такого пути равна L = N*N - 2 + N%2 (98 для сетки 10х10). Ходьба по дорожке может быть описана матрицей перехода, генерируемой T1d. переходная матрица

(Небольшая асимметрия затрудняет поиск аналитического решения, за исключением очень маленьких или бесконечных матриц, но мы получаем численное решение быстрее, чем это потребовалось бы для диагонализации матрицы в любом случае).
Вектор состояния имеет единицу 1в начальной позиции и после Kшагов(T1d**K) * state дает нам распределение вероятностей нахождения на определенном расстоянии от начала (что эквивалентно усреднению по всем 2**Kвозможным прогулкам по пути!)

Запуск симуляции для 10*L**2шагов и сохранение последнего элемента вектора состояния после каждого шага, что дает нам вероятность того, что мы дойдем до цели после определенного общего количества шагов - накопленного распределения вероятностей cd(t). Дифференцирование дает нам вероятность pдостижения цели точно в определенное время. Чтобы найти среднее время, которое мы интегрируем, t*p(t) dt
среднее время достижения цели пропорционально L**2коэффициенту, который очень быстро возрастает до 1. Стандартное отклонение почти постоянно и составляет около 79% от среднего времени.
Этот график показывает среднее время достижения цели для разных длин пути (соответствует размерам сетки от 5x5 до 15x15) введите описание изображения здесь

Вот как выглядит вероятность достижения цели. Вторая кривая выглядит заполненной, потому что на каждом нечетном временном шаге позиция нечетна и, следовательно, не может достигать цели. введите описание изображения здесь

Из этого мы видим, что сбалансированная стратегия двойного пути работает здесь лучше всего. Для более крупных сеток, где затраты на создание большего числа путей незначительны по сравнению с их размером, мы могли бы лучше увеличить число путей, подобно тому, как это описал Питер Тейлор, но сохраняя сбалансированную длину

Что если мы вообще не удаляем какие-либо узлы?

Тогда у нас будет вдвое больше проходных узлов, плюс четыре возможных направления вместо двух. Казалось бы, из-за этого вряд ли удастся когда-либо добраться. Тем не менее, результаты моделирования показывают обратное: после всего лишь 100 шагов по сетке 10х10 человек, скорее всего, достигнет своей цели, поэтому ловить его на островах - тщетная попытка, поскольку вы торгуете по потенциально N**2длинному извилистому пути со средним временем завершения N**4для остров, который проходит по N**2ступеням

вероятность прогулки по 2-й сетке

from numpy import *
import matplotlib.pyplot as plt

def L(N): # maximal length of a path on an NxN grid
    return N*N - 2 + N%2

def T1d(N): # transition along 1d path
    m = ( diag(ones(N-1),1) + diag(ones(N-1),-1) )/2.
    m[1,0] = 1
    m[-2,-1] = 0
    m[-1,-1] = 1
    return m

def walk(stepmatrix, state, N):
    data = zeros(N)
    for i in xrange(N):
        data[i] = state[-1]
        state = dot(stepmatrix, state)
    return data

def evaluate(data):
    rho = diff(data)/data[-1]
    t = arange(len(rho))
    av = sum(rho*t)
    stdev = sum((t-av)**2 * rho)**.5
    print 'average: %f\nstd: %f'%(av, stdev)
    return rho, av, stdev

gridsize = 10
M = T1d(L(gridsize))
initpos = zeros(L(gridsize))
initpos[0] = 1
cd = walk(M, initpos, L(gridsize)**2*5)

plt.subplot(2,1,1)
plt.plot(cd)
plt.title('p of reaching the goal after N steps')
plt.subplot(2,1,2)
plt.plot(evaluate(cd)[0])
plt.title('p of reaching the goal at step N')
plt.show()


''' 
# uncomment to run the 2D simulation
# /!\ WARNING /!\ generates a bunch of images, dont run on your desktop

def links(k,n):
    x = [k-n, k+n]
    if k%n != 0: x.append(k-1)
    if k%n != n-1: x.append(k+1)
    x = [i for i in x if 0<= i <n*n]
    return x

N = 10 # gridsize    

MM = zeros((N*N, N*N)) # build transition matrix
for i in range(N*N):
    temp = links(i,N)
    for j in temp: MM[i,j] = 1./len(temp)
MM[:,-1] = zeros(N*N)
MM[-1,-1] = 1

pos = zeros(N*N)
pos[0] = 1
for i in range(N*N):
    plt.imsave('grid_%.2d'%i, kron(pos.reshape((N,N)), ones((10,10))), cmap='gray')
    pos = dot(MM, pos)
'''
DenDenDo
источник
+1 за усилия и хорошие графики. Но это не отвечает на вопрос, и первые два слова противоречат заключению вашего анализа. И вы действительно должны пометить оси ваших графиков. Для какого размера сетки применим ваш график вероятности?
Половина
Прекрасные картинки, но я не уверен, что вы правильно поняли вопрос. Например, «поскольку человек движется случайным образом, можно подумать, что удаление любого узла только увеличит его шансы на возвращение домой в долгосрочной перспективе». 1) человек всегда будет в конечном итоге возвращаться домой в соответствии с установленными правилами, поэтому это не выглядит актуально, и 2) мы удаляем ребра, а не узлы.