Математический форум Math Help Planet
http://mathhelpplanet.com/

Занимательная головоломка
http://mathhelpplanet.com/viewtopic.php?f=59&t=66491
Страница 1 из 1

Автор:  Elia [ 10 сен 2019, 12:15 ]
Заголовок сообщения:  Занимательная головоломка

Привет!

Наткнулся на такую задачу. Оказалась очень занимательной,

Дана таблица 10х10, заполненная повторяющимися числами от 1 до 33.
Требуется найти путь от 1 до 33, проходящий через все 33 числа ровно по 1му разу.
По диагонали двигаться не разрешается.

115222414171015432
6418202681991811
32921232111512417
12291329152822233121
2715241211610282731
2623222628273041017
242019101571623921
424261582725103129
232217253232220519
17313217287151233


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

Вопрос: Как максимально математизировать эту задачу, чтобы минимизировать перебор?
Думал про теорию графов и линейную алгебру.

Автор:  Emphatic18 [ 10 сен 2019, 14:34 ]
Заголовок сообщения:  Re: Занимательная головоломка

Elia писал(а):
Требуется найти путь от 1 до 33, проходящий через все 33 числа ровно по 1му разу.

А путь должен быть по числам следующим в порядке возрастания 1-2-3...33 или в любом порядке, лишь бы по разу на каждом из чисел?

Автор:  Booker48 [ 10 сен 2019, 14:57 ]
Заголовок сообщения:  Re: Занимательная головоломка

Emphatic18 писал(а):
А путь должен быть по числам следующим в порядке возрастания 1-2-3...33?

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

Автор:  Emphatic18 [ 10 сен 2019, 15:06 ]
Заголовок сообщения:  Re: Занимательная головоломка

Алгоритм Дейкстры здесь нельзя применить?

Автор:  Booker48 [ 10 сен 2019, 15:08 ]
Заголовок сообщения:  Re: Занимательная головоломка

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

Автор:  Elia [ 10 сен 2019, 20:30 ]
Заголовок сообщения:  Re: Занимательная головоломка

Emphatic18 писал(а):
Алгоритм Дейкстры здесь нельзя применить?

Я не додумал как сформулировать задачу, в особенности - ограничения, в графах. Вершин брать 100 или 33, если 33 - то как ребра занумеровать и как отметить, что в зависимости от того, из какой вершины попал в текущую, доступна только часть маршрутов. А если брать 100 вершин как применять алгоритм, чтобы определять ненужные вершины?

Автор:  Elia [ 10 сен 2019, 20:35 ]
Заголовок сообщения:  Re: Занимательная головоломка

Booker48 писал(а):
Elia
В голову лезет волновой алгоритм, очень ресурсожоркий. Но ничего лучшего не могу предложить. И он, вроде бы, должен закончиться за 33 шага.


Спасибо, про волновой алгоритм кстати не подумал. Но он по сути как полный перебор будет?

Автор:  Booker48 [ 10 сен 2019, 21:11 ]
Заголовок сообщения:  Re: Занимательная головоломка

Elia писал(а):
...про волновой алгоритм кстати не подумал. Но он по сути как полный перебор будет?

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

Автор:  Booker48 [ 11 сен 2019, 12:35 ]
Заголовок сообщения:  Re: Занимательная головоломка

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

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/