Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Есть ли полный алгоритм поиска пути без перебора вариантов путей?
Да 33%  33%  [ 1 ]
Нет 66%  66%  [ 2 ]
Всего голосов : 3
Автор Сообщение
 Заголовок сообщения: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 12:15 
Не в сети
Начинающий
Зарегистрирован:
10 сен 2019, 11:52
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Привет!

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

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

115222414171015432
6418202681991811
32921232111512417
12291329152822233121
2715241211610282731
2623222628273041017
242019101571623921
424261582725103129
232217253232220519
17313217287151233


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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 14:34 
Не в сети
Мастер
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 247
Cпасибо сказано: 9
Спасибо получено:
36 раз в 34 сообщениях
Очков репутации: 5

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 14:57 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 1984
Cпасибо сказано: 132
Спасибо получено:
327 раз в 302 сообщениях
Очков репутации: 41

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Booker48 "Спасибо" сказали:
Elia
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 15:06 
Не в сети
Мастер
Зарегистрирован:
02 июн 2018, 08:50
Сообщений: 247
Cпасибо сказано: 9
Спасибо получено:
36 раз в 34 сообщениях
Очков репутации: 5

Добавить очки репутацииУменьшить очки репутации
Алгоритм Дейкстры здесь нельзя применить?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 15:08 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 1984
Cпасибо сказано: 132
Спасибо получено:
327 раз в 302 сообщениях
Очков репутации: 41

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 20:30 
Не в сети
Начинающий
Зарегистрирован:
10 сен 2019, 11:52
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Emphatic18 писал(а):
Алгоритм Дейкстры здесь нельзя применить?

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 20:35 
Не в сети
Начинающий
Зарегистрирован:
10 сен 2019, 11:52
Сообщений: 3
Cпасибо сказано: 1
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 10 сен 2019, 21:11 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 1984
Cпасибо сказано: 132
Спасибо получено:
327 раз в 302 сообщениях
Очков репутации: 41

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Занимательная головоломка
СообщениеДобавлено: 11 сен 2019, 12:35 
Не в сети
Light & Truth
Зарегистрирован:
02 дек 2016, 22:55
Сообщений: 1984
Cпасибо сказано: 132
Спасибо получено:
327 раз в 302 сообщениях
Очков репутации: 41

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 9 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Занимательная чушь

в форуме Палата №6

fibona

16

421

16 июл 2019, 18:06

Занимательная математика

в форуме Алгебра

vvd

13

510

04 май 2015, 02:25

Головоломка

в форуме Алгебра

Ellya

2

192

27 ноя 2014, 11:28

Головоломка

в форуме Объявления участников Форума

Hadros

1

227

05 окт 2015, 00:22

Во сколько раз дороже? Занимательная арифметика

в форуме Интересные задачи участников форума MHP

FEBUS

9

301

16 мар 2018, 17:31

Определитель над полем или занимательная агрономия.

в форуме Линейная и Абстрактная алгебра

Surtr_RJ

1

229

10 ноя 2016, 16:40

Задача головоломка

в форуме Специальные разделы

Pegas

2

268

12 апр 2016, 17:38

Задачка -головоломка

в форуме Задачи со школьных и студенческих олимпиад

Natalia Sherbakova

6

1001

23 ноя 2012, 12:33

Акция на распродаже. Занимательная задача для детей

в форуме Интересные задачи участников форума MHP

FEBUS

6

214

06 июл 2018, 02:21

Среднеквадратичное значение. Головоломка

в форуме Интересные задачи участников форума MHP

Custom

3

293

14 авг 2014, 12:53


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved